Zaman Pencereli Araç Rotalama Problemi Çözümü İçin Çok Amaçlı Genetik Algoritma Yaklaşımı

Abstract

Bu çalışmada, talepleri bilinen müşterilerin, konumu bilinen bir deponun ve belirli sayıda aynı kapasiteye ve özelliklere sahip özdeş araçların bulunduğu klasik Araç Rotalama Probleminin (ARP) bir çeşidi olan Zaman Pencereli Araç Rotalama Problemi (ZPARP) ele alınmıştır. Müşterilere belirli bir zaman aralığında hizmet verilebilen ZPARP için toplam yolu ve araç sayısını minimize etmek amaç fonksiyonları olarak belirlenmiştir. ZPARP’ye etkin çözümler üretilmesi amacı ile meta-sezgisel bir yöntem olan genetik algoritmanın sezgisel metotlarla melezleştirilmiş bir uyarlaması önerilmiştir. Genetik algoritmanın başlangıç popülasyonu oluşturma aşamasında süpürme algoritması ve en yakın komşu tabanlı bir algoritma kullanılarak üretilen kaliteli çözüm kümeleriyle aramaya başlaması, böylece optimum sonuçlara daha hızlı ulaşılması planlanmıştır. Genetik algoritmada başlangıç popülasyonları oluşturmada farklı sezgisel yöntemlerin kullanılmasının istenilen sonuca bir etkisi olup olmadığı test edilmiştir. Literatürde var olan bir veri problemi çözülmüş, süpürme algoritmasını kullanan genetik algoritma ile daha etkin sonuçlara ulaşıldığı görülmüştür.

In this study, Vehicle Routing Problem with Time Windows (VRPTW) which is a type ofclassical Vehicle Routing Problem (VRP) includes customers with known demands, a singledepot with known location and a certain number of identical vehicles with identical capacitiesand characteristics, is considered. Minimizing the total distance and the number of vehicles aredetermined as objective functions for VRPTW which is capable to serve the customers in aprespecified time interval. A hybridized version of genetic algorithm with heuristic methods isproposed to produce effective solutions for VRPTW. By using sweep algorithm and nearestneighbor-based algorithm at initial population generation phase of genetic algorithm, it is plannedto begin the search with quality solution sets and in this way, get the optimum solutions faster. Ithas been tested whether the use of different heuristic methods in generation of initial populationin genetic algorithm influences the desired solution. A benchmark problem in the literature hasbeen solved and it is observed that the genetic algorithm beginning with sweep algorithm at initialpopulation generation step reaches more effective solutions.