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.
Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems
DELL'AMICO, Mauro;
1995
Abstract
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.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
