8048
eng
reportzib
0
--
2020-11-24
--
Length-Constrained Cycle Partition with an Application to UAV Routing
In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflict hypergraphs, whose cliques yield valid constraints for the MIP models.
We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a fleet of uncrewed aerial vehicles (UAVs) patrols a set of areas.
1438-0064
urn:nbn:de:0297-zib-80489
false
true
Kai Hoppmann-Baum
Kai Hoppmann-Baum
Gioni Mexi
Oleg Burdakov
Carl Johan Casselgren
Thorsten Koch
ZIB-Report
20-30
Hoppmann, Kai
Koch, Thorsten
MODAL-GasLab
MODAL-Gesamt
Mexi, Gioni
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8048/zib_report_20_30.pdf