Dans ce mémoire, nous présentons une méthode de résolution du problème de tournées de véhicules grâce à une approche polyèdrale. Un état de l'art est fait sur la connaissance du polyèdre correspondant aux solutions de ce probleme et de nouvelles inégalités valides (et induisant des facettes) sont présentées pour ce polyèdre. Nous décrivons ensuite des heuristiques pour la séparation des contraintes les plus importantes ainsi qu'un algorithme de "Branchement et Coupe" qui nous permet d'améliorer les résultats connus pour la résolution exacte du problème de tournées.
Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00005026 |
Date | 12 June 1995 |
Creators | Augerat, Philippe |
Source Sets | CCSD theses-EN-ligne, France |
Language | French |
Detected Language | French |
Type | PhD thesis |
Page generated in 0.0016 seconds