Jun WU soutient sa thèse de doctorat, préparée au sein du laboratoire IBISC, Université d’Évry Paris-Saclay et de Xi’an Jiaotong University, le vendredi 17 octobre 2025 à 14h30, salle 334 du bâtiment IBGBI, Université Évry Paris-Saclay.
Titre: Conception d’algorithmes d’approximation à ratio constant pour plusieurs variantes du problème des chemins hamiltoniens multiples.
Résumé
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 à rapport 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 de travaux 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 conçoit des algorithmes d’approximation à rapport 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 rapport d’approximation de $3/2$ pour le MHPP-NE valable pour tout k >= 1. Concernant le MHPP-SD, nous étendons l’heuristique de Christofides afin d’obtenir un rapport d’approximation serré égal à 2 – 1/(2+k) pour tout k >= 1.
Deuxièmement, nous étudions le problème de couverture de chemins avec régions de service et objectif min-max (min-max PCPN) dans le plan, une variante du MHPP qui intègre un objectif min-max, un temps de traitement, et des régions de service (chaque client pouvant être servi dans un rayon donné autour de sa position). L’objectif est de minimiser le coût maximal parmi les k chemins. Nous examinons plusieurs variantes selon le type de clients (homogènes ou hétérogènes) et la configuration des dépôts (unique ou multiple). Pour traiter ces problèmes, nous introduisons le problème de l’arbre de Steiner généralisé avec régions de service comme sous-problème, et développons un algorithme d’approximation à rapport constant dont le ratio est inférieur au tiers du meilleur résultat connu. Cet algorithme sert ensuite à concevoir des algorithmes améliorés en temps polynomial avec un rapport constant pour diverses variantes du min-max PCPN. Nous étendons également cette approche à la résolution des problèmes de couverture d’arbres avec régions de service.
Troisièmement, nous étudions le problème de tournées avec chemins et livraisons fractionnées (SDPRP), 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: i) 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; ii) 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; iii) 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 concevons de nouveaux algorithmes paramétrés d’approximation à rapport constant.
Composition du jury de thèse/Composition of the doctoral thesis jury
| Membre du jury | Titre | Lieu d’exercice | Fonction dans le jury |
|---|---|---|---|
| Éric ANGEL | Professeur des Universités | Université Évry Paris-Saclay | Examinateur |
| Yong CHEN | Professeur | Hangzhou Dianzi University | Rapporteur |
| Feng CHU | Professeure des Universités | Université Évry Paris-Saclay | Directrice de thèse |
| Giorgio LUCARELLI | Maître de conférences | University of Lorraine | Examinateur |
| Kim-Thang NGUYEN | Professeur des Universités | Université Grenoble-Alpes | Rapporteur |
| Ruina YANG | Professeure | Xi’an Jiaotong University | Examinatrice |
| Zhen YANG | Maître de Conférences | Xi’an Jiaotong University | Co-directeur de thèse |
Jun WU defends his doctoral thesis, prepared at the IBISC laboratory, University of Évry Paris-Saclay and Xi’an Jiaotong University, on Friday October 17th, 2025 at 2:30 pm, room 334 of the IBGBI building, Évry Paris-Saclay University.
The session is also available online, via the link: (coming later) .
Title: Design constant-ratio approximation algorithms for several variants of the multiple Hamiltonian path problem
Abstract:
The Hamiltonian Path Problem (HPP), which seeks a minimum-length Hamiltonian path traversing each vertex exactly once, is an NP-hard combinatorial optimization problem fundamental to various applications, such as school bus route planning and data collection in wireless sensor networks. The Multiple Hamiltonian Path Problem (MHPP) generalizes HPP to multiple vehicles, finding k paths covering all vertices exactly once on a metric graph while minimizing the total path length. Due to its complexity, designing effective constant-ratio approximation algorithms for the MHPP and its variants remains challenging, leaving several research gaps: 1) approximation algorithms with constant ratios are underexplored; 2) the MHPP with neighborhoods and a handling time per customer under a min-max objective remains unexplored; 3) few studies investigate the MHPP with vehicle capacity and split delivery. To address these gaps, this thesis studies three categories of MHPP variants and develops new/improved constant-ratio approximation algorithms for them.
Firstly, two classical MHPP variants are investigated. The first is without prefixed start and end points for a path, referred to as MHPP-NE, while the second is the single-depot MHPP (MHPP-SD), in which all paths start at a common depot. We design the first polynomial-time 3/2-approximation algorithm for the MHPP-NE valid for any k >= 1. For the MHPP-SD, we extend the Christofides heuristic to achieve a tight approximation ratio of 2-1/(2+k) for any k >= 1.
Secondly, we study the min-max Path Cover Problem with Neighborhoods (min-max PCPN) in the plane, a variant of the MHPP that incorporates a min-max objective, handling time, and service regions (each customer can be served within a given radius around its location). The goal is to minimize the maximum cost among k paths. We explore several variants with different customer types (homogeneous vs. heterogeneous) and depot configurations (single vs. multiple). To tackle these problems, we introduce the generalized Steiner minimum tree with neighborhoods as a subproblem and develop a constant-ratio approximation algorithm with a ratio less than one-third of the best-known. It then serves for designing new/improved polynomial-time constant-ratio algorithms for min-max PCPN variants. We further extend to solve the min-max tree cover problems with neighborhoods.
- Date : vendredi 17/10/2025, 14h30
- Lieu : Salle 334 du bâtiment IBGBI Université Évry Paris-Saclay. La séance est également diffusée en ligne, via le lien : (prochainement disponible
- Doctorant : Jun WU, Université Évry Paris-Saclay, IBISC équipe AROBAS/Xi’an Jiaotong University
- Direction de thèse : Feng CHU (PR Univ. Évry, IBISC équipe AROBAS, directrice de thèse), Zhen YANG (Associate Professor, Xi’an Jiaotong University, co-dirtecteur de thèse)
