Length-constrained cycle partition with an application to UAV routing

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 cycl...

Full description

Saved in:
Bibliographic Details
Published in:Optimization methods & software 2022-11, Vol.37 (6), p.2080-2116
Main Authors: Hoppmann-Baum, Kai, Burdakov, Oleg, Mexi, Gioni, Casselgren, Carl Johan, Koch, Thorsten
Format: Article
Language:English
Subjects:
Algorithms
Chemical partition
Combinatorial optimization
Constraint modelling
Heuristic methods
Integer programming
Linear programming
Mixed integer
mixed-integer programming
Traveling salesman problem
travelling salesperson problem
uncrewed aerial vehicles
Unmanned aerial vehicles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1055-6788
1029-4937
1029-4937
DOI:10.1080/10556788.2022.2053972