Abstract
The stochastic uncapacitated single allocation p-hub center problem is an extension of the deterministic version which aims to minimize the longest origin-destination path in a hub and spoke network. Considering the stochastic nature of travel times on links is important when designing a network to guarantee the quality of service measured by a maximum delivery time for a proportion of all deliveries. We propose an efficient reformulation for a stochastic p-hub center problem and develop exact solution approaches based on variable reduction and a separation algorithm. We report numerical results to show effectiveness of our new reformulations and approaches by finding global solutions of small-medium sized problems. The combination of model reformulation and a separation algorithm is particularly noteworthy in terms of computational speed.
Similar content being viewed by others
References
Alumur, S., Kara, B.Y.: Network hub location problems: the state of the art. Eur. J. Oper. Res. 190(1), 1–21 (2008)
Baron, O., Berman, O., Krass, D.: Facility location with stochastic demand and constraints on waiting time. Manuf. Serv. Oper. Manag. 10, 484–505 (2008)
Campbell, J.F.: Location and allocation for distribution systems with transshipments and transportation economies of scale. Ann. Oper. Res. 40, 77–99 (1992)
Campbell, J.F.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72, 387–405 (1994)
Campbell, J.F., Ernst, A., Krishnamoorthy, M.: Hub location problems. In: Hamacher, H., Drezner, Z. (eds.) Location Theory: Applications and Theory, pp. 373–406. Springer, Berlin (2001)
Contreras, I., Cordeau, J.-F., Laporte, G.: Stochastic uncapacitated hub location (2011). HEC Montreal and Interuniversity Res. Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada
Contreras, I., Diaz, J.A., Fernandez, E.: Branch-and-price for large-scale capacitated hub location problems with single assignment. INFORMS J. Comput. 23, 41–55 (2011)
Ernst, A.T., Hamacher, H., Jiang, H., Krishnamoorthy, M., Woeginger, G.: Uncapacitated single and multiple allocation p-hub center problems. Comput. Oper. Res. 36, 2230–2241 (2009)
Ernst, A.T., Krishnamoorthy, M.: Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Sci. 4, 139–154 (1996)
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)
Fotheringham, A.S.: A new set of spatial interaction models. The theory of competing destinations. Environ. Plan. A 15–36 (1983). http://www.envplan.com/abstract.cgi?id=a150015
Garnett, O., Mandelbaum, A., Reiman, M.: Designing a call center with impatient customers. Manuf. Serv. Oper. Manag. 4(3), 208–227 (2002)
Gurvich, I., Armony, M., Mandelbaum, A.: Service-level differentiation in call centers with fully flexible servers. Manag. Sci. 54(2), 279–294 (2008)
Juette, S., Gavriliouk, O., Hamacher, H.: Polyhedral analysis of uncapacitated single allocation p-hub center problems. Technical Report 109, FB Mathematik, TU Kaiserslautern (2007)
Kara, B.Y., Tansel, B.: On the single assignment p-hub center problem. Eur. J. Oper. Res. 125(3), 648–655 (2000)
Marianov, V., Serra, D.: Location models for airline hubs behaving as m/d/c queues. Comput. Oper. Res. 30, 983–1003 (2003)
Meyer, T., Ernst, A.T., Krishnamoorthy, M.: A 2-phase algorithm for solving the single allocation p-hub center problem. Comput. Oper. Res. 36, 3143–3151 (2009)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
O’Kelly, M.E.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32, 393–404 (1987)
Elhedhli, H.W.S.: A Lagrangean heuristic for hub-and-spoke system design with capacity selection and congestion. INFORMS J. Comput. 22, 282–296 (2010)
Savage, S.: Decision Making with Insight. Duxbury, N. Scituate (2003)
Sim, T., Lowe, T., Thomas, B.: The stochastic p-hub center problem with service-level constraints. Comput. Oper. Res. 36, 3166–3177 (2009)
Skorin-Kapov, D., Skorin-Kapov, J., O’Kelly, M.E.: Tight linear programming relaxations of uncapacitated p-hub median problems. Eur. J. Oper. Res. 94, 582–593 (1996)
Wang, J.: The β-reliable median on a network with discrete probabilistic demand weights. Oper. Res. 55, 966–975 (2007)
Yang, T.-H.: Stochastic air freight hub location and flight routes planning. Appl. Math. Model. 33, 4424–4430 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is dedicated to Professor Masao Fukushima in celebration of his 65th birthday.
Appendix
Appendix
Proof of Lemma 1
(a) Suppose that X jm =1. Let j=i and m=k. Then constraint (7) reduces to \(\beta\geq t_{jjmm} + z_{\gamma} \delta_{jjmm} = 2 d_{jm} + z_{\gamma} \sqrt{2} \sigma_{jm}\), which implies that a feasible solution with X jm =1 gives a worse objective function value than the current available upper bound β U. Hence, X jm =0 is a valid cut for SpHCPL.
(b) Suppose that X jm =1. Then constraint (7) reduces to
which is greater than β U according to the assumption. This shows that any feasible solution with X jm =1 gives a worse objective function value than β U. Therefore, X jm =0 is a valid cut for SpHCPL.
(c) Suppose that X jm =1. Then constraint (7) reduces to
which is redundant for the given i,j,m.
(d) Suppose that X jm =1 and assume \(d_{mi} = \max_{\ell=1}^{N} d_{m\ell}\) and X in =1. It follows from constraint (7) and the triangle inequality property that
This shows that any feasible solution with X jm =1 gives a worse objective function value than β U. Hence X jm =0 is a valid cut.
(e) When X jm =0, the right-hand side of constraint (7) for any i and the corresponding j,m is non-positive. Clearly, this constraint is redundant for SpHCPL. □
Rights and permissions
About this article
Cite this article
Hult, E., Jiang, H. & Ralph, D. Exact computational approaches to a stochastic uncapacitated single allocation p-hub center problem. Comput Optim Appl 59, 185–200 (2014). https://doi.org/10.1007/s10589-013-9629-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-013-9629-5