CITIES
City Distance Datasets

CITIES is a collection of datasets describing intercity distances.

This data can be used for

• traveling salesman problems (connected path through every city);
• K-means calculations (find M spots that minimize total of the distance from each city to its nearest spot);
• K-medians calculations (make M of the cities "special", to minimize the total distance from each city to its nearest special city);
• Weighted K-means or K-medians (let the population of each city be used as a weight, which makes some cities more important);
• Minimal spanning trees (construct the shortest highway system that connects all the cities, using only straight paths from one city to another (ignore the possibility that two roads could cross, or that a Y-shaped connector between three cities might be cheaper);
• Voronoi diagrams (assign each spot of land to the nearest city, making "provinces");

Related Data and Programs:

ASA058 is a FORTRAN77 file containing the original text of the Sparks clustering algorithm ASA136.

ASA136 is a FORTRAN77 implementation of the K-Means algorithm.

CITIES is a FORTRAN90 library of routines for working with datasets of city locations.

KMEANS is a library of FORTRAN90 routines for the K-means problem of grouping a discrete set of N points into K clusters.

LAU_NP is a library of FORTRAN90 routines for heuristic approaches to certain NP-complete problems, including the traveling salesman problem, the K-center problem and the K-median problem.

SPAETH is a library of FORTRAN90 routines which can cluster data according to various principles.

The SPAETH dataset collection contains a set of test data.

SPAETH2 is a library of FORTRAN90 routines which can cluster data according to various principles.

The SPAETH2 dataset collection contains a set of test data.

TOMS456 is a routine for the routing problem, connecting some nodes in a network.

Datasets:

CO04 gives the distances between 4 cities; the goal is to choose some of the cities as distribution sites; for each city, we then choose the FURTHEST distribution site, so as to MAXIMIZE the total transportation cost to all cities.

• co04_main.txt, is the main file.
• co04_dist.txt, the city-to-city NONSYMMETRIC transportation matrix.
• co04_weight.txt, contains weights that may be applied to the cities.

HA29 describes the airline distances, in hundreds of miles, between 29 international cities.

• ha29_main.txt, is the main file.
• ha29_dist.txt, the city-to-city distance matrix.
• ha29_code.txt, contains a code for each city.
• ha29_name.txt, contains the name of each city.

KN57 describes the distance in miles between 57 cities.

• kn57_main.txt, is the main file.
• kn57_dist.txt, the city-to-city distance matrix.

LAU15 describes the distance between 15 cities, and seeks a solution to the traveling salesman problem.

• lau15_main.txt, is the main file.
• lau15_dist.txt, the city-to-city distance matrix.
• lau15_tsp.txt, an itinerary that solves the traveling salesman problem.

SGB128 describes 128 cities in North America.

• sgb128_main.txt, is the main file.
• sgb128_dist.txt, the city-to-city road distance matrix.
• sgb128_weight.txt, the weight (population) of each city.
• sgb128_name.txt, the name of each city.
• sgb128_dms.txt, the latitude and longitude of each city.
• sgb128_map.tex, a TeX file to draw a picture of the cities.
• sgb128_map.png, a PNG image of the map of the cities.

SH07 gives the distances between 7 cities; the goal is to choose 3 of the cities as distribution sites so as to minimize the total transportation cost to all cities.

• sh07_main.txt, is the main file.
• sh07_dist.txt, the city-to-city distance matrix.

SP11 describes 11 artificial cities, with arbitrary integer distances.

• sp11_main.txt, is the main file.
• sp11_dist.txt, the city-to-city distance matrix.
• sp11_code.txt, contains a code for each city.

UK12 describes 12 cities, with integer distances representing the travel time, in minutes, between pairs of cities.

• uk12_main.txt, is the main file.
• uk12_dist.txt, the city-to-city distance matrix.
• uk12_code.txt, contains a code for each city.
• uk12_name.txt, the name of each city.

USCA312 describes 312 cities in the US and Canada.

• usca312_main.txt, is the main file.
• usca312_name.txt, the name of each city.
• usca312_dist.txt, is the city-to-city distance, in miles, computed from the latitude/longitude data and rounded to integers.
• usca312_dms.txt, the latitude and longitude of each city.

WG22 describes 22 cities in West Germany.

• wg22_main.txt, is the main file.
• wg22_xy.txt, contains the (X,Y) coordinates of each city.
• wg22_xy.png, a PNG image of the (X,Y) coordinates of each city.
• wg22_name.txt, the name of each city.
• wg22_dist.txt, the city-to-city distance matrix.

WG59 describes 59 cities in West Germany.

• wg59_main.txt, is the main file.
• wg59_xy.txt, contains the (X,Y) coordinates of each city.
• wg59_xy.png, a PNG image of the (X,Y) coordinates of each city.
• wg59_name.txt, the name of each city.
• wg59_dist.txt, the city-to-city distance matrix.

You can go up one level to the DATASETS directory.