Algorithmes de génération de colonnes avec plans coupants pour des problèmes de tournées de véhicules à deux échelons

L’étude de la distribution de marchandises en zones urbaines a suscité beaucoup d’intérêt ces dernières années au sein de la communauté de la recherche opérationnelle. En effet, une planification minutieuse de ces activités contribue à réduire les charges sociales et environnementales placées sur les centres-villes tout en permettant de réaliser des économies d’échelle. Un moyen efficace pour atteindre ces objectifs est de diviser les chaînes d’approvisionnement en deux échelons, ce qui permet d’utiliser de gros véhicules en dehors du centre-ville et de plus petits dans le centre-ville. Cette thèse porte sur le développement d’approches de résolution exactes pour trois variantes du problème de tournées de véhicules à deux échelons : le problème de tournées de véhicules à deux échelons avec fenêtres de temps (2E-VRPTW) et deux de ses extensions, à savoir le problème de tournées de véhicules à deux échelons avec fenêtres de temps et commodités multiples (MC-2E-VRPTW) et le problème de tournées de véhicules à deux échelons avec fenêtres de temps, collectes et livraisons simultanées (2E-VRPTW-SPD). Dans ces problèmes, les véhicules de premier échelon assurent le transport des marchandises des dépôts centraux vers des dépôts intermédiaires, appelés satellites. Les véhicules de second échelon, plus petits que ceux de permier échelon et affectés à des routes commençant et terminant à un même satellite, desservent les clients à l’intérieur de leurs fenêtres de temps. En outre, les satellites n’ont pas de capacité d’entreposage et ne permettent pas la consolidation de fret, ce qui nécessite une synchronisation exacte des opérations (c’est-à-dire que les véhicules de premier et de second échelon doivent être présents simultanément aux satellites afin de permettre le transfert de marchandises). L’objectif est de déterminer un ensemble de routes de premier et de second échelon de moindres coûts, de sorte que chaque client soit desservi par un seul véhicule de second échelon pendant sa fenêtre de temps et que les contraintes liées à la2synchronisation des opérations au niveau des satellites soient satisfaites. Pour résoudre le 2E-VRPTW, nous développons un algorithme exact de génération de colonnes avec plans coupants (branch-price-and-cut, BPC) basé sur une formulation impliquant un grand nombre de routes de second échelon. Les sous-problèmes sont résolus à l’aide d’un algorithme d’étiquetage ad hoc qui génère des routes de second échelon, tout en respectant le schéma de synchronisation considéré aux satellites. Nous décrivons les ajustements nontriviaux à apporter à l’algorithme d’étiquetage afin de générer des variables associées à des routes de second échelon alimentées par des routes de premier échelon uniques. Pour accélérer le processus de résolution, nous proposons des inégalités duales, appelées inégalités de transfert, qui exploitent des informations spécifiques au problème afin de couper une partie de l’espace dual et de réduire le nombre d’itérations de génération de colonnes. L’algorithme BPC développé est capable de résoudre à l’optimalité, en trois heures de temps de calcul, des instances comportant jusqu’à trois dépôts, cinq satellites et 100 clients. De plus, de nouvelles solutions optimales sont trouvées pour 41 instances précédemment non résolues parmi 180 instances testées. Le MC-2E-VRPTW est une extension du 2E-VRPTW qui prend en compte un cas de figure rencontré en pratique où la demande de chaque client n’est disponible qu’à partir d’un dépôt central spécifique. Dans ce problème, les contraintes de synchronisation impliquent que la demande de chaque client doit être satisfaite par exactement un véhicule de premier échelon et un véhicule de second échelon. Cependant, il est possible qu’un véhicule de second échelon reçoive sa marchandise à partir de plusieurs véhicules de premier échelon. Pour résoudre ce problème, nous proposons un algorithme BPC adapté dans lequel la synchronisation des opérations est prise en compte au niveau des sous-problèmes. Pour résoudre ceux-ci, nous développons un algorithme d’étiquetage ad hoc générant des routes de second échelon tout en spécifiant la route de premier échelon ayant fourni la demande de chaque client visité. Nous proposons une règle de branchement adaptée au contexte de commodités multiples ainsi qu’une procédure de récupération assurant la faisabilité des solutions entières lorsque l’on considère les inégalités de transfert. Des instances comportant jusqu’à trois dépôts, cinq satellites et 100 dépôts sont résolues à l’optimalité en trois heures de temps de calcul. Enfin, le 2E-VRPTW-SPD aborde l’aspect des collectes et livraisons simultanées dans un contexte de deux échelons. Dans ce problème, chaque client a une demande de livraison, de collecte, ou les deux. De plus, la demande totale livrée (collectée) par un véhicule de second échelon est fournie (collectée) par un seul véhicule de premier échelon. Nous proposons un algorithme exact de type BPC pour ce problème. Nous considérons un sous-problème par satellite que nous résolvons via un algorithme d’étiquetage spécialisé. Chaque variable générée est associée à une route de second échelon et à une paire de routes de premier échelon. Nous appliquons des inégalités valides connues afin de renforcer les bornes inférieures obtenues et utilisons des inégalités de transfert pour accélérer la convergence de la génération de colonnes. Des instances comportant jusqu’à deux dépôts, trois satellites et 100 clients sont résolues à l’optimalité en trois heures de temps de calcul.

