İki aşamalı eş zamanlı topla-dağıt araç rotalama problemi için çözüm yaklaşımları
Solution approaches for two echelon vehicle routing problem with simultaneous pickup and delivery
Yazar: ÖNDER BELGİN
Danışman: PROF. DR. FULYA ALTIPARMAK
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
Dizin: Araç yönlendirme problemi = Vehicle routing problem ; Sezgisel algoritmalar = Heuristic algorithms ; Tam sayılı doğrusal programlama = Integer linear programming ; Yöneylem araştırması = Operations research

Özet:
Rekabetin artması ve çeşitli yasal zorunlulukların etkisiyle firmalar dağıtım ağlarının tasarımında yeni stratejiler geliştirmek zorunda kalmaktadır. Son yıllarda trafik yoğunluğu ve çevresel sorunlar gibi faktörlerin etkisiyle iki aşamalı dağıtım sistemlerinin uygulama alanları genişlemektedir. Etkin bir dağıtım sisteminin tasarlanabilmesi için ise araç rotalamaya ilişkin kararlar önemli bir yer tutmaktadır. Bu tezde, iki aşamalı eş zamanlı topla-dağıt araç rotalama problemi (2A/ETDARP) ele alınmıştır. 2A/ETDARP, iki aşamalı bir dağıtım sisteminde müşterilere dağıtım ve müşterilerden toplama faaliyetlerinin aynı araçla gerçekleştirildiği eş zamanlı topla-dağıt faaliyetlerinin dikkate alındığı araç rotalama problemi (ARP) olarak tanımlanabilir. Ele alınan bu problem, lojistik ve kargo hizmetleri, hipermarket ürünlerinin dağıtım, otomotiv  yedek parça dağıtımı ve şehir lojistiği gibi çeşitli alanlarda uygulanmaktadır. Literatürde ilk kez bu tez kapsamında ele alınan 2A/ETDARP'ın çözümü için düğüm tabanlı bir matematiksel model geliştirilmiş ve bu modelin 4 farklı türü ele alınmıştır. Geliştirilen matematiksel modeli kuvvetlendirmek amacıyla geçerli eşitsizliklerden yararlanılmıştır. 2A/ETDARP NP-zor sınıfında yer alan bir problem olduğundan, problemin çözümü için Değişken Komşu İniş Algoritması (DKİ) ve Yerel Arama Algoritması (YA)'nın birlikte kullanıldığı bir genel amaçlı sezgisel DKİ_YA algoritması önerilmiştir. Son olarak ise problemin çözümü için kesin algoritma sınıfında yer alan Kesme Düzlemi Algoritması (KDA) uygulanmıştır. Geliştirilen matematiksel modellerin, önerilen DKİ_YA algoritmasının ve KDA'nın performansnı literatürde yer alan test problemleri aracılığıyla analiz edilmiştir. Yapılan deneysel çalışmalar sonucunda hem DKİ_YA algoritması hem de KDA ile çözüm kalitesinde artışlar sağlandığı görülmüştür.

Abstract:
Companies are forced to develop new distribution strategies due to the increase in competition and legal obligations. In recent years application areas of two-echelon distribution systems because of the traffic congestion and environmental problems. Vehicle routing is an important decision area for an effective distribution system. In this thesis two-echelon vehicle routing problem with simultaneous pickup and deliveries (2E/VRPSPD) is considered. 2E/VRPSPD  can be described as a vehicle routing problem (VRP) in which pickup and delivery activities are achived by the same vehicle in a two-echelon distribution system and the problem is firstly considered in literature in this thesis.This problem has a various application areas such as logistics and cargo services, distribution of hypermarket goods, distribution of automotive spare parts and city logistics. First, a node-based mathematical model is developed for the 2E/VRPSPD, which is considered first time in this thesis, and four different variations of the problem are investigated. To strength the mathematical model, valid inequalities are used. Since 2E/VRPSPD  is an NP-hard problem a metaheuristic algorithm VND_LS, combination of Variable Neighborhood Descent (VND) and Local Search (LS), is proposed to solve the problem. Finally, an exact solution method Cutting Plane Algorithm (CPA) is used. The performance of proposed mathematical models, VND_LS and CPA is analyzed by means of test problems derived from the literature. The experimental studies indicate that both VND_LS and CPA provide increase in solution quality.