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

Abstract

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.

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.