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-01-01

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.
21
394
409
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.
Dell'Amico, Mauro; Carpaneto, G.; Toth, P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/451190
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 85
  • ???jsp.display-item.citation.isi??? 65
social impact