Online route planning in response to non-recurrent traffic disturbances

Actual traffic conditions substantially influence the timeliness of home deliveries. Route plans can account for recurrent traffic disturbances since these variations show repetition with respect to time and space of occurrence and corresponding network-wide impact. Non-recurrent disruptions, however, show seemingly random behavior with respect these aspects. To assure a reliable delivery process, route plans should not only adapt to incidents that occur during execution, but also anticipate on future conditions that emerge from these incidents.

In this paper, we propose and evaluate an online re-planning method that reduces the impact of non-recurrent traffic disturbances. We use real-time traffic information to detect incidents and anticipate on future network-wide traffic speeds. We propose and implement three main solution strategies for this Dynamic Vehicle Routing Problem: intra-route switching of trips, intra-route switching of customers, and inter-route helper actions that transfer goods between delivery vehicles.

We evaluate our solution method on a real-world example. We evaluate the proposed solution strategies independently and combined, using different prediction horizons with respect to the network-wide travel speeds. Numerical results show that we can significantly reduce the number of time-window violations using our online solution approach compared to a robust offline method.