Abstract

The study of freight distribution in urban areas have garnered a lot of interest during recent years within the operations research community. In fact, careful planning for these activities contribute to lessening social and environmental burdens placed on city centers while enabling economies of scale. An efficient and common way for achieving these goals is to divide supply chains into two echelons, allowing to use large vehicles outside the city center and smaller ones in the city center. This thesis addresses the development of exact solution approaches for three variants of the two-echelon vehicle routing problem : the two-echelon vehicle routing problem with time windows (2E-VRPTW) and two of its extensions, namely the multi-commodity two-echelon vehicle routing problem with time windows (MC-2E-VRPTW) and the two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery (2E-VRPTWSPD). In these problems, first-echelon vehicles transport goods from depots to intermediate depots, called satellites. Second-echelon vehicles, smaller than the first-echelon vehicles and assigned to routes starting and ending at a same satellite, service customers within their allocated time windows. Moreover, satellites have no storage capacity and do not allow for freight consolidation, which requires exact operation synchronization (i.e., first- and secondechelon vehicles need to be present simultaneously at the satellites to allow load transfer). The aim is to determine a set of least-cost and capacity-feasible first- and second-echelon routes such that each customer is serviced by a single second-echelon vehicle during its time window and that constraints related to operation synchronization at the satellites are satisfied. To solve the 2E-VRPTW, we develop an exact branch-price-and-cut (BPC) algorithm based on a route-based formulation involving a large number of second-echelon routes. The column generation subproblems are solved using an ad hoc labeling algorithm that generates secondechelon routes, while abiding by the considered synchronization scheme. We describe nontrivial adjustments to the labeling algorithm in order to generate variables associated with second-echelon routes supplied by unique first-echelon routes. To speed up the solution process, we propose dual inequalities, called transfer inequalities, that leverage problem-specific information to cut part of the dual space and decrease the number of column generation iterations. The developed BPC algorithm is able to solve to optimality, within a three-hour computational time limit, instances with up to three depots, five satellites and 100 customers. It also computes new optimal solutions for 41 previously unsolved instances out of 180 tested instances from the literature. The MC-2E-VRPTW is an extension of the 2E-VRPTW that considers a commomly encountered situation in practice where the demand of each customer is available solely at one specific depot. In this problem, synchronization constraints imply that each customer’s demand is supplied by exactly one first-echelon vehicle and one second-echelon vehicle. However, the total demand of any given second-echelon route can be supplied by multiple first-echelon vehicles. To tackle this problem, we propose a tailored BPC algorithm where operation synchronization is considered at the subproblem level. To solve the column generation subproblems, we develop an ad hoc labeling algorithm that generates second-echelon routes while determining each visited customer’s supplying-first-echelon route. The devised algorithm proposes a branching rule adapted to the multi-commodity context and a recovery procedure that ensures the feasibility of integer solutions when considering transfer inequalities. Instances with up to three depots, five satellites and 100 depots are solved to optimality within a three-hour computational time limit. Finally, the 2E-VRPTW-SPD addresses the aspect of simultaneous pickup and delivery in a two-echelon setting. In this problem, each customer has a delivery demand, a pickup demand, or both. Moreover, the total demand delivered (picked up) by a second-echelon vehicle is supplied (collected) by a single first-echelon vehicle. We propose an exact BPC algorithm to solve the problem. We consider one subproblem per satellite that we solve using a specialized labeling algorithm. Each generated variable is associated with a second-echelon route and a pair of first-echelon routes. We use transfer inequalities to speed up column generation and apply known valid inequalities to improve the lower bounds. Instances with up to two depots, three satellites and 100 customers are solved to optimality within three hours of computational time.