Scientific Program > Talks by Speaker > Ansmann Artur

In this paper, we study the Dynamic Vehicle Routing Problem with Stochastic Customers (DVRPSC), a common problem setting for Courier, Express and Parcel service providers. We focus on the case in which a dispatcher must decide which dynamically occurring customer requests should be confirmed and how to integrate these into the existing tour of a vehicle. The vehicle must serve all confirmed requests and return to its depot within a given time limit; usually, not all requests can be confirmed. In order to confirm a maximum number of requests, anticipation of future requests for a current state's decision is necessary. To allow real-time control, the required calculations need to be conducted offline, often by means of Value Function Approximation (VFA). The calculation's outcome for every state is then stored in aggregated form and can be accessed efficiently in the online execution. Current VFAs for the DVRPSC are not able to integrate any spatial information in their aggregation but solely draw on temporal state attributes. Therefore, in problem settings expressing characteristic spatial distribution of requests, these are not able to anticipate sufficiently. In this paper, we propose Anticipatory Time Budgeting with Spatial Information (ATBS) to close this gap. We compare ATBS to a state-of-the-art VFA of the literature on a set of benchmark instances with varying spatial distribution parameters. Results show that the integration of spatial information is highly beneficial.