©
Travelling salesman problem
  Solves the Travelling Salesman Problem (TSP) by the Carpaneto et al. algorithm.
2024.Nov.25 04:32:51
Cost Cost matrix (integer).

Supply:
 −1 for infinity;
 no tabs and no return at end;
 data as "27 43" or "27, 43", not "27,43". •

Solves the Travelling Salesman Problem (TSP) by a branch-and-bound algorithm by Carpaneto, Dell'Amico and Toth [1995].

The base problem is from Little et al. [1963], giving z* = 63, and circuit 1-4-3-5-6-2-1.


Other suggested data → and TSP_data.xlsx; Eiselt&Sandblom, p 324.txt
z* = 668 (1-3-4-2-5-1)
  -1 132 217 164  58 
 132  -1 290 201  79 
 217 290  -1 113 303 
 164 201 113  -1 196 
  58  79 303 196  -1
References: Plate: Carpaneto

• Carpaneto, G., M. Dell'Amico, P. Toth, 1995, "Exact solution of large-scale, asymmetric Traveling Salesman Problems", ACM Transactions on Mathematical Software, 21:4, December, pp 394–409. (Reserved access paper.pdf, 990 kb.)  Giorgio Carpaneto, Univ. di Modena; Mauro Dell'Amico, Politecnico di Milano; Paolo Toth, Univ. di Bologna.

• Little, John D. C., Katta G. Murty, Dura W. Sweeney and Caroline Karel, 1963, "An algorithm for the Traveling Salesman Problems", Operations Research, 11:6, pp 972–989 (paper.Pdf, 570 kb).

• Eiselt, H. A., C.-L. Sandblom, 2000, "Integer programming and network models", Springer-Verlag, Berlin. ISBN: 3-540-67191-9, 504 pp. IST Civil Library T57.74 EIS*INT EX. 1 SUTVS. (Explanation unclear, pp 323–325.)

• Search "traveling salesman problem"...

• 1646-07-01: Leibniz, Gottfried Wilhelm von (1716-11-14).

 
 
Valid HTML 4.01! IST http://web.ist.utl.pt/~mcasquilho/compute/or/Fx-tspCarpaneto.php
Created: 2012-07-01 — Last modified: 2018-11-03