A general variable neighborhood search heuristic for multiple traveling salesmen problem. (December 2015) - Soylu, Banu
Highlights: The multiple traveling salesmen problem ( m TSP) is considered. The minmax and minsum objectives are taken into consideration. A general variable neighborhood search (GVNS) heuristic for the m TSP is proposed. The heuristic is also applied to a real life problem, which exists in a traffic signalization network. Several experiments are conducted, and results are presented. Abstract: In this study, we consider the multiple traveling salesmen problem, which is the more general version of the single traveling salesman problem as it includes m > 1 salesmen starting and ending their tours at a fixed depot. We take into consideration two objective functions separately: one is to minimize the longest tour length and the other is to minimize the total length of all tours. A general variable neighborhood search, a well-known heuristic for combinatorial problems, is proposed for the m TSP. We test the performance of the heuristic on some test problems from the literature and compare it with existing approaches. We also apply the heuristic to a real life problem, which exists in the traffic signalization network of Kayseri province in Turkey, and obtain a considerable improvement.