Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$22,000.00

Optimisation des tournées de service

FY 2015-16

Summary
Les problèmes de tournées de service consistent à déterminer les itinéraires d'une flotte de véhicules pour couvrir les demandes de service sur un réseau. Nous nous intéressons aux problèmes où les services requis sont réalisés le long des arêtes ou arcs d'un réseau routier. Ces problèmes sont appelés problèmes de tournées sur les arcs (arc routing problems). Des exemples d'application de ces problèmes sont : la livraison du courrier par les facteurs, la collecte des ordures, l'épandage de sel de déglaçage sur un réseau routier, le déneigement, le relevé de compteurs par véhicules munis de lecteur à distance, etc. L'objectif de ce projet de recherche est de développer des méthodes pour résoudre des problèmes de tournées sur les arcs en prenant en compte des aspects stochastiques et des aspects dynamiques. Les aspects stochastiques portent sur la nature incertaine de certaines données, par exemple les temps de service sur les arcs ou les temps de déplacement sur le réseau. Les aspects dynamiques portent sur la réaction en temps réel à des aléas survenant au cours du déroulement des tournées planifiées, comme des retards dû au trafic, des incidents, des bris d'équipements, des changements météo, ou autres perturbations. Les nouvelles technologies informationnelles permettent d'obtenir en temps réel des quantités importantes de données sur l'état des systèmes logistiques. La démarche scientifique repose sur la modélisation mathématique et le développement de nouveaux algorithmes combinant les méthodes d'optimisation mathématique et les techniques informationnelles les plus récentes telles que les systèmes d'information géographiques (SIG), les systèmes de positionnement global (GPS) et les systèmes d'information météo. Du côté algorithmique, les aspects stochastiques seront traités par des approches de programmation stochastique et par des approches d'optimisation robuste. Les aspects dynamiques seront traités par des approches heuristiques, mieux adaptées à la gestion des systèmes en temps réel et compte tenu de la nécessité d'optimiser en très peu de temps. Le contexte d'application est l'entretien des réseaux routiers et se divise en deux volets : 1. Les activités de surveillance du réseau par des véhicules de patrouille. 2. L'entretien hivernal (épandage d'abrasif et déneigement) du réseau routier. L'ampleur des budgets consacrés au secteur de l'entretien des réseaux routiers à l'échelle du pays et l'impact sur l'environnement justifient une optimisation de ces opérations. Les travaux prévus visent à doter les gestionnaires d'outils puissants d'analyse. Les travaux algorithmiques devraient également bénéficier à la communauté des chercheurs en optimisation. Des développements tant sur les aspects de modélisation, de méthodologie de solution que d'intégration réussie de technologies sont escomptés.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-03909
Name nom
Langevin, André
Department département
Mathématiques et génie industriel - Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
1603
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Logistics
Research subject fr
Logistique
Partie
1
Nb partie
5
Application title
Optimisation des tournées de service
Keyword
NSERC
Application summary
<p>Les problèmes de tournées de service consistent à déterminer les itinéraires d'une flotte de véhicules pour couvrir les demandes de service sur un réseau. Nous nous intéressons aux problèmes où les services requis sont réalisés le long des arêtes ou arcs d'un réseau routier. Ces problèmes sont appelés problèmes de tournées sur les arcs (arc routing problems). Des exemples d'application de ces problèmes sont : la livraison du courrier par les facteurs, la collecte des ordures, l'épandage de sel de déglaçage sur un réseau routier, le déneigement, le relevé de compteurs par véhicules munis de lecteur à distance, etc. </p> <p> L'objectif de ce projet de recherche est de développer des méthodes pour résoudre des problèmes de tournées sur les arcs en prenant en compte des aspects stochastiques et des aspects dynamiques. Les aspects stochastiques portent sur la nature incertaine de certaines données, par exemple les temps de service sur les arcs ou les temps de déplacement sur le réseau. Les aspects dynamiques portent sur la réaction en temps réel à des aléas survenant au cours du déroulement des tournées planifiées, comme des retards dû au trafic, des incidents, des bris d'équipements, des changements météo, ou autres perturbations. Les nouvelles technologies informationnelles permettent d'obtenir en temps réel des quantités importantes de données sur l'état des systèmes logistiques. </p> <p> La démarche scientifique repose sur la modélisation mathématique et le développement de nouveaux algorithmes combinant les méthodes d'optimisation mathématique et les techniques informationnelles les plus récentes telles que les systèmes d'information géographiques (SIG), les systèmes de positionnement global (GPS) et les systèmes d'information météo. Du côté algorithmique, les aspects stochastiques seront traités par des approches de programmation stochastique et par des approches d'optimisation robuste. Les aspects dynamiques seront traités par des approches heuristiques, mieux adaptées à la gestion des systèmes en temps réel et compte tenu de la nécessité d'optimiser en très peu de temps. </p> <p> Le contexte d'application est l'entretien des réseaux routiers et se divise en deux volets : <br /> 1. Les activités de surveillance du réseau par des véhicules de patrouille. <br /> 2. L'entretien hivernal (épandage d'abrasif et déneigement) du réseau routier. </p> <p> L'ampleur des budgets consacrés au secteur de l'entretien des réseaux routiers à l'échelle du pays et l'impact sur l'environnement justifient une optimisation de ces opérations. Les travaux prévus visent à doter les gestionnaires d'outils puissants d'analyse. Les travaux algorithmiques devraient également bénéficier à la communauté des chercheurs en optimisation. Des développements tant sur les aspects de modélisation, de méthodologie de solution que d'intégration réussie de technologies sont escomptés.<br /> <br /> </p>