A lowest-first branch and bound algorithmfor the Asymmetric Travelling Salesman Problem is presented.The methodis based on the Assignment Problem relaxation and on a subtour elimination branching scheme.The effectiveness of the algorithm derives fromreduction procedures and parametric solution of therelaxed problems associated with the nodes of the branch-decision tree. Large size uniformly randomly-generated instances of complete digraphswith up to 2,000vertices are solved on a DECstation 5000/240 computer in less than3 minutes of CPU time.In addition, we solved on a PC 486/33 no-wait flow shop problems with up to 1,000 jobs in less than 11 minutes, and real world stacker crane problems with up to 443 movements in less than 6 seconds.
Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems / Dell'Amico, Mauro; Carpaneto, G.; Toth, P.. - In: ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE. - ISSN 0098-3500. - STAMPA. - 21:(1995), pp. 394-409.