An Estimated Formulation for the Capacitated Single Alocation p-hub Median Problem with Fixed Costs of Opening Facilities

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, University of Newcastle, Australia

2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

Abstract

In this paper, we consider the capacitated single allocation p-hub median problem generalized with fixed costs of opening facilities. The quadratic mathematical formulation of this problem is first adapted and then linearized. The typical approaches of linearization result in a high size complexity, i.e., having a large number of variables. To downsize the complexity, variables of the formulation are analyzed and some preprocessing approaches are defined. An estimated formulation is then developed to approximately solve large instances of the problem by commercial optimization solvers. The basic idea of this formulation is mapping the linearized formulation of the problem to a new formulation with fewer variables and a modified objective function. The efficacy of this formulation is shown by a computational study, where the estimated formulation is compared to a modified genetic algorithm from the literature. Results of computational experiments indicate that the estimated formulation is capable of generating good solutions within reasonable amount of time.

Keywords

Main Subjects

References

Alumur, S. and B. Y. Kara (2008). Network hub location problems: The state of the art. European Journal of Operational Research, Vol. 190(1), pp. 1-21.
Bixby, R. E. (2002). Solving Real-World Linear Programs: A Decade and More of Progress. Operations Research, Vol. 50(1), pp. 3-15.
Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, Vol. 72(2), pp. 387-405.
Campbell, J. F. and M. E. O'Kelly (2012). Twenty-Five Years of Hub Location Research. Transportation Science, Vol. 46(2), pp. 153-169.
Chen, J.-F. (2007). A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega, Vol. 35(2), pp. 211-220.
Correia, I., S. Nickel, and F. Saldanha-da-Gam. (2010). The capacitated single-allocation hub location problem revisited: A note on a classical formulation. European Journal of Operational Research, Vol. 207(1), pp. 92-96.
Ebery, J. (2001). Solving large single allocation p-hub problems with two or three hubs. European Journal of Operational Research, Vol. 128(2), pp. 447-458.
Ernst, A. T. and M. Krishnamoorthy (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science, Vol. 4(3), pp. 139-154.
Ernst, A. T. and M. Krishnamoorthy (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research, Vol. 86(0), pp. 141-159.
Farahani, R. Z., M. Hekmatfar, A., Boloori, and A.E. Nikbakhsh (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, Vol. 64(4), pp. 1096-1109.
Ilić, A., D. Urošević, J. Brimberg, and N. Mladenović (2010). A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research, Vol. 206(2), pp. 289-300.
Klincewicz, J. (1992). Avoiding local optima in thep-hub location problem using tabu search and GRASP. Annals of Operations Research, Vol. 40(1), pp. 283-302.
Klincewicz, J. G. (1991). Heuristics for the p-hub location problem. European Journal of Operational Research, Vol. 53(1), pp. 25-37.
Kratica, J., Z. Stanimirović, D. Tošić, and V. Filipović, (2007). Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research, Vol. 182(1), pp. 15-28.
Merakli, M. and H. Yaman (2017). A capacitated hub location problem under hose demand uncertainty. Computers & Operations Research, Vol. 88, pp. 58-70.
O'Kelly, M. (1992). Hub facility location with fixed costs. Papers in Regional Science, Vol. 71(3), pp. 293-306.
O'Kelly, M. E. (1986). The Location of Interacting Hub Facilities. Transportation Science, Vol. 20(2). pp. 92-106.
O'Kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, Vol. 32(3), pp. 393-404.
Puerto, J., A.B. Ramos, A.M. Rodríguez-Chía, and M.C. Sánchez-Gil (2016). Ordered median hub location problems with capacity constraints. Transportation Research Part C: Emerging Technologies, Vol. 70, pp. 142-156.
Rabbani, M., M. Ravanbakhsh, H. Farrokhi-Asl, M. Taheri, (2017). Using metaheuristic algorithms for solving a hub location problem: application in passive optical network planning.” International Journal of Supply and Operations Management, In-press.
Rostami, B., C. Buchheim, J.F. Meier and U. Clausen (2016). Lower Bounding Procedures for the Single Allocation Hub Location Problem. Electronic Notes in Discrete Mathematics, Vol, 52, pp. 69-76.
Silva, M. R. and C. B. Cunha (2009). New simple and efficient heuristics for the uncapacitated single allocation hub location problem. Computers & Operations Research, Vol. 36(12), pp. 3152-3165.
Skorin-Kapov, D. and J. Skorin-Kapov (1994). On tabu search for the location of interacting hub facilities. European Journal of Operational Research. Vol. 73(3), pp. 502-509.
Stanojević, P., M. Marić, Z. Stanimirović, (2015). A hybridization of an evolutionary algorithm and a parallel branch and bound for solving the capacitated single allocation hub location problem. Applied Soft Computing, Vol. 33, pp. 24-36.
Yaman, H. (2011). Allocation strategies in hub networks. European Journal of Operational Research, Vol. 211(3), pp. 442-451.
International Journal of Supply and Operations Management
Volume 4, Issue 1 - Serial Number 1
February 2016
Pages 53-62

Files

Share

How to cite

Statistics