Integrated Mathematical Model for Two-Echelon Location-Routing Problem and Application in a Public Institution

Yıl 2022, , 523 - 556, 28.07.2022

Erkan Aslantaş , Yasemin Yavuz

https://doi.org/10.35408/comuybd.940324

Öz

The location-routing problem (LRP) is among the most important optimization problems related to logistics planning decisions at the strategic and tactical levels. In this paper, we have introduced an original two-echelon LRP in line with the characteristics of a real transportation network encountered in a public institution in Turkey. The aim of the study is to design a transportation network to minimize transportation costs through an integrated solution approach that simultaneously considers location and routing decisions in the two-echelon LRP. For this purpose, we have developed an integer linear programming model for integrated solution of the two-echelon LRP. The variable closed vehicle routing has been defined in accordance with the characteristics of the addressed problem. The proposed model determines both the number and location of transfer centers (TC) to be included into the transportation network, assigns the demand centers to these TCs, and generates variable closed vehicle routes for each one of them. In the model, the total distance traveled along the transportation network is minimized as the primary objective, and the total number of used vehicles as the secondary one. The developed model has been implemented into the transportation problem of the public institution and the transportation network generated by the solution of the model has been compared with the existing network. The obtained results show that significant improvements can be achieved through proposed transportation network design.

Anahtar Kelimeler

Two-Echelon Location-Routing Problem, Facility Location Problem, Vehicle Routing Problem, Mathematical Model.

İki Kademeli Lokasyon-Rotalama Problemi İçin Bütünleşik Matematiksel Model ve Kamuda Bir Uygulama

Öz

Lokasyon-rotalama problemi (LRP), stratejik ve taktik düzeydeki lojistik planlama kararlarına ilişkin en önemli optimizasyon problemlerinin başında gelmektedir. Bu çalışmada, ülkemizdeki bir kamu kurumunda karşılaşılan gerçek bir taşıma ağının özelliklerinden yola çıkılarak iki kademeli özgün bir LRP tanımlanmıştır. Çalışmanın amacı, iki kademeli LRP’de lokasyon ve rotalama kararlarını eş zamanlı olarak ele alan bütünleşik bir çözüm yaklaşımı aracılığıyla taşıma maliyetlerini en aza indirmeye yönelik bir taşıma ağının tasarlanmasıdır. Bu amaç doğrultusunda, iki kademeli LRP’nin bütünleşik bir şekilde çözümü için tamsayılı bir doğrusal programlama modeli geliştirilmiştir. Çalışmada incelenen problemin özelliklerine uygun olarak değişken kapalı uçlu araç rotalama tanımı yapılmıştır. Önerilen modelde, taşıma ağında yer alacak aktarma merkezi (AKM) sayısı ve lokasyonlarının belirlenmesine, talep merkezlerinin bu AKM’lere atanmasına ve her bir AKM için değişken kapalı uçlu araç rotalarının oluşturulmasına çalışılmıştır. Modelde birinci öncelikli amaç olarak taşıma ağı boyunca katedilen toplam mesafenin, ikinci öncelikli amaç olarak ise kullanılan toplam araç sayısının minimize edilmesi hedeflenmiştir. Geliştirilen model, kamu kurumunda karşılaşılan taşıma problemine uygulanmış ve modelin çözümü sonucunda oluşturulan taşıma ağı mevcut ağ ile karşılaştırılmıştır. Elde edilen çözüm sonuçları, önerilen taşıma ağı yoluyla sistem performansında önemli düzeyde iyileştirmelerin sağlanabileceğini göstermiştir.

Anahtar Kelimeler

İki Kademeli Lokasyon-Rotalama Problemi, Tesis Lokasyon Problemi, Araç Rotalama Problemi, Matematiksel Model.

Kaynakça

