TSP Generator <- Research <- Sean Forman <- You Are Here
|
| 1 2 3 4 5 | 6 7 8 9
-----------------------+--------------------------------+-------------------------
1 Chicago IL | 203 748 954 579 | 712 672 997 400
2 Iowa City IA | 203 946 858 665 | 914 873 1070 222
3 Burlington VT | 748 946 1595 938 | 264 317 1240 1147
4 Houston TX | 954 858 1595 727 | 1433 1368 807 670
5 Atlanta GA | 579 665 938 727 | 732 666 418 676
-----------------------+--------------------------------+-------------------------
6 New York NY | 712 914 264 1433 732 | 66 992 1085
7 Philadelphia PA | 672 873 317 1368 666 | 66 929 1036
8 Tampa FL | 997 1070 1240 807 418 | 992 929 1039
9 Kansas City MO | 400 222 1147 670 676 | 1085 1036 1039
Maps produced by the U.S. Census Bureau's Tiger Mapping Service, and hence may not always be available. When mapping large distances the projection may become distorted.
REPETITIVE NEAREST NEIGHBOR SOLUTION
DISTANCES BY NEAREST NEIGHBOR BEGINNING AT: Chicago, IL 4247 Iowa City, IA 4623 Burlington, VT 4064 Houston, TX 4946 Atlanta, GA 4260 New York, NY 4363 Philadelphia, PA 4247 Tampa, FL 5030 Kansas City, MO 5074 BEST ROUTE BY REPETITIVE NEAREST NEIGHBOR: Burlington, VT 4064 ROUTE BY NEAREST NEIGHBOR: Burlington, VT -> New York, NY 264 New York, NY -> Philadelphia, PA 66 Philadelphia, PA -> Atlanta, GA 666 Atlanta, GA -> Tampa, FL 418 Tampa, FL -> Houston, TX 807 Houston, TX -> Kansas City, MO 670 Kansas City, MO -> Iowa City, IA 222 Iowa City, IA -> Chicago, IL 203 Chicago, IL -> Burlington, VT 748 ------ DISTANCE: 4064CHEAPEST LINK APPROXIMATE SOLUTION
ROUTE FOUND BY CHEAPEST LINK: Chicago, IL -> Iowa City, IA 203 Iowa City, IA -> Kansas City, MO 222 Kansas City, MO -> Houston, TX 670 Houston, TX -> Burlington, VT 1595 Burlington, VT -> New York, NY 264 New York, NY -> Philadelphia, PA 66 Philadelphia, PA -> Tampa, FL 929 Tampa, FL -> Atlanta, GA 418 Atlanta, GA -> Chicago, IL 579 ------ DISTANCE: 4946
BRANCH AND BOUND OPTIMUM SOLUTION
Technical Explanation THIS SOLUTION IS GUARANTEED TO BE OPTIMAL
ROUTE FOUND BY BRANCH AND BOUND: Iowa City, IA -> Kansas City, MO 222 Kansas City, MO -> Houston, TX 670 Houston, TX -> Tampa, FL 807 Tampa, FL -> Atlanta, GA 418 Atlanta, GA -> Philadelphia, PA 666 Philadelphia, PA -> New York, NY 66 New York, NY -> Burlington, VT 264 Burlington, VT -> Chicago, IL 748 Chicago, IL -> Iowa City, IA 203 ------ DISTANCE: 4064 Searched 57 nodes.
All distances are generated using a database of latitude and longitudes tied to zip codes. For cities with multiple zip codes the most heavily populated one is chosen. From the latitude and longitude, the great circle distance (explanation) is computed and used for the calculations.
The optimal solution is computed using a Insertion Branch-and-Bound Technique. This is implemented in Perl on a commercial server, so it is far from the fastest solver around. Any attempt at an optimal solution is terminated after 40000 nodes are searched or a solution is found, whichever comes first. This results in about 15 seconds of actual server use.