Development of a Hybrid Method for the Solution of the Vehicle Routing Problem with Time Windows

Yüksek Lisans TeziKüreselleşmeyle birlikte rekabetin hızla arttığı bir dünyada firmaların sürdürülebilir başarı sağlamasında müşteri memnuniyeti belirleyici faktörlerden biridir. Müşterilerin beklentilerine cevap verebilmek için güçlü bir tedarik alt yapısı oluşturmak hayati derecede önemlidir. Tedarik zincirindeki en önemli süreçlerden biri de rota planlamasıdır. Günümüzde araç rotalama problemleri üzerine planlama yapmak özellikle lojistik ve hizmet sektöründe faaliyet gösteren şirketler için önemli hale gelmiştir. Artan talepleri karşılamak ve maliyetleri azaltmak için geliştirilen iş süreçlerinde rotalama ve optimizasyon çözümleri şirketler için oldukça önemlidir. Kötü yönetilen rota planları, şirketlerin müşterilerine hizmet vermesi açısından sorun teşkil etmekte, diğer lojistik ve hizmet süreçlerinde aksamalara neden olmaktadır. Hızla gelişen ve değişen küresel rekabet ortamı işletmeleri daha iyi süreç yönetimi için planlama yapmaya zorlamaktadır. Bu planlamanın doğru yapılması için hem müşteri memnuniyetine önem verilmeli hem de işletme maliyetleri düşürülmelidir. Araç rotalama maliyetleri, lojistik sistem içindeki taşıma ve dağıtım maliyetlerinin önemli bir parçasıdır. Araç rotalama probleminin amacı, bir araç filosu için en küçük maliyetli rota kümesini tasarlamaktır. Araç rotalama problemlerinden biri olan zaman pencereli araç rotalama problemi (ZPARP) birçok araştırmacının çalışma alanını oluşturmaktadır. ZPARP her bir müşteriye ait bir zaman aralığı kısıtı olan araç rotalama problemidir. Bu problemde dağıtım aracı, her bir müşteriye belirli bir zaman aralığında hizmet vermek zorundadır. Bu çalışmada, ZPARP'nin çözümü için yapay arı kolonisi (Artificial Bee Colony-ABC) algoritması ile Order Crossover (OX1) operatörü melezleştirilmiş ve ABC-OX1 olarak adlandırılan hibrit bir yöntem önerilmiştir. ABC-OX1 yönteminde başlangıç çözümleri rastgele olarak üretilmiş ve bu çözümler tur geliştirici 3-opt algoritması ile iyileştirilmiştir. İşçi arı fazında insertion, swap ve divideandswap yerel arama operatörleri eşit olasılıkla kullanılmıştır. Gözcü arı fazında OX1 operatörü ile besin çeşitliliği sağlanmış ve kaliteli çözümler üzerinde aramaya devam edilmiştir. Kâşif arı fazında ise yeni çözümler rastgele oluşturulmuş ve bu çözümler tur geliştirici 2-opt algoritması ile iyileştirilmiştir. ABC-OX1 yönteminde popülasyondaki çözümlerin uygunluk değerlendirmesi için Bellman algoritması kullanılmıştır. ABC-OX1, Solomon'un 56 adet farklı veri kümesinden oluşan örnekler üzerinde test edilmiştir. Sonuçlar ABC-OX1'in temel ABC'ye göre daha yüksek bir performansa sahip olduğunu göstermiştir.In a world where competition is increasing rapidly with globalization, customer satisfaction is one of the determining factors in the sustainable success of companies. It is vitally important to create a strong supply infrastructure in order to meet the expectations of the customers. One of the most important processes in the supply chain is route planning. Today, planning on vehicle routing problems has become important especially for companies operating in the logistics and service sector. Routing and optimization solutions in business processes developed to meet increasing demands and reduce costs are very important for companies. Poorly managed route plans pose a problem for companies to serve their customers and cause disruptions in other logistics and service processes. The rapidly developing and changing global competitive environment forces businesses to plan for better process management. In order for this planning to be done correctly, both customer satisfaction should be given importance and operating costs should be reduced. Vehicle routing costs are an important part of transportation and distribution costs within the logistics system. The purpose of the vehicle routing problem is to design the least costly set of routes for a fleet of vehicles. Vehicle routing problem with time window (WRPTW), which is one of the vehicle routing problems, constitutes the study area of many researchers. WRPTW is a vehicle routing problem with a time interval constraint for each customer. In this problem, the delivery vehicle has to serve each customer within a certain time interval. In this study, artificial bee colony (ABC) algorithm and order crossover (OX1) operator were hybridized for the solution of WRPTW and a hybrid method called ABC-OX1 was proposed. In the ABC-OX1 method, the initial solutions were randomly generated and these solutions were improved with the tour developer 3-opt algorithm. Local search operators insertion, swap and divideandswap were used with equal probability in the worker bee phase. In the onlooker bee phase, food diversity was provided with the OX1 operator and the search for quality solutions continued. In the scout phase, new solutions were randomly generated and these solutions were improved with the tour developer 2-opt algorithm. In the ABC-OX1 method, the Bellman algorithm was used for the suitability evaluation of the solutions in the population. ABC-OX1 was tested on samples from Solomon's 56 different datasets. The results showed that ABC-OX1 had a higher performance than basic ABC