Improvements on Column-Generation-Based Algorithms for Vehicle Routing and Other Combinatorial Problems

Plusieurs applications dans le contexte de la logistique et de la planification de la production peuvent être modélisées comme des problèmes d'optimisation combinatoire (POC). En particulier,l'un des problèmes les plus étudiés dans ce domaine est le problème de tournées de véhicules (PTV). Le PTV consiste à trouver des tournées de véhicules qui minimisent le coût total de transport pour visiter un ensemble de clients, de telle sorte que leur demande soit complètement satisfaite en une seule visite, et que la capacité des véhicules ne soit jamais dépassée. Présentement, la principale méthode de résolution exacte pour les PTVs est la génération de colonnes. Dans cette thèse, nous nous intéressons à l'étude des algorithmes de génération de colonnes et proposons de nouvelles idées pour améliorer leur efficacité. Dans le Chapitre 4, nous présentons une revue de littérature très exhaustive dans laquelle nous mettons en évidence les principales contributions algorithmiques et de modélisation apportées au cours des dernières années dans la cadre du développent des algorithmes de génération de colonnes et de plans coupants intégrés à des méthodes d'énumération implicite pour le PTV. Notre étude est divisée en deux parties principales. Dans la première partie, nous présentons des aspects qui peuvent s'appliquer à la plupart des variantes de PTV, à savoir : des algorithmes de résolution du sous-problème de la génération de colonnes, la séparation de plans coupants, les stratégies de branchement et la stabilisation des variables duales dans le problème-maître. La deuxième partie est dédiée à la résolution de problèmes spécifiques. Dans cette partie, nous discutons comment les spécificités de chaque problème peuvent êtres traitées lors du développement des algorithmes d'énumération implicite combinant génération de colonnes et plans coupants. On étude les attributs suivants : l'existence d'une flotte hétérogène et des dépôts multiples, la considération de fenêtres de temps souples chez les clients, la possibilité d'effectuer des livraisons fractionnées, les coûts dépendant du temps, la réalisation de cueillettes et livraisons, la présence d'incertitude dans les données et des aspects environnementaux. Dans le Chapitre 5, nous proposons un algorithme sélectif pour résoudre des sous-problèmes de la génération de colonnes afin de générer des routes relaxées de type arc-ng. Notre méthode considère une généralisation de la dominance par ensemble proposée par Bulhões et al. [1]. Les résultats numériques obtenus sur des instances du PTV avec fenêtres de temps montrent que le nouveau mécanisme aide à réduire le nombre d'étiquettes non-dominées dans l'algorithme d'étiquetage utilisé pour résoudre le sous-problème et, par conséquent, le temps de calcul. Enfin, dans le Chapitre 6, nous présentons une nouvelle méthode de stabilisation pour des POCs avec des structures qui favorisent l'parution de dégénérescence. Le nouvel algorithme de stabilisation, appelé dyn-SAR, est basé sur la séparation dynamique de contraintes agrégées, qui sont obtenues en additionnant des contraintes du problème maître de génération de colonnes. L'effet de stabilisation induit par dyn-SAR provient des fortes interactions qui surviennent entre les variables duales, ce qui n'est pas observé lors de la résolution explicite d'une formulation de partition d'ensemble (recouvrement / empaquetage). L'intérêt principal pour l'utilisation du dyn-SAR est dû à sa simplicité et généralité. Ce dernier aspect est confirmé dans nos expériences, où nous considérons des problèmes dont la fonction objectif et le sous-problème de génération de colonnes sont considérablement différents. Les résultats numériques montrent un avantage important du dyn-SAR par rapport à une méthode de génération de colonnes standard en termes de nombre d'itérations et de temps de calcul.

Abstract

Several applications arising in the context of logistics and production planning can be modeled as combinatorial optimization problems (COPs). In particular, one of the most studied problems in this field is the vehicle routing problem (VRP). The VRP is the problem of finding least-cost routes to visit a set of customers in such a way that their demand is completely satisfied in a single visit, and the capacity of vehicles is not exceeded. Nowadays, the leading exact method to cope with different classes of VRPs is column generation (CG). In this thesis, we are interested in studying CG algorithms and propose new ideas to enhance their efficiency. In Chapter 4, we present a methodological survey in which we highlight and discuss the main algorithmic and modeling contributions made over the years in the context of branch-priceand-cut methods for VRPs. Our study is divided into two main parts. In the first part, we discuss topics that may apply to most VRPs variants, namely: pricing algorithms, cut separation, branching strategies, and dual variable stabilization. The second part is more problem-oriented and describes how aspects such as heterogeneous fleet, multi-depots, soft time windows, split deliveries, time dependency, pickups and deliveries, uncertainty, and environmental aspects can be handled in devising branch-price-and-cut algorithms. In Chapter 5, we propose a selective pricing algorithm to solve pricing subproblems defined in terms of arc-ng-route relaxations. Our method extends the set-based dominance rule proposed by Bulhões et al. [1], making it more general and stronger. Computational experiments performed over instances of the VRP with time windows show that the proposed mechanism helps in reducing the number of non-dominated labels kept by the labeling algorithm and, as a consequence, the CPU time. Finally, in Chapter 6, we develop a new stabilization framework to tackle COPs with degenerate structures. The new stabilization method, called dyn-SAR, relies on the dynamic separation of aggregated constraints, which are obtained by summing up constraints from the CG master problem. The stabilization effect induced by dyn-SAR is due to strong interactions that arise from dual variables, which is not observed when solving explicitly a set-partitioning (covering/packing) formulation. The main interests in using the dyn-SAR method are its simplicity and generality. The latter aspect is confirmed in our experiments, where we solve instances from problems differing considerably in their objective function and pricing subproblem. Numerical results show a clear advantage of dyn-SAR over a standard CG method in terms of both the number of iterations and running time.