An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

Avci M., Topaloglu Ş. A.

COMPUTERS & INDUSTRIAL ENGINEERING, cilt.83, ss.15-29, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 83
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.cie.2015.02.002
  • Dergi Adı: COMPUTERS & INDUSTRIAL ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.15-29
  • Anahtar Kelimeler: Local search, Vehicle routing problem with simultaneous pickup and delivery, Reverse logistics, METAHEURISTIC ALGORITHM, HEURISTIC ALGORITHMS, BACKHAULS, SERVICE, SINGLE
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time. (C) 2015 Elsevier Ltd. All rights reserved.