Genetik Algoritma ile Eş Zamanlı Topla-Dağıt Araç Rotalama: İstanbul Anadolu Yakası için Bir Uygulama

Abstract

Araç rotalama problemi, lojistik alanındaki en önemli problemlerden biridir. Eş zamanlı Topla-Dağıt Araç Rotalama Problemi, Araç Rotalama Problemi’nin bir türüdür. Bu problem türünde, müşteri veya iş merkezlerinin toplama ve dağıtım talepleri eşzamanlı olarak karşılanmaktadır. Çözümü zor problemler arasında yer alan Eş zamanlı Topla-Dağıt Araç Rotalama Problemi’nde dikkate alınması gereken bir diğer unsur da araçların kapasitesidir. Bu probleme yönelik olarak son yıllarda yapılan çalışmalarda metasezgisel yöntemlerin sıklıkla kullanıldığı gözlemlenmiştir. Bu çalışmada, İstanbul’un Anadolu yakasında yer alan Ataşehir ilçesinde ana deposu bulunan bir perakende işletmesinin 12 farklı marketinin dağıtım ve toplama taleplerini eş zamanlı karşılayan araç rotalama problemi ele alınmıştır. Problemin çözümü için ceza-tabanlı Genetik Algoritma önerilmiştir. Bu doğrultuda, oluşturulan örnek problem setleri üzerinde kat edilen toplam mesafe en küçüklenecek şekilde en az sayıda araç ile müşterilerin tüm dağıtım ve toplama taleplerini karşılayan verimli rotalar hesaplanmaktadır. Önerilen ceza-tabanlı Genetik Algoritma ile elde edilen sonuçlar bir diğer metasezgisel algoritma olan Tavlama Benzetimi ile karşılaştırılarak algoritmanın performansı değerlendirilmiştir. Karşılaştırma sonuçları incelendiğinde ceza-tabanlı Genetik Algoritma ile hem maliyet hem de işlem süresi açısından daha iyi sonuçların elde edildiği görülmüştür.

Keywords

• Eş Zamanlı Topla-Dağıt Araç Rotalama Problemi
• Genetik Algoritma
• Tavlama Benzetimi

Simultaneous Pick-Up and Delivery Vehicle Routing Using Genetic Algorithm: An Application for the Anatolian Side of Istanbul

Abstract

Vehicle routing problem is one of the most important problems in logistics. Simultaneous Pick-up and Delivery Vehicle Routing Problem is a type of Vehicle Routing Problem. In this type of problem, pick-up and delivery requests of customers or business centers are met simultaneously. Simultaneous Pick-up and Delivery Vehicle Routing Problem is one of the difficult problems to solve. Another factor to consider is the capacity of the vehicles. In recent years, it has been observed that metaheuristics methods are used for the solution of this problem. In this study, the vehicle routing problem, which meets the pick-up and delivery demands of 12 different markets of a retail company with a main warehouse in Ataşehir district on the Anatolian side of Istanbul, is discussed. A penalty-based Genetic Algorithm is proposed for the solution of the problem. Accordingly, efficient routes that meet all pick-up and delivery demands of the customers are generated with the least number of vehicles so that the total distance traveled on the sample problem sets is minimized. The performance of the algorithm is evaluated by comparing the results of the proposed penalty-based Genetic Algorithm with another metaheuristics algorithm, Simulated Annealing. When the comparison results are analyzed, it is seen that better results are obtained in terms of both cost and computation time with the penalty-based Genetic Algorithm.

Keywords

• Simultaneous Pick-Up and Delivery Vehicle Routing
• Genetic Algorithm
• Simulated Annealing

References

1. Ai J, Kachitvichyanukul V, 2009. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers and Operations Research, 36(5): 1693-1702.
2. Avci M, Topaloglu S, 2015. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers and Industrial Engineering, 83: 15–29.
3. Awad H, Elshaer R, 2019. A Taxonomic Review of Metaheuristic Algorithms for Solving the Vehicle Routing Problem and Its Variants. Computers and Industrial Engineering, 106242.
4. Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G, 2007. Static pickup and delivery problems: A Classification scheme and survey. Top, 15(1): 1-31.
5. Bianchessi N, Righini G, 2007. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers and Operations Research, 34 (2): 578-594.
6. Catay B, 2010. A new saving-based ant algorithm for the vehicle routing problem. Expert Systems with Applications, 37 (10): 6809-6817.
7. Chen CL, Neppalli RV, Aljaber N, 1996. Genetic Algorithm Applied to the Continuous Flow Shop Problem. Computers and Industrial Engineering, 30(4), 919-929.
8. Chen J, 2006. Approaches for the vehicle routing problem with simultaneous deliveries and pick-ups. Journal of the Chinese Institude of Industrial Engineers, 23(2): 141-150.

