Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests

Parcel services route vehicles to pick up parcels in the service area. Pickup requests occur dynamically during the day and are unknown before their actual request. Because of working hour restrictions, service vehicles only have a limited time to serve dynamic requests. As a result, not all requests can be confirmed. To achieve an overall high number of confirmed requests, dispatchers have to budget their time effectively by anticipating future requests. To determine the value of a decision, i.e., the expected number of future confirmations given a point of time and remaining free time budget, we present an anticipatory time budgeting heuristic (ATB) drawing on methods of approximate dynamic programming. ATB frequently simulates a problem’s realization to subsequently approximate the values for every vector of point of time and free time budget to achieve an approximation of an optimal decision policy. Since the number of vectors is vast, we introduce the dynamic lookup table (DLT), a general approach adaptively partitioning the vector space to the approximation process. Compared with state-of-the-art benchmark heuristics, ATB allows an effective use of the time budget resulting in anticipatory decision making and high solution quality. Additionally, the DLT significantly strengthens and accelerates the approximation process. The online appendix is available at https://doi.org/10.1287/trsc.2016.0719 .