Optimisation de tournées de véhicules avec contrainte de fragilité

Dans le cadre du transport maritime, les marchandises sont empilées verticalement selon leur ordre de collecte ou de livraison. La nature des marchandises peut être très différente, par exemple dans le cas du ravitaillement des villes dans le nord du Canada, il faut amener des voitures, de l'essence, des médicaments ou du matériel de construction. Ces différentes marchandises n'ont pas la même masse et il faut donc faire attention à la manière dont sont superposées ces marchandises. Des barils d'essence transportés sur une voiture risquent de rendre la voiture inutilisable et les bidons d'essence aussi par la même occasion. Ces problèmes de marchandises légères et lourdes ne pouvant être superposées se retrouvent également lors du chargement de remorques à partir de chariots élévateurs amenant des palettes. Ce mémoire cherche à améliorer la construction des tournées de véhicules en tenant compte de cette contrainte de fragilité. En partant du problème connu de tournées de véhicules avec fenêtres de temps et de capacité, ce mémoire va développer des méthodes pour respecter la contrainte de fragilité et l'intégrer aux algorithmes de type Branch-Price-and-Cut existants le plus efficacement possible. La plupart des modifications se feront sur les algorithmes d'étiquetage durant la génération des routes. Il convient que les algorithmes doivent être capables de résoudre la plupart des instances classiques pour que la solution proposée soit applicable dans la vie réelle. À cette fin, des tests seront menés sur des instances classiques et interprétés. Les méthodes proposées dans les chapitres 4 et 5 permettent de générer des routes respectant la contrainte de fragilité en regardant uniquement la séquence d'entrée des marchandises et sans s'intéresser aux dispositions possibles dans la cale. Ces résultats théoriques sont ensuite intégrés à un algorithme existant afin de construire des algorithmes respectant la contrainte de fragilité. Le chapitre 4 se concentre sur le cas des piles de hauteur 2 tandis que le chapitre 5 s'intéresse au cas général, sans connaitre la hauteur des piles a priori. Les résultats théoriques permettent d'obtenir des algorithmes efficaces comme le montrent les résultats expérimentaux obtenus dans les chapitres 4 et 5. Ces résultats expérimentaux sont des tests effectués avec nos algorithmes et une analyse des résultats selon différents paramètres. Ces analyses mettront en valeur l'intérêt et les spécificités de notre problème. Des comparaisons seront également effectuées avec d'autres algorithmes pour montrer la pertinence de notre recherche.