The Search for Flexibility in Location and Route Planning: Location Routing Problem Considering Alternative Paths

Year 2025, Volume: 10 Issue: 1, 287 - 315, 28.02.2025

Ergül Kısa Toğrul

https://doi.org/10.25229/beta.1594825

Abstract

Location Routing Problem (LRP) is an important optimization problem in logistics and supply chain management. This problem aims to reduce costs and increase operational efficiency by combining a number of factors affecting distribution and storage processes. The goal of the study is to propose a flexible modeling approach that minimizes the impact of any disruptions in the distribution network, ensuring that operations are affected as little as possible and deliveries are not disrupted. In this context, the Multi Graph Location Routing Problem (MG-LRP) is considered, which takes into account alternative paths between nodes (warehouses and customers) to optimize warehouse locations and vehicle routes in order to minimize the total cost. A Mixed Integer Linear Programming (MILP) model is proposed for the problem. In order to demonstrate the applicability of the mathematical model, two separate data sets were derived and optimum results were obtained. Furthermore, sensitivity analyses are conducted to examine the impact of considering alternative routes on the solutions. It has been concluded that, although considering alternative routes requires more solution time, it can provide flexibility to the model in obtaining optimal solutions and reduce the total cost.

Keywords

Logistics, Cost, Routing, Location Routing Problem, Multi Graph

Ethical Statement

This study, which does not require ethics committee approval and/or legal/special permission, complies with research and publication ethics.

Konum ve Rota Planlamasında Esneklik Arayışı: Alternatif Yolları Dikkate Alan Konum Rotalama Problemi

Abstract

Konum Rotalama Problemi (KRP), lojistik ve tedarik zinciri yönetiminde önemli bir optimizasyon problemidir. Bu problem, dağıtım ve depolama süreçlerini etkileyen bir dizi faktörü birleştirerek, maliyetlerin azaltılması ve operasyonel verimliliğin artırılmasını hedeflemektedir. Çalışmanın amacı, dağıtım ağında meydana gelebilecek herhangi bir aksaklığa karşı operasyonları olabildiğince az etkileyecek ve teslimatları aksatmayacak esnek bir modelleme yaklaşımının önerilmesidir. Bu bağlamda, toplam maliyeti minimize etmek amacıyla depo konumlarını ve araç rotalarını optimize etmeye yönelik, düğümler (depolar ve müşteriler) arasında alternatif yolların hesaba katıldığı, Çoklu Grafikte Konum Rotalama Problemi (ÇG-KRP) ele alınmıştır. Problemin çözümü için Karma Tamsayılı Doğrusal Programlama (KTDP) modeli önerilmiştir. Matematiksel modelin uygulanabilirliğini göstermek amacıyla iki ayrı veri seti türetilmiş ve optimum sonuçlar elde edilmiştir. Ayrıca, dağıtım ağında alternatif yolların dikkate alınmasının çözümler üzerindeki etkisini incelemek amacıyla duyarlılık analizleri gerçekleştirilmiştir. Alternatif yolları dikkate almanın daha fazla çözüm süresi gerektirmesine rağmen optimal çözümler elde edilmesinde modele esneklik kazandırabileceği ve toplam maliyeti azaltabileceği sonucuna varılmıştır.

Keywords

Lojistik, Maliyet, Rotalama, Konum Rotalama Problemi, Çoklu Grafik

Ethical Statement

Etik komite onayı ve/veya yasal/özel izin gerektirmeyen bu çalışma, araştırma ve yayın etiğine uygundur.

References

