Open this publication in new window or tab >>Show others...
2022 (English)In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 37, no 6, p. 2080-2116Article in journal (Refereed) Published
Abstract [en]
This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e. a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.
Place, publisher, year, edition, pages
TAYLOR & FRANCIS LTD, 2022
Keywords
Combinatorial optimization; mixed-integer programming; uncrewed aerial vehicles; travelling salesperson problem
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-185276 (URN)10.1080/10556788.2022.2053972 (DOI)000794250800001 ()
Note
Funding Agencies|German FederalMinistry of Education and Research (BMBF) [05M14ZAM, 05M20ZBM]; Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation; Swedish Research Council [2017-05077]
2022-05-252022-05-252023-03-28Bibliographically approved