Una heurística de asignación generalizada para el enrutamiento de vehículos

Resumen Consideramos una variante común del problema de enrutamiento de vehículos en el que una flota de vehículos entrega productos almacenados en un depósito central para satisfacer los pedidos de los clientes. Cada vehículo tiene una capacidad fija, y cada pedido utiliza una porción fija de la capacidad del vehículo. La decisión de enrutamiento implica determinar cuál de las demandas será satisfecha por cada vehículo y qué ruta seguirá cada vehículo para atender su demanda asignada con el fin de minimizar el costo total de entrega. Presentamos una heurística para este problema en la que se obtiene una asignación de clientes a vehículos resolviendo un problema de asignación generalizada con una función objetivo que aproxima el costo de entrega. Esta heurística tiene muchas características atractivas. Ha superado a las mejores heurísticas existentes en una muestra de problemas de prueba estándar. Siempre encontrará una solución factible si existe, algo que ninguna otra heurística existente puede garantizar. Puede adaptarse fácilmente para acomodar muchas complejidades adicionales del problema. Al variar paramétricamente el número de vehículos en la flota, nuestro método puede usarse para resolver óptimamente el problema de encontrar el tamaño mínimo de flota que pueda atender la demanda especificada de manera factible.