Hub location problem in round-trip service applications

Kemmar, Omar; Bouamrane, Karim; Gelareh, Shahin

doi:10.1051/ro/2020125

Kemmar, Omar ; Bouamrane, Karim ; Gelareh, Shahin

RAIRO. Operations Research, Tome 55 (2021), pp. S2831-S2858

Résumé

In this paper, we introduce a new hub-and-spoke structure for service networks based on round-trips as practiced by some transport service providers. This problem is a variant of Uncapacitated Hub Location Problem wherein the spoke nodes allocated to a hub node form round-trips (cycles) starting from and ending to the hub node. This problem is motivated by two real-life practices in logistics wherein runaway nodes and runaway connections with their associated economies of scale were foreseen to increase redundancy in the network. We propose a mixed integer linear programming mathematical model with exponential number of constraints. In addition to the separation routines for separating from among exponential constraints, we propose a hyper-heuristic based on reinforcement learning and its comparable counterpart as a variable neighborhood search. Our extensive computational experiments confirm efficiency of the proposed approaches.

MR

DOI : 10.1051/ro/2020125

Classification : 68T20, 90C59, 90C27, 90B80, 90C35, 90C05, 90C11
Keywords: Hub location problem, liner shipping, runaway node, branch-and-cut, hyper-heuristic, variable neighborhood search, reinforcement learning, $$-means

@article{RO_2021__55_S1_S2831_0,
     author = {Kemmar, Omar and Bouamrane, Karim and Gelareh, Shahin},
     title = {Hub location problem in round-trip service applications},
     journal = {RAIRO. Operations Research},
     pages = {S2831--S2858},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020125},
     mrnumber = {4223172},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020125/}
}

TY  - JOUR
AU  - Kemmar, Omar
AU  - Bouamrane, Karim
AU  - Gelareh, Shahin
TI  - Hub location problem in round-trip service applications
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2831
EP  - S2858
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020125/
DO  - 10.1051/ro/2020125
LA  - en
ID  - RO_2021__55_S1_S2831_0
ER  -

%0 Journal Article
%A Kemmar, Omar
%A Bouamrane, Karim
%A Gelareh, Shahin
%T Hub location problem in round-trip service applications
%J RAIRO. Operations Research
%D 2021
%P S2831-S2858
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020125/
%R 10.1051/ro/2020125
%G en
%F RO_2021__55_S1_S2831_0

Kemmar, Omar; Bouamrane, Karim; Gelareh, Shahin. Hub location problem in round-trip service applications. RAIRO. Operations Research, Tome 55 (2021), pp. S2831-S2858. doi: 10.1051/ro/2020125

Bibliographie
Cité par

[1] S. A. Alumur, H. Yaman and B. Y. Kara, Hierarchical multimodal hub location problem with time-definite deliveries. Transp. Res. Part E: Logistics Transp. Rev. 48 (2012) 1107–1120. | DOI

[2] N. Azizi, Managing facility disruption in hub-and-spoke networks: formulations and efficient solution methods. Ann. Oper. Res. 272 (2019) 159–185. | MR | DOI

[3] O. Berman, Z. Drezner and G. O. Wesolowsky, The transfer point location problem. Eur. J. Oper. Res. 179 (2007) 978–989. | MR | Zbl | DOI

[4] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan and R. Qu, Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64 (2013) 1695–1724. | DOI

[5] J. F. Campbell, Location and allocation for distribution systems with transshipments and transportion economies of scale. Ann. Oper. Res. 40 (1992) 77–99. | Zbl | DOI

[6] J. F. Campbell, Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72 (1994) 387–405. | Zbl | DOI

[7] S. R. Cardoso, A. P. Barbosa-Póvoa, S. Relvas and A. Q. Novais, Resilience metrics in the assessment of complex supply-chains performance operating under demand uncertainty. Omega 56 (2015) 53–73. | DOI

[8] G. Carello, F. D. Croce, M. Ghirardi and R. Tadei, Solving the hub location problem in telecommunication network design: a local search approach. Networks 44 (2004) 94–105. | MR | Zbl | DOI

[9] P. Carroll, B. Fortz, M. Labbé and S. Mcgarraghy, Improved formulations for the ring spur assignment problem, in Network Optimization. INOC 2011, edited by J. Pahl, T. Reiners and S. Voß. Vol. 6701 of Lecture Notes in Computer Science. Springer, Berlin-Heidelberg (2011) 24–36. | Zbl | DOI

