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.