An Integrated Approach for Reliable Facility Location/Network Design Problem with Link Disruption

Document Type : Research Paper


1 Department of Industrial Engineering, Yazd University, Yazd, Iran

2 Department of Industrial engineering, University of Kurdistan, Sanandaj, Iran


Proposing a robust designed facility location is one of the most effective ways to hedge against unexpected disruptions and failures in a transportation network system. This paper considers the combined facility location/network design problem with regard to transportation link disruptions and develops a mixed integer linear programming formulation to model it. With respect to the probability of link disruptions, the objective function of the model minimizes the total costs, including location costs, link construction costs and also the expected transportation costs. An efficient hybrid algorithm based on LP relaxation and variable neighbourhood search metaheuristic is developed in order to solve the mathematical model. Numerical results demonstrate that the proposed hybrid algorithm has suitable efficiency in terms of duration of solution time and determining excellent solution quality.


Main Subjects

Alinaghian, M., Hejazi S. R., and Bajoul., N. (2014). A novel hierarchical model to locate health care facilities with fuzzy demand solved by harmony search algorithm. International Journal of Supply and Operations Management, Vol. 1(2), pp. 245-259.
Barrionuevo, A. a. D., C. (September 1 (2005)). A distribution system brought to its knees. New York Times.
Bathgate, A. a. H., A. (April 10 (2008)). Airlines lining up for Boeing 787 compensation. Reuters.
Berman, O., Krass, D., & Menezes, M. B. C. (2007). Facility reliability issues in network pmedian problems: Strategic centralization and co-location effects. Operations Research, Vol. 55, pp. 332.
Bigotte, J. F., Krass, D., Antunes, A. P., & Berman, O. (2010). Integrated modeling of urban hierarchy and transportation network planning. Transportation Research Part A, Vol. 44, pp. 506–522.
Church, R., & ReVelle, C. (1974). The maximal covering location problem. Papers in regional science, Vol. 32, pp. 101-118.
Clark, D. a. T., Y. . (March 12 (2011)). Quake disrupts key supply chains. The Wall Street Journal Asia.
Cocking, C. (2008). Solutions to Facility Location–Network Design Problems. University of Heidelberg, Doctor of Philosophy Thesis.
Cocking, C., & Reinelt, G. (2009). Heuristics for budget facility location-network design problems with minisum objective. In Operations Research Proceedings 2008 (Vol. 12, pp. 563568): Springer Berlin Heidelberg.
Contreras, I., & Fernández, E. (2011). General network design: A unified view of combined location and network design problems. European Journal of Operational Research.
Contreras, I., Fernández, E., & Reinelt, G. (2012). Minimizing the maximum travel time in a combined model of facility location and network design. Omega.
Cornuejols, G., Nemhauser, G.L. and Wolsey, L.A. . (1990). The uncapacitated facility location problem. In discrete location theory (P.B. Mirchandani and R.L. Francis, eds.), Wiley, New York, pp. 119-171.
Cui, T., Ouyang, Y., & Shen, Z. J. M. (2010). Reliable facility location design under the risk of disruptions. Operations Research, Vol. 58, pp. 998-1011.
Daskin, M. S., Hurter, A. P., & VanBuer, M. G. (1993). Toward an integrated model of facility location and transportation network design. In Working Paper, : Transportation Center, Northwestern University.
Drezner, Z. (1987). Heuristic solution methods for two location problems with unreliable facilities. Journal of the Operational Research Society, pp. 509-514.
Drezner, Z., & Wesolowsky, G. O. (2003). Network Design: Selection and Design of Links and Facility Location. Transportation Research Part A, Vol. 37, pp. 241–256.
Duarte, A., Escudero, L. F., MartÃ-, R., Mladenovic, N., Pantrigo, J. J., & Sánchez-Oro, J. s. Variable neighborhood search for the vertex separation problem. Computers & Operations Research.
Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, pp. 450-459.
Hansen, P., Mladenović, N., & Moreno Pérez, J. A. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, Vol. 175, pp. 367-407.
Hendricks, K. a. S., V. . (2005). An empirical analysis of the effect of supply chain disruptions on long-run stock price performance and equity risk of the firm. Production and Operations Management, Vol. 14, pp. 35-52.
Hicks, M. (2002). When the chain snaps. eWeek. Enterprise News & Reviews,
JabalAmeli, M. S., & Mortezaei, M. (2011). A hybrid model for multi-objective capacitated facility location network design problem.
Jabbarzadeh, A., Jalali Naini, S. G., Davoudpour, H., & Azad, N. (2012). Designing a Supply Chain Network under the Risk of Disruptions. Mathematical Problems in Engineering, 12, DOI:10.1155/2012/234324.
Kuehn, A. A., & Hamburger, M. J. (1963). A heuristic program for locating warehouses. Management Science, Vol. 9, pp. 643-666.
Latour, A. (January 29 (2001)). Trail by fire: A blaze in albuquerque sets off major crisis for cellphone giants – Nokia handles supply chain shock with aplomb as Ericsson of Sweden gets burned – was Sisu the difference? Wall Street Journal, A1.
Liberatore, F., Scaparra, M. P., & Daskin, M. S. (2012). Hedging against disruptions with ripple effects in location analysis. Omega, 40, 21-30.

