Reliable hierarchical multimodal hub location problem: Models and Lagrangian relaxation algorithm

Document Type : Article

Authors

1 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

2 Faculty of Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

Hub facility location problems involve the establishment of strategic hub facilities and allocation of demand nodes to them. Meanwhile, with the emergence of new transport and distribution networks with multi-level structures, the design of such networks has been evolved. The diversity in transportation system has added multimodality to these problems. Considering the strategic nature and long-term implications of decision-making in this field, the decisions shall be of high reliability. The present study is an attempt to consider reliability of communication paths in proportion to the volume of transaction through them while covering all of the above-mentioned issues in hub location problems at the same time. Incorporating hierarchical characteristics of the problem into the model, one can obtained a significantly enhanced model in terms of multimodality and reliability. A Lagrangian solution method was developed considering the strategic level of the problem and the importance of the solution accuracy. The model was then validated in terms of time and quality.

Keywords

Main Subjects

References

References:
1. Farahani, R.Z., Hekmatfar, M., Arabani, A.B., and Nikbakhsh, E. "Hub location problems: A review of models, classification, solution techniques, and applications", Computers & Industrial Engineering, 64(4), pp. 1096-1109 (2013).
2. Teo, C. and Shu, J. "Warehouse-retailer network design problem", Operations Research, 52(3), pp. 396- 408 (2004).
3. Jia, H., Ordonez, F., and Dessouky, M. "A modeling framework for facility location of medical services for large-scale emergencies", IIE Transactions, 39(1), pp. 41-55 (2007).
4. Revelle, C.S., Eiselt, H.A., and Daskin, M.S. "A bibliography for some fundamental problem categories in discrete location science", European Journal of Operational Research, 184(3), pp. 817-848 (2008).
5. Melo, M., Nickel, S., and Saldanha-Da-Gama, F. "Facility location and supply chain management - a review", European Journal of Operational Research, 196(2), pp. 401-412 (2009).
6. Gelareh, S., Nickel, S., and Pisinger, D. "Liner shipping hub network design in a competitive environment", Transportation Research Part E: Logistics and Transportation Review, 46(6), pp. 991-1004 (2010).
7. Gelareh, S. and Nickel, S. "Hub location problems in transportation networks", Transportation Research Part E: Logistics and Transportation Review, 47(6), pp. 1092-1111 (2011).
8. Yaman, H. and Elloumi, S. "Star p-hub center problem and star p-hub median problem with bounded path lengths", Computers and Operations Research, 39(11), pp. 2725-2732 (2012).
9. Korani, E. and Sahraeian, R. "The hierarchical hub covering problem with an innovative allocation procedure covering radiuses", Scientia Iranica, Transaction E, Industrial Engineering, 20(6), pp. 2138-2160 (2013).
10. Alumur, S.A., Yaman, H., and Kara, B.Y. "Hierarchical multimodal hub location problem with timede finite deliveries", Transportation Research Part E: Logistics and Transportation Review, 48(6), pp. 1107- 1120 (2012a).
11. An, Y., Zhang, Y., and Zeng, B. "The reliable huband- spoke design problem: Models and algorithms",Transportation Research Part B: Methodological, 77,pp. 103-122 (2015).
12. Snyder, L.V., Atan, Z., Peng, P., Rong, Y., Schmitt,A.J., and Sinsoysal, B., OR/MS Models for Supply Chain Disruptions: A Review, Available at SSRN 1689882 (2012).
13. Kim, H. and O'Kelly, M.E. "Reliable p-hub location problems in telecommunication networks", Geographical Analysis, 41(3), pp. 283-306 (2009).
14. Zarandi, M.F., Davari, S., and Sisakht, S.H. "An empirical comparison of simulated annealing and iterated local search for the hierarchical single allocation hub median location problem", Scientia Iranica, Transaction E., Industrial Engineering, 22(3), pp. 1203-1217 (2015).
15. Kartal, Z., Hasgul, S., and Ernst, A.T. "Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery", Transportation Research Part E: Logistics and Transportation Review, 108, pp. 141-159 (2017).
16. Roni, M.S., Eksioglu, S.D., Cafferty, K.G., and Jacobson, J.J. "A multi-objective, hub-and-spoke model to design and manage biofuel supply chains", Annals of Operations Research, 249(1-2), pp. 351-380 (2017).
17. Yaman, H. "The hierarchical hub median problem with single assignment", Transportation Research Part B: Methodological, 43(6), pp. 643-658 (2009).
18. Chopra, S. "Designing the distribution network in a supply chain", Transportation Research Part E: Logistics and Transportation Review, 39(2), pp. 123- 140 (2003).
19. Chen, S., Yan, Y., and Song, H. "Optimal logistics hubs locations on the multimodal transportation network", In ICLEM 2010@ sLogistics For Sustained Economic Development: Infrastructure, Information, Integration, ASCE, pp. 2850-2855 (September, 2010).
20. Alumur, S.A., Kara, B.Y., and Karasan, O.E. "Multimodal hub location and hub network design", Omega, 40(6), pp. 927-939 (2012b).
21. Onyemechi, C. "Regional hubs and multimodal logistics efficiency in the 21st century", Journal of Maritime Research, 7(2), pp. 63-72 (2014).
22. SteadieSeifi, M., Dellaert, N., and Van Woensel, T. "A multimodal network  flow problem with product quality preservation, transshipment, and asset management", School of Industrial Engineering and Innovation Sciences, pp. 1-21 (2014).
23. Marianov, V. and Serra, D. "Hierarchical locationallocation models for congested systems", European Journal of Operational Research, 135(1), pp. 195-208 (2001).
24. Sahin, G. and Sural, H. "A review of hierarchical facility location models", Computers & Operations Research, 34(8), pp. 2310-2331 (2007).
25. Hakimi, S.L. "Optimum locations of switching centers and the absolute centers and medians of a graph", Operations Research, 12(3), pp. 450-459 (1964).
26. O'Kelly, M.E. "The location of interacting hub facilities", Transportation Science, 20(2), pp. 92-106 (1986).
27. Campbell, J.F. "Integer programming formulations of discrete hub location problems", European Journal of Operational Research, 72(2), pp. 387-405 (1994).
28. Skorin-Kapov, D., Skorin-Kapov, J., and O'Kelly, M. "Tight linear programming relaxations of uncapacitated p-hub median problems", European Journal of Operational Research, 94(3), pp. 582-593 (1996).
29. Ernst, A.T. and Krishnamoorthy, M. "Efficient algorithms for the uncapacitated single allocation p-hub median problem", Location Science, 4(3), pp. 139-154 (1996).
30. Alumur, S. and Kara, B.Y. "Network hub location problems: the state of the art", European Journal of Operational Research, 190(1), pp. 1-21 (2008).
31. Daskin, M. "Network and discrete location: models, algorithms and applications", Journal of the Operational Research Society, 48(7), pp. 763-764 (1997).
32. Elmastas, S. "Hub location problem for air-ground transportation systems with time restrictions", M.S. Thesis, Bilkent University, Department of Industrial Engineering (2006).
33. Zhong, W., Juan, Z., Zong, F., and Su, H. "Hierarchical hub location model and hybrid algorithm for integration of urban and rural public transport", International Journal of Distributed Sensor Networks, 14(4), pp. 1-14 (2018).
34. Shavarani, S.M., Nejad, M.G., Rismanchian, F., and Izbirak, G. "Application of hierarchical facility location problem for optimization of a drone delivery system: a case study of Amazon prime air in the city of San Francisco", The International Journal of Advanced Manufacturing Technology, 95(9-12), pp. 3141-3153 (2018).
35. Grubesic, T.H., O'Kelly, M.E., and Murray, A.T. "A geographic perspective on commercial Internet survivability", Telematics and Informatics, 20(1), pp. 51-69 (2003).
36. Pastor-Satorras, R., and Vespignani, A., Evolution and Structure of the Internet: A Statistical Physics Approach, New York, Cambridge University Press (2004).
37. Klincewicz, J.G. "Optimization issues in quality of service", In Handbook of Optimization in Telecommunications, Springer US, pp. 435-458 (2006).
38. Skorin-Kapov, D., Skorin-Kapov, J., and Boljuncic, V. "Location problems in telecommunications", In Handbook of Optimization in Telecommunications, M.G.C. Resende and P.M. Pardalos, Eds., New York, Springer, pp. 517-44 (2006).
39. Murray, A.T., and T.H. Grubesic, Eds., Critical Infrastructure: Reliability and Vulnerability, Berlin, Germany, Springer-Verlag (2007).
40. Masoumzadeh, S., Solimanpur, M., and Kamran, M.A. "A multi-objective fuzzy goal programming Phub location and protection model with back-up hubs considering hubs establishment fixed costs", Scientia Iranica, Transactions E, Industrial Engineering, 23(4), pp. 1941-1951 (2016).
41. Shishebori, D., Yousefi Babadi, A., and Noormohammadzadeh, Z. "A Lagrangian relaxation approach to fuzzy robust multi-objective facility location network design problem", Scientia Iranica, 25(3), pp. 1750- 1767 (2018).
42. Tikani, H., Honarvar, M., and Mehrjerdi, Y.Z. "Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry", Computational and Applied Mathematics, 37(3), pp. 3334-3364 (2018).
43. de Sa, E.M., Morabito, R., and de Camargo, R.S. "Benders decomposition applied to a robust multiple allocation incomplete hub location problem", Computers & Operations Research, 89, pp. 31-50 (2018).
44. Zetina, C.A., Contreras, I., Cordeau, J.F., and Nikbakhsh, E. "Robust uncapacitated hub location", Transportation Research Part B: Methodological, 106, pp. 393-410 (2017).
45. Li, Z.C., Huang, H.J., Lam, W.H., and Wong, S.C. "A model for evaluation of transport policies in multimodal networks with road and parking capacity constraints", Journal of Mathematical Modelling and Algorithms, 6(2), pp. 239-257 (2007).
46. Kumar, R.A., Mohapatra, P., Yew, W.K., Benyoucef, L. and Tiwar, M.K. "Route selection and consolidation in international intermodal freight transportation", Applications of Multi-Criteria and Game Theory Approaches, Springer Series in Advanced Manufacturing, pp. 181-194 (2014).
47. Ishfaq, R. and Sox, C.R. "Hub location-allocation in intermodal logistic networks", European Journal of Operational Research, 210(2), pp. 213-230 (2011).
48. Liu, L., Ma, Y., Gao, S., and Luo, C. "System framework and key activities of developing multimodal passenger transport hubs", In Fourth International Conference on Transportation Engineering (October, 2013).
49. Marufuzzaman, M. and Eksioglu, S.D. "Developing a reliable and dynamic intermodal hub and spoke supply chain for biomass", In IIE Annual Conference, Institute of Industrial Engineers-Publisher, Proceedings, pp. 2417-2426 (January, 2014).
50. Dukkanci, O. and Kara, B.Y. "Routing and scheduling decisions in the hierarchical hub location problem", Computers & Operations Research, 85, pp. 45-57 (2017).
51. Correia, I., Nickel, S., and Saldanha-da-Gama, F. "The capacitated single-allocation hub location problem revisited: A note on a classical formulation", European Journal of Operational Research, 207(1), pp. 92-96 (2010).
52. Ernst, A.T. and Krishnamoorthy, M. "Solution algorithms for the capacitated single allocation hub location problem", Annals of Operations Research, 86, pp. 141-159 (1999).
53. Karimi, H. and Setak, M. "Proprietor and customer costs in the incomplete hub location-routing network topology", Applied Mathematical Modelling, 38(3), pp. 1011-1023 (2014).
54. Ebery, J. "Solving large single allocation p-hub problems with two or three hubs", European Journal of Operational Research, 128(2), pp. 447-458 (2001).
55. Ernst, A.T., Jiang, H., Krishnamoorthy, M., Baatar,D., and Judge, C. "Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems", In Unpublished Report, CSIRO Mathematical and Information Sciences, (2005).
56. Fisher, M.L. "The Lagrangian relaxation method for solving integer programming problems", Management Science, 27(1), pp. 1-18 (1981).
57. Aykin, T. "Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem",
European Journal of Operational Research, 79(3), pp. 501-523 (1994).
58. Lee, Y., Lim, B.H., and Park, J.S. "A hub location problem in designing digital data service networks: Lagrangian relaxation approach", Location Science, 4(3), pp. 185-194 (1996).
59. Marin, A. "Uncapacitated Euclidean hub location: Strengthened formulation, new facets and a relax-andcut algorithm", Journal of Global Optimization, 33(3), pp. 393-422 (2005).
60. Contreras, I., Diaz, J.A., and Fernandez, E. "Lagrangean relaxation for the capacitated hub location problem with single assignment", OR Spectrum, 31(3), pp. 483-505 (2009).
61. Mohammadi, M., Torabi, S.A., and Tavakkoli- Moghaddam, R. "Sustainable hub location under mixed uncertainty", Transportation Research Part E: Logistics and Transportation Review, 62, pp. 89-115 (2014).
62. He, Y., Wu, T., Zhang, C., and Liang, Z. "An improved MIP heuristic for the intermodal hub location problem", Omega, 57, pp. 203-211 (2015).
63. Neamatian Monemi, R., Gelareh, S., Hanafi, S., and Maculan, N. "A co-opetitive framework for the hub location problems in transportation networks", Optimization, 66(12), pp. 1-18 (2017).
64. O'kelly, M.E. "A quadratic integer program for the location of interacting hub facilities", European Journal of Operational Research, 32(3), pp. 393-404 (1987).
65. Karimi, H. and Bashiri, M. "Hub covering location problems with different coverage types", Scientia Iranica, 18(6), pp. 1571-1578 (2011).
Scientia Iranica
Volume 27, Issue 3
Transactions on Industrial Engineering (E)
May and June 2020
Pages 1525-1543

Files

History

  • Receive Date: 15 April 2018
  • Revise Date: 26 August 2018
  • Accept Date: 02 October 2018

Share

How to cite

Statistics