Heuristiques avancées pour les problèmes complexes de tournées de véhicules

 

Michel Gendreau

École Polytechnique de Montréal

 

Domaine : structures abstraites

Programme projet de recherche en équipe

Concours 2013-2014

Les problèmes de tournées de véhicules se retrouvent au cœur des activités de distribution de nombreux produits et services. En Amérique du Nord, les grandes entreprises de commerce au détail, de vente de mobilier et d'électronique réalisent près de 100 millions de livraisons par année, à un coût moyen de 40$ par livraison. Il s'agit donc d'un marché d'environ 4 milliards de dollars.

Par ailleurs, les questions reliées à la confection de tournées sont centrales dans la mise en place de systèmes de logistique urbaine. En dépit de cela, de nombreux problèmes complexes de tournées de véhicules n'ont reçu à ce jour que peu d'attention de la part des chercheurs en transport et en logistique. L'objectif général de ce projet est le développement d'heuristiques à la fine pointe des connaissances actuelles pour des problèmes complexes de tournées de véhicules.

Les travaux envisagés s'appuieront sur une série de développements méthodologiques récents qui ont permis d'améliorer significativement la performance des heuristiques pour les problèmes génériques de tournées de véhicules et certaines de leurs variantes :

  • Les méthodes basées sur une population intelligente et diversifiée,
  • La recherche adaptative à grands voisinages,
  • Les méthodes de séparation locale,
  • Les méthodes basées sur l'apprentissage avant ou pendant la recherche,
  • Les méthodes coopératives et de décomposition par attributs.