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, vol.35, no.2, pp.563-580, 2020 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 35 Issue: 2
  • Publication Date: 2020
  • Doi Number: 10.17341/gazimmfd.490179
  • Journal Name: JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Page Numbers: pp.563-580
  • Keywords: 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 University Affiliated: Yes

Abstract

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.