Méthodes primales pour résoudre le problème de plus court chemin avec contraintes de ressources

Le problème de plus court chemin avec contraintes de ressources consiste à trouver un chemin entre deux noeuds dans un réseau (une source et une destination) à un coût minimum tout en respectant des contraintes sur la consommation de ressources. Il s'agit d'une généralisation du problème classique du plus court chemin non contraint. Ce problème a été largement étudié dans la littérature. Nous l'utilisons particulièrement comme sous-problème lors de la résolution des problèmes de planification de tournées de véhicules et d'horaires d'équipages par un algorithme de génération de colonnes. L'approche standard pour résoudre le problème de plus court chemin avec les contraintes de ressources est la programmation dynamique. Cette méthode est une extension du fameux algorithme de Bellman-Ford qui prend en considération les contraintes de ressources. Elle consiste à construire une séquence de sous-chemins provenant du noeud source en étendant ceux existants aux noeuds successeurs à l'aide d'une fonction de prolongation. Chaque sous-chemin correspond à un état et est reconnu par une étiquette qui mémorise son coût et ses consommations de ressources. La fonction de prolongation assure l'élimination des étiquettes non réalisables et garantit la mise à jour des coûts et des consommations de ressources après chaque prolongation. Des règles de dominance sont également utilisées pour interdire l'extension d'étiquettes peu prometteuses. D'un côté, cette approche est capable de gérer des règles complexes de travail provenant des conventions collectives et des mesures de sécurité et qui sont généralement non linéaires et même non convexes. D'un autre côté, la méthode de programmation dynamique permet de générer de nombreuses solutions réalisables (chemins réalisables) au lieu d'une seule, ce qui est nécessaire dans un contexte de génération de colonnes. Cependant, lorsqu'il faut gérer un grand nombre de ressources, le nombre d'étiquettes augmente de manière exponentielle, notamment dans le cas de réseaux de grande taille avec des centaines de milliers d'arcs. Par conséquent, le processus de résolution nécessite beaucoup de temps et dans de nombreux cas, nous ne sommes pas en mesure de trouver des solutions optimales. Plusieurs heuristiques ont été proposées pour gérer cette situation ; certaines dominent sur un sous-ensemble de ressources sélectionnées de manière empirique, alors que d'autres se contentent de prolonger un sous-ensemble d'étiquettes de chaque noeud. Bien évidemment, n'étant pas fondées mathématiquement, ces méthodes n'offrent aucune garantie sur la qualité des solutions retournées. Nous proposons dans ce travail différentes idées qui sont capables de remédier aux inconvénients mentionnés ci-dessus, afin d'améliorer la résolution du problème de plus court chemin avec les contraintes de ressources. Les méthodes proposées sont primales, exactes et tirent profit des avantages de la programmation dynamique. La première contribution de cette thèse est un nouvel algorithme primal multi-directionnel appelé MultiDirectional Dynamic Programming Algorithm. L'approche proposée partitionne l'espace d'états en petits sous-espaces disjoints qui sont explorés séquentiellement dans plusieurs itérations. Nous proposons aussi de nouvelles techniques d'apprentissage qui permettent à cet algorithme de tirer profit des résultats des itérations précédentes, afin de réduire la dimension des sous-espaces subséquents et générer rapidement de meilleurs chemins. Les expérimentations numériques sur des instances du problème de planification de tournées de véhicules et d'horaires d'équipages avec plus de 600.000 noeuds et 1.000.000 arcs démontrent que la nouvelle approche vainc l'algorithme standard de programmation dynamique. En particulier, elle est capable de générer des chemins réalisables avec jusqu'à 90% du coût optimal en moins de 10% du temps requis par l'algorithme standard de programmation dynamique. Étant convaincus de l'efficacité de l'exploration itérative de l'espace d'état, nous proposons dans une seconde contribution un autre algorithme primal exact appelé Primal Adjacency-Based algorithm. Nous fournissons d'abord une nouvelle étude polyédrique qui nous permet d'introduire une nouvelle partition de l'espace des états basée sur la notion d'adjacence. L'algorithme proposé utilise cette partition pour explorer de manière itérative l'espace d'états et produit une séquence d'ensembles de chemins réalisables de coûts non décroissants. Ces chemins sont ensuite utilisés pour enrichir l'information primale disponible, ce qui permet d'accélérer le processus de résolution dans les itérations suivantes. Les expérimentations numériques sur les mêmes instances citées ci-dessus montrent d'excellentes performances de cet algorithme. Il est capable, à l'instar de l'algorithme multi-directionnel, de produire des chemins de très bonne qualité dans des délais très courts. De plus, il réduit considérablement le nombre d'étiquettes créées par rapport à l'algorithme standard de programmation dynamique et à l'algorithme multi-directionnel. Les résultats obtenus ont montré que les approches proposées constituent des outils de résolution très efficaces, parfaitement adaptées à la méthode de génération de colonnes. Pour cette raison, nous nous concentrons dans notre troisième contribution sur le développement d'un nouveau cadre de résolution appelé Primal Column Generation Framework qui intègre ces méthodes primales dans un schéma de génération de colonnes. Ceci permet de trouver rapidement et intelligemment les colonnes de coûts réduits négatifs nécessaires en résolvant une séquence de sous-problèmes restreints en fonction des besoins. De plus, ce paradigme primal confère à la génération de colonnes une autonomie et une grande flexibilité. Des résultats expérimentaux montrent que l'outil proposé est capable de trouver des solutions optimales tout en réduisant le temps consommé à résoudre les sous-problèmes par des facteurs allant jusqu'à 7 fois par rapport à un algorithme de génération de colonnes standard. Cela engendre des gains significatifs en matière du temps total de résolution avec un facteur de réduction moyen de 3.5.

