Solves the Travelling
Salesman Problem (TSP) by a branch-and-bound algorithm by
Carpaneto, Dell'Amico and Toth [1995].
The header is optional. If given,
the number of words must match the problem "size".
The base problem is from Little et al. [1963],
giving z* = 63, and circuit 1-4-3-5-6-2-1.
Excel "all different".xlsx (Portuguese districts)
Other suggested data: data at right;
TSP_data.xlsx ("holes"); and
Eiselt & Sandblom, p 324.txt .
*Tabs permit, namely, to enter data by
copy-paste from Excel. |
| 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 | |
|
• 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,
=)
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).
• Search "traveling
salesman problem"...
• 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.)
• Google possessive with et al.
• 1815-11-02: Boole, George (1864-12-08). |
