Geographic TSP instances based on United States Cities
The files of the form city<n>.ll hold the longitude and latitude of the largest n cities in the United States (excluding Alaska and Hawaii) in millionths of a degree. (Longitude is degrees west of Meridian; latitude is degrees north of the equator.)
The files of the form city<n>.lab hold the gazateer data for the cities in the same order as city<n>.ll so you can label the cities with their names. This is not needed to contruct the problem instance.
If lon[c] and lat[c] are the longitude and latitude entries of file city<n>.ll for city c, then the distance between two cities x and y in tenths of a kilometer would be:
R*acos(
cos(lon[x]*S)*cos(lat[x]*S)*cos(lon[y]*S)*cos(lat[y]*S)+
sin(lon[x]*S)*sin(lat[x]*S)*sin(lon[y]*S)*sin(lat[y]*S)+
sin(lat[x]*S)*sin(lat[y]*S)
)
where
acos() is the arccosine function,
R=63781.5 (radius of the earth) and
S=0.00000001745329251994 (converts millionths of a degree to radians)
or you can use the following code to convert a file named city.ll to a full n by n matrix in a file named city.mtx.
Here are the problems:
For the asymmetric TSP problem generator developed by Bruno Repetto, click
here.
Neil Simonetti