A: This never occured so far. In all cases when someone believed to have found a better solution, it was not taken into account that it is exactly specified how distances for TSPLIB problems have to computed. Typical errors are
A: No, for every problem either the value of a provably optimal solution or an interval given by the best known lower and upper bound is listed. The optimality of solutions has been proven by branch-and-cut or branch-and-bound algorithms.
A: There has been some confusion of how to compute the distances. I use the following code.
For converting coordinate input to longitude and latitude in radian:
PI = 3.141592;
deg = (int) x[i];
min = x[i]- deg;
rad = PI * (deg + 5.0 * min/ 3.0) / 180.0;
For computing the geographical distance:
RRR = 6378.388;
q1 = cos( longitude[i] - longitude[j] );
q2 = cos( latitude[i] - latitude[j] );
q3 = cos( latitude[i] + latitude[j] );
dij = (int) ( RRR * acos( 0.5*((1.0+q1)*q2 - (1.0-q1)*q3) ) + 1.0);
A: The function "int nint (double x)" converts x into int format rounding to the nearest int value, except halfway cases are rounded to the int value larger in magnitude. This corresponds to the Fortran generic intrinsic function nint. But, rounding like "(int) (x+0.5)" should give the same results for TSPLIB problems.
A: Basically yes, but, in view of the many problem instances that are already available, new instances should either be real challenge problems or be of general interest.
A: No. We have included several optimal tours for testing purposes. It is not intended to provide all optimal tours. It should still be a challenge to find one.
A: So far, no other optimal solutions have been made available.
A: All data has been compressed with the command "gzip" and has to be read using "gzip -d". Please contact your system administrator if this command is not available.
Jünger, M., G. Reinelt and G. Rinaldi (1996), "The Traveling Salesman Problem", in: M. Ball, T. Magnanti, C. L. Monma and G.L. Nemhauser (eds.), Handbooks in Operations Research and Management Sciences: Networks, North-Holland
Jünger, M., G. Reinelt and G. Rinaldi (1997), "The Traveling Salesman Problem", in: M. Dell' Amico, F. Maffioli, S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization, 199-221, Wiley
Jünger, M., G. Reinelt and S. Thienel (1994), "Optimal and Provably Good Solutions for the Symmetric Traveling Salesman Problem", Zeitschrift fu"r Operations Research (40), 183-217
Padberg, M.W. and G. Rinaldi (1987), "Optimization of a 532 City Symmetric Traveling Salesman Problem by Branch and Cut", Operations Research Letters (6), 1-7
Padberg, M.W. and G. Rinaldi (1991), "A Branch and Cut Algorithm for
the Resolution of Large-scale Symmetric Traveling Salesman Problems" SIAM
Review (33), 60-100}