Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits

Justin C. Goodson; Jeffrey W. Ohlmann; Barrett W. Thomas

doi:10.1287/opre.1120.1127

Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits

Justin C. Goodson¹; Jeffrey W. Ohlmann²; Barrett W. Thomas²

¹ Department of Operations and Information Technology Management, John Cook School of Business, Saint Louis University, St. Louis, Missouri 63108 · ² Department of Management Sciences, Tippie College of Business, University of Iowa, Iowa City, Iowa 52242

Operations Research 2013

We develop a family of rollout policies based on fixed routes to obtain dynamic solutions to the vehicle routing problem with stochastic demand and duration limits (VRPSDL). In addition to a traditional one-step rollout policy, we leverage the notions of the pre- and post-decision state to distinguish two additional rollout variants. We tailor our rollout policies by developing a dynamic decomposition scheme that achieves high quality solutions to large problem instances with reasonable computational effort. Computational experiments demonstrate that our rollout policies improve upon the performance of a rolling horizon procedure and commonly employed fixed-route policies, with improvement over the latter being more substantial.

DOI: 10.1287/opre.1120.1127
Volume: 61 (1)
Pages: 138-154
Language: en
Export: BibTeX
Sources: crossref