Pyramidal tours with step-backs and the asymmetric traveling salesman problem

✍ Scribed by Hikoe Enomoto; Yoshiaki Oda; Katsuhiro Ota

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 495 KB
• Volume: 87
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00048-1

✦ Synopsis

In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time.