Lim, M., Daskin, M.S., Bassamboo, A., & Chopra, S. (2009). Facility location decisions in supply chain networks with random disruption and imperfect information. Working paper,” Department of Business Administration, University of Illinois.
Melkote, S. (1996). Integrated models of facility location and network design,. Northwestern University, Doctor of Philosophy, EVASTON, ILLINIOS.
Melkote, S., & Daskin, M. S. (2001a). An integrated model of facility location and transportation network design. Transportation Research Part A, Vol. 35, pp. 515-538.
Melkote, S., & Daskin, M. S. (2001b). Capacitated facility location-network design problems. European Journal of Operational Research, Vol. 129, pp. 481-495.
Mladenović, N., Urošević, D., Hanafi, S., & Ilić, A. (2012). A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, Vol. 220, pp. 270-285.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, Vol. 24, pp. 1097-1100.
Mouawad, J. (September 4 (2005)). Katrina’s shock to the system. The New York Times. O’Hanley, J. R., & Church, R. L. (2011). Designing robust coverage networks to hedge against worst-case facility losses. European Journal of Operational Research, Vol. 209, pp. 23-36.
Peng, P., Snyder, L. V., Lim, A., & Liu, Z. (2011). Reliable logistics networks design with facility disruptions. Transportation Research Part B: Methodological, Vol. 45, pp. 1190-1211.
Qi, L., & Shen, Z. J. M. (2007). A supply chain design model with unreliable supply. Naval Research Logistics (NRL), Vol. 54, pp. 829-844.
Qi, L., Shen, Z. J. M., & Snyder, L. V. (2010). The effect of supply disruptions on supply chain design decisions. Transportation Science, Vol. 44, pp. 274-289.
Rahmaniani, R., & Ghaderi, A. (2013). A combined facility location and network design problem with multi-type of capacitated links. Applied Mathematical Modelling.
Shen, Z. J. M., R. L. Zhan, J. Zhang.,. (2009). The reliable facility location problem: Formulations, heuristics, and approximation algorithms. Working paper,” Department of Business Administration, University of Illinois.
Shishebori, D., Jabalameli, M. S., & Jabbarzadeh, A. (2013). Facility Location-Network Design Problem: Reliability and Investment Budget Constraint. Journal of Urban Planning and Development.
Snyder, L., & Ülker, N. (2005). A model for locating capacitated, unreliable facilities. In IERC Conference, . Atlanta, GA, May 2005.
Snyder, L. V. (2003). Supply chain robustness and reliability: Models and algorithms (PHD Thesis). Northwestern University, Evanston, IL,.
Snyder, L. V., & Daskin, M. S. (2005). Reliability models for facility location: The expected failure cost case. Transportation Science, Vol. 39, pp. 400-416.
Snyder, L. V., & Daskin, M. S. (2007). Models for reliable supply chain network design. Critical Infrastructure : Reliability and Vulnerability, A.T. Murray and T.H. Grubesic (eds.),, Chapter 13, pp. 257-289.
Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, Vol. 19, pp. 1363-1373.