The k-Delivery Traveling Salesman Problem: Revisited

摘要

The k-delivery Travelling Salesman Problem (k-dTSP) is one of the most interesting variants of vehicle routing. Given a weighted graph, on which each node either holds an item or requires an item, and a vehicle of capacity of k which can carry at most k items at a time, one is asked to schedule a shortest route for the vehicle so that it starts from a depot and transports all items from the points holding them to the points requiring items, and returns home under the vehicle capacity constraint. It is clearly an NP-hard problem. Among quite a few results the best-known approximation algorithm is due to Charikar, Menuier and Raghavachari (2001). All the previous approaches first construct an approximate TSP tour. It is then expanded to a (much) larger but bounded one by repeatedly moving the vehicle on the tour, so that the pickup/delivery tasks can be completed. It motivates us to consider a simpler approach, that directly applies an optimal algorithm on a circle graph after we derive an approximate TSP tour. It is known that k-dTSP on a path graph is polynomially solvable, while the complexity is open on a circle graph. In this paper, we settle this issue by presenting a polynomial algorithm on a circle, and then apply it to k-dTSP on general graphs. Although the theoretical bound is yet unclear, experiments show that it outperforms the existing approaches.