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.

Abstract

In this dissertation, we address vehicle routing problems with two-dimensional loading constraints (2L-VRPs), in which vehicle routing and loading are optimized jointly to reach costeffective operations. As many other joint optimization problems, although such integration is profitable from the perspective of management, it brings more computational challenges than optimizing separately. Therefore, over the past decade, we have witnessed many efforts on algorithms for 2L-VRPs. The vast majority of the algorithms are meta-heuristics which are generally very fast to derive near-optimal solutions for the problems. By contrast, exact algorithms for 2L-VRPs have received much less attention. In this research, we are devoted to exact algorithms for 2L-VRPs, in particularly, the vehicle routing problem with time window constraints and two-dimensional loading constraints (2L-VRPTW), and the capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP). The complexity brought by the loading constraints is enormous if the goal is to develop exact algorithms, because checking exactly the loading constraints is equivalent to solving the strip packing problem (SPP), a strongly NP-hard problem. Besides, the loading constraints have no continuous counterpart; instead, the loading constraints have to be fully relaxed and are added iteratively. Therefore, linear relaxation-based algorithms such as the branch-and-cut (BC) algorithm struggle to solve the problems due to the weak dual bounds. Lastly, the column generation technique is regarded as the key component of the exact algorithms for vehicle routing problems. Nevertheless, there exists no efficient algorithm to exactly solve the pricing problem, of which the complexity is significantly increased due to the loading constraints. This project is conducted to address these issues caused by the loading constraints and thus proposes efficient exact algorithms. In the first article, we propose two branch-and-price (BP) algorithms to solve the 2LVRPTW. To address the loading constraints, the column generation algorithm implemented in the BP algorithms is accelerated by a machine learning model so that the number of checking the loading constraints is substantially reduced. The computational results show that the column generation algorithm with the machine learning model takes much less CPU time than the plain version. One of the BP algorithm runs in a heuristic fashion, but it manages to significantly improve the solutions of the existing instances from the literature. The other BP algorithm can exactly solve instances with up to 50 customers and 103 items. In the second article, a branch-and-cut (BC) algorithm is developed to solve the 2L-CVRP. Based on the state-of-the-art exact algorithm for the 2L-CVRP, we propose a separation heuristic to identify infeasible set inequality which turns out be effective for the 2L-CVRP. Comprehensive computational studies were carried out to test the BC algorithm. There are 6 open instances optimally solved by the algorithm. For other open instances 50 customers or fewer, the algorithm can substantially improve the best lower bound by 1.0% on average. Furthermore, the study also points out that the largest bottleneck of developing exact algorithms for 2L-CVRP is no longer the algorithm for checking the loading constraints as it was a decade ago. Instead, to close more open instances, tightening the linear relaxation of the 2L-CVRP would be a more worthy direction, which naturally leads to the third article. In the third third, a branch-and-price-and-cut (BPC) algorithm is proposed to solve the 2LCVRP. To this end, we develop a labeling algorithm that includes several novel techniques to solve the pricing problem, such as an exact dominance rule, a data structure, and two new completion bounds. The BPC algorithm is able to solve 14 instances to optimality for the first time. Computational analyses were also conducted to show the cost of respecting the last-in-first-out constraint (LIFO), which often occurs in practice.