Consider a cross-country trip where you want to travel the fewest miles to visit all of the capital cities in all US states except Alaska and Hawaii. Finding the optimal route is an instance of the traveling salesman problem, which is described in section Traveling Salesman Problem.
The following PROC SQL statements use the built-in data set maps.uscity
to generate a list of the capital cities and their latitude and longitude:
/* Get a list of the state capital cities (with lat and long) */ proc sql; create table Cities as select unique statecode as state, city, lat, long from maps.uscity where capital='Y' and statecode not in ('AK' 'PR' 'HI'); quit;
From this list, you can generate a links data set CitiesDist
that contains the distances, in miles, between each pair of cities. The distances are calculated by using the SAS function
GEODIST.
/* Create a list of all the possible pairs of cities */ proc sql; create table CitiesDist as select a.city as city1, a.lat as lat1, a.long as long1, b.city as city2, b.lat as lat2, b.long as long2, geodist(lat1, long1, lat2, long2, 'DM') as distance from Cities as a, Cities as b where a.city < b.city; quit;
The following PROC OPTGRAPH statements find the optimal tour through each of the capital cities:
/* Find optimal tour using OPTGRAPH */ proc optgraph loglevel = moderate data_links = CitiesDist out_nodes = TSPTourNodes; data_links_var from = city1 to = city2 weight = distance; tsp out = TSPTourLinks; run; %put &_OPTGRAPH_; %put &_OPTGRAPH_TSP_;
The progress of the procedure is shown in Output 1.15.1. The total mileage needed to optimally traverse the capital cities is miles.
Output 1.15.1: PROC OPTGRAPH Log: Traveling Salesman Tour through US Capital Cities
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Running OPTGRAPH version 14.1. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: The OPTGRAPH procedure is executing in single-machine mode. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Reading the links data set. |
NOTE: There were 1176 observations read from the data set WORK.CITIESDIST. |
NOTE: Data input used 0.01 (cpu: 0.00) seconds. |
NOTE: Building the input graph storage used 0.00 (cpu: 0.02) seconds. |
NOTE: The input graph storage is using 0.7 MBs of memory. |
NOTE: The number of nodes in the input graph is 49. |
NOTE: The number of links in the input graph is 1176. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Processing the traveling salesman problem. |
NOTE: The initial TSP heuristics found a tour with cost 10627.754318 using 0.08 (cpu: 0.08) |
NOTE: The MILP presolver value NONE is applied. |
NOTE: The MILP solver is called. |
Node Active Sols BestInteger BestBound Gap Time |
0 1 1 10627.7543183 10040.5139714 5.85% 0 |
0 1 1 10627.7543183 10241.6970024 3.77% 0 |
0 1 1 10627.7543183 10262.9074205 3.56% 0 |
0 1 1 10627.7543183 10350.0790852 2.68% 0 |
0 1 1 10627.7543183 10549.5506188 0.74% 0 |
0 1 1 10627.7543183 10576.0823291 0.49% 0 |
0 1 1 10627.7543183 10590.9748294 0.35% 0 |
0 1 1 10627.7543183 10607.8528157 0.19% 0 |
0 1 1 10627.7543183 10607.8528157 0.19% 0 |
NOTE: The MILP solver added 11 cuts with 2193 cut coefficients at the root. |
NOTE: Objective of the best integer solution found = 10627.754318. |
NOTE: Processing the traveling salesman problem used 0.10 (cpu: 0.09) seconds. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: The TSP solver is restarting using a reduced graph with 49 nodes and 91 links. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Processing the traveling salesman problem. |
NOTE: The initial TSP heuristics found a tour with cost 10627.754318 using 0.00 (cpu: 0.00) |
NOTE: The MILP presolver value NONE is applied. |
NOTE: The MILP solver is called. |
Node Active Sols BestInteger BestBound Gap Time |
0 1 1 10627.7543183 10042.0227092 5.83% 0 |
0 1 1 10627.7543183 10241.6970024 3.77% 0 |
0 1 1 10627.7543183 10262.9074205 3.56% 0 |
0 1 1 10627.7543183 10350.0790852 2.68% 0 |
0 1 1 10627.7543183 10549.5506188 0.74% 0 |
0 1 1 10627.7543183 10576.0823291 0.49% 0 |
0 1 1 10627.7543183 10590.9748294 0.35% 0 |
0 1 1 10627.7543183 10607.8528157 0.19% 0 |
0 1 1 10627.7543183 10607.8528157 0.19% 0 |
NOTE: The MILP solver added 10 cuts with 53 cut coefficients at the root. |
2 0 2 10627.7543183 10627.7543183 0.00% 0 |
NOTE: Objective = 10627.754318. |
NOTE: Processing the traveling salesman problem used 0.01 (cpu: 0.02) seconds. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: Creating nodes data set output. |
NOTE: Creating traveling salesman data set output. |
NOTE: Data output used 0.00 (cpu: 0.00) seconds. |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: ------------------------------------------------------------------------------------------ |
NOTE: The data set WORK.TSPTOURNODES has 49 observations and 2 variables. |
NOTE: The data set WORK.TSPTOURLINKS has 49 observations and 3 variables. |
STATUS=OK TSP=OPTIMAL |
STATUS=OPTIMAL OBJECTIVE=10627.754318 RELATIVE_GAP=0 ABSOLUTE_GAP=0 PRIMAL_INFEASIBILITY=0 |
BOUND_INFEASIBILITY=0 INTEGER_INFEASIBILITY=0 BEST_BOUND=10627.754318 NODES=3 |
ITERATIONS=383 CPU_TIME=0.11 REAL_TIME=0.11 |
The following PROC GPROJECT and PROC GMAP statements produce a graphical display of the solution:
/* Merge latitude and longitude */ proc sql; /* merge in the lat & long for city1 */ create table TSPTourLinksAnno1 as select unique TSPTourLinks.*, cities.lat as lat1, cities.long as long1 from TSPTourLinks left join cities on TSPTourLinks.city1=cities.city; /* merge in the lat & long for city2 */ create table TSPTourLinksAnno2 as select unique TSPTourLinksAnno1.*, cities.lat as lat2, cities.long as long2 from TSPTourLinksAnno1 left join cities on TSPTourLinksAnno1.city2=cities.city; quit;
/* Create the annotated data set to draw the path on the map (convert lat & long degrees to radians, since the map is in radians) */ data anno_path; set TSPTourLinksAnno2; length function color $8; xsys='2'; ysys='2'; hsys='3'; when='a'; anno_flag=1; function='move'; x=atan(1)/45 * long1; y=atan(1)/45 * lat1; output; function='draw'; color="blue"; size=0.8; x=atan(1)/45 * long2; y=atan(1)/45 * lat2; output; run; /* Get a map with only the contiguous 48 states */ data states; set maps.states (where=(fipstate(state) not in ('HI' 'AK' 'PR'))); run; data combined; set states anno_path; run;
/* Project the map and annotate the data */ proc gproject data=combined out=combined dupok; id state; run; data states anno_path; set combined; if anno_flag=1 then output anno_path; else output states; run;
/* Get a list of the endpoints locations */ proc sql; create table anno_dots as select unique x, y from anno_path; quit;
/* Create the final annotate data set */ data anno_dots; set anno_dots; length function color $8; xsys='2'; ysys='2'; when='a'; hsys='3'; function='pie'; rotate=360; size=0.8; style='psolid'; color="red"; output; style='pempty'; color="black"; output; run;
/* Generate the map with GMAP */ pattern1 v=s c=cxccffcc repeat=100; proc gmap data=states map=states anno=anno_path all; id state; choro state / levels=1 nolegend coutline=black anno=anno_dots des='' name="tsp"; run;
The minimal cost tour through the capital cities is shown on the US map in Output 1.15.2.
Output 1.15.2: Optimal Traveling Salesman Tour through US Capital Cities
The data set TSPTourLinks
contains the links in the optimal tour. To display the links in the order they are to be visited, you can use the following
DATA step:
/* Create the directed optimal tour */ data TSPTourLinksDirected(drop=next); set TSPTourLinks; retain next; if _N_ ne 1 and city1 ne next then do; city2 = city1; city1 = next; end; next = city2; run;
The data set TSPTourLinksDirected
is shown in Figure 1.153.
Figure 1.153: Links in the Optimal Traveling Salesman Tour
City Name | City Name | distance |
---|---|---|
Phoenix | Santa Fe | 378.27 |
Santa Fe | Oklahoma City | 474.92 |
Oklahoma City | Austin | 357.38 |
Austin | Baton Rouge | 394.78 |
Baton Rouge | Jackson | 139.75 |
Jackson | Little Rock | 206.87 |
Little Rock | Jefferson City | 264.75 |
Jefferson City | Topeka | 191.67 |
Topeka | Lincoln | 132.94 |
Lincoln | Des Moines | 168.10 |
Des Moines | Springfield | 243.02 |
Springfield | Indianapolis | 186.46 |
Indianapolis | Frankfort | 129.90 |
Frankfort | Nashville-Davidson | 175.58 |
Nashville-Davidson | Atlanta | 212.61 |
Atlanta | Montgomery | 145.39 |
Montgomery | Tallahassee | 177.14 |
Tallahassee | Columbia | 311.23 |
Columbia | Raleigh | 182.99 |
Raleigh | Richmond | 135.58 |
Richmond | Washington | 97.96 |
Washington | Annapolis | 27.89 |
Annapolis | Dover | 54.01 |
Dover | Trenton | 83.88 |
Trenton | Hartford | 151.65 |
Hartford | Providence | 65.56 |
Providence | Boston | 38.41 |
Boston | Concord | 66.30 |
Concord | Augusta | 117.36 |
Augusta | Montpelier | 139.32 |
Montpelier | Albany | 126.19 |
Albany | Harrisburg | 230.24 |
Harrisburg | Charleston | 287.34 |
Charleston | Columbus | 134.64 |
Columbus | Lansing | 205.08 |
Lansing | Madison | 246.88 |
Madison | Saint Paul | 226.25 |
Saint Paul | Bismarck | 391.25 |
Bismarck | Pierre | 170.27 |
Pierre | Cheyenne | 317.90 |
Cheyenne | Denver | 98.33 |
Denver | Salt Lake City | 373.05 |
Salt Lake City | Helena | 403.40 |
Helena | Boise City | 291.20 |
Boise City | Olympia | 401.31 |
Olympia | Salem | 146.00 |
Salem | Sacramento | 447.40 |
Sacramento | Carson City | 101.51 |
Carson City | Phoenix | 577.84 |
10,627.75 |