A general variable neighborhood search heuristic for multiple traveling salesmen problem. (December 2015)

• Record Type: Journal Article
• Authors: Soylu, Banu
• Is Part Of: Computers & industrial engineering. Volume 90(2015)
• Page Start: 390
• Page End: 401
• Publication Date: 2015-12
• Subjects: Multiple traveling salesmen problem -- Minmax mTSP -- Minsum mTSP -- General variable neighborhood search; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2015.10.010
• Languages: English
• ISSNs: 0360-8352

Abstract

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.