Journal
TRANSPORTATION SCIENCE
Volume 52, Issue 1, Pages 20-37Publisher
INFORMS
DOI: 10.1287/trsc.2016.0719
Keywords
dynamic vehicle routing; stochastic customer requests; time budget; subset selection; approximate dynamic programming; dynamic lookup table
Categories
Funding
- Deutsche Forschungsgemeinschaft Research Training Group [DFG RTG 1931]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available