Exact solution of large-scale, asymmetric traveling salesman problems

✍ Scribed by Carpaneto, G.; Dell'Amico, M.; Toth, P.

• Book ID: 121412402
• Publisher: Association for Computing Machinery
• Year: 1995
• Tongue: English
• Weight: 995 KB
• Volume: 21
• Category: Article
• ISSN: 0098-3500
• DOI: 10.1145/212066.212081

✦ Synopsis

A lowest-first, branch-and-bound algorithm for the
Asymmetric Traveling Salesman Problem
is presented. The method is based on the
Assignment Problem relaxation
and on a
subtour elimination branching scheme
. The effectiveness of the algorithm derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree. Large-size, uniformly, randomly generated instances of complete digraphs with up to 2000 vertices are solved on a DECstation 5000/240 computer in less than 3 minutes of CPU time. In addition, we solved on a PC 486/33
no wait flow shop
problems with up to 1000 jobs in less than 11 minutes and real-world
stacker crane
problems with up to 443 movements in less than 6 seconds.