[10] S. Çetiner, C. Sepil and H. Süral, Hubbing and routing in postal delivery systems. Ann. Oper. Res. 181 (2010) 109–124. | MR | DOI

[11] S. Chaharsooghi, F. Momayezi and N. Ghaffarinasab, An adaptive large neighborhood search heuristic for solving the reliable multiple allocation hub location problem under hub disruptions. Int. J. Ind. Eng. Comput. 8 (2016) 191–202.

[12] I. Contreras, M. Tanash and N. Vidyarthi, Exact and heuristic approaches for the cycle hub location problem. Ann. Oper. Res. 258 (2017) 655–677. | MR | DOI

[13] P. I. Cowling, G. Kendall and E. Soubeiga, A hyperheuristic approach to scheduling a sales summit. In: Practice and Theory of Automated Timetabling III, PATAT ’00. Springer (2001) 176–190. | Zbl | DOI

[14] W. Dai, J. Zhang, X. Sun and S. Wandelt, Hubbi: iterative network design for incomplete hub location problems. Comput. Oper. Res. 104 (2019) 394–414. | MR | DOI

[15] K. Danach, Hyperheuristics in Logistics. Ph.D. thesis, Ecole Centrale de Lille (2016).

[16] K. Danach, S. Gelareh and R. Neamatian Monemi, The capacitated single-allocation $p$ -hub location routing problem: a lagrangian relaxation and a hyper-heuristic approach. EURO J. Transp. Logistics. 8 (2019) 597–631. | DOI

[17] J. Denzinger and M. Fuchs, High performance ATP systems by combining several AI methods. In: Vol. 1 of IJCAI’97. Proceedings of the 15th International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. (1997) 102–107.

[18] J. Ebery, M. Krishnamoorthy, A. Ernst, and N. Boland, The capacitated multiple allocation hub location problem: formulations and algorithms. Eur. J. Oper. Res. 120 (2000) 614–631. | Zbl | DOI

[19] A. T. Ernst and M. Krishnamoorthy, Efficient algorithms for the uncapacitated single allocation $p$ -hub median problem. Location Sci. 4 (1996) 139–154. | Zbl | DOI

[20] S. Gelareh and S. Nickel, Hub location problems in transportation networks. Transp. Res. Part E: Logistics Transp. Rev. 47 (2011) 1092–1111. | DOI

[21] S. Gelareh, N. Maculan, P. Mahey and R. N. Monemi, Hub-and-spoke network design and fleet deployment for string planning of liner shipping. Appl. Math. Model. 37 (2013) 3307–3321. | MR | DOI

[22] S. Gelareh, R. Neamatian Monemic and F. Semet, Capacitated bounded cardinality hub routing problem: model and solution algorithm. Technical report Preprint arXiv:1705.07985 (2017).

[23] Z. He, Farthest-point heuristic based initialization methods for k-modes clustering. CoRR, abs/cs/0610043 (2006).

[24] D. Huang, Z. Liu, X. Fu and P. Blythe, Multimodal transit network design in a hub-and-spoke network framework. Transp. A: Transp. Sci. 14 (2018) 706–35.

[25] B. Jarboui, H. Derbel, S. Hanafi and N. Mladenovic, Variable neighborhood search for location routing. Comput. Oper. Res. 40 (2013) 47–57. | MR | DOI

[26] H. Kim and M. O’Kelly, Reliable p-hub location problems in telecommunication networks. Geogr. Anal. 41 (2009) 283–306. | DOI

[27] M. J. Kuby and R. G. Gray, The hub network design problem with stopovers and feeders: the case of federal express. Transp. Res. Part A: Policy Practice 27 (1993) 1–12.

[28] J. B. Macqueen, Some methods for classification and analysis of multivariate observations. In: Vol. 1 of Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability. University of California Press (1967) 281–297. | MR | Zbl

[29] E. Martins De Sá, I. Contreras and J.-F. Cordeau, Exact and heuristic algorithms for the design of hub networks with multiple lines. Eur. J. Oper. Res. 246 (2015) 186–198. | MR | DOI

[30] E. Martins De Sá, I. Contreras, J.-F. Cordeau, R. Saraiva De Camargo and G. De Miranda, The hub line location problem. Transp. Sci. 49 (2015) 500–518. | DOI

[31] N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl | DOI

