Capacitated Multiple Allocation Hub Covering Flow Problem

Year 2021, Volume: 9 Issue: 1, 72 - 84, 30.06.2021

Nazmi Sener , Orhan Feyzioğlu

Abstract

The aim of the Capacitated Multiple Allocation Hub Covering Flow Problem is to find the
optimal design for hub-and-spoke networks while taking into account hub opening and demand
routing costs. Every network node has the potential to be a hub and demand from an origin to a
destination must be sent through at least one hub. The network is incomplete in the sense that
the maximum allowed or coverage distance between any opened hub and demand origin/
destination is predefined. It is assumed that there is a cost saving to route demand via hubs due
to consolidation. Another important issue is the consideration of capacity restrictions imposed
on network links and opened hubs. The problem is developed as a mixed-integer linear
optimization problem. According to the results obtained from computational experiments, we
show that taking into account both flow related costs and capacities of network components
concurrently is very important to have a cost effective design.

Keywords

Facility Location, Network Design, Hub-and-Spoke Networks, Capacitated Hub Covering, Multiple Allocation

Supporting Institution

Galatasaray Üniversitesi

Project Number

17.402.007

Thanks

This work has been supported by the Scientic Research Projects Commission of Galatasaray University under grant number 17.402.007.

References

• [1] Campbell J.F., O'Kelly M.E., Twenty-ve years of hub location research, Transportation Science, 46, (2012), pp. 153-169.
• [2] Campbell J.F., Integer programming formulations of discrete hub location problems, European Journal of Operational Research, 72, (1994), pp. 387-405.
• [3] Farahani R.Z., Hekmatfar M., Arabani A.B., Nikbakhsh E., Hub location problems: A review of models, classication, solution techniques, and applications, Computers & Industrial Engineering, 64, (2013), pp. 1096-1109.
• [4] Hakimi S., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12, (1964), pp. 450-459.
• [5] Toh R., Higgins R., The impact of hub and spoke network centralization and route monopoly on domestic airline profitability, Transportation Journal, 24, (1985), pp. 16-27.
• [6] O'Kelly M.E., The location of interacting hub facilities, Transportation Science, 20, (1986b), pp. 92-106.
• [7] O'Kelly M.E., Activity levels at hub facilities in interacting networks, Geographical Analysis, 18, (1986), pp. 343-356.
• [8] Bryan D., O'Kelly M., Hub-and-spoke networks in air transportation: An analytical review. Journal of Regional Science, 39, (1999), pp. 275-295.
• [9] Campbell J., Ernst A., Krishnamoorthy, M., "Hub Location Problem" in Facility Location:Applications and Theory, Springer-Verlag, Berlin, 2002, pp. 373-407.
• [10] Alumur S., Kara B., Network hub location problems: The state of the art, European Journal of Operational Research, 190, (2008), pp. 1-21.
• [11] Contreras I., "Location Science" in Hub Location Problems, Springer International Publishing, Switzerland, 2015, pp. 311-344.
• [12] Yetis Kara B., Tansel B., The single-assignment hub covering problem: Models and linearizations, The Journal of the Operational Research Society, 54, (2003), pp. 59-64.
• [13] Ernst A.T., Jiang H., Krishnamoorthy M., Baatar D., Reformulations and computational results for uncapacitated single and multiple allocation hub covering problems, in: Unpublished Report, CSIRO Mathematical and Information Sciences, 2005.
• [14] Tan P.Z., Yetis Kara B., A hub covering model for cargo delivery systems, Networks, 49, (2007), pp. 28-39.
• [15] Wagner B., Model formulations for hub covering problems, The Journal of the Operational Research Society, 59, (2008), pp. 932-938.
• [16] Ernst A.T., Krishnamoorthy M., Efficient algorithms for the uncapacitated single allocation p-hub median problem, Location Science, 4, (1996), pp. 139-154.
• [17] Weng K., Wang Y., "Evolutionary algorithms for multiple allocation hub set covering problem", in: 2008 IEEE International Conference on Networking, Sensing and Control, 2008. pp. 408-411. Conference Paper in Print Proceedings
• [18] Qu B., Weng K., Path relinking approach for multiple allocation hub maximal covering problem, Computers & Mathematics with Applications, 57, (2009), pp. 1890-1894.
• [19] Alumur Alev S., Yetis Kara B., A hub covering network design problem for cargo applications in Turkey, The Journal of the Operational Research Society, 60, (2009), pp. 1349-1359.
• [20] Calik H., Alumur Alev S., Yetis Kara B., Karasan O.E., A tabu-search based heuristic for the hub covering problem over incomplete hub networks, Computers & Operations Research, 36, (2009), pp. 3088-3096.
• [21] Lowe T.J., Sim T., The hub covering flow problem, The Journal of the Operational Research Society, 64, (2013), pp. 973-981.
• [22] Alumur S., Kara B., Karasan O., Multimodal hub location and hub network design, Omega, 40, (2012), pp. 927-939.
• [23] Ghodratnama A., Tavakkoli-Moghaddam R., Azaron A., A fuzzy possibilistic bi-objective hub covering problem considering production facilities, time horizons and transporter vehicles, The International Journal of Advanced Manufacturing Technology, 66, (2013), pp. 187-206.
• [24] Campbell J.F., Location and allocation for distribution systems with transshipments and transportion economies of scale, Annals of Operations Research 40, (1992), pp. 77-99.
• [25] Aykin T., Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem, European Journal of Operational Research, 79, (1994), pp.501-523.
• [26] Bryan D., Extensions to the hub location problem: Formulations and numerical examples, Geographical Analysis, 30, (1998), pp. 315-330.
• [27] O'Kelly M., Bryan D.,Hub location with flow economies of scale, Transportation Research Part B: Methodological, 32, (1998), pp. 605-616.
• [28] Ernst A., Krishnamoorthy M., Solution algorithms for the capacitated single allocation hub location problem, Annals of Operations Research, 86, (1999), pp. 141-159.
• [29] Ebery J., Krishnamoorthy M., Ernst A., Boland N., The capacitated multiple allocation hub location problem: Formulations and algorithms, European Journal of Operational Research, 120, (2000), pp. 614-631.
• [30] Boland N., Krishnamoorthy M., Ernst A.T., Ebery J.,Preprocessing and cutting for multiple allocation hub location problems, European Journal of Operational Research 155, (2004), pp. 638-653.
• [31] Marin, A., Formulating and solving splittable capacitated multiple allocation hub location problems, Computers & Operations Research, 32, (2005), pp. 3093-3109.
• [32] Sasaki M., Fukushima M., On the hub-and-spoke model with arc capacity constraints, Journal of the Operations Research Society of Japan, 46, (2003), pp. 409-428.
• [33] Carello G., Della Croce F., Ghirardi M., Tadei R., Solving the hub location problem in telecommunication network design: A local search approach, Networks, 44, (2004), pp. 94-105.
• [34] Yetis Kara B., Tansel B., The single-assignment hub covering problem: Models and linearizations, The Journal of the Operational Research Society, 54, (2003), pp. 59-64.
• [35] Yaman H.,Star p-hub median problem with modular arc capacities, Computers & Operations Research, 35, (2008), pp. 3009-3019.
• [36] Rodriguez-Martin I., Salazar-Gonzalez J.J., Solving a capacitated hub location problem, European Journal of Operational Research, 184, (2008), pp. 468-479.
• [37] da Graça Costa M., Captivo M.E., Climaco J., Capacitated single allocation hub location problem-a bi-criteria approach, Computers & Operations Research, 35, (2008), pp. 3671-3695.
• [38] Mohammadi M., Tavakkoli-Moghadam R., Tolouei H., Yousefi M., Solving a hub covering location problem under capacity constraints by a hybrid algorithm, Journal of Applied Operational Research, 2, (2010), pp. 109-116.
• [39] Mohammadi M., Tavakkoli-Moghaddam R., Rostamib H., A multi-objective imperialist competitive algorithm for a capacitated hub covering location problem, International Journal of Industrial Engineering Computations, 2, (2011), pp. 671-688.
• [40] Contreras I., Cordeau J.F., Laporte G., Exact solution of large-scale hub location problems with multiple capacity levels, Transportation Science, 46, (2012), pp. 439-459.
• [41] Sadeghi M., Jolai F., Tavakkoli-Moghaddam R., Rahimi Y., A new stochastic approach for a reliable p-hub covering location problem, Computer and Industrial Engineering, 90, (2015), pp. 371-380.
• [42] Sedehzadeh S., Tavakkoli-Moghaddam R., Jolai F., A new multi-mode and multi-product hub covering problem: A priority m/m/c queue approach, International Journal of Industrial Mathematics, 7, (2015), pp. 139-148.
• [43] Karimia H., Bashiri M., Nickel S., Capacitated single allocation p-hub covering problem in multi-modal network using tabu search, International Journal of Engineering, 29, (2016), pp. 797-808.
• [44] Merakli M., Yaman H., A capacitated hub location problem under hose demand uncertainty, Computers and Operations Research, 88, (2017), pp. 58-70.
• [45] Hoff A., Peiro J., Angel C., Marti R., Heuristics for the capacitated modular hub location problem, Computers & Operations Research, 86, (2017), pp. 94-109.
• [46] Beasley J., Or-library. URL: http://people.brunel.ac.uk/ mastjjb/jeb/info.html, 1990.
• [47] Yetis Kara B., Turkish hub data set. URL:http://www.bilkent.edu.tr/ bkara/dataset.php, 2017.
• [48] McCarl B.A., Meeraus A., van der Eijk P., Bussieck M., Dirkse S., Nelissen F., McCarl Expanded GAMS User Guide, GAMS Release 24.6. GAMS Development Corporation. Washington, DC, USA. URL:https://www.gams.com/24.9/docs/index.html, 2016.