The location routing problem with facility sizing decisions

Abstract

The location routing problem (LRP) integrates operational decisions on vehicle routing operations with strategic decisions on the location of the facilities or depots from which the distribution will take place. In other words, it combines the well-known vehicle routing problem (VRP) with the facility location problem (FLP). Hence, the LRP is an NP-hard combinatorial optimization problem, which justifies the use of metaheuristic approaches whenever large-scale instances need to be solved. In this paper, we explore a realistic version of the LRP in which facilities of different capacities are considered, i.e., the manager has to consider not only the location but also the size of the facilities to open. In order to tackle this optimization problem, three mixed-integer linear formulations are proposed and compared. As expected, they have been proved to be cost- and time- inefficient. Hence, a biased-randomized iterated local search algorithm is proposed. Classical instances for the LRP with homogeneous facilities are naturally extended to test the performance of our approach.

El problema de ruta de ubicación (LRP) integra decisiones operativas sobre operaciones de ruta de vehículos con decisiones estratégicas sobre la ubicación de las instalaciones o depósitos desde donde se realizará la distribución. En otras palabras, combina el conocido problema de generación de rutas de vehículos (VRP) con el problema de ubicación de instalaciones (FLP). Por lo tanto, el LRP es un problema de optimización combinatoria NP-duro, lo que justifica el uso de enfoques metaheurísticos siempre que sea necesario resolver instancias a gran escala. En este artículo, exploramos una versión realista del PRL en el que se consideran instalaciones de diferentes capacidades, es decir, el administrador debe considerar no sólo la ubicación sino también el tamaño de las instalaciones a abrir. Para abordar este problema de optimización, se proponen y comparan tres formulaciones lineales enteras mixtas. Como era de esperar, se ha demostrado que son ineficientes en términos de costos y tiempo. Por lo tanto, se propone un algoritmo de búsqueda local iterado aleatorio sesgado. Los ejemplos clásicos del LRP con instalaciones homogéneas se amplían naturalmente para probar el rendimiento de nuestro enfoque.