Kapasite Kısıtlı Araç Rotalama Problemi için Melez Bir Algoritma

Son yıllarda yaşanan ekonomik daralma sonucunda üretim maliyetlerini azaltmak ve kar marjlarını arttırmak firmalar için önemli bir hedef haline gelmiştir. Özellikle lojistik ve dağıtım şirketlerinin operasyonel işlemleri araç rotalama problemi olarak ele alınarak değerlendirilmesi gerekmektedir. Araç rotalama problemi (ARP) kombinasyonel optimizasyon problemlerindendir ve NP-Zor sınıfında yer almaktadır. ARP’nin temel amacı belirli sayıda müşteriye hizmet vermek koşuluyla minimum mesafeli rotaları oluşturmaktır. Problem kapasite, zaman penceresi, mesafe gibi kısıtlar eklenerek farklı türlere ayrılabilmektedir. Kapasite kısıtlı ARP’nde bir rotada yer alan müşteri talepleri toplamının araç kapasitesini aşmaması gerekmektedir. Literatürde problemin çözümünde kesin, sezgisel ve metasezgisel çözüm yöntemleri mevcut olmakla birlikte bu çalışmada kapasite kısıtlı araç rotalama probleminin çözümü için en yakın komşu algoritması, Yapay Arı Koloni (YAK) algoritması ve 2-opt algoritmalarının birlikte kullanıldığı melez bir yapı önerilmiştir. Önerilen algoritmada başlangıç çözümlerinin yarısı rassal diğer yarısı ise en yakın komşu yöntemi ile oluşturulmuştur. Başlangıç çözümlerine uygulanan YAK algoritması ile elde edilen en iyi çözüme 2-opt algoritması uygulanarak tur maliyetleri azaltılmıştır. Önerilen algoritma literatürde halihazırda var olan test problemleri üzerinde denenmiş ve karşılaştırmalı sonuçları elde edilmiştir. Önerilen algoritmanın en iyi çözümlere yakın değerler ürettiği gözlemlenmiştir. Bu çalışmada sunulan çözüm yöntemi literatüre önemli katkılar sağlayabilir ve çok çeşitli kombinasyonel optimizasyon problemlerinin çözümünde kullanılabilir.

In recent years, due to the economic downturn, reducing production costs and increasing profit margins has become a significant goal for companies. In particular, the operational processes of logistics and distribution companies need to be evaluated as a vehicle routing problem. The vehicle routing problem (VRP) is a combinatorial optimization problem and belongs to the NP-Hard class. The main objective of the VRP is to create routes with minimum distances while serving a certain number of customers. The problem can be divided into different types by adding constraints such as capacity, time window, and distance. In a capacity-constrained VRP, the total number of customer requests on a route must not exceed the vehicle capacity. While exact, heuristic, and metaheuristic solution methods exist in the literature for solving the problem, this study proposes a hybrid structure using the nearest neighbor algorithm, Artificial Bee Colony (ABC) algorithm, and 2-opt algorithms together for solving the capacity-constrained vehicle routing problem. In the proposed algorithm, half of the initial solutions are generated randomly, and the other half using the nearest neighbor method. The tour costs were reduced by applying the 2-opt algorithm to the best solution obtained using the YAK algorithm applied to the initial solutions. The proposed algorithm was tested on existing test problems in the literature, and comparative results were obtained. It was observed that the proposed algorithm produced values ​​close to the best solutions. The solution method presented in this study can make significant contributions to the literature and can be used in solving a wide variety of combinatorial optimization problems.