A Meta-Heuristic Approach for Hub Location-Routing Problem with Capacity and Balancing Decisions

Document Type : Original Article

Authors

1 MSc, Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

2 Associate Professor, Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

Abstract

Hub location-routing problem is a practical subject in the last decades. This study considers a many-to-many hub location-routing problem where the best locations of hubs and tours for each hub are determined with simultaneous pickup and delivery. First, an optimization model is proposed to minimize the total sum of fixed costs of locating hubs, the costs of handling, traveling, assigning, and transportation costs. To find practical solutions, the hubs have constrained capacity, in which single allocations can service every node to the hubs. What is more, the balancing requisites are imposed on the network by allocating the appropriate number of demand nodes to the hubs. Then the problem is solved using GAMS software for small-size instances of the problem. Due to the NP-hard nature of the problem, the proposed optimization model is solved by the Genetic Algorithm (GA) and Imperialist Competitive Algorithm (ICA). For the problem instances, the comparative results indicate that GA has a better performance compared to ICA, and incorporating capacity and balancing considerations can influence the reduction of costs of the investigated network.    

Keywords

Main Subjects

References

  1. Abad, H.K.E., Vahdani, B., Sharifi, M. & Etebari, F. (2018). A bi-objective model for pickup and delivery pollution-routing problem with integration and consolidation shipments in cross-docking system. Journal of Cleaner Production, 193, 784-801.
  2. Abbasi, M., Mokhtari, N., Shahvar, H., & Mahmoudi, A. (2019). Application of variable neighborhood search for solving large-scale many to many hub location routing problems. Journal of Advances in Management Research. 16 No. 5, pp. 683-697.
  3. Ahmadzadeh, E. & Vahdani, B. (2017). A location-inventory-pricing model in a closed loop supply chain network with correlated demands and shortages under a periodic review system. Computers & Chemical Engineering, 101, 148-166.
  4. Alumur S.A, Kara B.Y. (2008). Network hub location problems: the state of the art. European Journal of Operational Research, 190(1), 1–21.
  5. Amin-Naseri, M. R., Yazdekhasti, A., & Salmasnia, A. (2018). Robust bi-objective optimization of uncapacitated single allocation p-hub median problem using a hybrid heuristic algorithm. Neural Computing and Applications, 29(9), 511-532.
  6. Atashpaz-Gargari E. Lucas C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress on Evolutionary Computation, singapore, 4661-4667.
  7. Bashiri, M., Rezanezhad, M., Tavakkoli-Moghaddam, R. & Hasanzadeh, H., (2018). Mathematical modeling for a p-mobile hub location problem in a dynamic environment by a genetic algorithm. Applied Mathematical Modelling, 54, 151-169.
  8. Bütün, C., Petrovic, S., & Muyldermans, L. (2021). The capacitated directed cycle hub location and routing problem under congestion. European Journal of Operational Research, 292(2), 714-734.
  9. de Camargo R.S., de Miranda G. and Løkketangen A., 2013. A new formulation and an exact approach for the many-to-many hub location-routing problem. Applied Mathematical Modelling, 37(12-13), 7465-7480.
  10. Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72(2), 387-405.
  11. Campbell, J. F., Ernst, A.T., Krishnamoorthy, M., Drezner, Z., & Hamacher, H.W. (2002). Hub Location Problems. Facility Location: Applications and Theory. Berlin, Springer. chapter.12, 373-407.
  12. Çetiner, S., Sepil, C., & Süral, H. (2010). Hubbing and postal routing in postal delivery systems. Oper. Res. 181, 109–124.
  13. Cheraghi, I., Heydari, J., & Razmi, J. (2015). The modeling of the multi-product hub location problem with considering financing methods. The Journal of Industrial Management Perspective, 4(4), 55-74. (In Persian)
  14. Correia, I., Nickel, S., & Saldanha-da-Gama, F. (2010a). Single-assignment hub location problems with multiple capacity levels. Transportation Research Part B, 44(8-9), 1047-1066.
  15. Correia, I., Nickel, S., & Saldanha-da-Gama, F. (2010b). The capacitated single-allocation hub location problem revisited: A note on a classical formulation. European Journal of Operational Research, 207(1), 92-96.
  16. Correia, I., Nickel, S., & Saldanha-da-Gama, F. (2011). Hub and spoke network design with single-assignment, capacity decisions and balancing requirements. Applied Mathematical Modelling, 35(10), 4841-4851.
  17. Gholami, H.R., Mehdizadeh, I., & Naderi, B. (2018). Mathematical modeling and Imperialist Competitive Algorithm for the jobshop flow assembly line problem. The Journal of Industrial Management Perspective, 8(1), 93-111. (In Persian)
  18. Holland, J.H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press.
  19. Khezerlou, H.S., Vahdani, B. & Yazdani, M. (2021). Designing a resilient and reliable biomass-to-biofuel supply chain under risk pooling and congestion effects and fleet management. Journal of Cleaner Production, 281,
  20. Khosravi, S., & Jokar, M. (2018). Many to many hub and spoke location routing problem based on the gravity rule. Uncertain Supply Chain Management, 6(4), 393-406.
  21. Lopes, M.C., de Andrade, C.E., de Queiroz, T.A., Resende, M.G. & Miyazawa, F.K. (2016). Heuristics for a hub location‐routing problem. Networks, 68(1), 54-90.
  22. Meier, J.F. (2017). An improved mixed integer program for single allocation hub location problems with stepwise cost function. International Transactions in Operational Research, 24(5), 983-991.
  23. Memarpour, M., Hassannayebi, E., Miab, N.F. & Farjad, A. (2019). Dynamic allocation of promotional budgets based on maximizing customer equity. Operational Research, 1-25.
  24. Mohammadi, M., Dehbari, S., & Vahdani, B. (2014). Design of a bi-objective reliable healthcare network with finite capacity queue under service covering uncertainty. Transportation Research Part E: Logistics and Transportation Review, 72, 15-41.
  25. Mokhtari, N., & Abbasi, M. (2015). Applying VNPSO algorithm to solve the many-to-many hub location-routing problem in a large scale. European Online Journal of Natural and Social Sciences: Proceedings, 3(4 (s)), 647-656.
  26. Nagy G, Salhi, S., (1998). The many-to-many location-routing problem, TOP 6, 261–275.
  27. Niakan, F., Vahdani, B. & Mohammadi, M. (2015). A multi-objective optimization model for hub network design under uncertainty: An inexact rough-interval fuzzy approach. Engineering Optimization, 47(12), 1670-1688.
  28. Nikbakhsh, E., &Zgordi, S. H. (2014). The covering hub edge location problem under disturbance The Journal of Industrial Management Perspective, 4(1), 9-29. (In Persian)
  29. Ratli, M., Urošević, D., El Cadi, A.A., Brimberg, J., Mladenović, N. & Todosijević, R. (2020). An efficient heuristic for a hub location routing problem. Optimization Letters, 1-20.
  30. Rieck, J., Ehrenberg, C., & Zimmermann, J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863-878.
  31. Salimi, F. & Vahdani, B. (2018). Designing a bio-fuel network considering links reliability and risk-pooling effect in bio-refineries. Reliability Engineering & System Safety, 174, 96-107.
  32.  
  33. Shang, X., Yang, K., Jia, B., Gao, Z. & Ji, H. (2021). Heuristic algorithms for the bi-objective hierarchical multimodal hub location problem in cargo delivery systems. Applied Mathematical Modelling, 91, 412-437.
  34. Vahdani, B., Tavakkoli-Moghaddam, R., Zandieh, M. & Razmi, J. (2012). Vehicle routing scheduling using an enhanced hybrid optimization approach. Journal of Intelligent Manufacturing, 23(3), 759-774.
  35. Vahdani, B., Niaki, S.T.A. & Aslanzade, S. (2017a). Production-inventory-routing coordination with capacity and time window constraints for perishable products: Heuristic and meta-heuristic algorithms. Journal of cleaner production, 161, 598-618.
  36. Vahdani, B., Soltani, M., Yazdani, M. & Mousavi, S.M. (2017b). A three level joint location-inventory problem with correlated demand, shortages and periodic review system: Robust meta-heuristics. Computers & Industrial Engineering, 109, 113-129.
  37. Vahdani, B. & Ahmadzadeh, E. (2019a). Designing a realistic ICT closed loop supply chain network with integrated decisions under uncertain demand and lead time. Knowledge-Based Systems, 179, 34-54.
  38. Vahdani, B. & Shahramfard, S. (2019b). A truck scheduling problem at a cross-docking facility with mixed service mode dock doors. Engineering Computations.
  39. Vahdani, B. (2019c). Assignment and scheduling trucks in cross-docking system with energy consumption consideration and trucks queuing. Journal of Cleaner Production, 213, 21-41.
  40. Vahdani, B., Mansour, F., Soltani, M. & Veysmoradi, D. (2019d). Bi-objective optimization for integrating quay crane and internal truck assignment with challenges of trucks sharing. Knowledge-Based Systems, 163, 675-692.
  41. Wasner M. Zäpfel G. 2004. An integrated multi-depot hublocation vehicle routing model for network planning of parcel service. Int. J. Prod. Econ, 90, 403–419.
  42. Winsper, M., & Chli, M. (2013). Decentralized supply chain formation using max‐sum loopy belief propagation. Computational Intelligence, 29(2), 281-309.
  43. Xu, X., Zheng, Y., & Yu, L. (2018). A bi-level optimization model of LRP in collaborative logistics network considered backhaul no-load cost. Soft Computing, 22(16), 5385-5393.
  44. Yang, X., Bostel, N. & Dejax, P. (2019). A MILP model and memetic algorithm for the hub location and routing problem with distinct collection and delivery tours. Computers & Industrial Engineering, 135, 105-119.
  45. Zandieh, M., Amiri, M., Vahdani, B. & Soltani, R. (2009). A robust parameter design for multi-response problems. Journal of computational and applied mathematics, 230(2), 463-476.
  46. Zhalechian M., Tavakkoli-Moghaddam R., Rahimi Y., & Jolai F. (2016). An interactive possibilistic programming approach for a multi-objective hub location problem: Economic and environmental design. Applied Soft Computing, 52, 699-713.

Files

Share

How to cite

Statistics