The Traveling Salesman Problem with Backhauls

The purpose of this paper is to propose new heuristics for the Traveling Salesman Problem with Backhauls. In this problem, the aim is to determine a least cost Hamiltonian tour through a set of linehaul and backhaul customers, in such a way that all backhaul customers are visited contiguously after all linehaul customers. Six heuristics, all having a good empirical performance ratio, are described and compared with a lower bound. Computational results indicate that the best of these heuristics yields high quality solutions.