Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : A Rollout Policy Framework for Dynamic Programming Approximations to the Vehicle Routing Problem with Stochastic Demand and Duration Limits
CONFÉRENCIER : Barrett Thomas, Department of Management Sciences, University of Iowa, USA
DATE et ENDROIT : 16 février, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau (514-343-7307)
RÉSUMÉ : Traditional rollout policies employ heuristic optimization to approximate value functions in dynamic programs, but can be difficult to obtain for problems with large action spaces. We introduce a rollout policy framework formalizing two new types of rollout policies and show how they can be used in combination to significantly reduce this computational burden. Our analysis provides a general framework for applying heuristic optimization techniques to address large-scale problems. We demonstrate the potential of our method by obtaining high-quality, dynamic solutions for the multi-vehicle routing problem with stochastic demand and duration limits, an important and difficult problem in supply chain management. Our computational results demonstrate that our method can significantly improve upon a method frequently implemented in practice. Moreover, our method is implementable in real time for large problem instances.