Sökning: id:"swepub:oai:DiVA.org:liu-169758" >
Minimum Cycle Parti...
Minimum Cycle Partition with Length Requirements
-
- Hoppmann, Kai (författare)
- Zuse Institute Berlin, Berlin, Germany; Chair of Software and Algorithms for Discrete Optimization, TU Berlin, Berlin, Germany
-
- Mexi, Gioni (författare)
- Zuse Institute Berlin, Berlin, Germany
-
- Burdakov, Oleg, 1953- (författare)
- Linköpings universitet,Optimeringslära,Tekniska fakulteten
-
visa fler...
-
- Casselgren, Carl Johan, 1982- (författare)
- Linköpings universitet,Matematik och tillämpad matematik,Tekniska fakulteten
-
- Koch, Thorsten (författare)
- Zuse Institute Berlin, Berlin, Germany; Chair of Software and Algorithms for Discrete Optimization, TU Berlin, Berlin, Germany
-
visa färre...
-
(creator_code:org_t)
- 2020-09-19
- 2020
- Engelska.
-
Ingår i: Integration of Constraint Programming, Artificial Intelligence, and Operations Research. - Cham : Springer International Publishing. - 9783030589417 ; , s. 273-282
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorseende och robotik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Vision and Robotics (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Robotteknik och automation (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Robotics (hsv//eng)
Nyckelord
- Travelling salesman problem
- Combinatorial optimization
- Mixed integer linear programming
- Conflict graph
- Unmanned Aerial Vehicles
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas