A general variable neighborhood search heuristic for multiple traveling salesmen problem


SOYLU B.

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

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 90
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.cie.2015.10.010
  • Dergi Adı: COMPUTERS & INDUSTRIAL ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.390-401
  • Anahtar Kelimeler: Multiple traveling salesmen problem, Minmax mTSP, Minsum mTSP, General variable neighborhood search, GROUPING GENETIC ALGORITHM, NEURAL-NETWORK, FORMULATIONS, DELIVERY, PICKUP
  • Erciyes Üniversitesi Adresli: Evet

Özet

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.