Real-time schedule adjustments for conflict-free vehicle routing

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 make things more complex, the uncertainty affecting both travel times and machine ready times often results in vehicle delays or anticipations that require real-time modifications to the fleet nominal plan. In this paper, the determination of such modifications (schedule adjustment problem in CFVRPs) is modeled as a sequential decision problem for which we develop a tailored fast exact algorithm suitable for any objective function that is non-decreasing in the arrival times. Computational results show that optimal solutions can be found within at most 3.3 milliseconds for instances with up to 300 vehicles with improvements of various performance measures up to 74% compared to state-of-the-art solution algorithms.