An Approximation Algorithm for the Three Depots Hamiltonian Path Problem

In this paper, we propose an approximation algorithm for solving the three depots Hamiltonian path problem (3DHPP). The problem studied can be viewed as a variant of the well-known Hamiltonian path problem with multiple depots (cf., Demange [Mathématiques et Informatique, Gazette, 102 (2004)] and Malik et al. [Oper. Res. Lett. 35, 747–753 (2007)]). For the 3DHPP, we show the existence of a \(\frac{3} {2}\)-approximation algorithm for a broad family of metric cases which also guarantees a ratio r < 2 in the general metric case. The proposed algorithm is mainly based on extending the construction scheme already used by Rathinam et al. [Oper. Res. Lett. 38, 63–68 (2010)]. The aforementioned result is established for a variant of the three-depot problem, that is, when costs are symmetric and satisfy the triangle inequality.