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

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

Sinem BOZKURT KESER, İnci SARIÇİÇEK, Açelya TOPRAK, Faruk Emre CİĞER, Mehmet DEMİRÖZ

Abstract

Vehicle routing problem is one of the most important problems in logistics. Simultaneous Pick-upand Delivery Vehicle Routing Problem is a type of Vehicle Routing Problem. In this type of problem, pick-upand delivery requests of customers or business centers are met simultaneously. Simultaneous Pick-up andDelivery Vehicle Routing Problem is one of the difficult problems to solve. Another factor to consider is thecapacity of the vehicles. In recent years, it has been observed that metaheuristics methods are used for the solutionof this problem. In this study, the vehicle routing problem, which meets the pick-up and delivery demands of 12different 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 numberof vehicles so that the total distance traveled on the sample problem sets is minimized. The performance of thealgorithm is evaluated by comparing the results of the proposed penalty-based Genetic Algorithm with anothermetaheuristics algorithm, Simulated Annealing. When the comparison results are analyzed, it is seen that betterresults are obtained in terms of both cost and computation time with the penalty-based Genetic Algorithm.

Özet

Araç rotalama problemi, lojistik alanındaki en önemli problemlerden biridir. Eş zamanlı Topla-DağıtAraç 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ındayer alan Eş zamanlı Topla-Dağıt Araç Rotalama Problemi’nde dikkate alınması gereken bir diğer unsur daaraçların kapasitesidir. Bu probleme yönelik olarak son yıllarda yapılan çalışmalarda metasezgisel yöntemlerinsıklıkla kullanıldığı gözlemlenmiştir. Bu çalışmada, İstanbul’un Anadolu yakasında yer alan Ataşehir ilçesindeana 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 rotalarhesaplanmaktadır. Önerilen ceza-tabanlı Genetik Algoritma ile elde edilen sonuçlar bir diğer metasezgiselalgoritma 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üresiaçısından daha iyi sonuçların elde edildiği görülmüştür.