A heuristic algorithm for a multi-product four-layer capacitated location-routing problem

Abstract: The purpose of this study is to solve a complex multi-product four-layer capacitated location-routing problem (LRP) in which two specific constraints are taken into account: 1) plants have limited production capacity, and 2) central depots have limited capacity for storing and transshipping products. The LRP represents a multi-product four-layer distribution network that consists of plants, central depots, regional depots, and customers. A heuristic algorithm is developed to solve the four-layer LRP. The heuristic uses GRASP (Greedy Randomized Adaptive Search Procedure) and two probabilistic tabu search strategies of intensification and diversification to tackle the problem. Results show that the heuristic solves the problem effectively.

How to cite this paper

 Hamidi, M., Farahmand, K., Sajjadi, S & Nygard, K. (2014). A heuristic algorithm for a multi-product four-layer capacitated location-routing problem.International Journal of Industrial Engineering Computations , 5(1), 87-100.

Refrences

Aksen, D., & Altinkemer, K. (2008). A location-routing problem for the conversion to the “click-and-mortar” retailing: The static case. European Journal of Operational Research, 186(2), 554-575.

Ambrosino, D., & Grazia Scutellà, M. (2005). Distribution network design: new problems and related models. European Journal of Operational Research, 165(3), 610-624.

Ambrosino, D., Sciomachen, A., & Scutellà, M. G. (2009). A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem. Computers & Operations Research, 36(2), 442-460.

Balakrishnan, A., Ward, J. E., & Wong, R. T. (1987). Integrated facility location and vehicle routing models: Recent work and future prospects. American Journal of Mathematical and Management Sciences, 7(1), 35-61.

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

Bruns, A., Klose, A., & St?hly, P. (2000). Restructuring of Swiss parcel delivery services. OR-Spektrum, 22(2), 285-302.

Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 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.

Feo, T. A., & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2), 109-133.

Glover, F., & Laguna, M. (1997). Tabu search (Vol. 22). Boston: Kluwer academic publishers.

Hamidi, M., Farahmand, K., & Sajjadi, S. R. (2011). Modeling a Four-Layer Location-Routing Problem. In Proceedings of the 2011 IAJC-ASEE International Conference, Hartford, CT, USA.

Hamidi, M., Farahmand, K., & Sajjadi, S. R. (2012a). Modeling a four-layer location-routing problem. International Journal of Industrial Engineering Computations, 3(1), 43-52.

Hamidi, M., Farahmand, K., Sajjadi, S. R., & Nygard, K. E. (2012b). A hybrid GRASP-tabu search metaheuristic for a Four-Layer Location-Routing Problem. International Journal of Logistics Systems and Management, 12(3), 267-287.

Laporte, G. (1988). Location-routing problems, in: Golden, B. L., Assad, A. A., Vehicle Routing: Methods and Studies, North-Holland, Amsterdam. 163-198.

Larsen, R.C., & Odoni, A.R. (2007). Urban operation research: logistical and transportation planning methods (2nd edition). Dynamic Ideas Belmont, Massachusetts.

Lee, J. H., Moon, I. K., & Park, J. H. (2010). Multi-level supply chain network design with routing. International Journal of Production Research, 48(13), 3957-3976.

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.

May, M. D., & Tu, C. Y. (2008, December). Location-routing based dynamic vehicle routing problem for express pick-up service. In IEEE International Conference on Industrial Engineering and Engineering Management, 2008. IEEM 2008. (pp. 1830-1834). IEEE.

Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1), 1-15.

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

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

Rego, C. (2001). Node-ejection chains for the vehicle routing problem: Sequential and parallel algorithms. Parallel Computing, 27(3), 201-222.

Resende, M. G., & Ribeiro, C. C. (2003). Greedy randomized adaptive search procedures. In Handbook of metaheuristics (pp. 219-249). Springer US.

Sajjadi, S.R., Hamidi, M., Farahmand, K., & Khiabani, V. (2011). A greedy heuristic algorithm for the capacitated location-routing problem. In Proceedings of the 2011 Industrial Engineering Research Conference (IERC), Reno, NV, USA.

The VRP Web, viewed 12 August 2013, http://neo.lcc.uma.es/radi-aeb/WebVRP/index.html

Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.

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(2), 288-299.