Dinamik eş zamanlı topla-dağıt araç rotalama problemi için matematiksel model ve sezgisel yaklaşımlar
Mathematical formulations and heuristic approaches for the dynamic vehicle routing problem with simultaneous pickup and delivery
Yazar: BURAK AYDOĞDU
Danışman: YRD. DOÇ. DR. BAHAR ÖZYÖRÜK
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2017
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Tedarik Zinciri Yönetiminin (TZY) önemli bir unsuru olan Araç Rotalama Problemleri (ARP) artan rekabet ortamında firmaların iyileştirmeleri gereken operasyonel süreçlerin başında gelmektedir. Firmaların birbirleri ile olan rekabetlerinde en önemli unsurlardan bir tanesi de maliyet kriteridir. Firmalar müşterilere yapılacak olan dağıtım faaliyetlerinden kaynaklanan maliyetlerin yanında, yasal ve çevresel zorunluluklar nedeniyle geri dönüşümlü/depozitolu ürünlerin toplanmasından dolayı ek maliyetlerle karşılaşabilmektedir. Gerçek hayatta müşterilerden gelen geri dönüşümlü/depozitolu ürünlerin toplanmasına ilişkin taleplerin dolaşımda bulunan araçlar tarafından karşılanması maliyet açısından firmalara büyük avantaj sağlayacaktır.  Bu çalışma kapsamında firmaların dağıtım ve toplama taleplerini minimum maliyetle karşılamak amacıyla Dinamik Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (DETD_ARP) ele alınmıştır. Tez kapsamında DETD_ARP için yeniden eniyileme süreci olarak periyodik ve sürekli yeniden eniyileme süreçlerinden, periyodik yeniden eniyileme süreci tercih edilmiştir. Bu süreç birinci aşama (statik problem) ve yeniden rotalamanın yapıldığı ikinci aşama (dinamik problem) olarak ikiye ayrılmıştır. Birinci aşamada Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (ETD_ARP) için literatürde yer alan bir matematiksel model kullanılmıştır. İkinci aşamada ise DETD_ARP için ayrıt tabanlı 0 – 1 tam sayılı bir matematiksel model geliştirilmiştir. Geliştirilen matematiksel modelin etkinliği literatürde yer alan problemler kullanılarak değerlendirilmiştir. DETD_ARP NP-Zor bir problem olduğu için orta ve büyük boyutlu problemler için makul sürelerde (7200sn) eniyi çözümü bulmak mümkün olmamıştır. Bu yüzden, problemin çözümü için Tavlama Benzetimi(TB), Yerel Arama Algoritması(YA) ile üst sezgisellerin(hyper-heuristics) kullanıldığı Tavlama Benzetimi –Tabu Arama(TB-TA) ve Yerel Arama-Rassal Değişken Komşu İniş (YA-RDKİ) algoritmaları kullanılmıştır. Sezgisel algoritmaların performans değerlendirmesi ilk aşama(statik) için yine literatürde yer alan problemler kullanılarak yapılmıştır. Yapılan değerlendirme neticesinde TB-TA algoritmasının diğer sezgisel algoritmalara göre daha iyi sonuçlar verdiği görülmüştür. Son olarak, DETD_ARP'nin TB-TA algoritması ile elde edilen sonuçları değerlendirilmiştir.

Abstract:
Vehicle Routing Problem (VRP), an important component of Supply Chain Management (SCM), is at the forefront of the operational processes that companies need to improve in an increasingly competitive environment. The cost criterion is one of the most important elements in competition of companies with each other. Companies may encounter additional costs due to the collection of recycled / returnable products due to legal and environmental obligations besides of customers' delivery costs.  In real life, it will be a great advantage for the companies in terms of cost to satisfy the requirements for pickup of recyclable / returnable products by vehicles in circulation. In this study, Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery (DVRPSPD) is dealt with to satisfy companies' pickup and delivery requirements with minimum cost. Within the scope of the thesis, the periodic re-optimization process is preferred from the periodic and continuous re-optimization process as the re – optimization process for DVRPSPD. This process is divided into two phases: the first phase (static problem) and the second phase (dynamic problem) in which re-routing is performed. In the first phase, a mathematical model from literature is used for Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). For the second phase, a mathematical model with binary variables for DVRPSPD  is developed. The effectiveness of the developed mathematical model was evaluated using the problems in the literature. Since DVRPSPD belongs to the class of NP-hard problem, it is difficult to find the optimal solution in a reasonable time (7200 sec.) for medium and large size instances. For this reason, Simulated Annealing (SA), Local Search (LS) together with Simulated Annealing – Tabu Search (SA-TS) and Random – İterative Local Search – Variable Neighborhood Descend (R-ILS-VNS) algorithms in which hyper-heuristics are used developed to solve the problem. The performance evaluation of the heuristics algorithms are performed using the instances in the literature for the first phase. Results show that SA-TS algorithm gives better results than those of other heuristic algorithms. Finally, the results obtained by the solution of DVRPSPD with the SA-TS algorithm have been evaluated.