Abstract

The shortest path problem with resource constraints is to find a path between two nodes in a network (a source and a sink) at minimum cost while respecting constraints on resource consumption. This problem is a generalization of the classical non constrained shortest path problem. This problem has been largely studied in the literature. We particularly use it as a subproblem to solve crew scheduling and vehicle routing problems by the column generation method. The standard approach to solve the shortest path problem with resource constraints is dynamic programming. This method is an extension of the well-known Bellman-Ford algorithm that takes into account the resource constraints. It constructs a sequence of subpaths originated from the source node, by extending the existing ones to the successor nodes. Each subpath corresponds to a state and is recognized using a label that stores its cost and its resource consumptions. The extension function ensures the elimination of infeasible labels and guarantees the update of costs and resource consumption after each extension. Dominance rules are also used to prohibit the extension of unpromising labels. This approach is able to handle complex working rules like collective agreement rules and other safety rules that may be nonlinear and even non convex. Also, it allows the generation of many feasible solutions (feasible paths) instead of one, which is required in a column generation context. However, when we have to deal with a large number of resources, the number of labels increases exponentially, especially in the case of huge networks of hundreds of thousands of arcs. Consequently, the solution process becomes time consuming and in many cases we are not able to find optimal solutions. Several heuristics have been proposed to handle this situation, some of them dominate on an empirically selected subset of resources, while others used to extend only limited subsets of labels from each node. Of course, given that these methods are not mathematically founded, they offer no guarantee on the quality of the returned solutions. We propose in this work different ideas that are able to handle the drawbacks mentioned above, in order to improve the resolution of the shortest path problem with resource constraints. The proposed methods are primal, exact and take profits from the advantages of dynamic programming. The first contribution of this thesis is a new primal algorithm called the MultiDirectional Dynamic Programming Algorithm. The proposed approach splits the state space into small disjoint subspaces that are sequentially explored in several iterations. Moreover, we propose new learning techniques that allow the proposed algorithm to build on the results of the previous iterations, to reduce the dimension of the subsequent subspaces and to quickly generate better paths. Numerical experiments on Vehicle and Crew Scheduling Problem instances with up to 600.000 nodes and 1.000.000 arcs demonstrate that the new approach outperforms the standard dynamic programming algorithm. In particular, the multidirectional algorithm is able to generate feasible paths with up to 90% of the optimal cost in less than 10% of the time required by standard dynamic programming. Being convinced of the efficiency of the iterative exploration of the state space, we propose in a second contribution another exact primal algorithm called Primal Adjacency-Based algorithm. We first provide a new polyhedral study that allows us to introduce a new path adjacency-based partition of the state space. The proposed algorithm uses this partition to iteratively explore the state space and produces a sequence of sets of feasible paths of non decreasing costs. These paths are used in order to enrich the available primal information which improve the solution process in the subsequent iterations. Computational experiments on the same instances cited above show the excellent performance of this algorithm. Similarly to the multidirectional algorithm, the Primal Adjacency-Based algorithm is able to produce very interesting paths in very limited portions of time. Moreover, it drastically reduces the number of created labels compared to both standard dynamic programming and multidirectional algorithms. The obtained results have shown that the proposed approaches provide a highly efficient solution tool, nicely suitable for the column generation method. For this reason, we focus in our third contribution on developing a new Primal Column Generation framework that embeds these primal methods inside a column generation scheme. This framework allows finding quickly and intelligently the required negative reduced costs columns by solving a sequence of restricted subproblems as needed. Furthermore, this primal paradigm endows the column generation with a self-acting ability and a large degree of flexibility. Computational experiments show that the proposed tool is able to find optimal solutions while reducing the time spent solving subproblems by factors up to 7 times. This yields significant gains in the total solution times with an average reduction factor of 3.5 compared to the standard column generation algorithm.