Araç rotalama problemleri için populasyon ve komşuluk tabanlı metasezgisel bir algoritmanın tasarımı ve uygulaması

Abstract

Bu tez çalışmasında firmalarda özellikle lojistik planlarının oluşturulması sırasında epeyce sıkkarşılaşılan kapasite ve mesafe kısıtlı Araç Rotalama Problemi için, populasyon ve lokalarama tabanlı bir metasezgisel algoritma önerilmiştir. Geliştirilen yöntem için populasyontabanlı metasezgisel tekniklerin çeşitlendirme stratejisi, komşuluk tabanlı tekniklerin iseyoğunlaştırma stratejisi göz önüne alınmıştır. Klasik sezgisel metotlar kullanılarak oluşturulanbaşlangıç çözümleri çözüm havuzu içerisinden kili Turnuva mantığı ile seçilmekte ve buçalışmada tanıtılan ?arama uzayında çözümler arası uzaklık? kavramı ile komşu çözümlerrasgele bir şekilde taranarak yeni çözümler üretilmektedir. Böylelikle arama işlemi, çözümuzayının en umut verici alanlarında yapılmakta ve üretilen çözüm kalitesi artırılmaktadır.Ayrıca algoritma süreci tamamen stokastik bir yapıda ilerlemekte ve bu sayede yöntem,oldukça az sayıda parametre içermektedir. Önerilen yöntem literatürde yer alan problemlerüzerinde denenmiş ve başarılı sonuçlar alınmıştır.Anahtar Kelimeler: Araç Rotalama Problemi, Metasezgisel Algoritmalarxi

TIn this thesis study, a population and neighborhood search based metaheuristic algorithm isproposed for capacity and distance restricted Vehicle Routing Problem, which is usuallyencountered during logistic planning in companies. When developing this method, populationbased techniques? diversification and local search based techniques? intensification strategiesare taken into account. Initial solutions are produced using classical heuristics and individualsare selected from solution pool with Binary Tournament sense. New generation is created byscanning neighborhood solutions randomly, considering ?distance between solutions in searchspace? concept introduced in this study. In this manner, search can be driven in solutionspace?s most promising regions and solutions quality is enhanced. Furthermore, algorithmprocess has a stochastic structure providing to set fairly few parameters. Proposed method isput into practice for several problems in literature and produce successful outputs.Keywords: Vehicle Routing Problem, Metaheuristic Algorithms