Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Minimum Cycle Partition with Length Requirements

  • In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Kai Hoppmann-Baum, Gioni Mexi, Oleg BurdakovORCiD, Carl Johan CasselgrenORCiD, Thorsten Koch
Editor:Emmanuel Hebrard, Nysret Musliu
Document Type:Book chapter
Parent Title (English):Integration of Constraint Programming, Artificial Intelligence, and Operations Research
First Page:273
Last Page:282
Series:Lecture Notes in Computer Science
Publisher:Springer International Publishing
Place of publication:Cham
Year of first publication:2020
Page Number:10
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.