5.2 Problèmes de calcul de tournées de
véhicules
5.2.1 Du problème du Voyageur de Commerce au
problème de Tournées de Véhicules
Le célèbre Problème du Voyageur de
Commerce, ou Traveling Salesman Problem, est un des
problèmes d'optimisation combinatoire les plus connus (voir le chapitre
2 pour plus de détails sur ce problème).
Au cours des années, au vu des progrès
effectués en terme de résolution, ainsi qu'en raison de la
variété des applications aux systèmes de transports, les
chercheurs ont été amenés à proposer de nombreuses
extensions ou variantes du problème du Voyageur de Commerce.
Le problème du Voyageur de Commerce a été
étendu au cas où m voyageurs de commerce doivent visiter
n villes, défini comme le Problème de Voyageurs de
Commerce Multiples ou Multiple Traveling Salesman Problem (mTSP). Ce
problème est très proche du problème de Tournées de
Véhicules ou Vehicle Routing Problem (VRP) pour lequel une
flotte de véhicules est disponible, et chaque véhicule est
limité par les distances qu'il peut parcourir.
Une des extensions les plus étudiées fut ensuite
de considérer les transports de marchandises. Ces marchandises sont
récoltées chez des clients au cours du trajet et ramenées
à un dépôt unique. De plus, les objets ramassés
possèdent un poids et une capacité maximale à ne pas
dépasser est associée à chaque véhicule. L'objectif
est donc d'assigner des clients à des véhicules. Cette extension
est connue sous le nom de problème de Tournées de
Véhicules avec Contraintes de Capacités (Capacited Vehicle
Routing Problem ou CVRP).
À cette extension se rajoutent un certain nombre de
contraintes :
- Contraintes temporelles : la visite des clients peut avoir
lieu uniquement pendant
des fenêtres de temps (Vehicle Routing
Problem with Time Windows ou VRPTW),
- Contraintes de précédence : les marchandises
doivent être transportées d'un lieu vers un autre au lieu
d'être ramenées au dépôt (Pick Up & Delivery
Problem ou PDP),
- Contraintes de chargement : plusieurs objets doivent
être livrés à des clients, en
respectant des contraintes de poids et de surface (ou de volume)
de chargement
du véhicule (Vehicle Routing Problem with Loading
Constraints ou VRPLC).
On peut relever d'autres extensions du TSP dans la
littérature, comme les problèmes avec fractionnement de la
livraison. Dans la version la plus simple connue sous le nom de Split &
Delivery Problem, une visite à un sommet peut ne donner lieu
qu'à une livraison partielle.
Pour chacun de ces problèmes, on distingue
généralement le cas à un seul véhicule, souvent
plus facile et rencontré comme sous-problème du cas à
plusieurs véhicules.
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
En plus de ces contraintes, une classification peut être
faite en se basant sur la distinction entre la nature des données :
- problèmes statiques, pour lesquels l'ensemble des
données est connu avant la résolution du problème,
- problèmes stochastiques, pour lesquels les
données sont définies par une fonction de probabilité,
- problèmes dynamiques, pour lesquels de nouvelles
données apparaissent au cours du temps.
| 
