New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization

We introduce a new combinatorial optimization problem called minimum cost connected multi-digraph problem with node-deficiency requirements (MCNDP), which includes as a special case the traveling salesman problem (TSP) and hence is NP-hard. We develop polynomial schemes for special cases of the MCNDP. As a result, we get polynomial schemes for new, non-trivial cases of the TSP. One of our interesting results is a polynomial scheme for a common generalization of two of the most well-known solvable cases viz. the warehouse order-picking problem of Ratliff and Rosenthal and the Gilmore-Gomory case of the TSP. Based on these results, we propose a heuristic for the MCNDP, which is expected to perform well on large subclasses of the TSP. (C) 2002 Elsevier Science B.V. All rights reserved.