Place Sainte Barbe 2/L5.02.01
Assistant de recherche
Année Label Institution 2013 Master en sciences informatiques, à finalité spécialisée Université catholique de Louvain 2019 Dosteur en sciences de l'ingénieur et technologies Université catholique de Louvain
Assistant de cours / Teaching assistant
Cours actuels / Present courses
- LINGI 1123 : Calculabilité et Complexité — Computability and complexity theory (Pr. Yves Deville)
- LINGI 2261 : Artificial Intelligence: representation and reasoning (Pr. Yves Deville)
- LINGI 2255 : Software Engineering Project (Pr. Kim Mens)
Passé / Past courses
- LSINF 1225 : Conception Orientée Objet et Gestion de Données — Object oriented programming and databases (Pr. Kim Mens)
- LINGI 1113 : Systèmes Informatiques 2 (Pr. Marc Lobel)
PhD thesis: Models and Algorithms for online Vehicle Routing Problems
Applications of online vehicle routing in the society are manyfold, from intelligent on demand public transportation to sameday delivery services and responsive home healthcare. Given a fleet of vehicles and a set of customers, each being potentially able to request a service at any moment, the current thesis aims at answering the following question. Provided the current state at some moment of the day, which are the best vehicle actions such that the expected number of unsatisfied requests is minimized by the end of the operational day?
We assume a stochastic knowledge on each operational problem we tackle, such as the probability that customer request arise at a given location and a given time of the day. By using techniques from operations research and stochastic programming, we are able to build and solve mathematical models that compute near-optimal anticipative actions, such as preventive vehicle relocations, in order to minimize the overall expected costs.
Generally speaking, this thesis explores some fundamentals of optimization under uncertainty. By integrating a stochastic component into the models to be optimized, it is in fact possible to create anticipation.
Keywords: online combinatorial optimization, stochastic programming, vehicle routing problems
Supervisor: Pr. Yves Deville
Side research projects: Robust Operations Management for space exploration
Unlike most classical scheduling problems, operations in a space mission must be planned days ahead. Complex decision chains and communication delays prevent schedules from being arbitrarily modified, hence online reoptimisation approaches are usually not appropriate. The problem of scheduling a set of operations in a constrained context such as space missions is not trivial, even in its classical deterministic version. It should be seen as a generalization of the well-known NP-complete job-shop scheduling problem, which has the reputation of being one of the most computationally demanding. The development of the a priori schedule of the Voyager 2 space probe, involving around 175 experiments, required 30 people during six months. Nowadays, hardware and techniques have evolved and it is likely that a couple of super-equipped (i.e. with a brand new laptop) human brains may suffice in that specific case. Yet, the problems and requirements have evolved too. Instead of the single machine Voyager 2, space missions have to deal with teams of astronauts.
Computing an optimal schedule becomes significantly less attractive as problem data, such as the processing time of each operation, are different from their predicted values. In a constrained environment with shared resources and devices, such deviations can propagate to the remaining operations, eventually leading to global infeasibility. Even provided only one non-human operator, uncertainty may be of significant impact. For instance, the future M2020 planetary rover will be equipped with an onboard scheduler, designed to operate under processing time uncertainty. One of my favorite hobby is to investigate, based on the real space missions case studies, the impact of stochastic robust modeling against classical deterministic approaches on the reliability of a priori mission planning.
Keywords: robust optimization, stochastic programming, planning and scheduling problems
Saint-Guillain, Michael ; Paquay, Célia ; Limbourg, Sabine. Time-Dependent Stochastic Vehicle Routing Problem with Random Requests: Application to online police patrol management in Brussels. In: European Journal of Operational Research, (2020). doi:10.1016/j.ejor.2020.11.007 (Accepté/Sous presse).
Perboli, Guido ; Rosano, Mariangela ; Saint-Guillain, Michael ; Rizzo, Pietro. Simulation–optimisation framework for City Logistics: an application on multimodal last-mile delivery. In: IET Intelligent Transport Systems, (2018). doi:10.1049/iet-its.2017.0357.
Saint-Guillain, Michael ; Stegun Vaquero, Tiago ; Agrawal, Jagriti ; Chien, Steve. Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions. Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) (Yokohama, Japan, du 11/7/2020 au 17/7/2020). In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, 2020. 9780999241165. doi:10.24963/ijcai.2020/576.
Saint-Guillain, Michael. Robust Operations Management on Mars. 29th International Conference on Automated Planning and Scheduling (ICAPS19) (Berkeley, CA, USA, du 11/07/2019 au 15/07/2019). In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, (2019).
Saint-Guillain, Michael ; Solnon, Christine ; Deville, Yves. The Static and Stochastic VRP with Time Windows and both random Customers and Reveal Times. EvoApplications 2017. In: Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part II, 2017. 978-3-319-55792-2, p. 110-127. doi:10.1007/978-3-319-55792-2_8.
Saint-Guillain, Michael ; Solnon, Christine ; Deville, Yves. Un nouveau VRPTW static et stochastique: vers une modélisation en deux étapes plus réaliste. Treizièmes journées Francophones de Programmation par Contraintes (Accepté/Sous presse).
Saint-Guillain, Michael ; Papavasiliou, Anthony ; Deville, Yves ; Solnon, Christine. The Static and Stochastic VRP with Time Windows and both random Customers and Reveal Times (abstract). XIV International Conference on Stochastic Programming (Buzios, Brezil, du 24/06/2016 au 01/01/2017).
Saint-Guillain, Michael ; Deville, Yves ; Solnon, Christine. A Multistage Stochastic Programming Approach to the Dynamic and Stochastic VRPTW. Twelfth International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR'15) (Barcelone, Espagne). doi:10.1007/978-3-319-18008-3_25.
Saint-Guillain, Michael ; Deville, Yves ; Solnon, Christine. Une approche basée sur la programmation stochastique multi-étapes pour résoudre le VRPTW dynamique et stochastique. Onzièmes Journées Francophones de Programmation par Contraintes (JFPC 2015).
Saint-Guillain, Michael. Models and algorithms for online stochastic vehicle routing problems, prom. : Deville, Yves ; Solnon, Christine, 13/09/2019.
Saint-Guillain, Michael ; Christine Solnon ; Deville, Yves. Progressive Focus Search for the Static and Stochastic VRPTW with both Random Customers and Reveal Times, 2019. 42 p.