• Aghalari, A., Salamah, D., Kabli, M., & Marufuzzaman, M. (2023). A two-stage stochastic location–routing problem for electric vehicles fast charging. Computers & Operations Research, 158, 106286. https://doi.org/10.1016/j.cor.2023.106286
• Akpunar, Ö. Ş., & Akpinar, Ş. (2021). A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem. Expert Systems with Applications, 168, 114304. https://doi.org/10.1016/j.eswa.2020.114304
• Albareda-Sambola, M., Fernández, E., & Laporte, G. (2007). Heuristic and lower bound for a stochastic location-routing problem. European Journal of Operational Research, 179(3), 940-955. https://doi.org/10.1016/j.ejor.2005.04.051
• Alinaghian, M., & Naderipour, M. (2016). A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study. Computers & Industrial Engineering, 99, 210-222. https://doi.org/10.1016/j.cie.2016.07.029
• Andelmin, J., & Bartolini, E. (2017). An exact algorithm for the green vehicle routing problem. Transportation Science, 51(4), 1288-1303. https://doi.org/10.1287/trsc.2016.0734
• Andelmin, J., & Bartolini, E. (2019). A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation. Computers & Operations Research, 109, 43-63. https://doi.org/10.1016/j.cor.2019.04.018
• Androutsopoulos, K. N., & Zografos, K. G. (2017). An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations. Transportation Research Part C: Emerging Technologies, 82, 180-209. https://doi.org/10.1016/j.trc.2017.06.013
• Araghi, M. E. T., Tavakkoli-Moghaddam, R., Jolai, F., & Molana, S. M. H. (2021). A green multi-facilities open location-routing problem with planar facility locations and uncertain customer. Journal of Cleaner Production, 282, 124343. https://doi.org/10.1016/j.jclepro.2020.124343
• Baldacci, R., Bodin, L., & Mingozzi, A. (2006). The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem. Computers & Operations Research, 33(9), 2667-2702. https://doi.org/10.1016/j.cor.2005.02.023
• Baldacci, R., Mingozzi, A., & Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing problem. Operations Research, 59(5), 1284-1296. https://doi.org/10.1287/opre.1110.0989
• Bard, J. F., & Nananukul, N. (2009). Heuristics for a multiperiod inventory routing problem with production decisions. Computers & Industrial Engineering, 57(3), 713-723. https://doi.org/10.1016/j.cie.2009.01.020
• Behnke, M., & Kirschstein, T. (2017). The impact of path selection on GHG emissions in city logistics. Transportation Research Part E: Logistics and Transportation Review, 106, 320-336. https://doi.org/10.1016/j.tre.2017.08.011
• Behnke, M., Kirschstein, T., & Bierwirth, C. (2021). A column generation approach for an emission-oriented vehicle routing problem on a multigraph. European Journal of Operational Research, 288(3), 794-809. https://doi.org/10.1016/j.ejor.2020.06.035
• Belenguer, J. M., Benavent, E., Prins, C., Prodhon, C., & Calvo, R. W. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38(6), 931-941. https://doi.org/10.1016/j.cor.2010.09.019
• Bozkaya, B., Salman, F. S., & Telciler, K. (2017). An adaptive and diversified vehicle routing approach to reducing the security risk of cash‐in‐transit operations. Networks, 69(3), 256-269. https://doi.org/10.1002/net.21735
• Breunig, U., Baldacci, R., Hartl, R. F., & Vidal, T. (2019). The electric two-echelon vehicle routing problem. Computers & Operations Research, 103, 198-210. https://doi.org/10.1016/j.cor.2018.11.005
• Caramia, M., & Guerriero, F. (2009). A heuristic approach to long-haul freight transportation with multiple objective functions. Omega, 37(3), 600-614. https://doi.org/10.1016/j.omega.2008.02.001
• Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2), 283-308. https://doi.org/10.1016/j.ejor.2014.08.030
• Ehmke, J. F., Campbell, A. M., & Thomas, B. W. (2016). Vehicle routing to minimize time-dependent emissions in urban areas. European Journal of Operational Research, 251(2), 478-494. https://doi.org/10.1016/j.ejor.2015.11.034
• Ehmke, J. F., Campbell, A. M., & Thomas, B. W. (2018). Optimizing for total costs in vehicle routing in urban areas. Transportation Research Part E: Logistics and Transportation Review, 116, 242-265. https://doi.org/10.1016/j.tre.2018.06.008
• Escobar-Vargas, D., & Crainic, T. G. (2024). Multi-attribute two-echelon location routing: Formulation and dynamic discretization discovery approach. European Journal of Operational Research, 314(1), 66-78. https://doi.org/10.1016/j.ejor.2023.09.031
• Fröhlich, G. E., Doerner, K. F., & Gansterer, M. (2020). Secure and efficient routing on nodes, edges, and arcs of simple‐graphs and of multi‐graphs. Networks, 76(4), 431-450. https://doi.org/10.1002/net.21993
• Gao, S., Wang, Y., Cheng, J., Inazumi, Y., & Tang, Z. (2016). Ant colony optimization with clustering for solving the dynamic location routing problem. Applied Mathematics and Computation, 285, 149-173. https://doi.org/10.1016/j.amc.2016.03.035
• Garaix, T., Artigues, C., Feillet, D., & Josselin, D. (2010). Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operational Research, 204(1), 62-75. https://doi.org/10.1016/j.ejor.2009.10.002
• Heni, H., Renaud, J., & Coelho, L. C. (2018). Time-dependent vehicle routing problem with emission and cost minimization considering dynamic paths. Teknik Rapor. CIRRELT-2018-14. Erişim: 14.05.2024, https://www.cirrelt.ca/documentstravail/cirrelt-2018-14.pdf
• Hou, D. K., Fan, H. M., Lv, Y. C., & Ren, X. X. (2022). Dynamic multicompartment refrigerated vehicle routing problem with multigraph based on real‐time traffic ınformation. Journal of Advanced Transportation, 2022(1), 5538113. https://doi.org/10.1155/2022/5538113
• Huang, Y., Zhao, L., Van Woensel, T., & Gross, J. P. (2017). Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95, 169-195. https://doi.org/10.1016/j.trb.2016.10.013
• Karimpour, A., Setak, M., & Hemmati, A. (2023). Estimating energy consumption and charging duration of electric vehicle in multigraph. Computers & Operations Research, 155, 106216. https://doi.org/10.1016/j.cor.2023.106216
• Lai, D. S., Demirag, O. C., & Leung, J. M. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 86, 32-52. https://doi.org/10.1016/j.tre.2015.12.001
• Laporte, G., Nobert, Y., & Arpin, D. (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 6, 291-310. https://doi.org/10.1007/BF02023807
• Li, Y., Lim, M. K., Tseng, M. L., Lin, Y., Shi, Y., Huang, X., & Xiong, W. (2024). A literature review of green location routing problem: a comprehensive analysis of problems, objectives and methodologies. International Journal of Logistics Research and Applications, 1-20. https://doi.org/10.1080/13675567.2024.2332362
• Liu, X., Qi, M., & Cheng, C. (2017). Green vehicle routing problem with path flexibility. 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, ss. 1037-1041. https://doi.org/10.1109/IEEM.2017.8290050
• Lopes, R. B., Ferreira, C., Santos, B. S., & Barreto, S. (2013). A taxonomical analysis, current methods and objectives on location‐routing problems. International Transactions in Operational Research, 20(6), 795-822. https://doi.org/10.1111/itor.12032
• Mara, S. T. W., Kuo, R. J., & Asih, A. M. S. (2021). Location‐routing problem: a classification of recent research. International Transactions in Operational Research, 28(6), 2941-2983. https://doi.org/10.1111/itor.12950
• Nadizadeh, A., & Nasab, H. H. (2014). Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. European Journal of Operational Research, 238(2), 458-470. https://doi.org/10.1016/j.ejor.2014.04.012
• Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672. https://doi.org/10.1016/j.ejor.2006.04.004
• Patoghi, A., Shakeri, Z., & Setak, M. (2017). A time dependent pollution routing problem in multi-graph. International Journal of Engineering, 30(2), 234-242. https://doi.org/10.5829/idosi.ije.2017.30.02b.00
• Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4), 470-483. https://doi.org/10.1287/trsc.1060.0187
• Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1), 1-17. https://doi.org/10.1016/j.ejor.2014.01.005
• Qian, J., & Eglese, R. (2016). Fuel emissions optimization in vehicle routing problems with time-varying speeds. European Journal of Operational Research, 248(3), 840-848. https://doi.org/10.1016/j.ejor.2015.09.009
• Reinhardt, L. B., Jepsen, M. K., & Pisinger, D. (2016). The edge set cost of the vehicle routing problem with time windows. Transportation Science, 50(2), 694-707. https://doi.org/10.1287/trsc.2015.0620
• Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156. https://doi.org/10.1016/0377-2217(89)90188-4
• Salhi, S., & Nagy, G. (1999). Consistency and robustness in location-routing. Studies in Locational Analysis, (13), 3-19.
• Schneider, M., & Drexl, M. (2017). A survey of the standard location-routing problem. Annals of Operations Research, 259, 389-414. https://doi.org/10.1007/s10479-017-2509-0
• Setak, M., Habibi, M., Karimi, H., & Abedzadeh, M. (2015). A time-dependent vehicle routing problem in multigraph with FIFO property. Journal of Manufacturing Systems, 35, 37-45. https://doi.org/10.1016/j.jmsy.2014.11.016
• Setak, M., Shakeri, Z., & Patoghi, A. (2017). A time dependent pollution routing problem in multi-graph. International Journal of Engineering, 30(2), 234-242. https://doi.org/10.5829/idosi.ije.2017.30.02b.10
• Soriano, A., Vidal, T., Gansterer, M., & Doerner, K. (2020). The vehicle routing problem with arrival time diversification on a multigraph. European Journal of Operational Research, 286(2), 564-575. https://doi.org/10.1016/j.ejor.2020.03.061
• Tadaros, M., & Migdalas, A. (2022). Bi-and multi-objective location routing problems: classification and literature review. Operational Research, 22(5), 4641-4683. https://doi.org/10.1007/s12351-022-00734-w
• Ticha, H. B., Absi, N., Feillet, D., & Quilliot, A. (2017). Empirical analysis for the VRPTW with a multigraph representation for the road network. Computers & Operations Research, 88, 103-116. https://doi.org/10.1016/j.cor.2017.06.024
• Ticha, H.B., Absi, N., Feillet, D., & Quilliot, A. (2018). Vehicle routing problems with road‐network information: State of the art. Networks, 72(3), 393-406. https://doi.org/10.1002/net.21808
• Ticha, H. B., Absi, N., Feillet, D., Quilliot, A., & Woensel, T. V. (2019a). A branch‐and‐price algorithm for the vehicle routing problem with time windows on a road network. Networks, 73(4), 401-417. https://doi.org/10.1002/net.21852
• Ticha, H. B., Absi, N., Feillet, D., & Quilliot, A. (2019b). Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows. Computers & Operations Research, 104, 113-126. https://doi.org/10.1016/j.cor.2018.11.001
• Ticha, H. B., Absi, N., Feillet, D., Quilliot, A., & Woensel, T. V. (2021). The time-dependent vehicle routing problem with time windows and road-network information. Operations Research Forum, 2(1), 4. https://doi.org/10.1007/s43069-020-00049-6
• Tikani, H., & Setak, M. (2019). Efficient solution algorithms for a time-critical reliable transportation problem in multigraph networks with FIFO property. Applied Soft Computing, 74, 504-528. https://doi.org/10.1016/j.asoc.2018.10.029
• Tikani, H., Setak, M., & Demir, E. (2021). A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty. European Journal of Operational Research, 293(2), 703-730. https://doi.org/10.1016/j.ejor.2020.12.020
• Wang, H., & Lee, Y. (2014). Two-stage particle swarm optimization algorithm for the time dependent alternative vehicle routing problem. Journal of Applied & Computational Mathematics, 3(4), 1-9. https://doi.org/10.4172/2168-9679.1000170
• Wang, C., Peng, Z., & Xu, X. (2021). A bi-level programming approach to the location-routing problem with cargo splitting under low-carbon policies. Mathematics, 9(18), 2325. https://doi.org/10.3390/math9182325
• Watson-Gandy, C. D. T., & Dohrn, P. J. (1973). Depot location with van salesmen—a practical approach. Omega, 1(3), 321-329. https://doi.org/10.1016/0305-0483(73)90108-4