Modélisation et résolution exacte de problèmes stochastiques de tournées de véhicules

 

Guy Desaulniers

École Polytechnique de Montréal

 

Domaine : structures abstraites

Programme projet de recherche en équipe

Concours 2011-2012

Les problèmes stochastiques de tournées de véhicules (PSTV) sont au coeur des activités liées à la distribution de marchandises pour un grand nombre d'entreprises. Ils consistent à déterminer des routes de véhicules afin de satisfaire à coût minimal les demandes d'un ensemble de clients. De plus, ils prennent en compte l'incertitude sur la valeur de certains paramètres tels que les demandes, les clients à desservir et les temps de parcours/service.

Dans ce projet, nous aborderons les PSTV en utilisant des approches d'optimisation a priori qui proposent de construire des routes a priori en tenant compte de l'incertitude et de les opérer telles que planifiées autant que possible. Nous étudierons les paradigmes de modélisation de programmation stochastique avec recours et de programmation avec contraintes probabilistes.

Les PSTV étant des problèmes complexes, les approches exactes existantes font appel à des modèles relativement simples et permettent de résoudre des problèmes de taille limitée. Les principaux objectifs de ce projet sont :

1- Proposer des modèles de PSTV plus réalistes;
2- Développer des méthodes exactes de résolution efficaces pour les PSTV;
3- Intégrer ces méthodes dans un cadre heuristique pour résoudre des PSTV très complexes ou de grande taille.

En particulier, nous adapterons aux PSTV les plus récents développements méthodologiques introduits pour les problèmes déterministes.