Pyramidal tours for the traveling salesman

Tour improvement is used to identify traveling salesman problems which have an optimal pyramidal tour. The work improves and extends the techniques of Burkard and van der Veen, resulting in a wider class of traveling salesman problems with an optimal pyramidal tour that can be recognized in polynomial time. Also, the work reduces the number of iterations in the tour improvement algorithm from quadratic to linear. As a result, it is now possible in linear time to change each tour for some traveling salesman problems to pyramidal without increasing the length of the tour. The theorems in this paper and the Demidenko recognition theorem are not subcases of each other. An example shows that more work is needed to recognize these traveling salesman problems.