Stokastik eşzamanlı topla-dağıt araç rotalama problemi için melez yaklaşım: Diferensiyel evrim algoritması

Abstract

Lojistik yönetimi ve tedarik zinciri yönetiminde en önemli işlemsel (operasyonel) kararlardan birisi toplam seyahat süresini enküçükleyecek şekilde tüm müşterilere servis sağlayacak araç rotalarının belirlenmesidir. Klasik araç rotalama problemi, bir depodan müşterilerin dağıtım ya da toplama taleplerini karşılayacak en uygun rotaların belirlenmesi olarak tanımlanır. Uygulamada karşılaşılan kısıtlamalara dayalı olarak ilgili kaynaklarda farklı araç rotalama problemleri tanımlanmaktadır. Bu problemlerden birisi Eşzamanlı Topla-Dağıt Araç Rotalama Problemidir (ETD_ARP). ETD_ARP depodan müşterilere ürün dağıtımının yanı sıra müşterilerden de depoya geri dönecek ürünlerin toplanması işlemlerinin eşzamanlı gerçekleştirildiği bir araç rotalama problemidir. Bu tür problemlerde müşterilerden toplanan ve dağıtılan miktarların sabit olmadığı durum göz önüne alındığında problem stokastik eşzamanlı topla-dağıt araç rotalama problemi (SETD_ARP) olmaktadır. Bu tez kapsamında, SETD_ARP çözümü için kesikli diferansiyel evrim algoritması (KDEA) ve KDEA ve yerel aramanın avantajlarını kullanan melez algoritma (m_KDEA) geliştirilmiştir. Bu iki algoritma ve rassal arama(RA) algoritması bir grup test problemleri üzerinde karşılaştırılmıştır. Karşılaştırma sonuçları m_KDEA `nın çözüm kalitesi açısından daha başarılı bir algoritma olduğunu göstermiştir.

One of the most important operational decisions in the field of logistics is to find a set of routes servicing all the customers with the objective of minimizing the total travel distance. Classical vehicle routing problem can be defined as the problem of designing optimal delivery or pickup routes from one depot to a number of customers. Different variants of vehicle routing problem depending on some restrictions, which are faced in the practice, have been proposed in the literature. One of these variants is the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRP_SPD). In the VRP_SPD, the pickup and delivery demands of customers in each route are met simultaneously. If pickup and delivery demands of customers are not fixed, this type of problems can be defined Vehicle Routing Problem with Stochastic Simultaneous Pickup and Delivery (VRP_SSPD). In this thesis, a Discrete Differential Evolution Algorithm (DDEA) and a hybrid algorithm, integrating the advantage af Discrete Differential Evolution and local search, called (h_DDEA) are presented for this problem. In addition, Random Search (RS) algorithm is developed to see the performance of these two algorithms. The proposed h_DDEA performs better solutions than DDEA and RS interms of solution quality over a suit of test problems.