Publication:
A relax-and-price heuristic for the inventory-location-routing problem

Thumbnail Image
Files

Files

A relax-and-price heuristic for the inventory-location-routing problem.pdf (487.54 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Guerrero, W. J.C
Prodhon, C.
Velasco, N.
Amaya, C. A.
Abstract (Spanish)
Este artículo considera el problema de diseñar una cadena de suministro asumiendo decisiones de enrutamiento. El objetivo es seleccionar un subconjunto de depósitos para abrir de un conjunto de candidatos, las políticas de inventario para un sistema de dos escalones y el conjunto de rutas para realizar la distribución desde el escalón superior al siguiente por una flota homogénea de vehículos sobre un horizonte finito de planificación considerando la demanda determinista. Para resolver el problema, se propone una partición utilizando una formulación de Dantzig-Wolfe sobre las variables de enrutamiento. Se presenta una hibridación entre generación de columnas, relajación lagrangiana y búsqueda local dentro de un procedimiento heurístico. Los resultados demuestran la capacidad del algoritmo para calcular soluciones de alta calidad y estimar empíricamente la mejora en la función de coste del modelo propuesto hasta en un 9 % en comparación con el enfoque secuencial. Además, el problema de fijación de precios sugerido es una nueva variante del problema del camino más corto con aplicaciones en transporte urbano y telecomunicaciones.
Abstract (English)
This paper considers the problem of designing a supply chain assuming routing decisions. The objective is to select a subset of depots to open from a set of candidates, the inventory policies for a two-echelon system, and the set of routes to perform distribution from the upper echelon to the next by a homogeneous fleet of vehicles over a finite planning horizon considering deterministic demand. To solve the problem, a partition is proposed using a Dantzig–Wolfe formulation on the routing variables. A hybridization between column generation, Lagrangian relaxation, and local search is presented within a heuristic procedure. Results demonstrate the capability of the algorithm to compute high quality solutions and empirically estimate the improvement in the cost function of the proposed model at up to 9% compared to the sequential approach. Furthermore, the suggested pricing problem is a new variant of the shortest path problem with applications in urban transportation and telecommunications.
Extent
20 páginas.
Rights

C 2014 The Authors.

URI: https://repositorio.escuelaing.edu.co/handle/001/1917
Collections

Collections

AI - Centro de Investigación en Manufactura y Servicios – CIMSER
References

Ambrosino, D., Scutella, M.-G., 2005. Distribution network design: New problems and related models. ` European Journal of Operational Research 165, 3, 610–624.

Balcik, B., Beamon, B., Krejci, C., Muramatsu, K., Ramirez, M., 2010. Coordination in humanitarian relief chains: Practices, challenges and opportunities. International Journal of Production Economics 126, 22–34.

Beasley, J.E., 1993. Lagrangean relaxation. In Reeves, C.R. (ed.) Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, New York, pp. 243–303.

Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., Wolfler-Calvo, R., 2011. A branch-and-cut method for the capacitated location-routing problem. Computers and Operations Research 38, 6, 931–941.

Daskin, M., Snyder, L., Berger, R., 2005. Facility location in supply chain design. Logistics Systems: Design and Optimization 1, 39–65.

Feillet, D., 2010. A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR: A Quarterly Journal of Operations Research 8, 407–424.

Geoffrion, A., 1974. Lagrangian relaxation for integer programming. Mathematical Programming Study 2, 82–114.

Guerrero, W., Prodhon, C., Velasco, N., Amaya, C., 2013a. Hybrid heuristic for the inventory location-routing problem with deterministic demand. International Journal of Production Economics 146, 1, 359–370.

Guerrero, W., Velasco, N., Prodhon, C., Amaya, C., 2013b. On the generalized elementary shortest path problem: a heuristic approach. Electronic Notes in Discrete Mathematics 41, 503–510.

Hansen, P., Mladenovic, N., 2003. Variable neighborhood search. In Glover, F., Kochenberger, G.A. (eds) Handbook of Metaheuristics, Kluwer, Boston, MA, pp. 145–184.

Javid, A.A., Azad, N., 2010. Incorporating location, routing and inventory decisions in supply chain network design. Transportation Research Part E: Logistics and Transportation Review 46, 5, 582–597.

Kallehauge, B., Larsen, J., Madsen, O.B.G., 2006. Lagrangian duality applied to the vehicle routing problem with time windows. Computers and Operations Research 33, 5, 1464–1487.

Liu, S.C., Lee, S.B., 2003. A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration. The International Journal of Advanced Manufacturing Technology 22, 941–950.

Liu, S.C., Lin, C.C., 2005. A heuristic method for the combined location routing and inventory problem. The International Journal of Advanced Manufacturing Technology 26, 372–381.

Manzini, R., 2012. A top-down approach and a decision support system for the design and management of logistic networks. Transportation Research Part E: Logistics and Transportation Review 48, 6, 1185–1204.

Melo, M.T., Nickel, S., da Gama, F.S., 2009. Facility location and supply chain management: a review. European Journal of Operational Research 196, 2, 401–412.

Mete, H.O., Zabinsky, Z.B., 2010. Stochastic optimization of medical supply location and distribution in disaster management. International Journal of Production Economics 126, 1, 76–84.

Nishi, T., Isoya, Y., Inuiguchi, M., 2011. An integrated column generation and lagrangian relaxation for solving flowshop problems to minimize the total weighted tardiness. International Journal of Innovative Computing, Information and Control 7, 11, 6453–6471.

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., Wolfer-Calvo, R., 2006. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR: A Quarterly Journal of Operations Research 4, 221–238.

Prodhon, C., Prins, C., 2014. A survey of recent research on location-routing problems. European Journal of Operational Research. In Press. doi: http://dx.doi.org/10.1016/j.ejor.2014.01.005

Raidl, G., Puchinger, J., 2008. Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. Hybrid Metaheuristics 114, 31–62.

Sajjadi, S.R., Cheraghi, S.H., 2011. Multi-products location-routing problem integrated with inventory under stochastic demand. International Journal of Industrial and Systems Engineering 7, 4, 454–476.

Salhi, S., Rand, G.K., 1989. The effect of ignoring routes when locating depots. European Journal of Operational Research 39, 2, 150–156.

Shen, Z.-J.M., Qi, L., 2007. Incorporating inventory and routing costs in strategic location models. European Journal of Operational Research 179, 2, 372–389.

Wagner, H.M., Whitin, T.M., 1958. Dynamic version of the economic lot size model. Management Science 5, 1, 89–96.