Un algoritmo exacto para el problema de ruteo de vehículos asimétrico con restricciones de capacidad

GABRIELA CORSANO

Curitiba

Jornada; VII Jornadas de Jovens Pesquisadores; 1999

Universidade Federal do Paraná

El Problema de Ruteo de Vehículos (VRP) es un problema de optimización combinatoria en el que se busca determinar rutas óptimas para una flota de vehículos establecida en uno o más depósitos, que debe servir a un conjunto de nodos (clientes), de tal manera que cada vehículo empiece y termine su viaje en el depósito y que cada nodo restante sea visitado por exactamente un vehículo. Existe una gran variedad de problemas de ruteo que son modelados de acuerdo a las características que estos tomen de la vida real. En este trabajo se considera un problema de ruteo de vehículos asimétrico con restricciones de capacidad (CVRP). El CVRP es conocido como un problema de la clase NP-hard y tiene aplicaciones prácticas importantes en el campo de distribución física y logística. En este trabajo se desarrolla en detalle un algoritmo de tipo exacto presentado inicialmente por Laporte, Mercure y Nobert (LMN) y analizado posteriormente por Toth y Vigo (TV) que explota una estructura especial del modelo la cual permite resolver problemas de hasta 300 nodos. El problema es resuelto en términos de un esquema de “branch-and-bound” sobre un árbol especial definido por Reglas de Particionado en el cual cada subproblema consiste en un problema de asignación sujeto a algunas restricciones adicionales, el cual recibe el nombre de problema de asignación modificada (MAP). La ventaja de resolver MAPs es que estos poseen una estructura unimodular y por lo tanto una solución entera. Las reglas de particionado van eliminando los subtours ilegales (un subtour es ilegal si se encuentra desconectado del depósito o si la demanda de la ruta sobrepasa la capacidad del vehículo). Se analiza el cálculo de cotas inferiores en los distintos nodos del árbol. El uso de una cota inferior sobre el valor objetivo de cada subproblema reduce el número de MAPs a resolver. También se estudian distintas reglas de particionado, las propiedades de las matrices unimodulares y la resolución de los MAPs por medio del método húngaro. Por último se propone la incorporación de otras restricciones que generan una cota inferior diferente a la propuesta por LMN. En las pruebas realizadas, el valor que toma la cota propuesta en este trabajo es mejor que el encontrado por LMN, lo cual indica que se descartan más subproblemas a resolver, ahorrando tiempo de cálculo y memoria.