A variable neighborhood descent based heuristic to solve the capacitated location-routing problem

Abstract: Location-routing problem (LRP) is established as a new research area in the context of location analysis. The primary concern of LRP is on locating facilities and routing of vehicles among established facilities and existing demand points. In this work, we address the capacitated LRP which arises in many practical applications within logistics and supply chain management. The objective is to minimize the overall system costs which include the fixed costs of opening depots and using vehicles at each depot site, and the variable costs associated with delivery activities. A novel heuristic is proposed which is based on variable neighborhood descent (VND) algorithm to solve the resulted problem. The computational study indicates that the proposed VND based heuristic is highly competitive with the existing solution algorithms in terms of solution quality.

How to cite this paper

 Jabal-Ameli, M., Aryanezhad, M & Ghaffari-Nasab, N. (2011). A variable neighborhood descent based heuristic to solve the capacitated location-routing problem.International Journal of Industrial Engineering Computations , 2(1), 141-154.

Refrences

Barreto, S. S. (2004). Análise e Modelização de Problemas de localização- distribuição, Analysis and modelling of location-routing problems. Ph.D. Thesis, University of Aveiro, Aveiro, Portugal.

Barreto, S., Ferriera, C., Paixao, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179, 968-977.

Clarke, G. & Wrights, J. W. (1964). Scheduling of vehicles form a central depot to a number of delivery points. Operations Research, 12, 568-581.

Duhamel, C., Lacomme,P., Prins, C., & Prodhon, C. (2010). A GRASP×ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.

Eilon, S., Watson-Gandy, C. D. T. & Christofides, N. (1971). Distribution management: mathematical modeling and practical analysis. New York, Hafner publishing company.

Hansen. P. & Mladenovic, M. (2003). A tutorial on variable neighborhood serach. Les Cahiers du GERAD G-2003-46, Montreal, Canada.

Hassan-Pour, H. A., Mosadegh-Khan, M., & Tavakkoli-Moghaddam, R. (2009). Solving a multi-objective multi-depot stochastic location-routing problem by a hybrid simulated annealing algorithm. Proc. IMechE, Part B., 223, 1045-1054.

Laporte, G. (1988). Location Routing Problems, In: Golden, B.L. and Assad, A.A. (eds), Vehicle Routing: Methods and Studies, 163–197, North-Holland, Amsterdam.

Laporte G., N., Y., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation science, 22, 161-172.

Larson, R. C. & Odoni, A. R. (1981). Urban Operations Research, Prentice-Hall, NJ

Lin, J.-R., & Lei, H.-C. (2009). Distribution systems design with two-level routing considerations. Annals of Operations Research, 172 (1), 329-347.

Marinakis, Y., & Marinaki, M. (2008). A Bilevel Genetic Algorithm for a real life location routing problem. International Journal of Logistics Research and Applications, 11 (1), 49-65.

Min, H., Jayaraman, V. & Srivastava, R. (1998). Combined Location-Routing Problems: A Research Directions Synthesis and Future. European Journal of Operational Research, 108, 1-15.

Mladenovic, M. & P. Hansen. P. (1997). Variable neighborhood search. Computers and Operations Research, 24,1097-1100.

Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods, European Journal of Operational Research, 177, 649-672.

Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation granular tabu search heuristic. Transportation Science, 41(4), 470-483.

Prins, C., Prodhon, C., & Wolfler Calvo, R. (2006). Solving the capacitated location routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.

Schwardt, M., & Fischer, K. (2009). Combined location-routing problems-a neural network approach, Annals of Operations Research, 167 (1), 253-269.

Simchi-Levi, D., Kaminsky, P., & Simchi-Levi, E. (2003). Designing and Managing the Supply Chain: Concepts, Strategies, and Case Studies. Irwin, Boston: McGraw-Hill.

Talbi, E. G. (2009). Metaheuristics: From Design to Implementation. Hoboken, New Jersey. John Wiley & Sons, Inc.

Tuzun, D., & Bruke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116, 87-99.

Yu, V. F., Lin, S-W., Lee, W., & Ting, C-J. (2010). A simulated annealing heuristic for the capacitated location-routing problem. Computers & Industrial Engineering, 58, 288-299.