TSP Generator <- Research <- Sean Forman <- You Are Here
|
| 1 2 3 4 5 | 6 7 8
-----------------------+--------------------------------+-------------------
1 Philadelphia PA | 11 71 60 58 | 97 43 31
2 Camden NJ | 11 60 71 53 | 94 50 37
3 Dover DE | 71 60 129 61 | 105 102 89
4 Newark NJ | 60 71 129 94 | 139 63 64
5 Atlantic Cit NJ | 58 53 61 94 | 142 101 89
-----------------------+--------------------------------+-------------------
6 Harrisburg PA | 97 94 105 139 142 | 76 76
7 Bethlehem PA | 43 50 102 63 101 | 76 13
8 Quakertown PA | 31 37 89 64 89 | 76 13
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: Philadelphia, PA 481 Camden, NJ 472 Dover, DE 519 Newark, NJ 457 Atlantic City, NJ 547 Harrisburg, PA 513 Bethlehem, PA 476 Quakertown, PA 489 BEST ROUTE BY REPETITIVE NEAREST NEIGHBOR: Newark, NJ 457 ROUTE BY NEAREST NEIGHBOR: Newark, NJ -> Philadelphia, PA 60 Philadelphia, PA -> Camden, NJ 11 Camden, NJ -> Quakertown, PA 37 Quakertown, PA -> Bethlehem, PA 13 Bethlehem, PA -> Harrisburg, PA 76 Harrisburg, PA -> Dover, DE 105 Dover, DE -> Atlantic City, NJ 61 Atlantic City, NJ -> Newark, NJ 94 ------ DISTANCE: 457CHEAPEST LINK APPROXIMATE SOLUTION
ROUTE FOUND BY CHEAPEST LINK: Philadelphia, PA -> Camden, NJ 11 Camden, NJ -> Atlantic City, NJ 53 Atlantic City, NJ -> Dover, DE 61 Dover, DE -> Harrisburg, PA 105 Harrisburg, PA -> Newark, NJ 139 Newark, NJ -> Bethlehem, PA 63 Bethlehem, PA -> Quakertown, PA 13 Quakertown, PA -> Philadelphia, PA 31 ------ DISTANCE: 476
BRANCH AND BOUND OPTIMUM SOLUTION
Technical Explanation THIS SOLUTION IS GUARANTEED TO BE OPTIMAL
ROUTE FOUND BY BRANCH AND BOUND: Camden, NJ -> Atlantic City, NJ 53 Atlantic City, NJ -> Dover, DE 61 Dover, DE -> Harrisburg, PA 105 Harrisburg, PA -> Quakertown, PA 76 Quakertown, PA -> Bethlehem, PA 13 Bethlehem, PA -> Newark, NJ 63 Newark, NJ -> Philadelphia, PA 60 Philadelphia, PA -> Camden, NJ 11 ------ DISTANCE: 442 Searched 45 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.