Engel içeren ortamlarda kapasite sınırlı araç rotalama problemine metasezgisel algoritmalarla çözüm yöntemi geliştirilmesi
Developing a solution method to capacity constrained vehicle routing problem for the environments with obstacles using metaheuristic algorithms
Yazar: MEHMET KARAKOÇ
Danışman: PROF. DR. AYBARS UĞUR
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Araç yönlendirme problemi = Vehicle routing problem ; Benzetim = Simulation ; Genetik algoritmalar = Genetic algorithms ; Metasezgiseller = Metaheuristics ; Optimizasyon = Optimization ; Optimizasyon problemi = Optimization problem

Özet:
Kapasiteli araç rotalama probleminde, her biri özdeş ve belirli kapasiteye sahip bir araç filosu için en uygun rota kümesini bulmak hedeflenir. Araçlar, merkezî bir depodan hareket eder, bir dizi müşteriye hizmet verir ve bu depoya geri dönerler. Bu işlemin, en az sayıda araçla ve en az maliyetle gerçekleştirilmesi amaçlanır. Engellerin bulunduğu ortamlar için literatürde değişik yol planlama problemlerine yönelik yakın tarihli çalışmalar mevcuttur. Bu tezde ise engel içeren ortamlarda kapasite sınırlı araç rotalama problemi ilk kez ele alınmaktadır.
Problemin tanımlanması ve modelin oluşturulmasından sonra, çözüm için genetik algoritmalar ve yerel arama stratejilerinden oluşan melez meta-sezgisel bir yöntem geliştirilmiştir. Depo-müşteri konumlarına ek olarak, daireler ve dışbükey çokgenler olarak iki farklı türdeki engellerin de eklenebildiği görsel bir benzetim ortamı oluşturulmuştur. Geliştirilen algoritma, tasarlanan çeşitli senaryolar için test edilmiştir. Farklı müşteri, engel sayıları ve engel büyüklükleri için kapsamlı başarım testleri literatürde ilk kez yapılarak, elde edilen sonuçlar sunulmuştur. Ayrıca, problemin bu özel şeklinin potansiyel uygulama alanları tartışılmıştır.

Abstract:
In capacitated vehicle routing problem, it is targeted to find the optimum set of routes for a fleet of vehicles in which each one is identical with a certain capacity. These vehicles start at a central depot, serve a set of customers and return back to this depot. It is aimed to realize this operation with the minimum number of vehicles and the minimum cost. There are recent studies intended for different path planning problems for the environments in which obstacles exist in literature. In this thesis, on the other hand, capacity constrained vehicle routing problem for the environments with obstacles is addressed for the first time.
After the problem was defined and a model was created, a hybrid meta-heuristic method that consists of genetic algorithms and local search strategies was developed for the solution. A visual simulation tool was implemented in which two different types of obstacles as circles and convex polygons may be added in addition to depot-customer locations. The algorithm developed was tested for various scenarios designed. Comprehensive performance tests were conducted for different numbers of customers and obstacles, and obstacle sizes for the first time in literature, and the results obtained were presented. Additionally, potential application areas of this particular form of the problem were discussed.