Solving the Assignment of Customers to Trucks and Visit Days in a Periodic Routing Real-World Case

Solución a la asignación de clientes a camiones y días de visita en un caso real de ruteo periódico

Introducción: Este trabajo propone un modelo y dos algoritmos heurísticos para asignar clientes a camiones y días de visita como una primera fase en la solución de un problema de ruteo, que está estrechamente relacionado con el PVRP (Periodic Vehicle Routing Problem), aunque una decisión estratégica de la compañía impone la restricción adicional, de que cada cliente debe ser siempre visitado por el mismo camión. Métodos: el modelo propuesto tiene como objetivo agrupar a los clientes que son visitados el mismo día por el mismo camión lo más cerca posible por medio de clustering basado en centroides. La primera heurística propuesta tiene una etapa constructiva y tres heurísticas subyacentes de mejora, mientras que la segunda usa un algoritmo de programación lineal exacto. Resultados: los algoritmos son evaluados por instancias tomadas de la literatura y generadas, teniendo en cuenta las características presentadas en el caso real abordado.

1. INTRODUCCIÓN

Una estrategia común para resolver problemas de enrutamiento es la partición del problema en diferentes fases. Por ejemplo, en el VRP (problema de enrutamiento de vehículos) se utiliza ampliamente la estrategia "cluster first-route second", donde cada cluster representa los clientes asignados a un camión. En [1], los clusters se crearon resolviendo un GAP (problema de asignación generalizado), mientras que los algoritmos de barrido presentados en [2] y [3] tienen una primera fase de clustering y una segunda fase de resolución de un TSP (traveling salesman problem) para cada cluster. En [4], se realizan dos fases de clustering antes del enrutamiento. Para resolver el MDVRP (problema de enrutamiento de vehículos de múltiples depósitos), en [5] y [6], se realiza una fase de agrupación para asignar los clientes a los depósitos. Para el SB-VRP (problema de enrutamiento de vehículos con caja móvil), [7] crea clusters independientes compuestos por clientes y ubicaciones de intercambio. Para el PVRP (problema de enrutamiento periódico de vehículos), es habitual resolver una fase de asignación asignando los días de visita a los clientes y luego resolver un VRP para cada día. En [8], los clientes se asignan a los días haciendo clusters compactos para cada día utilizando tres medidas estadísticas. En [9], la asignación de los clientes a los días se realiza adaptando el GAP de [1] al PVRP, mientras que en [10] y [11] se proponen modelos lineales enteros para asignar los clientes a los días de visita para minimizar la demanda máxima en cada día, pero no se consideran las coordenadas geográficas de los clientes. En este trabajo, reunimos las fases de asignación de camiones y días de visita de nuestro problema particular, a las que nos referiremos habitualmente como las fases de agrupación y asignación; en consecuencia, cada agrupación está asociada a un camión.