Sökning: id:"swepub:oai:DiVA.org:liu-185276" >
Length-constrained ...
Length-constrained cycle partition with an application to UAV routing*
-
- Hoppmann-Baum, Kai (författare)
- Zuse Inst Berlin, Germany; TU Berlin, Germany
-
- Burdakov, Oleg, 1953- (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
- Mexi, Gioni (författare)
- Zuse Inst Berlin, Germany
-
visa fler...
-
- Casselgren, Carl Johan, 1982- (författare)
- Linköpings universitet,Algebra, geometri och diskret matematik,Tekniska fakulteten
-
- Koch, Thorsten (författare)
- Zuse Inst Berlin, Germany; TU Berlin, Germany
-
visa färre...
-
(creator_code:org_t)
- 2022-05-12
- 2022
- Engelska.
-
Ingår i: Optimization Methods and Software. - : TAYLOR & FRANCIS LTD. - 1055-6788 .- 1029-4937. ; 37:6, s. 2080-2116
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Combinatorial optimization; mixed-integer programming; uncrewed aerial vehicles; travelling salesperson problem
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas