An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem

Jun Wu (1, 2) , Zhen Yang (1, 3, 4) , Guiqing Zhang (5) , Yongxi Cheng (1, 4)

1 School of Management
2 IBISC - Informatique, BioInformatique, Systèmes Complexes
3 Logistics Science and Technology Innovation Integrated Development Research Center
4 State key laboratory for manufacturing systems engineering
5 School of Economics and Finance

We study a generalization of the classical Hamiltonian path problem, where multiple salesmen are positioned at the same depot, of which no more than k can be selected to service n destinations, with the objective to minimize the total travel distance. Distances between destinations (and the single depot) are assumed to satisfy the triangle inequality. We develop a non-trivial extension of the well-known Christofides heuristic for this problem, which achieves an approximation ratio of 2-1/(2+k) with O(n3) running time for arbitrary k≥1.

Mots clés: Approximation ratio; Christofides heuristic; Multiple Hamiltonian path problem

Domaines: Recherche opérationnelle [math.OC]

Jun Wu, Zhen Yang, Guiqing Zhang, Yongxi Cheng. An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem. Journal of Combinatorial Optimization, 2024, 47 (2), pp.7. ⟨10.1007/s10878-023-01104-8⟩. ⟨hal-04476979⟩