HETEROJEN EŞ-ZAMANLI TOPLA-DAĞIT ARAÇ ROTALAMA PROBLEMİ: MATEMATİKSEL MODELLER VE SEZGİSEL BİR ALGORİTMA
HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY: MATHEMATICAL FORMULATIONS AND A HEURISTIC ALGORITHM
Yazar: Keçeci, Barış; Altıparmak, Fulya; Kara, İmdat
Dergi: Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, Vol. 30 No. 2, 2015
Anahtar kelimeler: Engineering ; Mühendislik ; Heterogeneous fleet,simultaneous pickup and delivery,vehicle routing problem,mixed integerprogramming formulation,heuristics,Clarke-Wright savings algorithm ; Heterojen filo, eşzamanlı topla-dağıt, araç rotalama problemi, karma tamsayılı matematiksel modelleme, sezgiseller, Clarke-Wright tasarruf algoritması

Lojistik yönetiminde en önemli operasyonel kararlardan birisi müşterilere hizmet verecek araç rotalarının belirlenmesidir. Araç Rotalama Problemi (ARP), bir depodan müşterilerin dağıtım (toplama) taleplerini karşılayacak en uygun rotaların belirlenmesi olarak tanımlanabilir. Gerçek hayat lojistik uygulamalarında, filoda bulunan araçlar farklı özelliklerde olabilirler. Ayrıca müşterilerden/taşınanlardan kaynaklı gereklilikler de farklı özellikte araç kullanımı zorunluluğunu ortaya çıkarabilir. Bunun yanısıra firmalar, mamul, yarı mamul ve hammaddelerin tersine akışının yönetimini de hem ekonomik getirisi hem de yasal ve çevresel yükümlülüklerinden dolayı daha fazla önemsemektedirler. Bu makalede, heterojen araç filosunun bulunduğu ve müşterilerin dağıtım ve toplama taleplerinin eşzamanlı gerçekleştiği durumların birlikte dikkate alındığı bir ARP türü üzerinde çalışılmıştır. Bu problem Heterojen Eşzamanlı Topla-Dağıt Araç Rotalama Problemi (HETD-ARP) olarak adlandırılmıştır. HETD-ARP, toplam maliyeti enküçükleyen araç rotalarının ve herbir rotada kullanılan araç tipinin belirlenmesi olarak tanımlanabilir. Problem için polinom sayıda kısıta sahip akış tabanlı bir matematiksel model önerilmiştir. HETD-ARP, NP-zor problemler sınıfında olduğundan dolayı makul sürelerde orta boyutlu problemlere bile en iyi çözümü bulmak zordur. Bu nedenle bu makalede orta ve büyük boyutlu HETD-ARP’nin çözümü için basit bir kurucu sezgisel algoritma önerilmiştir. Bu algoritma, kaynaklarda ARP için önerilen Clarke-Wright Tasarruf (CWT) algoritmasının HETD-ARP için uyarlanmış halidir. Önerilen matematiksel modelin ve sezgisel algoritmanın etkinliği test problemleri üzerinde incelenmiştir.

One of the most important operational decisions in the logistics management is to determine the vehicle routes serving the customers. The Vehicle Routing Problem (VRP) can be defined as the determination of the optimal routes which meet the delivery (or pickup) demands from the depot to the customers. In the real life applications of logistics, vehicles in a fleet may differ from each other. In addition, the requirements arising from customers/goods may reveal the necessity to use different vehicles. Besides, companies do care more about the management of reverse flow of products, semi-finished and raw materials because of their economic benefits and as well as legal and environmental liabilities. In this paper, a variant of the VRP is considered with heterogeneous fleet of vehicles and simultaneous pickup and delivery. This problem is referred to Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery (HVRPSPD). The HVRPSPD can be defined as determining the routes and the vehicle types on each route while minimizing the total cost. In this paper, a polynomial sized flow-based mathematical model is proposed for the HVRPSPD. Since the HVRPSPD is in the class of NP-hard problems, it is difficult to find the optimal solution in a reasonable time even for the moderate size problems. Therefore, a simple and constructive heuristic algorithm is proposed to solve the medium and large scale HVRPSPD s. This algorithm is the adaptation of very well-known Clarke-Wright Savings approach, which has originally developed for the VRP, to the HVRPSPD. The performances of the proposed mathematical model and the heuristic algorithm have been examined on the test problems.