Étude de la séparation des inégalités valides pour le problème de tournées de véhicules avec plusieurs dépôts

Le problème de tournées de véhicules avec plusieurs dépôts et des dates fixes pour les trajets (nommé MDVSP) est un des problèmes les plus importants en optimisation combinatoire; le MDVSP est un problème NP-complet. Dans le présent mémoire nous présentons un algorithme de type « Branch-and-Cut » pour la résolution du MDVSP. Notre algorithme combine la méthode de séparation et évaluation progressive et une procédure de séparation des inégalités valides, qui consiste à détecter certains trous impairs et à les lifter. Nous présentons aussi les résultats des tests effectués et l'analyse des comparaisons entre notre algorithme et les méthodes utilisées par le logiciel CPLEX.\ud ______________________________________________________________________________ \ud MOTS-CLÉS DE L’AUTEUR : Le problème de tournées de véhicules avec plusieurs dépôts, séparation des inégalités valides, trous impairs, algorithme de « Branch-and-Cut » pour la résolution du MDVS