Pro-Active Strategies in Online Routing

In this paper, we summarize the basic ideas of recent approaches for the efficient controlling of urgent delivery processes in real-time. As in real-world applications the requests to be serviced the same day are usually unknown and will occur dynamically, such delivery processes possess a considerable degree of dynamism that has to be handled by a real-time approach. For this purpose, the transportation plan that is already in execution is continuously adapted by applying suitable optimization approaches according to all decisions that are not implemented. Due to the assumed urgency of the considered requests, the aim of these approaches is to minimize the total weighted request response times in order to minimize resulting customer inconveniences. Through the exploitation of past request data, stochastic knowledge about future request occurrences is derived that enables significant reductions of the request response times if the given data possesses a certain degree of diversity. Furthermore, empirical analyses reveal that the degree of structural diversity enables reliable forecasts concerning the positive impact of integrating stochastic knowledge derived from the given past request data. More recently, this approach has been extended for identifying recurring request patterns in real time in order to improve the quality of forecasts concerning future request arrivals. In addition to that, it has been shown that frequent en route diversions executed during iterative plan adaptations can be strongly limited without significantly worsening the attained request response times. Note that an unlimited exhaustive usage of en route diversions may cause an increase of accidents due to driver distractions.