Conflict-Free Vehicle Routing Problems (CFVRPs) arise in manufacturing, transportation and logistics applications where Automated Guided Vehicles (AGVs)are utilized to move pallets and containers. A peculiar feature of these problems is that collision avoidance among vehicles must be considered explicitly. To makethings more complex, the uncertainty affecting both travel times and machine ready times often results in vehicle delays or anticipations that require real-timemodifications to the fleet nominal plan. In this paper, we model the CFVRP schedule adjustment problem as a sequential decision problem for which we developa tailored fast exact algorithm suitable for any objective function that is non-decreasing in the arrival times. Computational results show that optimalsolutions can be found within 1 millisecond for instances with up to 300 vehicles with improvements of various performance measures up to 74% compared to state-of-the-art solution algorithms.
Authors: Tommaso Adamo; Gianpaolo Ghiani; Emanuela Guerriero