Capacitated Multiple Allocation Hub Covering Flow Problem

Nazmi Sener; Orhan Feyzioğlu

doi:10.51354/mjen.809844

EN

Capacitated Multiple Allocation Hub Covering Flow Problem

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 Scientic 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, classication, 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 profitability, 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.

Details

Primary Language

English

Subjects

Engineering

Journal Section

Research Article

Authors

Nazmi Sener ^*
0000-0002-4027-5143
Türkiye

Orhan Feyzioğlu This is me
0000-0002-8919-191X
Türkiye

Publication Date

June 30, 2021

Submission Date

October 15, 2020

Acceptance Date

January 25, 2021

Published in Issue

Year 2021 Volume: 9 Number: 1

DOI

https://doi.org/10.51354/mjen.809844

IZ

https://izlik.org/JA74BG36BB

APA

Sener, N., & Feyzioğlu, O. (2021). Capacitated Multiple Allocation Hub Covering Flow Problem. MANAS Journal of Engineering, 9(1), 72-84. https://doi.org/10.51354/mjen.809844

AMA

1.Sener N, Feyzioğlu O. Capacitated Multiple Allocation Hub Covering Flow Problem. MJEN. 2021;9(1):72-84. doi:10.51354/mjen.809844

Chicago

Sener, Nazmi, and Orhan Feyzioğlu. 2021. “Capacitated Multiple Allocation Hub Covering Flow Problem”. MANAS Journal of Engineering 9 (1): 72-84. https://doi.org/10.51354/mjen.809844.

EndNote

Sener N, Feyzioğlu O (June 1, 2021) Capacitated Multiple Allocation Hub Covering Flow Problem. MANAS Journal of Engineering 9 1 72–84.

IEEE

[1]N. Sener and O. Feyzioğlu, “Capacitated Multiple Allocation Hub Covering Flow Problem”, MJEN, vol. 9, no. 1, pp. 72–84, June 2021, doi: 10.51354/mjen.809844.

ISNAD

Sener, Nazmi - Feyzioğlu, Orhan. “Capacitated Multiple Allocation Hub Covering Flow Problem”. MANAS Journal of Engineering 9/1 (June 1, 2021): 72-84. https://doi.org/10.51354/mjen.809844.

JAMA

1.Sener N, Feyzioğlu O. Capacitated Multiple Allocation Hub Covering Flow Problem. MJEN. 2021;9:72–84.

MLA

Sener, Nazmi, and Orhan Feyzioğlu. “Capacitated Multiple Allocation Hub Covering Flow Problem”. MANAS Journal of Engineering, vol. 9, no. 1, June 2021, pp. 72-84, doi:10.51354/mjen.809844.

Vancouver

1.Nazmi Sener, Orhan Feyzioğlu. Capacitated Multiple Allocation Hub Covering Flow Problem. MJEN. 2021 Jun. 1;9(1):72-84. doi:10.51354/mjen.809844

Manas Journal of Engineering

16155

Abstract

Project Number

Capacitated Multiple Allocation Hub Covering Flow Problem

Abstract

Keywords

Supporting Institution

Project Number

Thanks

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite