Araç Rotalama Probleminin Çözümü İçin Çok Amaçlı Genel Değişken Komşuluk Arama Metasezgisel Yaklaşımı

Year 2022, Issue: 34, 428 - 432, 31.03.2022

Hacer Yumurtacı Aydoğmuş , Yücel Özcan

https://doi.org/10.31590/ejosat.1082592

Abstract

İşletmeler açısından rotalama problemleri büyük önem taşıyan ve çözümü için çeşitli yöntemler geliştirilmeye çalışılan problemlerden birisidir. Günümüzde sera gazı salınımının düşürülmesine yönelik sürdürülebilirlik çerçevesinde çeşitli önlemler alınmaktadır. Araç rotalama problemleri de sera gazı salınımının yaklaşık yüzde yirmilik kısmını oluşturan ulaştırma sektörü içinde karşılaşılabilen problemlerdendir. Bu açıdan araç rotalama problemlerinde genellikle minimum mesafe, minimum araç sayısı, minimum karbon emisyonu gibi amaç fonksiyonları kullanılmaktadır. 1997 yılında ilk olarak Mladenovic ve Hansen tarafından geliştirilen ve sistematik olarak komşuluk değişimleri fikrini kullanan Değişken Komşuluk Arama (DKA) metasezgiseli farklı çeşitlere sahiptir. Bu çeşitlerden birisi de Genel Değişken Komşuluk Arama (GDKA) yapısıdır. Bu çalışmada çok amaçlı araç rotalama problemine uygulamak üzere geliştirilen ve değişken komşuluk arama metasezgisel yaklaşımı temelli Çok Amaçlı Genel Değişken Komşuluk Arama (ÇAGDKA) yönteminin gerçek hayat probleminde uygulanarak mevcut rotalar üzerinde iyileştirme yapılması amaçlanmıştır. ÇAGDKA (Yumurtacı Aydoğmuş, 2011) yaklaşımı, Geiger’in 2004 yılında ilk defa ortaya attığı çok amaçlı değişken komşuluk arama (ÇADKA) yönteminden yola çıkarak geliştirilmiştir. Çalışmada ÇAGDKA yaklaşımının mevcut rotadan daha iyi sonuç verdiği ve farklı iki senaryo ile elde edilen sonuçlarla da karşılaştırıldığında da daha iyi sonuçlar sunduğu görülmüştür.

Keywords

Çok Amaçlı Genel Değişken Komşuluk Arama, Meta Sezgisel, Araç Rotalama

Multi Objective General Variable Neighborhood Search Metaheuristic for Solving Vehicle Routing Problem

Abstract

Routing problems are one of the problem types that are of great importance for businesses and various methods are tried to be developed for their solution. Today, different measures are taken within the framework of sustainability to reduce greenhouse gas emissions. Vehicle routing problems are also one of the problems that can be encountered in the transportation sector, which accounts for about twenty percent of greenhouse gas emissions. In this respect, objective functions such as minimum distance, minimum number of vehicles, minimum carbon emission are generally used in vehicle routing problems. Variable Neighborhood Search (VNS), which was first developed by Mladenovic and Hansen in 1997 and systematically uses the idea of neighborhood changes, has different varieties of metaheuristics. One of these types is the General Variable Neighborhood Search (GVNS) structure. In this study, it is aimed to improve the existing routes by applying the variable neighborhood search metaheuristic approach-based Multi-Objective General Variable Neighborhood Search (MOGVNS) method, which was developed to apply to the multi-objective vehicle routing problem, in a real life problem. The MOGVNS (Yumurtacı Aydoğmuş, 2011) approach was developed based on the Multi-Objective Variable Neighborhood Search (MOVNS) method, which was first introduced by Geiger in 2004. In the study, it was seen that the MOGVNS approach gave better results than the current route and provided better results when the results obtained with the two different scenarios were compared.

Keywords

Multi-Objective General Variable Neighborhood Search, Vehicle Routing, Metaheuristic

References

• Nagarajan, V., & Ravi, R. (2012). Approximation algorithms for distance constrained vehicle routing problems. Networks, 59(2), 209-214.
• Pradenas, L., Oportus, B., & Parada, V. (2013). Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling. Expert Systems with Applications, 40(8), 2985-2991.
• Kancharla, S. R., & Ramadurai, G. (2018). Incorporating driving cycle based fuel consumption estimation in green vehicle routing problems. Sustainable cities and society, 40, 214-221.
• Bouyahyiouy, K., & Bellabdaoui, A. (2021). A mixed-integer linear programming model for the selective full-truckload multi-depot vehicle routing problem with time windows. Decision Science Letters, 10(4), 471-486.
• Kuo, Y., & Wang, C. C. (2012). A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, 39(8), 6949-6954.
• Laporte, G., 2009, Fifty years of vehicle routing. Transportation Science. Vol.43, No.4, 408-416. Publisher:INFORMS.
• Jozefowiez, N., Semet, F., & Talbi, E. G. (2008). From single-objective to multi-objective vehicle routing problems: Motivations, case studies, and methods. In The vehicle routing problem: Latest advances and new challenges (pp. 445-471). Springer, Boston, MA.
• Kuo, Y. (2010). Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59(1), 157-165.
• Lin, S. W., Vincent, F. Y., & Lu, C. C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
• Wei, L., Zhang, Z., Zhang, D., & Leung, S. C. (2018). A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European journal of operational research, 265(3), 843-859.
• Bernal, J., Escobar, J. W., Paz, J. C., Linfati, R., & Gatica, G. (2018). A probabilistic granular tabu search for the distance constrained capacitated vehicle routing problem. International Journal of Industrial and Systems Engineering, 29(4), 453-477.
• Caballero-Morales, S. O., Martínez-Flores, J. L., & Sánchez-Partida, D. (2018). An evolutive tabu-search metaheuristic approach for the capacitated vehicle routing problem. In New Perspectives on Applied Industrial Tools and Techniques (pp. 477-495). Springer, Cham.
• Alba, E., & Dorronsoro, B. (2004). Solving the vehicle routing problem by using cellular genetic algorithms. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 11-20). Springer, Berlin, Heidelberg.
• Marinakis, Y., & Migdalas, A. (2007). Annotated bibliography in vehicle routing. Operational Research, 7(1), 27-46.
• Azad, T., & Hasin, M. A. A. (2019). Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems and Management, 32(1), 132-146.
• Yumurtacı Aydoğmuş, H. (2011). Değişken komşuluk arama sezgisel yaklaşımı ve tedarik zinciri yönetiminde bir uygulama. Doktora Tezi. İstanbul Üniversitesi, Endüstri Mühendisliği Ana Bilim Dalı.