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

In maritime merchandise transport, goods are stocked vertically according to their pick-up or delivery order. The nature of the goods can differ and sometimes heavy items cannot be put above light items. For instance, if you are carrying iron and porcelain, you do not want the porcelain to be under the iron. Building routes that respect this condition is not an easy task and an algorithm that would take care of this fragility constraint would be very useful. This research aims at developping methods to avoid violating the fragility constraint for new routes to include in the problem. Starting from the classic vehicle routing problem, we will develop Branch-Price-and-Cut algorithms that respect time windows and capacity constraints but also respect the fragility one. Such algorithms should be efficient to solve a majority of the instances in a reasonable amount of time. Theoretical results from chapters 4 and 5 would let us build route without a fragility problem. just by knowing the order of the goods collected. Chapter 4 focus on vehicles with two floors while chapter 5 takes the number of floor as a parameter. With those results, we build algorithms that respect the fragility constraint and solve our route-building problem. To show the efficiency of our algorithms, we will conduct some tests and analyse the results according to different parameters. This analysis will show the strength of our results and the specificity of our problem.

Résumé

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.