A genetic algorithm based solution approach for vehicle routing problem

Abstract

Klasik Araç Rotalama Probleminin (ARP) bir türü olan Zaman Pencereli Araç Rotalama Problemi (ZPARP), tedarik zinciri yönetiminin önemli bir parçası olan lojistik yönetiminin içerdiği bir taşımacılık sorununu ele alır. ZPARP, bir depodan müşterilere belirli bir zaman aralığında teslimat yapan araç filosu için optimum rotaları araştırır. Rota optimizasyonu, hızlı teslimat ve daha düşük maliyetle müşteri memnuniyetine olan etkisinden dolayı lojistik yönetiminde önemli bir yere sahiptir. Literatüre göre, ZPARP bir kombinatoryal optimizasyon problemi olduğundan çözüm için genellikle sezgisel veya metasezgisel yöntemler tercih edilir. Bu tezde ZPARP'yi çözmek için çok amaçlı bir genetik algoritma (GA) yaklaşımı önerilmiştir. Amaçlar, araçların toplam mesafesinin ve bekleme süresinin minimizasyonu olarak belirlenmiştir. GA adımlarında bireylerin değerlendirilmesi, sıralanması ve seçilmesinde çok amaçlı optimizasyon tekniklerinden biri olan NSGA-II kullanılmıştır. Literatürde, başlangıç popülasyonunun kalitesinin algoritmalar üzerindeki etkisinden bahsedilmiştir. Bu çalışmada, başlangıç popülasyonunun etkisini analiz etmek için çok amaçlı GA'da başlangıç popülasyonu üretimi aşamasında üç farklı yöntem kullanılmıştır. Başlangıç popülasyonları ilk olarak rasgele, ikinci olarak en yakın komşu tabanlı bir algoritma ile ve üçüncü olarak da süpürme tabanlı bir algoritma ile oluşturulmuştur. Oluşturulan üç algoritma, Solomon'un karşılaştırma problemleri üzerinde test edilmiştir. Başlangıç popülasyonu süpürme tabanlı algoritma ile oluşturulan GA ile daha etkili sonuçlara ulaşıldığı görülmüştür. Bu çalışmanın amacı, GA ile elde edilen sonuçlarda başlangıç popülasyonunun etkisini ortaya koymak ve ZPARP çözümü için karşılaştırmalı bir yaklaşım sunmaktır.

Vehicle Routing Problem with Time Windows (VRPTW) which is a type of classical Vehicle Routing Problem (VRP) handles a transportation issue that is comprised in the logistics management which is a substantial component of the supply chain management. VRPTW searches optimum routes for a fleet of vehicles making delivery from a depot to the customers in a specified time interval. Route optimization has a significant importance in logistics management owing to the effect on the customer satisfaction by fast delivery and lower cost. According to the literature, heuristic or metaheuristic methods are generally preferred for the solution since VRPTW is a combinatorial optimization problem. In this thesis, a multi objective genetic algorithm (GA) approach is offered to solve VRPTW. The objectives are determined as the minimization of the total distance and waiting time of the vehicles. NSGA-II, which is one of the multi objective optimization techniques is used in the evaluation, ranking, and selection of the individuals at GA steps. The influence of the quality of the initial population for an algorithm has been mentioned in different studies. In this study, three different methods are used to analyze this influence in the generation of the initial population step in multi objective GA. The initial populations are generated first randomly, second by a nearest neighbor based algorithm, and third by a sweep based algorithm. The formed three algorithms are tested on Solomon's benchmark problems. The GA with the initial population generated by sweep based algorithm has provided more effective results. The purpose of the study is to reveal the effect of initial population on the solutions obtained from GA and present a comparative approach for VRPTW solution.