A MATHEMATICAL FORMULATION AND HEURISTIC APPROACH FOR THE HETEROGENEOUS FIXED FLEET VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY


KEÇECİ B., Altiparmak F., KARA İ.

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, cilt.17, sa.3, ss.1069-1100, 2021 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 17 Sayı: 3
  • Basım Tarihi: 2021
  • Doi Numarası: 10.3934/jimo.2020012
  • Dergi Adı: JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.1069-1100
  • Anahtar Kelimeler: Vehicle routing problem, simultaneous pickup-delivery, heterogeneous fixed fleet, mathematical model, simulated annealing algorithm, HYBRID METAHEURISTIC ALGORITHM, VARIABLE NEIGHBORHOOD SEARCH, TABU SEARCH, SIZE, OPTIMIZATION, VARIANTS, SINGLE
  • Gazi Üniversitesi Adresli: Evet

Özet

This study considers a variant of the vehicle routing problem (VRP) called the heterogeneous VRP with simultaneous pickup and delivery (HVRPSPD). The HVRPSPD may broadly be defined as identifying the minimum cost routes and vehicle types. To solve the HVRPSPD, first, we propose a polynomial-size mixed integer programming formulation. Because the HVRPSPD is an NP-hard problem, it is difficult to determine the optimal solution in a reasonable time for moderate and large-size problem instances. Hence, we develop a hybrid metaheuristic approach based on the simulated annealing and local search algorithms called SA-LS. We conduct a computational study in three stages. First, the performance of the mathematical model and SA-LS are investigated on small and medium-size HVRPSPD instances. Second, we compare SA-LS with the constructive heuristics, nearest neigh-borhood and Clarke-Wright savings algorithms, adapted for the HVRPSPD. Finally, the performance of SA-LS is evaluated on the instances of the heterogeneous VRP (HVRP), which is a special case of the HVRPSPD. Computational results demonstrate that the mathematical model can solve small-size instances optimally up to 35 nodes; SA-LS provides good quality solutions for medium and large-size problems. Moreover, SA-LS is superior to simple constructive heuristics and can be a preferable solution method to solve HVRP and VRPSPD instances successfully.