Pyramidal tours and the traveling salesman problem

• Published in: European journal of operational research 1991-05, Vol.52 (1), p.90-102
• Main Authors: van der Veen, Jack A.A., Sierksma, Gerard, van Dal, René
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Demidenko conditions; distribution matrix; Exact sciences and technology; Flows in networks. Combinatorial problems; Functions; Heuristic; heuristics; Mathematical models; Operational research and scientific management; Operational research. Management science; Operations research; pyramidal tour; Statistical analysis; Studies; Theory; Traveling salesman problem
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/0377-2217(91)90339-W

A traveling salesman problem is studied, containing a shortest Hamiltonian tour that is as long as a shortest pyramidal tour. A tour is pyramidal if it consists of a path from city 1 to n with cities in between visited in ascending order, and a path from n to 1 with cities in between visited in descending order. If the distance matrix satisfies the so-called Demidenko conditions, in which case it is called a Demidenko matrix, then there exists an optimal tour that is pyramidal. A new proof of this theorem is given for symmetric Demidenko matrices. The proof cannot be used for the nonsymmetric case. If, however, the Demidenko conditions are replaced by somewhat stronger conditions it is possible to give a similar proof for the nonsymmetric case. A method to construct Demidenko matrices is presented and, finally, several TSP heuristics are tested on the class of Demidenko matrices.