Un modelo compacto de programación lineal entera mixta para el Location-or-Routing Problem.

Abstract

El Location-or-Routing Problem (LoRP) es una generalización del problema de localización y ruteo de vehículos (Location-Routing Problem, LRP). El objetivo del LRP es minimizar el costo de abrir un subconjunto de depósitos candidatos y el costo de las rutas realizadas desde estos depósitos, con el fin de cubrir a todos los clientes mediante rutas. En el LoRP, la cobertura se puede realizar con un depósito o con una ruta. Así, la función objetivo es la suma del costo de abrir un subconjunto de depósitos candidatos, el costo de las rutas realizadas desde estos depósitos y el costo de cubrir a los clientes con cierto rango de cobertura. La investigación de este problema tiene una gran relevancia, ya que se sitúa en la última milla y es uno de los principales costos dentro de una empresa. Por tanto, este trabajo propone un modelo compacto de programación lineal entera mixta para el LoRP y también, restricciones de refuerzo para mejorar el modelo propuesto. Además, se presenta un Branch & Cut (B&C) que considera desigualdades válidas relacionadas con las subrutas, basadas en la capacidad y la distancia máxima de los vehículos. El rendimiento del modelo y algoritmo propuesto es validado sobre instancias de la literatura. Los resultados muestran que el modelo con restricciones de refuerzo obtiene el mejor rendimiento promedio entre los algoritmos y modelos propuestos. Finalmente, el B&C que sólo considera las restricciones de distancia de subrutas y desigualdades válidas de demanda, obtiene los mejores resultados entre los algoritmos propuestos en promedio.

The Location-or-Routing Problem (LoRP) is a generalization of the Location-Routing Problem (LRP). The LRP objective is to minimize the cost of opening a subset of candidate depots and the routes cost performed from these depots in order to cover all customers via routes. In LoRP, coverage can be achieved with either a depot or a route. Thus, the objective function is the cost sum of opening a subset of candidate depots, the routes cost performed from these depots, and the cost of covering customers within a certain coverage range. Research on this problem is highly relevant as it pertains to the last mile and is one of the major costs within a company. Therefore, this work proposes a compact mixed-integer linear programming model for LoRP and also strength constraints to enhance the proposed model. Additionally, a Branch & Cut (B&C) algorithm is presented that considers valid inequalities related to subroutes based on vehicle capacity and maximum distance. The performance of the proposed model and algorithm is validated on literature instances. The results indicate that the model with strength constraints achieves the best average performance among the proposed algorithms and models. Finally, the B&C algorithm that only considers subroute distance constraints and valid demand inequalities achieves the best average results among the proposed algorithms.