The OPTNET Procedure

Road Network Shortest Path

Consider the following road network between a SAS employee’s home in Raleigh, NC, and the SAS headquarters in Cary, NC.

In this road network (graph), the links are the roads and the nodes are intersections between roads. With each road, you assign a link attribute in the variable time_to_travel to describe the number of minutes it takes to drive from one node to another. The following data were collected using Google Maps (Google 2011), which gives an approximate number of minutes to traverse between two points based on the length of the road and the typical speed during normal traffic patterns:

data LinkSetInRoadNC10am;
   input start_inter $1-20 end_inter $20-40 miles miles_per_hour;
   datalines;
614CapitalBlvd      Capital/WadeAve      0.6  25
614CapitalBlvd      Capital/US70W        0.6  25
614CapitalBlvd      Capital/US440W       3.0  45
Capital/WadeAve     WadeAve/RaleighExpy  3.0  40
Capital/US70W       US70W/US440W         3.2  60
US70W/US440W        US440W/RaleighExpy   2.7  60 
Capital/US440W      US440W/RaleighExpy   6.7  60
US440W/RaleighExpy  RaleighExpy/US40W    3.0  60
WadeAve/RaleighExpy RaleighExpy/US40W    3.0  60
RaleighExpy/US40W   US40W/HarrisonAve    1.3  55
US40W/HarrisonAve   SASCampusDrive       0.5  25
;

data LinkSetInRoadNC10am;
   set LinkSetInRoadNC10am;
   time_to_travel = miles * 1/miles_per_hour * 60;
run;

Using PROC OPTNET, you want to find the route that yields the shortest path between home (614CapitalBlvd) and the SAS headquarters (SASCampusDrive). This can be done with the SHORTPATH statement as follows:

proc optnet
   data_links   = LinkSetInRoadNC10am;
   data_links_var
      from      = start_inter
      to        = end_inter
      weight    = time_to_travel;
   shortpath
      out_paths = ShortPath
      source    = "614CapitalBlvd"
      sink      = "SASCampusDrive";
run;

For more details about shortest path algorithms in PROC OPTNET, see the section Shortest Path. Figure 2.1 displays the output data set ShortPath, which gives the best route to take to minimize travel time at 10:00 a.m. This route is also shown in Google Maps in Figure 2.2.

Figure 2.1: Shortest Path for Road Network at 10:00 A.M.

order start_inter end_inter time_to_travel
1 614CapitalBlvd Capital/WadeAve 1.4400
2 Capital/WadeAve WadeAve/RaleighExpy 4.5000
3 WadeAve/RaleighExpy RaleighExpy/US40W 3.0000
4 RaleighExpy/US40W US40W/HarrisonAve 1.4182
5 US40W/HarrisonAve SASCampusDrive 1.2000
      11.5582


Figure 2.2: Shortest Path for Road Network at 10:00 A.M. in Google Maps

Shortest Path for Road Network at 10:00 A.M. in Google Maps


Now imagine that it is rush hour (5:00 p.m.) and the time to traverse the roads has changed due to traffic patterns. You want to find the route that gives the shortest path for going home from SAS headquarters under different speed assumptions due to traffic. The following data set lists approximate travel times and speeds for driving in the opposite direction:

data LinkSetInRoadNC5pm;
   input start_inter $1-20 end_inter $20-40 miles miles_per_hour;
   datalines;
614CapitalBlvd      Capital/WadeAve      0.6  25
614CapitalBlvd      Capital/US70W        0.6  25
614CapitalBlvd      Capital/US440W       3.0  45
Capital/WadeAve     WadeAve/RaleighExpy  3.0  25 /*high traffic*/
Capital/US70W       US70W/US440W         3.2  60
US70W/US440W        US440W/RaleighExpy   2.7  60 
Capital/US440W      US440W/RaleighExpy   6.7  60
US440W/RaleighExpy  RaleighExpy/US40W    3.0  60
WadeAve/RaleighExpy RaleighExpy/US40W    3.0  60
RaleighExpy/US40W   US40W/HarrisonAve    1.3  55
US40W/HarrisonAve   SASCampusDrive       0.5  25
;

data LinkSetInRoadNC5pm;
   set LinkSetInRoadNC5pm;
   time_to_travel = miles * 1/miles_per_hour * 60;
run;

The following statements are similar to the first PROC OPTNET run, except that they use the LinkSetInRoadNC5pm data set and the SOURCE and SINK option values are reversed:

proc optnet
   data_links   = LinkSetInRoadNC5pm;
   data_links_var
      from      = start_inter
      to        = end_inter
      weight    = time_to_travel;
   shortpath
      out_paths = ShortPath
      source    = "SASCampusDrive"
      sink      = "614CapitalBlvd";
run;

Now, the output data set ShortPath, shown in Figure 2.3, shows the best route for going home. Since the traffic on Wade Avenue is typically heavy at this time of day, the route home is different from the route to work.

Figure 2.3: Shortest Path for Road Network at 5:00 P.M.

order start_inter end_inter time_to_travel
1 SASCampusDrive US40W/HarrisonAve 1.2000
2 US40W/HarrisonAve RaleighExpy/US40W 1.4182
3 RaleighExpy/US40W US440W/RaleighExpy 3.0000
4 US440W/RaleighExpy US70W/US440W 2.7000
5 US70W/US440W Capital/US70W 3.2000
6 Capital/US70W 614CapitalBlvd 1.4400
      12.9582


This new route is shown in Google Maps in Figure 2.4.

Figure 2.4: Shortest Path for Road Network at 5:00 P.M. in Google Maps

Shortest Path for Road Network at 5:00 P.M. in Google Maps