.... Solving TSPs
....


World TSP

National TSPs

VLSI TSPs

CIA Factbook

GEOnet Server

GNIS Data

Earth


TSP Links

TSPLIB

Home page


We list below 25 TSP instances taken from the World TSP. For these instances, the cost of travel between cities is specified by the Eulidean distance rounded to the nearest whole number (the TSPLIB EUC_2D-norm). The TSPs range in size from 29 cities in Western Sahara to 71,009 cities in China; they provide additional tests to complement the TSPLIB collection. The TSPs were derived from data contained in the National Imagery and Mapping Agency database of geographic feature names. In a number of instances the data sets contained duplicates of city locations (with different names); the TSP instances with duplications are noted in the list below.

We will be most happy to report any improved tours or improved lower bounds that you may find.  A summary of the current solution status for the instances can be found here.


Argentina Flag (CIA Factbook)

Argentina - 9,152 Cities (Includes duplications; 6,723 distinct cities)
Point Set
Tour (within 0.012% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, ar9125)
Log of Computation

Burma Flag (CIA Factbook)

Burma - 33,708 Cities
Point Set
Tour (within 0.031% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, bm33708)
Log of Computation



China Flag (CIA Factbook)

China - 71,009 Cities
Point Set
Tour (within 0.024% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, ch71009)
Log of Computation

Djibouti Flag (CIA Factbook)

Djibouti - 38 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, dj38)
Log of Computation



Egypt Flag (CIA Factbook)

Egypt - 7,146 Cities
Point Set
Tour (within 0.021% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, eg7146)
Log of Computation

Finland Flag (CIA Factbook)

Finland - 10,639 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, fi10639)
Log of Computation



Greece Flag (CIA Factbook)

Greece - 9,882 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, gr9882)
Log of Computation

Honduras Flag (CIA Factbook)

Honduras - 14,473 Cities (Includes duplications; 7,103 distinct cities)
Point Set
Tour (within 0.093% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, ho14473)
Log of Computation



Ireland Flag (CIA Factbook)

Ireland - 8,246 Cities
Point Set
Tour (within 0.021% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, ei8246)
Log of Computation

Japan Flag (CIA Factbook)

Japan - 9,847 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, ja9847)
Log of Computation



Kazakhstan Flag (CIA Factbook)

Kazakhstan - 9,976 Cities
Point Set
Tour (within 0.028% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, kz9976)
Log of Computation

Luxembourg Flag (CIA Factbook)

Luxembourg - 980 Cities (Includes duplications; 634 distinct cities)
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, lu980)
Log of Computation



Morocco Flag (CIA Factbook)

Morocco - 14,185 Cities
Point Set
Tour (within 0.031% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, mo14185)
Log of Computation

Nicaragua Flag (CIA Factbook)

Nicaragua - 3,496 Cities (Includes duplications; 2,373 distinct cities)
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, nu3496)
Log of Computation



Oman Flag (CIA Factbook)

Oman - 1,979 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, mu1979)
Log of Computation

Nicaragua Flag (CIA Factbook)

Panama - 8,079 Cities (Includes duplications; 4,951 distinct cities)
Point Set
Sample Tour
CIA World Factbook Map
Data (TSPLIB Format, pm8079)
Log of Computation



Qatar Flag (CIA Factbook)

Qatar - 194 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, qa194)
Log of Computation

Rwanda Flag (CIA Factbook)

Rwanda - 1,621 Cities (Includes duplications; 866 distinct cities)
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, rw1621)
Log of Computation



Sweden Flag (CIA Factbook)

Sweden - 24,978 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, sw24978)
Log of Computation

Tanzania Flag (CIA Factbook)

Tanzania - 6,117 Cities
Point Set
Tour (within 0.027% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, tz6117)
Log of Computation



Uruguay Flag (CIA Factbook)

Uruguay - 734 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, uy734)
Log of Computation

Vietnam Flag (CIA Factbook)

Vietnam - 22,775 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, vm22775)
Log of Computation



Western Sahara Flag (African Studies Page)

Western Sahara - 29 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, wi29)
Log of Computation

Yeman Flag (CIA Factbook)

Yemen - 7,663 Cities
Point Set
Tour (within 0.030% of optimal)
CIA World Factbook Map
Data (TSPLIB Format, ym7663)
Log of Computation



Zimbabwe Flag (CIA World Factbook)

Zimbabwe - 929 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, zi929)
Log of Computation



Canada Flag (CIA World Factbook)

Canada - 4,663 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, ca4663)
Log of Computation

Italy Flag (CIA World Factbook)

Italy - 16,862 Cities
Point Set
Optimal Tour
CIA World Factbook Map
Data (TSPLIB Format, it16862)
Log of Computation

Back to TSP home.

Last Updated:  April 28, 2009
Contact:  bico@uwaterloo.ca