Capacitated Multiple Allocation Hub Covering Flow Problem

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.

PDF

___

[1] Campbell J.F., O’Kelly M.E., Twenty-five 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, classification, 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 Pub- lishing, 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] Wagner B., Model formulations for hub covering problems, The Journal of the Operational Research Society, 59, (2008), pp. 932-938.
[15] Ernst A.T., Krishnamoorthy M., Efficient algorithms for the uncapacitated single allocation p-hub median problem, Location Science, 4, (1996), pp. 139-154.
[16] 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
[17] Qu B., Weng K., Path relinking approach for multiple allocation hub maximal covering problem, Computers & Mathematics with Applications, 57, (2009), pp. 1890- 1894.
[18] 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.
[19] 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.
[20] Lowe T.J., Sim T., The hub covering flow problem, The Journal of the Operational Research Society, 64, (2013), pp. 973-981.
[21] Alumur S., Kara B., Karasan O., Multimodal hub location and hub network design, Omega, 40, (2012), pp. 927-939.
[22] 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.
[23] Aykin T., Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem, European Journal of Operational Research, 79, (1994), pp.501-523.
[24] Bryan D., Extensions to the hub location problem: Formulations and numerical examples, Geographical Analysis, 30, (1998), pp. 315-330.
[25] O’Kelly M., Bryan D.,Hub location with flow economies of scale, Transportation Research Part B: Methodological, 32, (1998), pp. 605-616.
[26] Ernst A., Krishnamoorthy M., Solution algorithms for the capacitated single allocation hub location problem, Annals of Operations Research, 86, (1999), pp. 141-159.
[27] 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.
[28] Marín, A., Formulating and solving splittable capacitated multiple allocation hub location problems, Computers & Operations Research, 32, (2005), pp. 3093-3109.
[29] 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.
[30] 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.
[31] 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.
[32] Yaman H.,Star p-hub median problem with modular arc capacities, Computers & Operations Research, 35, (2008), pp. 3009-3019.
[33] Rodríguez-Martín I., Salazar-González J.J., Solving a capacitated hub location problem, European Journal of Operational Research, 184, (2008), pp. 468-479.
[34] da Graça Costa M., Captivo M.E., Clímaco J., Capacitated single allocation hub location problem-a bi-criteria approach, Computers & Operations Research, 35, (2008), pp. 3671-3695.
[35] 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.
[36] 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.
[37] 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.
[38] 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.
[39] Merakli M., Yaman H., A capacitated hub location problem under hose demand uncertainty, Computers and Operations Research, 88, (2017), pp. 58-70.
[40] Hoff A., Peiró J., Ángel C., Martí R., Heuristics for the capacitated modular hub location problem, Computers & Operations Research, 86, (2017), pp. 94-109.
[41] Demir I., Ergin F. C., Kiraz, B., A New Model for the Multi-Objective Multiple Allocation Hub Network Design and Routing Problem, IEEE Access, 7, (2019), pp. 90678-90689.
[42] Danach K., Gelareh S., Neamatian Monemi R., The capacitated single-allocation p-hub location routing problem: a Lagrangian relaxation and a hyper-heuristic approach, EURO Journal on Transportation and Logistics, 8, (2019), pp.597–631.
[43] Taherkhani G., Alumur S.A., Hosseini M., Benders Decomposition for the Profit Maximizing Capacitated Hub Location Problem with Multiple Demand Classes, Transportation Science, 54:6, (2020), pp 1446-1470.
[44] Butun C., Petrovic S., Muyldermans L., The Capacitated Directed Cycle Hub Location and Routing Problem Under Congestion, European Journal of Operational Research, (2020), In Press.
[45] Beasley J., Or-library. URL: http://people.brunel.ac.uk/ mastjjb/jeb/info.html, 1990.
[46] Yetis Kara B., Turkish hub data set. URL:http://www.bilkent.edu.tr/ bkara/dataset.php, 2017.
[47] McCarl B.A., Meeraus A., van der Eĳk P., Bussieck M., Dirkse S., Nelissen F., McCarl Expanded GAMS User Guide, GAMS Release 24.6. GAMS Development Corporation. Washington, DC, USA.

ISSN: 1694-7398
Yayın Aralığı: Yılda 2 Sayı
Başlangıç: 2001
Yayıncı: KIRGIZİSTAN-TÜRKİYE MANAS ÜNİVERSİTESİ

Arşiv