Khachai, Daniil
[Verfasser:in]
;
Bordeaux
[Mitwirkende:r];
Detienne, Boris
[Mitwirkende:r];
Battaïa, Olga
[Mitwirkende:r]
Algorithmes efficaces pour les problèmes de routage avec des contraintes spécifiques ; Efficient Algorithms for Routing Problems with Specific Constraints
Titel:
Algorithmes efficaces pour les problèmes de routage avec des contraintes spécifiques ; Efficient Algorithms for Routing Problems with Specific Constraints
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...