Distributed and incremental travelling salesman algorithm on time-evolving graphs

摘要

Travelling salesman problem (TSP) is a graph problem that has been widely used in many applications, especially for transportation and logistics. Because TSP is a NP hard problem, minimizing the complexity of TSP algorithms is an important problem. Many heuristic algorithms have been proposed to compute the TSP tours of a given static graph. But limited studies have been done on time-evolving graph (TEG) where the graph can change over time due to update events, such as weight changes on edges or vertices. It is a more challenging problem because the speed of TSP computations must be high enough to catch up the graph update frequency. In this paper, we make the very first attempt to minimize the computation time of solving TSP on time-evolving graphs. By exploring parallel computing power and reusing previous computing results, we proposed a distributed and incremental TSP algorithm which can be implemented on vertex-centric parallel graph computing frameworks to efficiently find TSP tours on large changing graphs. Our incremental algorithm can maintain shortest TSP tour with minimum amount of recomputation. Through our experimental evaluation, we have shown incremental TSP algorithm is 98% faster than distributed algorithm.