Kapasiteli araç rotalama problemi için değişken komşuluk iniş ve tavlama benzetimi hibrit sezgisel çözüm yaklaşımı
Variable neighborhood descent and simulated annealing hybrid heuristic solution approach for capacitated vehicle routing problem
Yazar: HÜSNA TOKEL
Danışman: PROF. ERTAN GÜNER
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2024
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Kapasiteli araç rotalama problemi (KARP), bir depodan, sabit kapasiteli araçlar ile farklı coğrafik bölgelerde bulunan müşterilerin önceden belirlenen taleplerinin karşılanması için en uygun rotalar belirlenerek hizmet verildiği, toplam tur uzunluğunun en küçüklenmesinin amaçlandığı araç rotalama problemidir. KARP için farklı meta-sezgisel algoritmaların performanslarının birleştirilerek daha güçlü bir algoritma önerilmesi fikrinden yola çıkılarak, değişken komşu iniş ve tavlama benzetimi algoritması birleştirilerek hibrit bir sezgisel algoritma önerilmiştir. İncelemelerimize göre KARP problemleri için bu iki algoritmanın hibrit bir çözüm yaklaşımı içerisinde birleştirilerek kullanıldığı bir çalışmaya rastlanmamıştır. Bu iki algoritmanın avantajları birleştirilerek, çözümde iyileşme olduğunda aramayı yoğunlaştıran, çözümde iyileşme olmadığında belli oranda kötü çözümleri kabul ederek yerel minimuma takılmayı önleyen ve yeni çözüm kabul edilemediği durumda farklı komşuluk yapıları ile arama yapılarak çözümü çeşitlendiren çözüm yaklaşımı önerilmiştir. 22, 23, 30, 33, 51 ve 76 müşteri boyutlu problem için E veri seti DKİ-TB hibrit çözüm yaklaşımı kullanılarak çözülmüştür. Başlangıç sıcaklığı, nihai sıcaklık, soğutma oranı ve iterasyon sayısı parametrelerinin çözüm değerlerine etkisi incelenmiştir. Her bir veri seti için DKİ-TB hibrit çözüm yaklaşımı 10 kez çalıştırılarak en iyi çözüm değeri dikkate alınmıştır. Bu çözüm değerleri, KARP çözmek için kullanılan CVRP-FA ve ISA-CO algoritmalarının çözüm değerleri ile karşılaştırılmıştır. DKİ-TB hibrit çözüm yaklaşımının, literatürde mevcut olan diğer algoritmalara göre daha iyi sonuç verdiği görülmüştür. Önerilen çözüm yaklaşımının performansını incelemek amacıyla Sakarya ilinde yer alan ekmek üretimi ve dağıtımı hizmeti veren bir fırın için gerçek dünya uygulaması yapılmıştır. Uygulamada 24 ve 30 müşteri boyutlu 2 homojen araç kapasiteli mesafe kısıtlı KARP yer almaktadır. Bu problem, Tlili, Faiz ve Krichen (2014) matematiksel modeli, homojen kapasiteli mesafe kısıtlı KARP' e uyarlanarak çözülmüştür. Çözüm sonuçları DKİ-TB hibrit çözüm yaklaşımı sonuçları ile karşılaştırıldığında, DKİ-TB'nin optimal çözüme yakın sonuçlar verdiği görülmüştür. 50 müşteri boyutludan büyük problemler matematiksel model kullanılarak çözülememektedir, bu durumda DKİ-TB hibrit çözüm yaklaşımı kullanılabilir.

Abstract:
Capacity vehicle routing problem (KARP) is a vehicle routing problem in which the most appropriate routes are determined to meet the predetermined demands of customers in different geographical regions with fixed capacity vehicles from a warehouse, and the aim is to minimize the total tour length. Starting from the idea of proposing a stronger algorithm by combining the performances of different meta-heuristic algorithms for KARP, a hybrid heuristic algorithm has been proposed by combining variable neighbor descent and simulated annealing algorithm. According to our investigations, we have not found any study in which these two algorithms are combined in a hybrid solution approach for KARP problems. By combining the advantages of these two algorithms, a solution approach has been proposed that intensifies the search when there is an improvement in the solution, prevents getting stuck in a local minimum by accepting a certain amount of bad solutions when there is no improvement in the solution, and diversifies the solution by searching with different neighborhood structures when a new solution cannot be accepted. Data set E for 22, 23, 30, 33, 51 and 76 customer size problems was solved using the DKİ-TB hybrid solution approach. The effects of initial temperature, final temperature, cooling rate and number of iteration parameters on the solution values were examined. For each data set, the DKİ-TB hybrid solution approach was run 10 times and the best solution value was taken into account. These solution values were compared with the solution values of CVRP-FA and ISA-CO algorithms used to solve KARP. It has been observed that the DKİ-TB hybrid solution approach gives better results than other algorithms available in the literature. In order to examine the performance of the proposed solution approach, a real-world application was made for a bakery providing bread production and distribution services in Sakarya province. In practice, there is a distance-restricted KARP with a capacity of 2 homogeneous vehicles of 24 and 30 customer sizes. This problem was solved by adapting the mathematical model of Tlili, Faiz, and Krichen (2014) to the homogeneous capacity distance-constrained KARP. When the solution results were compared with the DKİ-TB hybrid solution approach results, it was seen that DKİ-TB gave results close to the optimal solution. Problems larger than 50 customer sizes cannot be solved using mathematical models, in which case the DKİ-TB hybrid solution approach can be used.