Metasezgisel algoritmalarla araç rotalama probleminin modellenmesi
Modeling of vehicle routing problem with metaheuristic algorithms
Yazar: KADİR YILDIZ
Danışman: DR. ÖĞR. ÜYESİ BİLAL BABAYİĞİT
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Günümüzde nakliye, tedarik zinciri, üretim planlaması, telekomünikasyon ve daha bir çok alanda uygulanabilen Araç Rotalama Problemi yaygın olarak kullanılan kombinasyonel optimizasyon problemlerinin başında gelmektedir. Gezgin Satıcı Probleminin genelleştirilmiş hali olan Araç Rotalama Probleminde temel amaç belirli kısıtlar göz önünde bulundurularak belirli sayıda düğüm noktasına hizmet veren minimum mesafe rotaları oluşturmaktır. ARP, Np-zor sınıfı problemi olduğundan çözüm yöntemi olarak kesin çözüm yöntemleri yerine optimal çözüm üreten metasezgisel algoritmalar tercih edilmektedir. Bu tez çalışmasında 120 müşterili bir dağıtım firmasının optimal dağıtım rotaları, kapasite kısıtı göz önüne alınarak oluşturulmuştur. Rotalama yapılırken kullanılan temel algoritmalar Yapay Arı Kolonisi ve Genetik algoritmalardır. Optimizasyona yönelik tur kurucu sezgisel algoritması olarak Greedy yaklaşımına dayalı En yakın komşu algoritması ve tur geliştirici sezgisel algoritması olarak ise 2-opt algoritmasına dayanan hibrit YAK ve Genetik algoritmaları önerilmiştir. Önerilen hibrit algoritmalarla elde edilen sonuçlar firmanın dağıtım rotaları ile karşılaştırılmış ve daha iyi sonuçlar elde edilmiştir. Ayrıca, önerilen modeller literatürde halihazırda var olan veri setleri üzerinde denenmiş ve optimal sonuçlara yakın değerler elde edilmiştir.

Anahtar Kelimeler: Araç Rotalama Problemi, Yapay Arı Koloni Algoritması, Genetik Algoritma, Kombinasyonel Optimizasyon

Abstract:
Nowadays, Vehicle Routing Problem, which can be applied to transportation, supply chain, production planning, telecommunication and many other fields, is one of the most commonly used combinatorial optimization problems. VRP is a generalized version of the Travelling Salesman Problem its main purpose is to create minimum distance roots that serve a certain number of node points by considering certain constraints. Since VRP is a NP-Hard class problem, metaheuristic algorithms, are preferred as a solution method instead of the exact solution methods because they produce optimal solutions. In this thesis study optimal distribution routes are created by considering the capacity constraint of a distribution company which has 120 customers. Algorithms used for VRP are based on mainly Artificial Bee Colony algorithm and Genetic algorithm. Hybrid ABC and GA algorithms based on as the tour constructor heuristic algorithm the nearest neighborhood based on the Greedy approach and as the tour improvement heuristic algorithm the 2-opt are proposed. Obtained results with proposed hybrid algorithms are compared with the distribution routes of the company and better results are produced. The proposed models are also tested on the existing data sets in the literature and the obtained values are close to the optimal results. 

Keywords: Vehicle Routing Problem, Artificial Bee Colony Algorithm, Genetic Algorithm, Combinational Optimization