Research Article
BibTex RIS Cite

Capacitated Multiple Allocation Hub Covering Flow Problem

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

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.

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.
Year 2021, Volume: 9 Issue: 1, 72 - 84, 30.06.2021

Abstract

Project 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.
There are 48 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Research Article
Authors

Nazmi Sener 0000-0002-4027-5143

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

Project Number 17.402.007
Publication Date June 30, 2021
Published in Issue Year 2021 Volume: 9 Issue: 1

Cite

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 Sener N, Feyzioğlu O. Capacitated Multiple Allocation Hub Covering Flow Problem. MJEN. June 2021;9(1):72-84. doi:10.51354/mjen.809844
Chicago Sener, Nazmi, and Orhan Feyzioğlu. “Capacitated Multiple Allocation Hub Covering Flow Problem”. MANAS Journal of Engineering 9, no. 1 (June 2021): 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 N. Sener and O. Feyzioğlu, “Capacitated Multiple Allocation Hub Covering Flow Problem”, MJEN, vol. 9, no. 1, pp. 72–84, 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 2021), 72-84. https://doi.org/10.51354/mjen.809844.
JAMA 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, 2021, pp. 72-84, doi:10.51354/mjen.809844.
Vancouver Sener N, Feyzioğlu O. Capacitated Multiple Allocation Hub Covering Flow Problem. MJEN. 2021;9(1):72-84.

Manas Journal of Engineering 

16155