A general variable neighborhood search heuristic for multiple traveling salesmen problem


SOYLU B.

COMPUTERS & INDUSTRIAL ENGINEERING, vol.90, pp.390-401, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 90
  • Publication Date: 2015
  • Doi Number: 10.1016/j.cie.2015.10.010
  • Journal Name: COMPUTERS & INDUSTRIAL ENGINEERING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.390-401
  • Keywords: Multiple traveling salesmen problem, Minmax mTSP, Minsum mTSP, General variable neighborhood search
  • Erciyes University Affiliated: Yes

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 mTSP. 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. (C) 2015 Elsevier Ltd. All rights reserved.