Paper Info
Title
An approximate dynamic programming approach for the vehicle routing problem with stochastic demands
Abstract
This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).
Year
DOI
Venue
2009
10.1016/j.ejor.2008.03.023
European Journal of Operational Research
Keywords
Field
DocType
Transportation,Stochastic vehicle routing,Approximate dynamic programming
Dynamic programming,Mathematical optimization,Vehicle routing problem,Monte Carlo method,Computer science,A priori and a posteriori,Filter (signal processing),Algorithm,Cost estimate,Perfect information,Computation
Journal
Volume
Issue
ISSN
196
2
0377-2217
Citations 
PageRank 
References 
63
1.80
25
Authors
2
Name
Order
Citations
PageRank
Clara Novoa1715.34
Robert H. Storer228939.52