Volume 2 Issue 3 pp. 509-522 Summer, 2011


A hybrid model for multi-objective capacitated facility location network design problem


Mohammad saeed JabalAmeli and Marzieh Mortezaei


One of the primary concerns on many traditional capacitated facility location/network problems is to consider transportation and setup facilities in one single objective function. This simple assumption may lead to misleading solutions since the cost of transportation is normally considered for a short period time and, obviously, the higher cost of setting up the facilities may reduce the importance of the transportation cost/network. In this paper, we introduce capacitated facility location/network design problem (CFLNDP) with two separate objective functions in forms of multi-objective with limited capacity. The proposed model is solved using a new hybrid algorithm where there are two stages. In the first stage, locations of facilities and design of fundamental network are determined and in the second stage demands are allocated to the facilities. The resulted multi-objective problem is solved using Lexicography method for a well-known example from the literature with 21 node instances. We study the behaviour of the resulted problem under different scenarios in order to gain insight into the behaviour of the model in response to changes in key problem parameters.


DOI: 10.5267/j.ijiec.2011.04.001

Keywords: Facility Location, Network design, Hybrid algorithm, Simulated annealing algorithm
References

Balakrishnan, A., Magnani, T.L., & Wong, R.T. (1989). A dual-ascent procedure for large-scale uncapacitated network design. Operation Research, 37(5), 716-740.

Bazaraa, M. S., Jarvis, J. J., & Sherali, H. D. (1990). Linear programming and network flows. New York: Springer.

Berman, O., Ingco, D.I., Odoni, A.R., (1992). Improving the location of minisum facilities trough network modification. Annals of Operations Research 40(1), 1-16.

Bhadury, J., Gewali, L.P., Chandrasekaran, R., & Badr, M., (2003). Network design subject to facility location. 15th Canadian Conference on Computational Geometry.

Campbell, J.F., (1994). A survey of network hub location. Studies in Locational Analysis 6, 31-49.

Daskin, M.S., & Jones, P.C. (1993). A new approach to solving applied location/allocation Problems. Computer-aided Civil and Infrastructure Engineering, 8(6), 409-421.

Daskin, M.S., Snyder, L.V., & Berger, R.Y.(2005). Facility location in supply chain design. Logistics Systems: Design and Optimization. 39-65.

Drezner, Z., Wesolowsky, G. O. (1998). Design-location problems. INFORMS National Meeting, seattle.

Drezner, Z., & Wesolowsky, G. O. (2003). Network design: selection and design of links and facility location. Transportation Research Part A. 37(3), 241–256.

Friesz, T.L., Shah, S., & Bernstein, D. (1998). Disequilibrium network design: a new paradigm for transportation planning and control. In: Network Infrastructure and the Urban Environment: Advances in Spatial Systems Modeling. Springer, Berlin.

Klincewicz, J.G. (1998). Hub location in backbone/tributary network design: a review. Location Science, 6(1-4), 307-335.

Kirkpatrick S, Gelatt jr. CD, & Vecchi MP. (1983). Optimization by simulated annealing. Science. 220, 671-680.

Laporte, G., (1998). Location-routing problems. In Golden, B.L., Assad, A.A.(Eds), Vehicle Routing: Methods and studies. North-Holland, Amsterdam, 163-198.

Magnanti, T.L. & Wong, R.T. (1984). Network design and transportation planning: models and algorithms. Transportation Science, 18(1), 1-55.

Melkote, S., (1996). Integrated models of facility location and network design. PhD Dissertation. Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL.

Melkote, S., & Daskin, M. S. (2001). An integrated model of facility location and transportation network design. Transportation Research Part A: Policy and Practice, 35(6), 515–538.

Melkote, S., & Daskin, M. S. (2001). Capacitated facility location-network design problems. European Journal of Operational Research, 129(3), 481-495.

Metropolis, N., Rosenbluth, A.W, Rosenbluth, M.N., Teller, A.H, & Teller, E. (1953). Equations of state calculations by fast computing machines. Journal of chemical- physics, 21(6). 1087-1092.

Mitchel, D.H., & Smith, J.M. (2001). Topological network design of pedestrian networks. Transportation Research Part B: Methodological, 35(2), 107–135.

Peeters, D., & Thomas,I. (1995). The effect of spatial structure on p-median results. Transportation Science, 29(4), 366-373.

Pardalos, P.M., & Du, D. (1998). Network design: Connectivity and facilities location. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 40. American Mathematical Society.

Ravi, R., & Sinha, A. (2006). Approximation algorithms for problems combining facility location and network design. Operations Research. 54. 73–81

Solanki, R.S., Gorti, J.K., & Southworth, F. (1998). Using decomposition in large-scale highway network design with a quasi-optimization heuristic. Transportation Research Part B: Methodological ,32(2), 127–140.

Yang, H. (1998). Models and algorithms for road network design: a review and some new developments. Transport Reviews 18(3), 257–278.