Academic
Publications
Exact solution of large-scale, asymmetric traveling salesman problems

Exact solution of large-scale, asymmetric traveling salesman problems,10.1145/212066.212081,ACM Transactions on Mathematical Software,Giorgio Carpanet

Exact solution of large-scale, asymmetric traveling salesman problems   (Citations: 47)
BibTex | RIS | RefWorks Download
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.
Journal: ACM Transactions on Mathematical Software - TOMS , vol. 21, no. 4, pp. 394-409, 1995
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: