Polytechnique Montr�al
February 14, 2023, 11:00, Room GC B1 10 (click here for the map)
Logistics and transport problems, for example routing and scheduling problems, are typically challenging to solve and many of them have been proven to be NP-hard. Moreover, these problems are subject to many operational uncertainties that further increase their complexity. In this talk, I will first introduce decomposition methods, and in particular the column generation algorithm, as well as optimization frameworks to tackle uncertain problems. Then, I will present a recent work where we combined the latter for a classical public transportation scheduling problem, the multi-depot vehicle scheduling problem (MDVSP). In this work, we formulated the reliable MDVSP with stochastic travel time (R-MDVSP-STT) as a bi-objective problem where the objective is to build vehicle schedules that are both cost- and delay-efficient. We modeled the R-MDVSP-STT using a path-based formulation and proposed a heuristic branch-and-price algorithm to solve it. The reliability of a schedule is assessed according to the discrete probability mass function of its trips� departure time. We have developed a method to compute the exact convolution of the latter distributions using the probability mass functions of the travel time and have integrated this information into the stochastic pricing problems. In a test with real data collected by buses running in Montr�al (Canada), we showed that the R-MDVSP-STT provides schedules that are more tolerant to delays for a negligible increase in planned costs.
L�a Ricard is a Ph.D. candidate at the Canada Excellence Research Chair in �Data Science for Real-Time Decision-Making�. They completed a Bachelor degree in Industrial Engineering at Polytechnique Montr�al in 2017. Between their undergraduate and graduate studies, L�a worked as a production planning coordinator at Rolls Royce Canada. In 2018, they started a Master degree in Computer Science at the University of Montr�al and followed a fast track from the Master�s to the Ph.D. in the same program. In 2021, L�a was awarded the Alexander Graham Bell Canada Graduate Scholarships-Doctoral Program from the Natural Sciences and Engineering Research Council of Canada and the HORizon Alma Mater Arts and Sciences fellowship from the Faculty of Arts and Sciences of the University of Montr�al. Their research focuses on mixed integer programming, column generation, stochastic optimization, and machine learning applied to public transportation. Their doctoral research project is carried out under the supervision of Andrea Lodi, Guy Desaulniers, and Louis-Martin Rousseau and in collaboration with GIRO Inc., a world leader in the development of optimization-based software for public transportation.