Una heurística con una garantía de rendimiento para el problema de enrutamiento de vehículos de entrega partida restringido por mercancías

Resumen El problema de enrutamiento de vehículos de entrega partida restringido por mercancías (C‐SDVRP) es un problema de enrutamiento donde las demandas de los clientes están compuestas por múltiples mercancías. Una flota de vehículos con capacidad debe atender las demandas de los clientes de manera que minimice el costo total de enrutamiento. Los vehículos pueden transportar cualquier conjunto de mercancías y se permite visitar a los clientes múltiples veces. Sin embargo, la demanda de una sola mercancía debe ser entregada por un solo vehículo. En este trabajo, desarrollamos una heurística con una garantía de rendimiento para resolver el C‐SDVRP. La heurística propuesta se basa en una formulación de cobertura de conjuntos, donde las variables exponencialmente muchas corresponden a rutas. Primero, un subconjunto de las variables se obtiene resolviendo la relajación lineal de la formulación mediante un enfoque de generación de columnas que incorpora una nueva heurística de precios destinada a reducir el tiempo computacional. Resolver la relajación lineal da un límite inferior válido que se utiliza como garantía de rendimiento para la heurística. Luego, ideamos una heurística maestra restringida para proporcionar buenos límites superiores: la formulación se restringe al subconjunto de variables encontradas hasta ahora y se resuelve como un programa entero con un solucionador comercial. Se aplica una búsqueda local basada en un operador de programación matemática para mejorar la solución. Probamos el algoritmo heurístico en instancias de referencia de la literatura. La comparación con las heurísticas de vanguardia para resolver el C‐SDVRP muestra que nuestro enfoque mejora significativamente el tiempo de solución, mientras mantiene una calidad de solución comparable y mejora algunas de las soluciones mejor conocidas. Además, nuestro enfoque es capaz de resolver grandes instancias con 100 clientes y seis mercancías, y también proporciona límites inferiores de muy buena calidad. Además, una instancia del C‐SDVRP puede transformarse en una instancia de CVRP simplemente duplicando cada cliente tantas veces como las mercancías solicitadas y asignando como demanda la demanda de la única mercancía. Por lo tanto, comparamos heurísticas para el C‐SDVRP con la heurística de vanguardia para el Problema de Enrutamiento de Vehículos con Capacidad (CVRP). Este último enfoque resultó tener el mejor rendimiento. Sin embargo, nuestro enfoque proporciona soluciones de calidad comparable y tiene el interés de ofrecer una garantía de rendimiento.