Capacitated vehicle routing problem with time windows

Abstract

ÖZETZaman Kısıtlı Araç Rotalama Problemi, Araç Rotalama Problemi'nin biruzantısıdır. Problemde amaç, tüm kısıtları sağlayan optimal rotalar oluşturmaktır.Bu çalışmada Zaman Kısıtlı Araç Rotalama Problemi için bir doğrusal tamsayılıprogramlama modeli ve problemin çözümü için hibrid sezgisel yaklaşımlarönerilmiştir. Modeldeki amaç fonksiyonu, araçlar tarafından kat edilen toplammesafenin en küçüklenmesidir. Tüm araçlar aynı özelliklere sahiptir ve araçlarınkapasiteleri göz önünde bulundurulmaktadır.Önerilen sezgisel algoritmalar iki bölümden oluşmaktadır. Birinci bölüm dahasonra geliştirilebilmek üzere bir başlangıç çözümü oluşturmaya yöneliktir. Başlangıççözümü algoritmasının paralel ve sıralı versiyonları önerilmiştir. Her iki yaklaşım damüşterileri rotalara atarken onları gruplandırma esasına dayanmaktadır.İkinci kısım ise üç farklı prosedürü içeren bir çözüm geliştirme algoritmasıdır. Buüç prosedür rotalar arası değişim, rotalar arası taşıma ve rota içi değişim'dir. Önerilensezgisel algoritmalarda bu prosedürler iç içe, birbirine bağlanmış şekilde kullanılmıştır.Bu üç prosedürü farklı şekillerde birbirine bağlayarak kullanan iki farklı yerel aramaalgoritması geliştirilmiştir.Ayrıca, çözüm geliştirme algoritmaları dağıtma adlı yeniden başlatmaalgoritmasıyla desteklenmiştir. Çalışmada iki farklı dağıtma metodu önerilmiştir.Bunlardan biri çözümü maliyet değişimini göz önünde bulundurmadan bozmakta, diğeriise daha kötü çözümlere sabit ve belirli bir olasılıkla gitmektedir.Çalışmada önerilen hibrid sezgisel algoritmalar, tüm başlangıç çözümü, çözümgeliştirme ve dağıtma algoritmalarının farklı kombinasyonlarıdır.Algoritmalar, Solomon'un 1987 yılında oluşturduğu ve araç rotalama içingeliştirilen algoritmaların karşılaştırılmasında çok yaygın olarak kullanılan 56 problemile test edilmiştir. Hibrid algoritmalar hem bilinen bazı sezgisel-ötesi yaklaşımlarla, hemde problemlerin literatürdeki bilinen en iyi çözümleri ile karşılaştırıldığında, genelanlamda iyi sonuçlar vermektedir.

ABSTRACTVehicle Routing Problem with Time Windows (VRPTW) is an extension of theCapacitated Vehicle Routing Problem. The objective is to design optimal routes thatsatisfy all of the constraints.In this study, a linear IP model and hybrid heuristics for the VRPTW areproposed. The objective function considered in the model is the total distance traveledby all vehicles. Vehicles are identical, capacities of the vehicles are finite and the timewindow constraints are assumed to be strict.The proposed hybrid heuristics are combined by two parts. The first part, whichhas both parallel and sequential versions, finds an initial solution. Both parallel andsequential initial solution algorithms are based on the idea of clustering the customerswhile doing the insertion. Second part is an improvement heuristic, which is acombination of three procedures: Inter-route exchanges, inter-route moves and intra-route exchanges. In the proposed heuristics, these operators are used nested with eachother. There are two improvement heuristics proposed that use these operators indifferent ways. The improvement algorithms are supported with a restart mechanismcalled diversification in order to escape the local optima and widen the search space. Inthis study, two diversification methods are proposed.The hybrid algorithms in this study are the combinations of the initial solution,improvement and diversification methods proposed.The algorithms have been tested on the 56 benchmark problem instances ofSolomon (1987), which were used widely in the literature. The hybrid algorithms areproven to give better results when compared to not only some known metaheuristics,but also to the best known results in the literature.