Conception d'algorithmes d'approximation à ratio constant pour plusieurs variantes du problème des chemins hamiltoniens multiples

Le problème du chemin hamiltonien (HPP), qui consiste à trouver un chemin hamiltonien de longueur minimale visitant chaque sommet exactement une fois, est un problème d'optimisation combinatoire NP-difficile, fondamental pour de nombreuses applications telles que la planification de circuits de ramassage scolaire ou la collecte de données dans les réseaux de capteurs sans fil. Le problème des chemins hamiltoniens multiples (MHPP) généralise le HPP à plusieurs véhicules, en recherchant k chemins couvrant tous les sommets exactement une fois dans un graphe métrique, tout en minimisant la longueur totale. En raison de sa complexité, la conception d'algorithmes d'approximation efficaces en temps polynomial pour le MHPP et ses variantes reste un défi, ce qui laisse plusieurs lacunes dans la littérature : 1) les algorithmes d'approximation à ratio constant sont encore peu explorés ; 2) le MHPP avec voisinages et un temps de traitement par client selon un objectif min-max reste inexploré; 3) peu d'études considèrent le MHPP avec contraintes de capacité et livraisons fractionnées. Pour combler ces lacunes, cette thèse étudie trois catégories de variantes du MHPP et développe des algorithmes d'approximation à ratio constant, nouvellement conçus ou améliorés. Premièrement, deux variantes classiques du problème des chemins hamiltoniens multiples (MHPP) sont étudiées. La première variante, notée MHPP-NE, ne spécifie aucun point de départ ou d'arrivée pour les chemins, tandis que la seconde, nommée MHPP à dépôt unique (MHPP-SD), impose que tous les chemins débutent à partir d'un dépôt commun. Nous concevons le premier algorithme polynomial avec un ratio d'approximation de 3/2 pour le MHPP-NE valable pour tout k ge 1. Concernant le MHPP-SD, nous étendons l'heuristique de Christofides afin d'obtenir un ratio serré d'approximation égal à 2 - 1/(2+k) pour tout k ge 1. Deuxièmement, nous étudions un problème de couverture de chemins avec régions de service sous critère min-max (min-max PCPN) dans le plan euclidien, une variante du MHPP prenant en compte un objectif min-max, un temps de traitement par client et une zone de service. En particulier, un client peut être desservi à l'intérieur d'un rayon spécifié plutôt qu'en un point fixe. L'objectif est de minimiser le coût maximum parmi les k chemins. Plusieurs variantes sont analysées selon le type de clients (homogènes ou hétérogènes) et la configuration des dépôts (unique ou multiple). Pour résoudre ces variantes, nous concevons d'abord un algorithme d'approximation à rapport constant pour une relaxation du problème, servant de base au développement d'algorithmes pour les versions complètes. Nous étendons ensuite ces techniques pour résoudre les problèmes de couverture d'arbres avec objectif min-max et voisinages. Troisièmement, nous étudions le problème de tournées avec chemins et livraisons fractionnées (SDPRP) ainsi que ses variantes, généralisant le MHPP en introduisant des contraintes de capacité sur les véhicules et en permettant les livraisons fractionnées. Nous considérons trois variantes spécifiques du SDPRP : 1) le problème de tournées à chemins et livraisons fractionnées sans dépôt ni terminal (MSDPRP), où chacun des k véhicules peut commencer et terminer chez n'importe quel client ; 2) le problème de localisation multi-dépôts avec tournées à chemins et livraisons fractionnées (m-DL-SDPRP), dans lequel chaque véhicule doit être affecté à l'un des m dépôts candidats ; 3) le problème multi-dépôts et multi-terminaux avec tournées à chemins et livraisons fractionnées (m-DT-SDPRP), où chaque véhicule démarre d'un dépôt prédéfini et termine à un terminal prédéfini. Pour ces trois variantes, nous développons de nouveaux algorithmes paramétrés d'approximation à ratio constant.