Optimal Solution Approaches to the Chance Constrained Mathematical Model of the Stochastic Demand Vehicle Routing Problem with Simulated Annealing Algorithm

Year 2023, , 252 - 270, 30.04.2023

Adem Şehitoğlu , Şakir İşleyen

https://doi.org/10.53433/yyufbed.1174742

Abstract

Supply chain and logistics management have an important place in the global economy, from the production stage of the raw material to the delivery to the end customer. Vehicle routing problems play an important role, providing the distribution network of finished products from a central warehouse to the end customer. Vehicle routing problems are modelled as more complex and stochastic every day to take the most effective decisions. Stochastic vehicle routing problems are probabilistically modelled from the uncertainty of customer demands, time, routes, and service parameters. The stochastic demand vehicle routing problem is one of the problems in which the customer demands are not known beforehand, and the service vehicle is known after it reaches the customer. In this study, a chance-constrained model with stochastic demand was created with the routes, demands and coordinates followed by a bread factory in Van during the distribution of bread to the markets. The factory's route information is compared with the near-optimal problem solution obtained from a meta-heuristic, Annealing Simulation algorithm. According to the results, the routes obtained from the algorithm gave better results than the routes followed by the bakery.

Keywords

Chance constrained, Optimization, Simulated annealing, Vehicle routing with stochastic demand

Stokastik Talepli Araç Rotalama Probleminin Şans Kısıtlı Matematiksel Modeline Tavlama Benzetimi Algoritması ile Optimal Çözüm Yaklaşımları

Abstract

Tedarik zinciri ve lojistik yönetimi ham maddenin üretim aşamasından son müşteriye ulaşmasına kadar küresel ekonomide önemli bir yere sahip olmuştur. Bitmiş ürünlerin merkezi bir depodan son müşteriye kadar dağıtım ağını sağlayan araç rotalama problemleri önemli bir rol oynamaktadır. Araç rotalama problemleri en etkili kararları alabilmek için her geçen gün daha karmaşık ve stokastik olarak modellenmektedir. Stokastik araç rotalama problemleri müşteri taleplerinin, zamanın, yolların ve hizmet gibi parametrelerinin belirsizliğinden olasılıksal olarak modellenmektedir. Stokastik talepli araç rotalama problemi, müşteri taleplerinin önceden bilinmediği hizmet aracının müşteriye ulaştıktan sonra tam olarak bilindiği problemlerdendir. Bu çalışmada, Van’da bir ekmek fabrikasının marketlere ekmek dağıtımı sırasında izlediği rotalar, talepler ve koordinatlar ile stokastik talepli şans kısıtlı bir model oluşturulmuştur. Fabrikanın kendi rota bilgileri, bir meta sezgisel olan Tavlama Benzetimi algoritmasından elde edilen optimale yakın problem çözümü ile karşılaştırılmıştır. Sonuçlara göre algoritmadan elde edilen rotalar fırının izlediği rotalardan daha iyi sonuçlar vermiştir.

Keywords

Optimizasyon, Stokastik talepli araç rotalama, Şans kısıtı, Tavlama benzetimi

References

