Chercheur :
Antoine Legrain
Établissement :
Polytechnique de Montréal
Année de concours :
2022-2023
Les services de transport à la demande ont réduit la dépendance aux véhicules personnels et ont offert de nouvelles options de mobilité à divers segments de la population. Récemment, le partage des trajets a été proposé pour les clients utilisant ces services (UberPool, Lyft Shared ou Via par exemple). Ce partage a le potentiel de réduire la congestion, diminuer les émissions de gaz à effet de serre et rendre la mobilité accessible à de nouveaux segments de population en diminuant les prix des voyages.
Ces systèmes se composent de deux parties : des applications mobiles pour les passagers et les conducteurs, et un serveur central qui connecte en temps-réel les utilisateurs. Lorsqu’un trajet n’est pas partagé, l’opérateur central doit faire correspondre la requête d’un passager (une origine, une destination et une heure de départ) avec un chauffeur pour minimiser le temps d’attente. Cependant le partage rend le problème immensément plus complexe car plusieurs demandes peuvent être servies par le même véhicule. L’opérateur central doit également prendre en compte l’ordre dans lequel les passagers sont ramassés et déposés et contrôler le détour effectué. Il doit aussi toujours pouvoir proposer une bonne solution en peu de temps en ré-optimisant le système régulièrement. Cependant, il faut trouver un équilibre entre le temps passé dans la ré-optimisation et le délai entre l’état réel du système et la planification actuelle des itinéraires. Un algorithme est dit instantané si ce délai est négligeable. Les services de transport à la demande ont également des pics de demandes réguliers qui peuvent être anticipés afin de garder un service efficace.
Ce projet vise à développer un algorithme instantané et guidé par les données pour aider les systèmes de transport à la demande en créant des itinéraires plus efficaces. Plus précisément, le projet propose de développer un algorithme basé sur le simplexe en nombres entiers : une méthode exacte qui a la possibilité de redémarrer la recherche à partir d’une solution précédente au lieu de la recommencer à zéro. Cette proposition est ainsi composée de deux sous-objectifs: le premier tentera de modifier ce simplexe pour gérer l’optimisation stochastique et les systèmes dynamiques, tandis que le second vise à tester l’approche sur un ensemble de données public décrivant les trajets historiques en taxi de New York (des milliers de voyages quotidiens). Le projet permettra de faire avancer la recherche fondamentale, de former deux étudiants de cycles supérieurs, de publier 3 articles dans des revues scientifiques prestigieuses, ainsi que de créer des liens avec des agences de transport public.
Enfin, les systèmes de gestion des opérations en ligne deviennent incontournables à l’ère du nuage informatique et des applications mobiles, car ces technologies permettent de résoudre en temps-réel des problèmes qui étaient auparavant résolus quotidiennement. L’approche proposée améliorera l’efficacité de nombreux autres services tels que la livraison de nourriture, la prise de rendez-vous, la gestion des stocks pour ne citer que quelques problèmes d’optimisation complexes qui doivent être résolus en temps-réel.