Algorithmes efficaces pour les problèmes de routage avec des contraintes spécifiques

Abstract

Cette thèse se concentre sur la conception algorithmique de trois problèmes d’optimisation combinatoire liés à la recherche en transport, logistique et production avec des types spécifiques de contraintes industrielles. Tout d’abord, nous considérons le problème du voyageur de commerce généralisé à contraintes de priorité (PCGTSP). Ce problème est une extension de deux problèmes d’optimisation combinatoire bien connus : le problème généralisé du voyageur de commerce (GTSP) et le problème du voyageur de commerce asymétrique à contrainte de préséance (PCATSP), dont la version de chemin est connue sous le nom de problème de commande séquentielle (SOP).Semblable au GTSP classique, le but du PCGTSP est de trouver pour un digraphe d’entrée donné et une partition de son ensemble de nœuds en clusters un itinéraire cyclique (tour) à coût minimum visitant chaque cluster dans un seul nœud. De plus, comme dans le PCATSP, les visites réalisables sont limitées à la visite des clusters dans le respect de l’ordre partiel donné. Contrairement au GTSP et au SOP, à notre connaissance, lePCGTSP reste encore peu étudié tant en termes de théorie polyédrique que d’algorithmes. Dans cette thèse, pour la première fois pour le PCGTSP, nous proposons plusieurs familles d’inégalités valides, établissons la dimension du polytope PCGTS et prouvons des conditions suffisantes garantissant que les inégalités π et σ étendues de Balas deviennent des facettes -induisant. En nous appuyant sur ces résultats théoriques et les approches algorithmiques existantes pour le PCATSP et le SOP, nous introduisons une famille de modèles MILP et plusieurs variantes de l’algorithme branch-and-cut pour le PCGTSP. Nous étudions leurs performances sur les instances de la bibliothèque publique de benchmark PCGTSPLIB, une adaptation connue du SOPLIB classique au problème en question. Les résultats obtenus montrent l’efficacité de l’algorithme.Notre deuxième sujet de recherche est lié à une application industrielle spécifique du PCGTSP - le problème du chemin de coupe discret (CPP). Dans ce problème, nous avons cherché à trouver une trajectoire optimale pour un outil de coupe, afin de minimiser le coût total de traitement, y compris la découpe, le mouvement de l’air, le perçage et autres dépenses, soumis aux contraintes induites par les restrictions de découpe industrielle. Ilivest pratique de considérer ces restrictions en termes de contraintes de préséance. Nous introduisons un cadre de solution général pour le RPC qui comprend : (i) l’approche de réduction universelle pour de nombreuses variantes de ce problème au problème du voyageur de commerce généralisé avec contraintes de préséance ; (ii) un support méthodologique pour trouver des solutions (sous-) optimales à ce problème sur la base de l’algorithme de branchement et de coupe et de la méta-heuristique PCGLNS. Les résultats des expériences informatiques montrent l’efficacité du cadre proposé pour résoudre les instances industrielles du problème.Enfin, nous abordons le problème de routage de véhicules capacitaires (CVRP). CVRP est fortement NP-difficile (même sur le plan euclidien), difficile à approximer dans le cas général et APX-complet pour une métrique arbitraire. Cependant, pour les paramètres géométriques du problème, il existe un certain nombre de schémas d’approximation temporelle quasi-polynomiale et même polynomiale connus. Parmi ces résultats, le célèbre système d’approximation temporelle quasi-polynomiale (QPTAS) proposé par A. Das et C. Mathieu semble être le plus général. Dans cette thèse, nous proposons la première extension de ce schéma à une classe plus large d’espaces métriques. En fait, nous montrons que la métrique CVRP a un QPTAS à tout moment lorsque le problème est installé dans l’espace métrique de toute dimension de doublement fixe d > 1 et que la capacité ne dépasse pas polylog(n).