Heterojen eş-zamanlı topla-dağıt araç rotalama problemi için matematiksel modeller ve sezgisel yaklaşımlar
Mathematical formulations and heuristic approaches for the heterogeneous vehicle routing problem with simultaneous pickup and delivery
Yazar: BARIŞ KEÇECİ
Danışman: PROF. DR. FULYA ALTIPARMAK ; PROF. DR. İMDAT KARA
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2014
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Araç Rotalama Problemi (ARP), ulaştırma, dağıtım, lojistik, çizelgeleme, stok ve hizmet yönetimi, üretim planlama vb. gibi konularda operasyonel düzeyde karşılaşılabilen önemli endüstri mühendisliği problemlerinden birisidir. Gerçek hayat lojistik uygulamalarında, filoda bulunan araçlar birbirlerinden farklı olabilirler. Ayrıca, müşterilerden ve/veya taşınanlardan kaynaklı gereklilikler de farklı araç kullanımı zorunluluğunu ortaya çıkarabilir. Bunun yanında firmalar, mamul, yarı mamul ve/veya 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 tezde, 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 Kapasiteli Araç Rotalama Problemi 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 her bir rotada kullanılan araç tipinin belirlenmesi olarak tanımlanabilir. Tez kapsamında HETD-ARP için polinom boyutta kısıta ve 0-1 tamsayılı karar değişkenine sahip biri ayrıt, diğeri düğüm tabanlı iki matematiksel model önerilmiştir. HETD-ARP, NP-Zor bir problem olduğundan makul sürelerde orta ve büyük boyutlu problemler için eniyi çözümü bulmak zordur. Bu nedenle, problemin çözümü için tavlama benzetimi (TB) ve yerel arama (YA) algoritmalarına dayalı bir karma sezgisel algoritma geliştirilmiştir. Geliştirilen karma sezgisel algoritmanın etkinliği ARP için geliştirilmiş basit çözüm kurucu sezgiseller olan Enyakın Komşu (EYK) ve Clarke-Wright Tasarruf (CWT) algoritmaları ile karşılaştırılarak incelenmiştir. Kaynaklarda Heterojen ARP için oluşturulmuş test problemleri, yine kaynaklarda bulunan ayrıştırma yöntemleri ile HETD-ARP'ye uyarlanmış ve bu test problemleri kullanılarak, önerilen matematiksel modellerin ve geliştirilen sezgisel yaklaşımların etkinlikleri araştırılmıştır.

Abstract:
Vehicle Routing Problem (VRP) is one of the most important industrial engineering problems which may be encountered at the operational level on the topics such as transportation, distribution, logistics, scheduling, inventory and service management, production planning, and etc. In the real life applications of logistics, vehicles in a fleet may differ from each other. In addition, the requirements arising from customers and/or 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/or raw materials because of their economic benefits and as well as legal and environmental liabilities. In this study, a variant of Capacitated Vehicle Routing Problem (CVRP) 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). HVRPSPD can be defined to determine the routes and the vehicle types on each route while minimizing the total cost. In this dissertation, two polynomial size mathematical models that have polynomial sized constraints and binary variables, one with arc-based and the other with node-based auxiliary decision variables, have been proposed for the HVRPSPD. It is difficult (or may be impossible) to find the optimal solution in a reasonable time for the moderate and large size problems, since HVRPSPD is in the NP-hard problem class. Therefore, to solve an HVRPSPD instance we developed a hybrid metaheuristic approach based on the Simulated Annealing (SA) and Local Search (LS) algorithms. The performance of metaheuristic approach is compared with the very well-known and basic constructive heuristics, Nearest Neighborhood (NN) and Clarke-Wright Savings (CWS) algorithms which have been originally developed for the CVRP. We adapted the test problems of Heterogeneous VRP for the HVRPSPD using demand splitting procedures proposed in the literature and by using those test problems the performance of each mathematical model and heuristic approaches were investigated.