Traveling Salesman Problem for a Class of Carrier-Vehicle Systems

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/publishe