9. Chen, JF, Wu TH, 2006. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5): 579–587.
10. Cheng R, Gent M, Tosawa T, 1995. Genetic Algorithms for Designing Loop Layout Manufacturing Systems. Computers and Industrial Engineering, 31(3-4): 587-591.
11. Chu PC, Beasley JE, 1996. A Genetic Algorithm for the Generalised Assigment Problem. Computers and Operations Research, 24(1): 17-23.
12. Crispim J, Brandao J, 2005. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society, 56(11): 1296-1302.
13. Dantzig GB, Ramser JH, 1959. The truck dispatching problem. Management Science, 6(1): 80–91.
14. 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.
15. Dethloff J, 2001. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 23(1): 79-96.
16. Elbasan S, 2015. Karbon Ayak İzini Dikkate Alan Eşzamanlı Topla-Dağıt Araç Rotalama, Eskişehir Osmangazi Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi (Basılmış).
17. Ekşioğlu B, Vural AV, Reisman A, 2009. The vehicle routing problem: A taxonomic review. Computers and& Industrial Engineering, 57(4): 1472-1483.
18. Fan J, 2011. The vehicle routing problem with simultaneous pick-up and delivery based on customer satisfaction. Advanced in Control Engineering and Information Science, 15: 5284-5289.
19. Gajpal Y, Abad P, 2009. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers and Operations Research, 36(12): 3215-3223.
20. Goksal FP, Karaoglan İ, Altıparmak F, 2013. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computer Industrial Engineering, 65(1): 39-53.
21. Günther HO, Kulak O, Kalayci CB, Polat O, 2015. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 242(2): 369-382.
22. Halse K, 1992. Modeling and solving complex vehicle routing problems, Technical University of Denmark, Institute of Mathematical Statistics and Operations Research, Doktora Tezi (Basılmış).
23. Holland J, 1975. Adaptation in Natural and Artificial Systems, Society for Industrial and Applied Mathematics, No:3, Philadelphia-United States.
24. Kaya C, 2017. Eş Zamanlı topla dağıt araç rotalama problemi için karınca koloni sistemi ile güçlendirilmiş değişken komşuluk arama algoritması, Pamukkale Üniversitesi, Yüksek Lisans Tezi (Basılmış).
25. Kirkpatrick S, Gelatt CD, Vecchi MP, 1983. Optimization by simulated annealing. Science, 220(4598): 671-680. Koç Ç Laporte G, 2018. Vehicle routing with backhauls: Review and research perspectives. Computers and Operations Research, 91: 79-91.
26. Lee CY, Kim SJ, 1995. Parallel Genetic Algorithm for the Earliness Tardiness Job Scheduling Problem With General Penalty Weights. Computers and Industrial Engineering, 28(2): 231-243.
27. Liu R, Xie X, Augusto V, Rodriguez C, 2013. Heuristic approaches for a special simultaneous pick-up and delivery problem with time windows in home healthcare industry. European Journal of Operational Research, 230(3): 475-486.
28. Min H, 1989. The multiple vehicle routing problem with simultaneous delivery and Pick up points, Transportation Research, 23(5): 377-386.
29. Montane FAT, Galvao RD, 2006. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computer Operations Research, 33(3): 595-619.
30. Nagy G, Salhi S, 2003. Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries. European Journal of Operational Research, 162(1): 126-141.
31. Ropke S, Pisinger D, 2006. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3): 750-775.
32. Subramanian A, Drummond LM, Bentes C, Ochi LS, Farias R, 2010. A parallel heuristic for the vehicle routing problem with simultaneous pick-up and delivery. Computers and Operations Research, 37(11): 1899-1911.
33. Subramanian A, Uchoa E, Pessoa A A, Ochi L S, 2011. Branch and cut with lazy separation for the vehicle routing problem with simultaneous pick-up and delivery. Operations Research Letters, 39(5): 338-341.
34. Tasan S, Gen M, 2012. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers and Industrial Engineering, 62(3): 755-761.
35. Wang HF, Chen YY, 2012. A genetic algorithm for the simultaneous delivery and pick-up problems with time windows. Computer Industrial Engineering, 62(1): 84-95.
36. Yazgan HR, Büyükyilmaz RG, 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.
37. Zachariadis E, Tarantilis CD, Kiranoudis CT, 2010. An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 202(2): 401-41.
38. Zachariadis EE, Kiranoudis CT, 2011. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 38(3): 2717-2726.
39. Zachariadis EE, Tarantilis CD, Kiranoudis CT, 2009. A Hybrid Metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert System with Applications, 36(2): 1070-1081.
40. Zachariadis, EE., Tarantilis, CD., Kiranoudis, CT., 2009. A Hybrid Metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert System with Applications, 36, 1070-1081.