Acta Infologica

SUBMITINFORMATION
EnglishTürkçe

Research Article


DOI :10.26650/acin.831973   IUP :10.26650/acin.831973    Full Text (PDF)

A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery

Mustafa Demirbilek

Nowadays, logistic companies are dealing with the pressure of a highly competitive environment and trying to reduce operational costs. At the same time, customers are requiring not to wait so long to get their delivery and pickup demands satisfied. In this study, these two factors are considered with a-static-periodic solution strategy. The problem is modelled as Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery (DVRPSPD) where delivery and pickup demands of customers continuously arrived in a planning horizon are satisfied at the same time and by the same vehicle. Furthermore, we proposed a solution methodology based on solving routing problems repeatedly for each time period by considering new and unvisited previous customers. A well-known heuristic, the Nearest Neighbourhood Algorithm (NNA), is used to solve VRPSPDs in each time period. Important real-life aspects such as demand fluctuations, different number of customers, and routing periods are integrated into the problem. According to results, the average waiting times per customer significantly increase whereas average travel times per visit notably decrease when the length of time period increases. If routes are constructed 8 times in a day, each customer waits an average 5 minutes compared to 66 minutes if it is made 4 times in the day. More routing plans cause more than 7-minute average travel times per visit. Different test settings are analysed and the results are explained to help decision makers find the best solution for both companies and customers. 

Keywords: Vehicle routing problem with simultaneous pickup and delivery, The nearest neighbourhood algorithm, Dynamic customer arrivals, Decision making
DOI :10.26650/acin.831973   IUP :10.26650/acin.831973    Full Text (PDF)

Dinamik Eş Zamanlı Toplamalı ve Dağıtmalı Araç Rotalama Problemi için Statik Periyodik Çözüm Stratejisi

Mustafa Demirbilek

Günümüzde lojistik firmaları yüksek rekabet ortamının getirdiği baskılarla mücadele etmekte ve operasyonel maliyetleri düşürmeye çalışmaktadırlar. Aynı zamanda müşteriler, dağıtım ve toplama taleplerinin karşılanması için çok beklemek istememektedirler. Bu çalışmada, bahsedilen iki faktör statik periyodik çözüm stratejisiyle beraber ele alınmıştır. Problem, bir planlama dönemi içinde sürekli olarak gelen müşterilerin, toplama ve dağıtım taleplerinin aynı zamanda ve araçla karşılandığı “Dinamik Eş Zamanlı Toplamalı ve Dağıtmalı Araç Rotalama Problemi (DEZTDARP)” olarak modellenmiştir. Bununla beraber yeni ve ziyaret edilmemiş eski müşterileri göz önüne alarak rotalama problemlerini her zaman periyodu için tekrar tekrar çözen bir çözüm metodu önerilmiştir. Literatürde çok kullanılan bir sezgisel olan En Yakın Komşu Algoritması, her periyotta EZTDARP’lerini çözmek için kullanılmıştır. Talep dalgalanması, farklı sayıda müşteri, farklı rotalama periyotları gibi gerçek hayatta karşılaşılabilecek önemli hususlar probleme entegre edilmiştir. Sonuçlara bakıldığında, rotalama periyotlarının süresi arttığı zaman müşteri başı ortalama bekleme sürelerinin ciddi şekilde arttığı, ziyaret başı ortalama seyahat sürelerinin ise azaldığı görülmüştür. Rotalama planları günde 8 sefer yapıldığında müşteri başı ortalama bekleme süresi 5 dakika iken, plan sayısı 4 olduğunda bekleme süresi 66 dakikaya yükselmektedir. Daha fazla rotalama ise ziyaret başı fazladan 7 dakika ortalama seyahat süresine neden olmaktadır. Karar vericilerin hem firmalar hem de müşteriler için en iyi çözümü bulmalarına yardımcı olmak amacıyla farklı testler analiz edilmiş ve sonuçları açıklanmıştır.

Keywords: Eş zamanlı toplamalı ve dağıtmalı araç rotalama problemi, En yakın komşu algoritması, Dinamik müşteri gelişleri, Karar verme

PDF View

