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.