TITRE : Stochastic and Robust Vehicle Routing with Deadlines
CONFÉRENCIER : Yossiri Adulyasak, Massachusetts Institute of Technology (MIT), États-Unis,
DATE et ENDROIT : 11 octobre 2013, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau
RÉSUMÉ : This study considers the vehicle routing problem with deadlines (VRP-D) under travel time uncertainty in the contexts of stochastic and robust optimization. This problem concerns the routing of a fleet of vehicles to serve a set of customers where deadlines are imposed at a subset of customers. In the stochastic VRP-D, the travel times along the arcs are characterized by probability distributions and the objective is to minimize the expected number of deadline violations. In the robust VRP-D, the exact distribution of travel time is unknown and some information such as minimum, maximum and mean values is available. The objective of this problem is to optimize a performance measure, called lateness index, which represents the risk of violating the deadlines. We introduce formulations that can be used to solve the problems with multiple capacitated vehicles and propose algorithms based on a branch- and-cut framework. The experiments show that these approaches provide substantial improvements in computational efficiency compared to the approaches in the literature. For the stochastic approach, instances with a very large number of scenarios can be solved efficiently. Finally, we provide a computational comparison to evaluate the solution quality of the stochastic and robust VRP-Ds. The results show that the robust VRP-D provides competitive results compared to those obtained by the stochastic VRP-D, while the robust VRP-D is much less sens itive to the distributional uncertainty.