• Abbassi, A., Kharraja, S., El Hilali Alaoui, A., Boukachour, J. ve Paras, D. (2021). Multi-Objective Two-Echelon Location-Distribution of Non-Medical Products. International Journal of Production Research, 59(17), 5284-5300.
• Ahmadi-Javid, A., Amiri, E. ve Meskar, M. (2018). A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm. European Journal of Operational Research, 271(3), 866-881.
• Albareda-Sambola, M., Dı́az, J. A. ve Fernández, E. (2005). A Compact Model and Tight Bounds for a Combined Location-Routing Problem. Computers & Operations Research, 32(3), 407-428.
• Bala, K., Brcanov, D. ve Gvozdenović, N. (2017). Two-Echelon Location Routing Synchronized with Production Schedules and Time Windows. Central European Journal of Operations Research, 25(3), 525-543.
• Bektas, T. (2006). The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures. Omega, 34(3), 209-219.
• Bellmore, M. ve Nemhauser, G. L. (1968). The Traveling Salesman Problem: A Survey. Operations Research, 16(3), 538-558.
• Berger, R. T., Coullard, C. R. ve Daskin, M. S. (2007). Location-Routing Problems with Distance Constraints. Transportation Science, 41(1), 29-43.
• Cao, J. X., Wang, X. ve Gao, J. (2021). A Two-Echelon Location-Routing Problem for Biomass Logistics Systems. Biosystems Engineering, 202, 106-118.
• Chan, Y. ve Baker, S. F. (2005). The Multiple Depot, Multiple Traveling Salesmen Facility-Location Problem: Vehicle Range, Service Frequency, and Heuristic Implementations. Mathematical and Computer Modelling, 41(8-9), 1035-1053.
• Cheng, C., Zhu, R., Costa, A. M., Thompson, R. G. ve Huang, X. (2021). Multi-Period Two-Echelon Location Routing Problem for Disaster Waste Clean-up. Transportmetrica A: Transport Science, doi: 10.1080/23249935.2021.1916644.
• Chopra, S. ve Meindl, P. (2013). Supply Chain Management: Strategy, Planning, and Operation. 5th Ed., USA: Pearson Education, Inc.
• Cuda, R., Guastaroba, G. ve Speranza, M. G. (2015). A Survey on Two-Echelon Routing Problems. Computers & Operations Research, 55, 185-199.
• Current, J., Daskin, M. ve Schilling, D. (2002). Discrete Network Location Models. Z. Drezner ve H. W. Hamacher (Ed.), Facility Location: Applications and Theory içinde, (s. 85-122). Heidelberg: Springer-Verlag.
• Çetiner, S., Sepil, C. ve Süral, H. (2010). Hubbing and Routing in Postal Delivery Systems. Annals of Operations Research, 181(1), 109-124.
• Drexl, M. ve Schneider, M. (2015). A Survey of Variants and Extensions of the Location-Routing Problem. European Journal of Operational Research, 241(2), 283-308.
• Fallahtafti, A., Ardjmand, E., Young li, W. A. ve Weckman, G. R. (2021). A Multi-Objective Two-Echelon Location-Routing Problem for Cash Logistics: A Metaheuristic Approach. Applied Soft Computing, 111, 107685.
• Ghiani, G., Laporte, G. ve Musmanno, R. (2013). Introduction to Logistics Systems Management (2nd Ed.). UK: John Wiley & Sons, Ltd.
• Hines, P. ve Taylor, D. (2000). Going Lean. UK: Lean Enterprise Research Centre, Cardiff Business School.
• Jacobsen, S. K. ve Madsen, O. B. G. (1980). A Comparative Study of Heuristics for a Two-Level Routing-Location Problem. European Journal of Operational Research, 5(6), 378-387.
• Jünger, M., Reinelt, G. ve Rinaldi, G. (1995). The Traveling Salesman Problem. M. O. Ball, T. L. Magnanti, C. L. Monma ve G. L. Nemhauser (Ed.), Handbooks in Operations Research and Management Science: Network Models içinde, Vol. 7, (s. 225-230). Elsevier Science.
• Karaoglan, I., Altiparmak, F., Kara, I. ve Dengiz, B. (2012). The Location-Routing Problem with Simultaneous Pickup and Delivery: Formulations and a Heuristic Approach. Omega, 40(4), 465-477.
• KGM (2019), Karayolları Genel Müdürlüğü, İller Arası Mesafe Cetveli (01.01.2019), https://www.kgm.gov.tr/Sayfalar/KGM/SiteTr/Root/Uzakliklar.aspx, (Erişim T.: 22.11.2019).
• Laporte, G. (1992). The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, 59(3), 345-358.
• Laporte, G. ve Nobert, Y. (1981). An Exact Algorithm for Minimizing Routing and Operating Costs in Depot Location. European Journal of Operational Research, 6(2), 224-226.
• Laporte, G., Nobert, Y. ve Arpin, D. (1986). An Exact Algorithm for Solving a Capacitated Location-Routing Problem. Annals of Operations Research, 6(9), 291-310.
• Laporte, G., Nobert, Y. ve Pelletier, P. (1983). Hamiltonian Location Problems. European Journal of Operational Research, 12(1), 82-89.
• Lopes, R. B., Ferreira, C., Santos, B. S. ve Barreto, S. (2013). A Taxonomical Analysis, Current Methods and Objectives on Location-Routing Problems. International Transactions in Operational Research, 20(6), 795-822.
• Madsen, O. B. G. (1983). Methods for Solving Combined Two Level Location-Routing Problems of Realistic Dimensions. European Journal of Operational Research, 12(3), 295-301.
• Mara, S. T. W., Kuo, R. J. ve Asih, A. M. S. (2021). Location-Routing Problem: A Classification of Recent Research. International Transactions in Operational Research, 28(6), 2941-2983.
• Maranzana, F. E. (1964). On the Location of Supply Points to Minimize Transport Costs. Operational Research Quarterly, 15(3), 261-270.
• Mirhedayatian, S. M., Crainic, T. G., Guajardo, M. ve Wallace, S. W. (2021). A Two-Echelon Location-Routing Problem with Synchronisation. Journal of the Operational Research Society, 72(1), 145-160.
• Nadizadeh, A. ve Hosseini Nasab, H. (2019). Modelling and Solving the Capacitated Location-Routing Problem with Simultaneous Pickup and Delivery Demands. International Journal of Transportation Engineering, 6(3), 217-235.
• Nagy, G. ve Salhi, S. (2007). Location-Routing: Issues, Models and Methods. European Journal of Operational Research, 177(2), 649-672.
• Pichka, K., Bajgiran, A. H., Petering, M. E. H., Jang, J. ve Yue, X. (2018). The Two Echelon Open Location Routing Problem: Mathematical Model and Hybrid Heuristic. Computers & Industrial Engineering, 121, 97-112.
• Pitakaso, R., Sethanan, K. ve Theeraviriya, C. (2020). Variable Neighborhood Strategy Adaptive Search for Solving Green 2-Echelon Location Routing Problem. Computers and Electronics in Agriculture, 173, 105406.
• Prodhon, C. ve Prins, C. (2014). A Survey of Recent Research on Location-Routing Problems. European Journal of Operational Research, 238(1), 1-17.
• Rahmani, Y., Ramdane Cherif-Khettaf, W. ve Oulamara, A. (2016). The Two-Echelon Multi-Products Location-Routing Problem with Pickup and Delivery: Formulation and Heuristic Approaches. International Journal of Production Research, 54(4), 999-1019.
• Salhi, S. ve Rand, G. K. (1989). The Effect of Ignoring Routes When Locating Depots. European Journal of Operational Research, 39(2), 150-156.
• Schneider, M. ve Drexl, M. (2017). A Survey of the Standard Location-Routing Problem. Annals of Operations Research, 259(1), 389-414.
• Ting, C. J. ve Chen, C. H. (2013). A Multiple Ant Colony Optimization Algorithm for the Capacitated Location Routing Problem. International Journal of Production Economics, 141(1), 34-44.
• Toth, P. ve Vigo, D. (2002). An Overview of Vehicle Routing Problems. P. Toth ve D. Vigo (Ed.), The Vehicle Routing Problem içinde, SIAM Monographs on Discrete Mathematics and Applications, (s. 1-26). Philadelphia: Society for Industrial and Applied Mathematics.
• Tuzun, D. ve Burke, L. I. (1999). A Two-Phase Tabu Search Approach to the Location Routing Problem. European Journal of Operational Research, 116(1), 87-99.
• Vidović, M., Ratković, B., Bjelić, N. ve Popović, D. (2016). A Two-Echelon Location-Routing Model for Designing Recycling Logistics Networks with Profit: MILP and Heuristic Approach. Expert Systems with Applications, 51, 34-48.
• Von Boventer, E. (1961). The Relationship between Transportation Costs and Location Rent in Transportation Problems. Journal of Regional Science, 3(2), 27-40.
• Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M. ve Wang, Y. (2018). Two-Echelon Location-Routing Optimization with Time Windows Based on Customer Clustering. Expert Systems with Applications, 104, 244-260.
• Wu, T. H., Low, C. ve Bai, J. W. (2002). Heuristic Solutions to Multi-Depot Location-Routing Problems. Computers & Operations Research, 29(10), 1393-1415.
• Yücel, A. (2016). Mesafe Kısıtlı Çok Yönlü Kümelenmiş Açık Araç Rotalama Probleminin Genetik Algoritma ile Çözümü ve Bir Uygulama, Doktora Tezi. İstanbul: İstanbul Üniversitesi Sosyal Bilimler Enstitüsü.
• Zhao, Q., Wang, W. ve De Souza, R. (2018). A Heterogeneous Fleet Two-Echelon Capacitated Location-Routing Model for Joint Delivery Arising in City Logistics. International Journal of Production Research, 56(15), 5062-5080.