TSP Generator <- Research <- Sean Forman <- You Are Here
|
| 1 2 3 4 5 | 6 7 8 9 10 | 11 12 13 14 15 | 16
-----------------------+--------------------------------+--------------------------------+--------------------------------+-------
1 Philadelphia PA | 11 71 60 58 | 97 43 31 69 39 | 18 15 41 84 46 | 100
2 Camden NJ | 11 60 71 53 | 94 50 37 64 29 | 29 11 48 73 51 | 102
3 Dover DE | 71 60 129 61 | 105 102 89 76 42 | 88 61 96 29 100 | 137
4 Newark NJ | 60 71 129 94 | 139 63 64 118 98 | 48 68 43 144 70 | 120
5 Atlantic Cit NJ | 58 53 61 94 | 142 101 89 110 66 | 74 44 51 89 103 | 156
-----------------------+--------------------------------+--------------------------------+--------------------------------+-------
6 Harrisburg PA | 97 94 105 139 142 | 76 76 32 76 | 95 104 138 86 69 | 50
7 Bethlehem PA | 43 50 102 63 101 | 76 13 59 61 | 29 57 73 104 7 | 61
8 Quakertown PA | 31 37 89 64 89 | 76 13 54 49 | 20 45 65 93 14 | 69
9 Lancaster PA | 69 64 76 118 110 | 32 59 54 45 | 71 74 110 62 53 | 64
10 Wilmington DE | 39 29 42 98 66 | 76 61 49 45 | 52 36 76 47 58 | 98
-----------------------+--------------------------------+--------------------------------+--------------------------------+-------
11 New Hope PA | 18 29 88 48 74 | 95 29 20 71 52 | 33 45 98 33 | 89
12 Marlton NJ | 15 11 61 68 44 | 104 57 45 74 36 | 33 40 78 59 | 112
13 Lakewood NJ | 41 48 96 43 51 | 138 73 65 110 76 | 45 40 117 78 | 134
14 Chestertown MD | 84 73 29 144 89 | 86 104 93 62 47 | 98 78 117 101 | 126
15 Allentown PA | 46 51 100 70 103 | 69 7 14 53 58 | 33 59 78 101 | 56
-----------------------+--------------------------------+--------------------------------+--------------------------------+-------
16 Bloomsburg PA | 100 102 137 120 156 | 50 61 69 64 98 | 89 112 134 126 56 |
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 642 Camden, NJ 657 Dover, DE 614 Newark, NJ 650 Atlantic City, NJ 682 Harrisburg, PA 651 Bethlehem, PA 647 Quakertown, PA 647 Lancaster, PA 626 Wilmington, DE 614 New Hope, PA 599 Marlton, NJ 635 Lakewood, NJ 650 Chestertown, MD 637 Allentown, PA 648 Bloomsburg, PA 635 BEST ROUTE BY REPETITIVE NEAREST NEIGHBOR: New Hope, PA 599 ROUTE BY NEAREST NEIGHBOR: New Hope, PA -> Philadelphia, PA 18 Philadelphia, PA -> Camden, NJ 11 Camden, NJ -> Marlton, NJ 11 Marlton, NJ -> Wilmington, DE 36 Wilmington, DE -> Dover, DE 42 Dover, DE -> Chestertown, MD 29 Chestertown, MD -> Lancaster, PA 62 Lancaster, PA -> Harrisburg, PA 32 Harrisburg, PA -> Bloomsburg, PA 50 Bloomsburg, PA -> Allentown, PA 56 Allentown, PA -> Bethlehem, PA 7 Bethlehem, PA -> Quakertown, PA 13 Quakertown, PA -> Newark, NJ 64 Newark, NJ -> Lakewood, NJ 43 Lakewood, NJ -> Atlantic City, NJ 51 Atlantic City, NJ -> New Hope, PA 74 ------ DISTANCE: 599CHEAPEST LINK APPROXIMATE SOLUTION
ROUTE FOUND BY CHEAPEST LINK: Philadelphia, PA -> Camden, NJ 11 Camden, NJ -> Marlton, NJ 11 Marlton, NJ -> Wilmington, DE 36 Wilmington, DE -> Dover, DE 42 Dover, DE -> Chestertown, MD 29 Chestertown, MD -> Atlantic City, NJ 89 Atlantic City, NJ -> Lakewood, NJ 51 Lakewood, NJ -> Newark, NJ 43 Newark, NJ -> Bloomsburg, PA 120 Bloomsburg, PA -> Harrisburg, PA 50 Harrisburg, PA -> Lancaster, PA 32 Lancaster, PA -> Allentown, PA 53 Allentown, PA -> Bethlehem, PA 7 Bethlehem, PA -> Quakertown, PA 13 Quakertown, PA -> New Hope, PA 20 New Hope, PA -> Philadelphia, PA 18 ------ DISTANCE: 625
BRANCH AND BOUND OPTIMUM SOLUTION
Technical Explanation THIS SOLUTION IS GUARANTEED TO BE OPTIMAL
ROUTE FOUND BY BRANCH AND BOUND: Camden, NJ -> Wilmington, DE 29 Wilmington, DE -> Dover, DE 42 Dover, DE -> Chestertown, MD 29 Chestertown, MD -> Lancaster, PA 62 Lancaster, PA -> Harrisburg, PA 32 Harrisburg, PA -> Bloomsburg, PA 50 Bloomsburg, PA -> Allentown, PA 56 Allentown, PA -> Bethlehem, PA 7 Bethlehem, PA -> Quakertown, PA 13 Quakertown, PA -> New Hope, PA 20 New Hope, PA -> Newark, NJ 48 Newark, NJ -> Lakewood, NJ 43 Lakewood, NJ -> Atlantic City, NJ 51 Atlantic City, NJ -> Marlton, NJ 44 Marlton, NJ -> Philadelphia, PA 15 Philadelphia, PA -> Camden, NJ 11 ------ DISTANCE: 552 Searched 38256 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.