Exact Algorithms for Vehicle Routing Problems with Two-Dimensional Loading Constraints

Dans cette thèse, nous abordons les problèmes de tournées de véhicules avec contraintes de chargement à deux dimensions, dans lesquels les tournées et le chargement des véhicules sont optimisés conjointement pour réduire les coûts opérationnels. Cependant, l'intégration soulève des défis de calcul. Nous avons assisté à de nombreux efforts sur les algorithmes pour traiter ces problèmes. La grande majorité des algorithmes sont des méta-heuristiques tandis que les algorithmes exacts pour ces problèmes ont reçu beaucoup moins d'attention. Dans cette recherche, nous proposons des algorithmes exacts pour le problème de tournées de véhicules avec fenêtres de temps et contraintes de chargement à deux dimensions (2LVRPTW) et le problème de tournées avec contrainte de capacité (2L-CVRP). Développer des algorithmes exacts pour ces problèmes est très difficile, car vérifier exactement les contraintes de chargement équivaut à résoudre le problème de “strip packing problem (SPP)”, un problème fortement NP-difficile. De plus, les contraintes de chargement n'ont pas de relaxation linéaire. Par conséquent, les algorithmes basés sur la relaxation linéaire tels que l'algorithme de Branch-and-Cut (BC) ont du mal à résoudre les problèmes dus à la faiblesse des bornes duales. Enfin, la technique de génération de colonnes est considérée comme l'élément clé des algorithmes exacts pour les problèmes de tournées de véhicules. Néanmoins, il n'existe pas d'algorithme efficace pour résoudre exactement le problème de “pricing”, dont la complexité est considérablement augmentée en raison des contraintes de chargement. Ce projet est mené pour pallier ces problèmes causés par les contraintes de chargement et propose ainsi des algorithmes exacts efficaces. Dans le premier article, nous proposons deux algorithmes de Branch-and-Price (BP) pour le 2L-VRPTW. Pour faire face aux contraintes de chargement, l'algorithme de géneration de colonnes intégré dans les algorithmes BP est accéléré par un modèle d'apprentissage machine de sorte que le nombre de vérifications des contraintes de chargement est substantiellement réduit. Les résultats de calcul montrent que l'algorithme de génération de colonnes avec le modèle d'apprentissage machine prend beaucoup moins de temps de calcul que la version simple. L'un des algorithmes BP s'exécute de manière heuristique, mais il parvient à améliorer considérablement les solutions des instances existantes issues de la littérature. L'autre algorithme BP peut résoudre exactement des instances avec jusqu'à 50 clients et 103 éléments. Dans le deuxième article, un algorithme de BC est développé pour résoudre le 2L-CVRP. Sur la base de l'algorithme exact de pointe pour le 2L-CVRP, nous proposons une heuristique de séparation pour identifier l'inégalité d'ensembles non réalisables qui s'avère efficace pour le 2L-CVRP. Des expériences ont été menées pour tester l'algorithme BC. Il y a 6 instances ouvertes qui sont résolues de manière optimale par l'algorithme. Pour les autres instances ouvertes avec 50 clients ou moins, l'algorithme peut considérablement améliorer la meilleure borne inférieure de 1,0 % en moyenne. En outre, l'étude souligne également que le plus gros goulot d'étranglement dans le développement d'algorithmes exacts pour 2L-CVRP n'est plus l'algorithme de vérification des contraintes de chargement comme il y a dix ans. Au lieu de cela, pour fermer d'autres instances ouvertes, resserrer la relaxation linéaire du 2L-CVRP serait une direction plus valable, ce qui conduit naturellement au troisième article. Dans le troisième article, un algorithme BPC (branch-and-price-and-cut) est proposé pour résoudre le 2L-CVRP. Dans ce but, nous développons un algorithme d'étiquetage pour résoudre le sous-problème, y compris une règle de dominance exacte, une structure de données, et deux nouvelles bornes de complétion. L'algorithme BPC est capable de résoudre 14 instances à l'optimalité pour la première fois. Des analyses expérimentales ont également été menées pour montrer le coût du respect de la contrainte de LIFO, qu'on retrouve souvent dans la pratique.