[32] M. Mohammadi, R. Tavakkoli-Moghaddam, A. Siadat and Y. Rahimi, A game-based meta-heuristic for a fuzzy bi-objective reliable hub location problem. Eng. App. Artif. Intel. 50 (2016) 1–19. | DOI

[33] R. N. Monemi and S. Gelareh, The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach. Comput. Oper. Res. 88 (2017) 91–102. | MR | DOI

[34] S. Mourelo Ferrandez, T. Harbison, T. Weber, R. Sturges and R. Rich, Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. J. Ind. Eng. Manage. 9 (2016) 374.

[35] M. O’Kelly, Hub facility location with fixed costs. Papers Regional Sci. 71 (1992) 293–306. | DOI

[36] M. O’Kelly, A clustering approach to the planar hub location problem. Ann. Oper. Res. 40 (1993) 339–353. | Zbl | DOI

[37] M. P. Pérez, F. A. Rodíguez and J. M. Moreno-Vega, A hybrid VNS-path relinking for the $p$ -hub median problem. IMA J. Manage. Math. 18 (2007) 157–171. | MR | Zbl

[38] J. Pérez-Ortega, N. A.-O. Nelva, A. Vega-Villalobos, R. Pazos-Rangel, C. Zavala-Díaz and A. Martínez-Rebollar, The $K$ -means algorithm evolution, edited by K. Sud, P. Erdogmus and S. Kadry. In: Introduction to Data Science and Machine Learning. IntechOpen, Rijeka (2020). | DOI

[39] R. Rahmaniani, G. Rahmaniani and A. Jabbarzadeh, Variable neighborhood search based evolutionary algorithm and several approximations for balanced location-allocation design problem. Int. J. Adv. Manuf. Technol. 72 (2014) 145–159. | DOI

[40] I. Rodriguez-Martin, J. J. Salazar González and H. Yaman, A branch-and-cut algorithm for the hub location and routing problem. Comput. Oper. Res. 50 (2014) 161–174. | MR | DOI

[41] I. Rodriguez-Martin, J. J. Salazar González and H. Yaman, The ring/ $k$ -rings network design problem: model and branch-and-cut algorithm. Networks 68 (2016) 130–140. | MR | DOI

[42] B. Rostami, N. Kämmerling, C. Buchheim and U. Clausen, Reliable single allocation hub location problem under hub breakdowns. Comput. Oper. Res. 96 (2018) 15–29. | MR | DOI

[43] E. Serper and S. A. Alumur, The design of capacitated intermodal hub networks with different vehicle types. Transp. Res. Part B: Methodol. 86 (2016) 51–65. | DOI

[44] D. Skorin-Kapov, J. Skorin-Kapov and M. O’Kelly, Tight linear programming relaxations of uncapacitated $p$ -hub median problems. Eur. J. Oper. Res. 94 (1996) 582–593. | Zbl | DOI

[45] R. Todosijević, D. Urošević, N. Mladenović and S. Hanafi, A general variable neighborhood search for solving the uncapacitated $r$ -allocation $p$ -hub median problem. Optim. Lett. 11(2017) 1109-1121. | MR | DOI

[46] UNCTAD, Review of maritime transport. In: United Nations Conference on Trade and Development, New York and Geneva (2018).

[47] M. Yahyaei, M. Bashiri and Y. Garmeyi, Multicriteria logistic hub location by network segmentation under criteria weights uncertainty. Int. J. Eng. Trans. B: App. 27 (2014) 1205–1214.

[48] M. Yahyaei, M. Bashiri and M. Randall, A model for a reliable single allocation hub network design under massive disruption. Appl. Soft Comput. 82 (2019) 105561. | DOI

[49] H. Yaman, B. Y. Kara and B. Tansel, The latest arrival hub location problem for cargo delivery systems with stopovers. Transp. Res. Part B: Methodol. 41 (2007) 906–919. | DOI

[50] K. Yang, Y. Liu and G. Yang, An improved hybrid particle swarm optimization algorithm for fuzzy $p$ -hub center problem. Comput. Ind. Eng. 64 (2013) 133–142. | DOI

[51] M. Zhalechian, S. A. Torabi and M. Mohammadi, Hub-and-spoke network design under operational and disruption risks. Transp. Res. Part E: Logistics Transp. Rev. 109 (2018) 20–43. | DOI

[52] W. Zhong, Z. Juan, F. Zong and H. Su, Hierarchical hub location model and hybrid algorithm for integration of urban and rural public transport. Int. J. Distr. Sensor Netw. 14 (2018).

Cité par Sources :