Mathematical model and heuristic approach for solving dynamic vehicle routing problem with simultaneous pickup and delivery: Random iterative local search variable neighborhood descent search


Creative Commons License

Aydogdu B., ÖZYÖRÜK B.

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, cilt.35, sa.2, ss.563-580, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 35 Sayı: 2
  • Basım Tarihi: 2020
  • Doi Numarası: 10.17341/gazimmfd.490179
  • Dergi Adı: JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.563-580
  • Anahtar Kelimeler: Dynamic vehicle routing problem, simultaneous pickup and delivery, hyper heuristics, local Search, mathematical model, ANT COLONY SYSTEM, TIME WINDOWS, ALGORITHM, DEPOT, UPS, OPTIMIZATION, SINGLE
  • Gazi Üniversitesi Adresli: Evet

Özet

Vehicle Routing Problems (VRP) are used to find the most suitable routes for fulfill the delivery and pickup demands of the companies. In real life, new pickup requests received by routed vehicles will provide a significant reduction in transport costs. As a result, a new mathematical model called as Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery (DVRPSPD) has been developed for new pickup requests received by routed vehicles. Small and medium-sized problems were generated and solved for evaluate the effectiveness of the proposed model. The results obtained with the mathematical model were evaluated. The solution time increased exponentially as the problem size increased. In this study, heuristic algorithms were used to solve the problem in a short time. A new algorithm called Random Iterative Local Search Variable Neighborhood Descending (R-ILS-VND) algorithm has been developed. Order of the neighborhood structures was changed continuously by decreasing permutation method at R-ILS-VND algorithm. In order to evaluate the effectiveness of the developed algorithm, the results were compared to the mathematical models results. When the results are analyzed, the heuristic algorithm has similar results to the mathematical model. Finally, the medium and large size problems were solved by using the proposed R-ILS-VND algorithm and the results were analyzed.