The OPTNET Procedure

Example 2.7 Traveling Salesman Tour through US Capital Cities

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 OPTNET statements find the optimal tour through each of the capital cities:

/* Find optimal tour using OPTNET */
proc optnet
   loglevel   = moderate
   data_links = CitiesDist
   out_nodes  = TSPTourNodes;
   data_links_var
      from    = city1
      to      = city2
      weight  = distance;
   tsp
      out     = TSPTourLinks;
run;
%put &_OROPTNET_;
%put &_OROPTNET_TSP_;

The progress of the procedure is shown in Output 2.7.1. The total mileage needed to optimally traverse the capital cities is $10,627.75$ miles.

Output 2.7.1: PROC OPTNET Log: Traveling Salesman Tour through US Capital Cities

NOTE: ------------------------------------------------------------------------------------------
NOTE: ------------------------------------------------------------------------------------------
NOTE: Running OPTNET version 13.2.                                                              
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.00 (cpu: 0.02) seconds.                                                 
NOTE: Building the input graph storage used 0.00 (cpu: 0.00) seconds.                           
NOTE: The input graph storage is using 0.2 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 10645.918753 using 0.08 (cpu: 0.06)     
NOTE: The MILP presolver value NONE is applied.                                                 
NOTE: The MILP solver is called.                                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time                   
             0       1       1  10645.9187534  10040.5139714    6.03%       0                   
             0       1       1  10645.9187534  10241.6970024    3.95%       0                   
             0       1       1  10645.9187534  10262.9074205    3.73%       0                   
             0       1       1  10645.9187534  10350.0790852    2.86%       0                   
             0       1       1  10645.9187534  10381.4538838    2.55%       0                   
             0       1       1  10645.9187534  10470.6122886    1.67%       0                   
             0       1       1  10645.9187534  10492.6949171    1.46%       0                   
             0       1       1  10645.9187534  10560.1837745    0.81%       0                   
             0       1       1  10645.9187534  10576.0823291    0.66%       0                   
             0       1       1  10645.9187534  10590.9748294    0.52%       0                   
             0       1       1  10645.9187534  10607.8528157    0.36%       0                   
             0       1       1  10645.9187534  10607.8528157    0.36%       0                   
NOTE: The MILP solver added 12 cuts with 3309 cut coefficients at the root.                     
NOTE: Objective of the best integer solution found = 10645.918753.                              
NOTE: Processing the traveling salesman problem used 0.09 (cpu: 0.08) seconds.                  
NOTE: ------------------------------------------------------------------------------------------
NOTE: ------------------------------------------------------------------------------------------
NOTE: The TSP solver is restarting using a reduced graph with 49 nodes and 110 links.           
NOTE: ------------------------------------------------------------------------------------------
NOTE: ------------------------------------------------------------------------------------------
NOTE: Processing the traveling salesman problem.                                                
NOTE: The initial TSP heuristics found a tour with cost 10645.918753 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  10645.9187534  10040.5139714    6.03%       0                   
             0       1       1  10645.9187534  10241.6970024    3.95%       0                   
             0       1       1  10645.9187534  10262.9074205    3.73%       0                   
             0       1       1  10645.9187534  10350.0790852    2.86%       0                   
             0       1       1  10645.9187534  10381.4538838    2.55%       0                   
             0       1       1  10645.9187534  10549.5506188    0.91%       0                   
             0       1       1  10645.9187534  10576.0823291    0.66%       0                   
             0       1       1  10645.9187534  10590.9748294    0.52%       0                   
             0       1       1  10645.9187534  10607.8528157    0.36%       0                   
             0       1       6  10645.9187534  10607.8528157    0.36%       0                   
NOTE: The MILP solver added 9 cuts with 61 cut coefficients at the root.                        
             3       1       7  10627.7543183  10627.5490341    0.00%       0                   
NOTE: Optimal within relative gap.                                                              
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_RGAP                                                                     
STATUS=OPTIMAL_RGAP  OBJECTIVE=10627.754318  RELATIVE_GAP=0.000019  ABSOLUTE_GAP=0.2052842127   
PRIMAL_INFEASIBILITY=0  BOUND_INFEASIBILITY=0  INTEGER_INFEASIBILITY=0  BEST_BOUND=10627.549034 
 NODES=4  ITERATIONS=380  CPU_TIME=0.09  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 2.7.2.

Output 2.7.2: Optimal Traveling Salesman Tour through US Capital Cities

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 2.76.

Figure 2.76: Links in the Optimal Traveling Salesman Tour

City Name City Name distance
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
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
    10,627.75