• Ağayeva, Ç., & Alpaslan Takan, M. (2020). Stokastik talepli kapasite kısıtlı araç rotalama problemine yönelik karşılaştırmalı bir yaklaşım. Bilecik Şeyh Edebali Üniversitesi Fen Bilimleri Dergisi, 7(2), 971-979. doi:10.35193/bseufbd.722677
• Ağpak, K., & Gökçen, H. (2007). A chance-constraint approach to stochastic line balancing problem. European Journal of Operational Research, 180(3), 1098-1115. doi:10.1016/j.ejor.2006.04.042
• Baykoç, Ö. F., & İşleyen, S. K. (2007). Stokastik talepli araç rotalama problemi için şans kısıtı yaklaşımı. Teknoloji, 10(1), 31-39.
• Bertsimas, D. J. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3), 574-585. doi:10.1287/opre.40.3.574
• Breedam, A. V. (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operations Research, 86(3), 480-490. doi:10.1016/0377-2217(94)00064-J
• Cerny, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 41-51. doi:10.1007/bf00940812
• Chiang, W. C., & Russell, R. A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63(1), 3–27. doi:10.1007/BF02601637
• Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. doi:10.1287/opre.12.4.568
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. doi:10.1287/mnsc.6.1.80
• Florio, A. M., Hartl, R. F., Minner, S., & Salazar-González, J. J. (2020). A branch-and-price algorithm for the vehicle routing problem with stochastic demands and probabilistic duration constraints. Transportation Science, 55(1), 122-138. doi:10.1287/trsc.2020.1002
• Garey M. R., & Johnson D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: WH Freeman & Co.
• Gendreau, M., Laporte, G., & Séguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science, 29(2), 143-155. doi:10.1287/trsc.29.2.143
• Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12. doi:10.1016/0377-2217(95)00050-X
• Gendreau, M., & Potvin, J. Y. (2005). Metaheuristics in combinatorial optimization. Annals of Operations Research, 140(1), 189-213. doi:10.1007/s10479-005-3971-7
• Goodson, J. C. (2015). A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands. European Journal of Operational Research, 241(2), 361-369. doi:10.1016/j.ejor.2014.09.031
• Gruler, A., Juan, A. A., Klüter, A., & Rabe, M. (2017). A simulation-optimization approach for the two-echelon location routing problem arising in the creation of urban consolidation centres. Simulation in Produktion and Logistik 2017, 129-138.
• Gutierrez, A., Dieulle, L., Labadie, N., & Velasco, N. (2018). A hybrid metaheuristic algorithm for the vehicle routing problem with stochastic demands. Computers & Operations Research, 99, 135-147. doi:10.1016/j.cor.2018.06.012
• Güden, H., Vakvak, B., Özkan, B. E., Altıparmak, F., & Dengiz, B. (2005). Genel amaçlı arama algoritmaları ile benzetim eniyilemesi: En iyi kanban sayısının bulunması. Endüstri Mühendisliği Dergisi, 16(1), 2-15.
• Gülsün, B., Tuzkaya, G., & Bildik, E. (2008). Reverse logistics network design: A simulated annealing approach. Journal of Engineering and Natural Sciences, 26(1), 68-80.
• Güner, E., & Altıparmak, F. (2003). İki ölçütlü tek makinalı çizelgeleme problemi için sezgisel bir yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 18(3), 27-42.
• Hernandez, F., Gendreau, M., Jabali, O., & Rei, W. (2019). A local branching metaheuristic for the multi-vehicle routing problem with stochastic demands. Journal of Heuristics, 25(2), 215-245. doi:10.1007/s10732-018-9392-y
• Hu, T. Y., Liao, T. Y., & Lu, Y. C. (2003). Study of solution approach for dynamic vehicle routing problems with real-time information. Transportation Research Record, 1857(1), 102-108. doi:10.3141/1857-12
• İlhan, İ. (2020). A population based simulated annealing algorithm for capacitated vehicle routing problem. Turkish Journal of Electrical Engineering & Computer Sciences, 28(3), 1217-1235. doi:10.3906/elk-1902-122
• Ismail, Z., & Irhamah, I. (2008). Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm- tabu search. Journal of Mathematics and Statistics, 4(3), 161-167.
• Jabali, O., Rei, W., Gendreau, M., & Laporte, G. (2014). Partial-route inequalities for the multi-vehicle routing problem with stochastic demands. Discrete Applied Mathematics, 177, 121-136. doi:10.1016/j.dam.2014.05.040
• Kalkancı, Ç. (2014). Organization of emergency response teams in combating winter conditions in natural disaster management. (PhD), Istanbul University, Institute of Science and Technology Istanbul, Turkey.
• Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. doi:10.1126/science.220.4598.671
• Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4(3), 66-74. doi:10.4236/iim.2012.43010
• Laporte, G., Louveaux, F. V., & Van Hamme, L. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 50(3), 415-423. doi:10.1287/opre.50.3.415.7751
• Louveaux, F. V., & Salazar-González, J. J. (2018). Exact approach for the vehicle routing problem with stochastic demands and preventive returns. Transportation Science, 52(6), 1463-1478. doi:10.1287/trsc.2017.0780
• Marinakis, Y., Iordanidou, G. R., & Marinaki, M. (2013). Particle swarm optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing, 13(4), 1693-1704. doi:10.1016/j.asoc.2013.01.007
• Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11), 1886-1898. doi:10.1016/j.cor.2009.06.015
• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087-1092. doi:10.1063/1.1699114
• Novoa, C., & Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 196(2), 509-515. doi:10.1016/j.ejor.2008.03.023
• Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, 421-451. doi:10.1007/BF02023004
• Rabbouch, B., Saadaoui, F., & Mraihi, R. (2020). Empirical-type simulated annealing for solving the capacitated vehicle routing problem. Journal of Experimental & Theoretical Artificial Intelligence, 32(3), 437-452. doi:10.1080/0952813X.2019.1652356
• Salavati-Khoshghalb, M., Gendreau, M., Jabali, O., & Rei, W. (2019). A hybrid recourse policy for the vehicle routing problem with stochastic demands. EURO Journal on Transportation and Logistics, 8(3), 269-298. doi:10.1007/s13676-018-0126-y
• Taha, H.A. (2017). Yöneylem Araştırması. Literatür Yayıncılık, 43, İstanbul. 910.
• Tan, K. C. (2001). A framework of supply chain management literature. European Journal of Purchasing & Supply Management, 7(1), 39-48. doi:10.1016/S0969-7012(00)00020-4
• Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 176(2), 445-454. doi:10.1016/j.amc.2005.09.040
• Teodorovic, D., & Pavkovic, G. (1992). A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand. Transportation Planning and Technology, 16(4), 261-273. doi:10.1080/03081069208717490
• Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia, USA: Society for Industrial and Applied Mathematics.
• Uslu, A., Çetinkaya, C., & İşleyen, S. K. (2017). Vehicle routing problem in post-disaster humanitarian relief logistics: A case study in Ankara. Sigma Journal of Engineering & Natural Sciences, 35(3), 481-499.
• Wang, K., Lan, S., & Zhao, Y. (2017). A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service. Journal of the Operational Research Society, 68(11), 1409-1421. doi:10.1057/s41274-016-0170-7
• Wei, L., Zhang, Z., Zhang, D., & Leung, S. C. H. (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. doi:10.1016/j.ejor.2017.08.035
• Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location routing problems. Computers & Operations Research, 29(10), 1393-1415. doi:10.1016/S0305-0548(01)00038-7
• Yılmaz Yalçıner, A. (2021). Tavlama benzetimi temelli yaklaşım ile kapasite kısıtlı araç rotalama optimizasyonu: Karadeniz bölgesi örneği. Avrupa Bilim ve Teknoloji Dergisi, 22, 239-248. doi:10.31590/ejosat.851540
• Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Computers & Operations Research, 39(7), 1419-1431. doi:10.1016/j.cor.2011.08.013