References

  • Ai, T. J., & Kachitvichyanukul, V. (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36(5), 1693-1702. google scholar
  • Avci, M., & Topaloglu, S. (2015). An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering, 83, 15-29. google scholar
  • Aydoğdu, B., & Özyörük, B. (2020). Dinamik eş zamanlı topla dağıt araç rotalama probleminin çözümü için matematiksel model ve sezgisel yaklaşım: Rassal iteratif yerel arama değişken komşu iniş algoritması. Journal of the Faculty of Engineering & Architecture of Gazi University, 35(2). google scholar
  • B. Columbus, “Book Reviews,” no. September, pp. 558-559, 1972. google scholar
  • Chen, J. F., & Wu, T. H. (2006). Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5), 579-587. google scholar
  • Christofides, N., & Eilon, S. (2006). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309-318. google scholar
  • Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91. google scholar
  • Dell’Amico, M., Righini, G., & Salani, M. (2006). A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation science, 40(2), 235-247. google scholar
  • Demirbilek, M. (2020). A Tactical/Strategic Level Cost Analysis Based On Visit Time Preferences For Vehicle Routing Problem With Simultaneous Pickup And Delivery. European Journal of Technique (EJT), 10 (2), 301-312. google scholar
  • Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 23(1), 79-96. google scholar
  • Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53. google scholar
  • Hezer, S. & Kara, Y. (2013). Eşzamanlı dağıtımlı ve toplamalı araç rotalama problemlerinin çözümü için bakteriyel besin arama optimizasyonu tabanlı bir algoritma. Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 28(2). google scholar
  • Kalayci, C. B., & Kaya, C. (2016). An ant colony system empowered variable neighbourhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 66, 163-175. google scholar
  • Kececi, B., Altiparmak, F., & Kara, I. (2015). Heterogeneous vehicle routing problem with simultaneous pickup and delivery: Mathematical formulations and a heuristic algorithm. Journal of the Faculty of Engineering and Architecture of Gazi University, 30(2), 185-195. google scholar
  • Koç, Ç., & Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79-91. google scholar
  • Laporte, G. (2009). Fifty years of vehicle routing. Transportation science, 43(4), 408-416. google scholar
  • Li, J., Pardalos, P. M., Sun, H., Pei, J., & Zhang, Y. (2015). Iterated local search embedded adaptive neighbourhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Systems with Applications, 42(7), 3551-3561. google scholar
  • Lund, K., Madsen, O. B., & Rygaard, J. M. (1996). Vehicle routing problems with varying degrees of dynamism. IMM Institute of Mathematical Modelling. google scholar
  • Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386. google scholar
  • Montane, F. A. T., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595-619. google scholar
  • Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research, 162(1), 126-141. google scholar
  • Subramanian, A., Drummond, L. M. D. A., Bentes, C., Ochi, L. S., & Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11), 1899-1911. google scholar
  • Wassan, N. A., & Nagy, G. (2014). Vehicle routing problem with deliveries and pickups: modelling issues and meta-heuristics solution approaches. International Journal of Transportation, 2(1), 95-110. google scholar
  • Yazgan, H. R., & Büyükyilmaz, R. G. (2017). Eş zamanlı topla dağıt araç rotalama problemine sezgisel bir çözüm yaklaşımı. Sakarya Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22(2), 436-449. google scholar
  • Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2016). The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints. European Journal of Operational Research, 251(2), 369-386. google scholar

Citations

Copy and paste a formatted citation or use one of the options to export in your chosen format


EXPORT



APA

Demirbilek, M. (2021). A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery. Acta Infologica, 5(1), 1-12. https://doi.org/10.26650/acin.831973


AMA

Demirbilek M. A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery. Acta Infologica. 2021;5(1):1-12. https://doi.org/10.26650/acin.831973


ABNT

Demirbilek, M. A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery. Acta Infologica, [Publisher Location], v. 5, n. 1, p. 1-12, 2021.


Chicago: Author-Date Style

Demirbilek, Mustafa,. 2021. “A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery.” Acta Infologica 5, no. 1: 1-12. https://doi.org/10.26650/acin.831973


Chicago: Humanities Style

Demirbilek, Mustafa,. “A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery.” Acta Infologica 5, no. 1 (May. 2024): 1-12. https://doi.org/10.26650/acin.831973


Harvard: Australian Style

Demirbilek, M 2021, 'A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery', Acta Infologica, vol. 5, no. 1, pp. 1-12, viewed 10 May. 2024, https://doi.org/10.26650/acin.831973


Harvard: Author-Date Style

Demirbilek, M. (2021) ‘A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery’, Acta Infologica, 5(1), pp. 1-12. https://doi.org/10.26650/acin.831973 (10 May. 2024).


MLA

Demirbilek, Mustafa,. “A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery.” Acta Infologica, vol. 5, no. 1, 2021, pp. 1-12. [Database Container], https://doi.org/10.26650/acin.831973


Vancouver

Demirbilek M. A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery. Acta Infologica [Internet]. 10 May. 2024 [cited 10 May. 2024];5(1):1-12. Available from: https://doi.org/10.26650/acin.831973 doi: 10.26650/acin.831973


ISNAD

Demirbilek, Mustafa. “A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery”. Acta Infologica 5/1 (May. 2024): 1-12. https://doi.org/10.26650/acin.831973



TIMELINE


Submitted26.11.2020
Accepted31.05.2021
Published Online07.06.2021

LICENCE


Attribution-NonCommercial (CC BY-NC)

This license lets others remix, tweak, and build upon your work non-commercially, and although their new works must also acknowledge you and be non-commercial, they don’t have to license their derivative works on the same terms.


SHARE




Istanbul University Press aims to contribute to the dissemination of ever growing scientific knowledge through publication of high quality scientific journals and books in accordance with the international publishing standards and ethics. Istanbul University Press follows an open access, non-commercial, scholarly publishing.