Benders decomposition applied to profit maximizing hub location problem with incomplete hub network. (English) Zbl 1511.90287
Summary: This paper addresses a profit maximizing multiple allocation hub network design problem, which is a hub location problem with incomplete hub network, aiming to determine the quantity and location of the hubs, allocate demand nodes to these hubs, establish the network topology, and route the demand flows to satisfy the demands between the origin and destination pairs that were selected to be served in order to obtain the highest profit. This problem also considers the multiple allocation strategy, does not allow direct connections between non-hub nodes, does not impose capacity constraints, and assumes that there are fixed costs involved in installing hubs and installing hub arcs. A new formulation for the problem is presented and it is proved that this formulation is stronger than another one in the literature, which models the same problem. Several versions of the Benders decomposition method, combining the generation of Pareto-optimal cuts, multiple cuts strategies, and Benders branch-and-cut scheme, are proposed and analyzed through extensive computational experiments on benchmark instances. The best-proposed Benders decomposition versions were compared with the CPLEX solver, with and without the activation of its Benders decomposition algorithm. The results showed that these algorithms perform much better than the solver versions. The proposed Benders decomposition approach can solve benchmark instances with up to 150 nodes.
MSC:
| 90B80 | Discrete location and assignment |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
hub network design problem; profit maximization; incomplete hub network; hub location problem; Benders decomposition method; branch-and-cut algorithmReferences:
| [1] | Adulyasak, Y.; Cordeau, J.-F.; Jans, R., Benders decomposition for production routing under demand uncertainty, Oper. Res., 63, 851-867 (2015) · Zbl 1329.90018 |
| [2] | Alibeyg, A.; Contreras, I.; Fernández, E., Hub network design problems with profits, Transp. Res. E, 96, 40-59 (2016) |
| [3] | Alibeyg, A.; Contreras, I.; Fernández, E., Exact solution of hub network design problems with profits, Eur. J. Oper. Res., 1-15 (2017) |
| [4] | Alumur, S. A.; Campbell, J. F.; Contreras, I.; Kara, B. Y.; Marianov, V.; O’Kelly, M. E., Perspectives on modeling hub location problems, Eur. J. Oper. Res., 291, 1-17 (2021) · Zbl 1487.90425 |
| [5] | Alumur, S.; Kara, B. Y., A hub covering network design problem for cargo applications in Turkey, J. Oper. Res. Soc., 60, 1349-1359 (2009) · Zbl 1196.90019 |
| [6] | Alumur, S. A.; Kara, B. Y.; Karasan, O. E., The design of single allocation incomplete hub networks, Transp. Res. B, 43, 0-951 (2009) |
| [7] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252 (1962) · Zbl 0109.38302 |
| [8] | Bertsimas, D.; Tsitsiklis, J., Introduction to Linear Optimization (1997), Athena Scientific |
| [9] | Birge, J. R.; Louveaux, F. V., A multicut algorithm for two-stage stochastic linear programs, Eur. J. Oper. Res., 34, 384-392 (1988) · Zbl 0647.90066 |
| [10] | Bollapragada, R.; Li, Y.; Rao, U. S., Budget-constrained, capacitated hub location to maximize expected demand coverage in fixed-wireless telecommunication networks, Inf. J. Comput., 18, 422-432 (2006) · Zbl 1241.90022 |
| [11] | Calik, H.; Alumur, S. A.; Kara, B. Y.; Karasan, O. E., A tabu-search based heuristic for the hub covering problem over incomplete hub networks, Comput. Oper. Res., 36, 3088-3096 (2009) · Zbl 1177.90201 |
| [12] | Camargo, R.d.; Miranda, G., Single allocation hub location problem under congestion: Network owner and user perspectives, Expert Syst. Appl., 39, 3385-3391 (2012) |
| [13] | Camargo, R. S.d.; Miranda, G.d.; Luna, H., Benders decomposition for the uncapacitated multiple allocation hub location problem, Comput. Oper. Res., 35, 1047-1064 (2008) · Zbl 1180.90038 |
| [14] | Camargo, R. S.; Miranda, G.d.; O’Kelly, M. E.; Campbell, J. F., Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints, Appl. Math. Model., 274-301 (2017) · Zbl 1480.90162 |
| [15] | Campbell, J. F., Location and allocation for distribution systems with transshipments and transportion economies of scale, Ann. Oper. Res., 40, 1, 77-99 (1992) · Zbl 0782.90064 |
| [16] | Campbell, J. F.; Ernst, A. T.; Krishnamoorthy, M., Hub arc location problems: Part I: Introduction and results, Manage. Sci., 51, 1540-1555 (2005) · Zbl 1232.90258 |
| [17] | Campbell, J. F.; Ernst, A. T.; Krishnamoorthy, M., Hub arc location problems: Part II: Formulations and optimal algorithms, Manage. Sci., 51, 1556-1571 (2005) · Zbl 1232.90259 |
| [18] | Campbell, J. F.; O’Kelly, M. E., Twenty-five years of hub location research, Transp. Sci., 46, 153-169 (2012) |
| [19] | Carello, G.; Croce, F. D.; Ghirardi, M.; Tadei, R., Solving the hub location problem in telecommunication network design: A local search approach, Networks, 44, 94-105 (2004) · Zbl 1055.90044 |
| [20] | Çetiner, S.; Sepil, C.; Süral, H., Hubbing and routing in postal delivery systems, Ann. Oper. Res., 181, 109-124 (2010) |
| [21] | Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Oper. Res., 54, 756-766 (2006) · Zbl 1167.90601 |
| [22] | Contreras, I., Hub location problems, (Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location Science (2015), Springer International Publishing), 311-344 |
| [23] | Contreras, I.; Cordeau, J.-F.; Laporte, G., Benders decomposition for large-scale uncapacitated hub location, Oper. Res., 59, 1477-1490 (2011) · Zbl 1242.90094 |
| [24] | Contreras, I.; Cordeau, J.-F.; Laporte, G., Exact solution of large-scale hub location problems with multiple capacity levels, Transp. Sci., 46, 439-459 (2012) |
| [25] | Contreras, I.; Fernández, E., Hub location as the minimization of a supermodular set function, Oper. Res., 62, 557-570 (2014) · Zbl 1304.90120 |
| [26] | Contreras, I.; Fernández, E.; Marín, A., The tree of hubs location problem, Eur. J. Oper. Res., 202, 390-400 (2010) · Zbl 1175.90396 |
| [27] | Čvokić, D. D.; Stanimirović, Z., A single allocation hub location and pricing problem, Comput. Appl. Math., 39, 1, 1-24 (2020) · Zbl 1449.90246 |
| [28] | Davari, S.; Zarandi, M. H.F.; Turksen, I. B., The incomplete hub-covering location problem considering imprecise location of demands, Sci. Iran., 20, 983-991 (2013) |
| [29] | Ernst, A. T.; Krishnamoorthy, M., Efficient algorithms for the uncapacitated single allocation p-hub median problem, Locat. Sci., 4, 0-154 (1996) · Zbl 0927.90065 |
| [30] | Ernst, A. T.; Krishnamoorthy, M., Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, Eur. J. Oper. Res., 104, 1, 100-112 (1998) · Zbl 0955.90055 |
| [31] | Esmaeili, M.; Sedehzade, S., Designing a hub location and pricing network in a competitive environment, J. Ind. Manage. Optim., 16, 2, 653-667 (2020) · Zbl 1449.90247 |
| [32] | Farahani, R. Z.; Hekmatfar, M.; Arabani, A. B.; Nikbakhsh, E., Hub location problems: A review of models, classification, solution techniques, and applications, Comput. Ind. Eng., 64, 1096-1109 (2013) |
| [33] | Floyd, R. W., Algorithm 97: Shortest path, Commun. ACM, 5, 345 (1962) |
| [34] | Fortz, B.; Poss, M., An improved benders decomposition applied to a multi-layer network design problem, Oper. Res. Lett., 37, 359-364 (2009) · Zbl 1279.90025 |
| [35] | Gelareh, S.; Nickel, S., Hub location problems in transportation networks, Transp. Res. E, 47, 1092-1111 (2011) |
| [36] | Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by benders decomposition, Manage. Sci., 20, 822-844 (1974) · Zbl 0304.90122 |
| [37] | Ghaffarinasab, N., A highly efficient exact algorithm for the uncapacitated multiple allocation p-hub center problem, Decis. Sci. Lett., 9, 181-192 (2020) |
| [38] | Huo, J.-Z.; Hou, Y.-T.; Chu, F.; He, J.-K., A combined average-case and worst-case analysis for an integrated hub location and revenue management problem., Discrete Dyn. Nat. Soc., 1-13 (2019) · Zbl 1453.90094 |
| [39] | Jaillet, P.; Song, G.; Yu, G., Airline network design and hub location problems, Locat. Sci., 4, 0-212 (1996) · Zbl 0929.90048 |
| [40] | Kim, H.; O’Kelly, M. E., Reliable p-hub location problems in telecommunication networks, Geogr. Anal., 41, 283-306 (2009) |
| [41] | Kuby, M. J.; Gray, R. G., The hub network design problem with stopovers and feeders: The case of federal express, Transp. Res. A, 27, 1-12 (1993) |
| [42] | Labbé, M.; Yaman, H., Solving the hub location problem in a star-star network, Networks, 51, 19-33 (2008) · Zbl 1146.90035 |
| [43] | Lee, C.-H.; Ro, D.-W., Topological design of a two-level network with ring-star configuration, Comput. Oper. Res., 20, 625-637 (1993) · Zbl 0771.90041 |
| [44] | Lin, C.-C.; Lee, S.-C., Hub network design problem with profit optimization for time-definite LTL freight transportation, Transp. Res. E, 114, 104-120 (2018) |
| [45] | Lin, C. C.; Lin, J. Y.; Chen, Y. C., The capacitated p-hub median problem with integral constraints: An application to a Chinese air cargo network, Appl. Math. Model., 36, 2777-2787 (2012) · Zbl 1246.90087 |
| [46] | Lüer-Villagra, A.; Marianov, V., A competitive hub location and pricing problem, Eur. J. Oper. Res., 231, 3, 734-744 (2013) · Zbl 1317.90167 |
| [47] | Magnanti, T. L.; Wong, R. T., Accelerating benders decomposition: Algorithmic enhancement and model selection criteria, Oper. Res., 29, 464-484 (1981) · Zbl 0455.90064 |
| [48] | Mahmoodjanloo, M.; Tavakkoli-Moghaddam, R.; Baboli, A.; Jamiri, A., A multi-modal competitive hub location pricing problem with customer loyalty and elastic demand, Comput. Oper. Res., 123, Article 105048 pp. (2020) · Zbl 1458.90447 |
| [49] | Martins de Sá, E.; Contreras, I.; Cordeau, J.-F.; de Camargo, G., The hub line location problem, Transp. Sci., 49, 500-518 (2015) |
| [50] | Martins de Sá, E.; de Camargo, R. S.; de Miranda, G., An improved benders decomposition algorithm for the tree of hubs location problem, Eur. J. Oper. Res., 226, 185-202 (2013) · Zbl 1292.90176 |
| [51] | Martins de Sá, E.; Morabito, R.; de Camargo, R. S., Benders decomposition applied to a robust multiple allocation incomplete hub location problem, Comput. Oper. Res., 89, 31-50 (2018) · Zbl 1391.90386 |
| [52] | McDaniel, D.; Devine, M., A modified benders’ partitioning algorithm for mixed integer programming, Manage. Sci., 24, 312-319 (1977) · Zbl 0371.90102 |
| [53] | Meraklı, M.; Yaman, H., A capacitated hub location problem under hose demand uncertainty, Comput. Oper. Res., 88, 58-70 (2017) · Zbl 1391.90388 |
| [54] | Mercier, A.; Cordeau, J.-F.; Soumis, F., A computational study of benders decomposition for the integrated aircraft routing and crew scheduling problem, Comput. Oper. Res., 32, 1451-1476 (2005) · Zbl 1122.90355 |
| [55] | Mokhtar, H.; Krishnamoorthy, M.; Ernst, A. T., The 2-allocation p-hub median problem and a modified benders decomposition method for solving hub location problems, Comput. Oper. Res., 104, 375-393 (2019) · Zbl 1458.90449 |
| [56] | Najy, W.; Diabat, A., Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion, Transp. Res. B, 133, 62-84 (2020) |
| [57] | Naoum-Sawaya, J.; Elhedhli, S., An interior-point benders based branch-and-cut algorithm for mixed integer programs, Ann. Oper. Res., 210, 33-55 (2013) · Zbl 1284.90042 |
| [58] | Neamatian Monemi, R.; Gelareh, S.; Hanafi, S.d.; Maculan, N., A co-opetitive framework for the hub location problems in transportation networks, Optimization, 66, 12, 2089-2106 (2017) · Zbl 1411.90057 |
| [59] | Nickel, S.; Schöbel, A.; Sonneborn, T., Hub location problems in urban traffic networks, (Pursula, M.; Niittymäki, J., Mathematical Methods on Optimization in Transportation Systems (2001), Springer), 95-107 · Zbl 1005.90013 |
| [60] | O’Kelly, M. E., A quadratic integer program for the location of interacting hub facilities, Eur. J. Oper. Res., 32, 393-404 (1987) · Zbl 0627.90030 |
| [61] | O’Kelly, M. E.; Luna, H. P.L.; de Camargo, R. S.; de Miranda, G., Hub location problems with price sensitive demands, Netw. Spatial Econ., 15, 917-945 (2015) · Zbl 1332.90139 |
| [62] | O’Kelly, M. E.; Miller, H. J., The hub network design problem, J. Transp. Geogr., 2, 31-40 (1994) |
| [63] | Papadakos, N., Practical enhancements to the Magnanti-Wong method, Oper. Res. Lett., 36, 444-449 (2008) · Zbl 1155.90432 |
| [64] | Pessoa, L. S.; Santos, A. C.; Resende, M. G.C., A biased random-key genetic algorithm for the tree of hubs location problem, Optim. Lett., 1371-1384 (2016) · Zbl 1382.90112 |
| [65] | Rahmaniani, R.; Crainic, T. G.; Gendreau, M.; Rei, W., The benders decomposition algorithm: A literature review, Eur. J. Oper. Res., 259, 3, 801-817 (2017), URL: http://www.sciencedirect.com/science/article/pii/S0377221716310244 · Zbl 1402.90158 |
| [66] | Sadeghi Dastaki, M.; Setak, M.; Karimi, H., The multi-zone location-routing problem with pricing: a flow-based formulation and two heuristic approaches, Soft Comput., 25, 1, 741-769 (2021) · Zbl 1491.90097 |
| [67] | Salehi, M.; Tikani, H., Using revenue management technique to allocate the capacity in reliable hub network design under uncertain air passenger traffic, J. Ind. Eng. Manage. Stud., 7, 2, 139-164 (2020) |
| [68] | Taherkhani, G.; Alumur, S. A., Profit maximizing hub location problems, Omega, 86, 1-15 (2018) |
| [69] | Taherkhani, G.; Alumur, S. A.; Hosseini, S. M., Benders decomposition for the profit maximizing capacitated hub location problem with multiple demand classes, Transp. Sci., 54, 1446-1470 (2020) |
| [70] | Tan, P. Z.; Kara, B. Y., A hub covering model for cargo delivery systems, Networks, 49, 28-39 (2007) · Zbl 1131.90422 |
| [71] | Tikani, H.; Honarvar, M.; Mehrjerdi, Y. Z., Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry, Comput. Appl. Math., 37, 3, 3334-3364 (2018) · Zbl 1409.90112 |
| [72] | Tiwari, R.; Jayaswal, S.; Sinha, A., Alternate solution approaches for competitive hub location problems, Eur. J. Oper. Res., 290, 1, 68-80 (2021) · Zbl 1487.90450 |
| [73] | Wieberneit, N., Service network design for freight transportation: a review, OR Spectrum, 30, 77-112 (2008) · Zbl 1133.90314 |
| [74] | Xu, Y.; Dai, W.; Sun, X.; Wandelt, S., Improved benders decomposition for capacitated hub location problem with incomplete hub networks, (2017 IEEE Symposium Series on Computational Intelligence (SSCI) (2017)), 1-8 |
| [75] | Yaman, H., Allocation strategies in hub networks, Eur. J. Oper. Res., 211, 442-451 (2011) · Zbl 1237.90137 |
| [76] | Yaman, H.; Elloumi, S., Star p-hub center problem and star p-hub median problem with bounded path lengths, Comput. Oper. Res., 39, 2725-2732 (2012) · Zbl 1251.90253 |
| [77] | Yoon, M.-G.; Current, J., The hub location and network design problem with fixed and variable arc costs: Formulation and dual-based solution heuristic, J. Oper. Res. Soc., 59, 80-89 (2008) · Zbl 1166.90355 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
