Traveling Salesman Problem for a Class of Carrier-Vehicle Systems
Authors:
- 1 July 2011
- journal article
- Published by American Institute of Aeronautics and Astronautics (AIAA) in Journal of Guidance, Control, and Dynamics
- Vol. 34 (4) , 1272-1276
Abstract
The traveling-salesman problem (TSP) for a class of carrier-vehicle systems in which a slow carrier with infinite operating range cooperates with a faster vehicle that has a limited operating range, was studied. A heuristic solution based on the Euclidean TSP (E-TSP) has been proposed and an analytical bound on its conservativeness has been derived. One of the main feature of this class of TSP problems is that, although still NP-hard, they admit polynomial-in-time optimization schemes. The CV-TSP heuristic proposed consists of two steps. First, it determines the visiting order of the almost-optimal E-TSP tour for the set of given points, and second, it uses the visiting order to solve the resulting visit of n points via the convex optimization formulation. The targets to be visited are limited to five randomly generated points that still make the computation of the exact optimal solution in a reasonable time possible.SCOPUS: ar.jinfo:eu-repo/semantics/publisheKeywords
This publication has 7 references indexed in Scilit:
- Search and Rescue Robotics2008
- Multiple Mobile Robot Systems2008
- Recent Research in Cooperative Control of Multivehicle SystemsJournal of Dynamic Systems, Measurement, and Control, 2007
- Planning Algorithms2006
- Coordinated target assignment and intercept for unmanned air vehiclesIEEE Transactions on Robotics and Automation, 2002
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean PlaneOperations Research, 1991