×

Uncapacitated single and multiple allocation \(p\)-hub center problems. (English) Zbl 1158.90372

Summary: The hub median problem is to locate hub facilities in a network and to allocate non-hub nodes to hub nodes such that the total transportation cost is minimized. In the hub center problem, the main objective is one of minimizing the maximum distance/cost between origin destination pairs. In this paper, we study uncapacitated hub center problems with either single or multiple allocation. Both problems are proved to be NP-hard. We even show that the problem of finding an optimal single allocation with respect to a given set of hubs is already NP-hard. We present integer programming formulations for both problems and propose a branch-and-bound approach for solving the multiple allocation case. Numerical results are reported which show that the new formulations are superior to previous ones.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bryan, D. L.; O’Kelly, M. E., Hub-and-spoke networks in air transportation: an analytical review, Journal of Regional Science, 39, 2, 275-295 (1999)
[2] Chung, S.-H.; Myung, Y.-S.; Tcha, D.-W., Optimal design of a distributed network with a two-level hierarchical structure, European Journal of Operational Research, 62, 105-115 (1992) · Zbl 0758.90072
[3] Ernst, A. T.; Krishnamoorthy, M., Efficient algorithms for the uncapacitated single allocation \(p\)-hub median problem, Location Science, 4, 139-154 (1996) · Zbl 0927.90065
[4] Alumur, S.; Kara, B. Y., Network hub location problems: the state of the art, European Journal of Operational Research, 190, 1, 1-21 (2008) · Zbl 1146.90455
[5] Campbell, J. F.; Ernst, A.; Krishnamoorthy, M., Hub location problems, (Hamacher, H.; Drezner, Z., Location theory: applications and theory (2001), Springer: Springer Berlin), 373-406 · Zbl 1061.90069
[6] Kara, B. Y.; Tansel, B., The latest arrival hub location problem, Management Science, 47, 10, 1408-1420 (2001) · Zbl 1232.90116
[7] O’Kelly, M. E.; Miller, H. J., Solution strategies for the single facility minimax hub location problem, Papers in Regional Science: The Journal of the RSAI, 70, 367-380 (1991)
[8] Campbell, J. F., Integer programming formulations of discrete hub location problems, European Journal of Operational Research, 72, 387-405 (1994) · Zbl 0790.90048
[9] Kara, B. Y.; Tansel, B., On the single assignment \(p\)-hub center problem, European Journal of Operational Research, 125, 3, 648-655 (2000) · Zbl 0971.90042
[10] Pamuk, P.; Sepil, C., A solution to the hub center problem via a single-relocation algorithm with tabu search, IEE Transactions, 33, 399-411 (2001)
[11] Hamacher H, Meyer T. Hub cover and hub center problems. Technical Report 98, FB Mathematik, TU Kaiserslautern; 2006.; Hamacher H, Meyer T. Hub cover and hub center problems. Technical Report 98, FB Mathematik, TU Kaiserslautern; 2006.
[12] Juette S, Gavriliouk O, Hamacher H. Polyhedral analysis of uncapacitated single allocation \(p\); Juette S, Gavriliouk O, Hamacher H. Polyhedral analysis of uncapacitated single allocation \(p\)
[13] Campbell, J. F.; Ernst, A. T.; Krishnamoorthy, M., Hub arc location problems: Part I—introduction and results, Management Science, 51, 10, 1540-1555 (2005) · Zbl 1232.90258
[14] Podnar, H.; Skorin-Kapov, J.; Skorin-Kapov, D., Network cost minimization using threshold-based discounting, European Journal of Operational Research, 137, 2, 371-386 (2002) · Zbl 1008.90004
[15] Cánovas, L.; García, S.; Marín, A., Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique, European Journal of Operational Research, 179, 3, 990-1007 (2007) · Zbl 1163.90595
[16] Hamacher, H.; Labbé, M.; Nickel, S.; Sonneborn, T., Adapting polyhedral properties from facility to hub location problems, Discrete Applied Mathematics, 145, 1, 104-116 (2004) · Zbl 1058.90033
[17] Marín, A.; Cánovas, L.; Landete, M., New formulations for the uncapacitated multiple allocation hub location problem, European Journal of Operational Research, 172, 1, 274-292 (2006) · Zbl 1116.90071
[18] de Camargo, R. S.; Miranda, G.; Luna, H. P., Benders decomposition for the uncapacitated multiple allocation hub location problem, Computers & Operations Research, 35, 4, 1047-1064 (2008) · Zbl 1180.90038
[19] Marín, A., Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm, Journal of Global Optimization, 33, 3, 393-422 (2005) · Zbl 1093.90022
[20] Daskin, M., Network and discrete location: models, algorithms, and applications (1995), Wiley: Wiley New York · Zbl 0870.90076
[21] Crescenzi P, Kann V, Halldorsson M, Karpinski M, Woeginger G. A compendium of NP optimization problems, \(2001 \langle;\) http://www.nada.kth.se/∼;viggo/problemlist/compendium.html \(\rangle;\); Crescenzi P, Kann V, Halldorsson M, Karpinski M, Woeginger G. A compendium of NP optimization problems, \(2001 \langle;\) http://www.nada.kth.se/∼;viggo/problemlist/compendium.html \(\rangle;\)
[22] Ernst, A. T.; Krishnamoorthy, M., An exact solution approach based on shortest-paths for \(p\)-hub median problems, INFORMS Journal on Computing, 10, 2, 149-162 (1998) · Zbl 1034.90505
[23] Ernst, A. T.; Krishnamoorthy, M., Exact and heuristic algorithms for the uncapacitated multiple allocation \(p\)-hub median problem, European Journal of Operational Research, 104, 1, 100-112 (1998) · Zbl 0955.90055
[24] Fotheringham, A. S., A new set of spatial interaction models: the theory of competing destinations, Environment and Planning A, 15-36 (1983)
[25] O’Kelly, M. E., A quadratic integer program for the location of interacting hub facilities, European Journal of Operational Research, 32, 393-404 (1987) · Zbl 0627.90030
[26] Meyer T, Ernst AT, Krishnamoorthy M. A 2-phase algorithm for solving the single allocation \(p10.1016\)/j.cor.2008.07.011; Meyer T, Ernst AT, Krishnamoorthy M. A 2-phase algorithm for solving the single allocation \(p10.1016\)/j.cor.2008.07.011 · Zbl 1176.90360
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.