| Article ID: | iaor1993386 |
| Country: | Netherlands |
| Volume: | 53 |
| Issue: | 2 |
| Start Page Number: | 173 |
| End Page Number: | 197 |
| Publication Date: | Jan 1992 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Fischetti Matteo, Toth Paolo |
| Keywords: | heuristics |
In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure. Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems.