Implementación de planos de corte para el problema de ruteo de vehículos con conflictos por vértices

Abstract

Estudiamos en este trabajo el problema de ruteo de vehículos con conflictos por vértices (VRPVC), donde se combina el problema clásico de ruteo de vehículos (VRP) con el de coloreo de vértices de un grafo (VCP). El VRPVC consiste en determinar un conjunto de rutas para una flota de vehículos de manera tal de visitar a todos los clientes de un conjunto predeterminado (i.e., VRP) respetando la restricción adicional que impide que ciertos pares de clientes sean visitados por el mismo vehículo. Estos problemas surgen en diversos escenarios reales, como por ejemplo en la entrega de productos a clientes, donde la imposibilidad de ciertos productos para viajar en un mismo vehículo se debe a diversas restricciones como por ejemplo, no mezclar productos alimenticios con productos de limpieza, o productos que no toleran los mismos niveles de refrigeración. En este trabajo formulamos modelos de programación lineal entera para el VRPVC, combinando características de formulaciones existentes para VRP y VCP. Utilizamos como base para la construcción de nuestras formulaciones dos modelos clásicos de la literatura de VCP, así como dos modelos de VRP que se diferencian por la manera de eliminar subtours en las soluciones. De los modelos de VCP tomamos el modelo estandár y el de representantes asimétrico y de VRP, la formulación two-index de Laporte et al. que elimina subtours mediante una familia exponencial de desigualdades válidas y la formulación MTZ de Miller et al. Siguiendo esta misma línea, analizamos desigualdades válidas conocidas para los distintos modelos de VRP y VCP de la literatura, como las desigualdades Comb propuesta por Chvátal y Grótschel y Padberg y las Clique que plantearon Méndez-Díaz y Zabala. Analizamos la validez de estas desigualdades en los modelos de VRPVC y presentamos también nuevas familias de desigualdades válidas para algunos de los modelos propuestos. Implementamos algoritmos de separación para estas desigualdades (tanto las nuevas como las existentes) y evaluamos empíricamente el uso de las mismas mediante una experimentación computacional. Utilizamos para ello tanto instancias aleatorias como generadas a partir de instancias existentes en la literatura de VRP y VCP (i.e., adaptamos al VRPVC).