The NETFLOW Procedure

Example 5.1: Shortest Path Problem

Whole pineapples are served in a restaurant in London. To ensure freshness, the pineapples are purchased in Hawaii and air freighted from Honolulu to Heathrow in London. The network diagram in Figure 5.40 outlines the different routes that the pineapples could take.

The cost to freight a pineapple is known for each arc. You can use PROC NETFLOW to determine what routes should be used to minimize total shipping cost. The shortest path is the least cost path that all pineapples should use. The SHORTPATH option indicates this type of network problem.

Figure 5.40: Pineapple Routes: Shortest Path Problem

The SINK= option value HEATHROW LONDON is not a valid SAS variable name so it must be enclosed in single quotes. The TAILNODE list variable is FFROM. Because the name of this variable is not _TAIL_ or _FROM_, the TAILNODE list must be specified in the PROC NETFLOW statement. The HEADNODE list must also be explicitly specified because the variable that belongs to this list does not have the name _HEAD_ or _TO_, but is TTO.

  
   title 'Shortest Path Problem'; 
   title2 'How to get Hawaiian Pineapples to a London Restaurant'; 
   data aircost1; 
      input   ffrom&$13. tto&$15. _cost_ ; 
      datalines; 
   Honolulu       Chicago          105 
   Honolulu       San Francisco     75 
   Honolulu       Los Angeles       68 
   Chicago        Boston            45 
   Chicago        New York          56 
   San Francisco  Boston            71 
   San Francisco  New York          48 
   San Francisco  Atlanta           63 
   Los Angeles    New York          44 
   Los Angeles    Atlanta           57 
   Boston         Heathrow London   88 
   New York       Heathrow London   65 
   Atlanta        Heathrow London   76 
   ; 
  
   proc netflow 
      shortpath 
      sourcenode=Honolulu 
      sinknode='Heathrow London'   /* Quotes for embedded blank */ 
      ARCDATA=aircost1 
      arcout=spath; 
      tail    ffrom; 
      head    tto; 
      run; 
  
   proc print data=spath; 
      sum _fcost_; 
      run;
 

The length at optimality is written to the SAS log as

  
   NOTE: Number of nodes= 8 . 
   NOTE: Number of arcs= 13 . 
   NOTE: Number of iterations performed (neglecting any 
         constraints)= 5 . 
   NOTE: Of these, 4 were degenerate. 
   NOTE: Optimum (neglecting any constraints) found. 
   NOTE: Shortest path= 177 . 
   NOTE: The data set WORK.SPATH has 13 observations and 13 
         variables.
 

The output data set ARCOUT=SPATH in Output 5.1.1 shows that the best route for the pineapples is from Honolulu to Los Angeles to New York to Heathrow London.

Output 5.1.1: ARCOUT=SPATH

Shortest Path Problem How to get Hawaiian Pineapples to a London Restaurant Obs ffrom tto _cost_ _CAPAC_ _LO_ _SUPPLY_ _DEMAND_ _FLOW_ _FCOST_ _RCOST_ _ANUMB_ _TNUMB_ _STATUS_ 1 San Francisco Atlanta 63 99999999 0 . . 0 0 37 9 3 LOWERBD NONBASIC 2 Los Angeles Atlanta 57 99999999 0 . . 0 0 24 10 4 LOWERBD NONBASIC 3 Chicago Boston 45 99999999 0 . . 0 0 49 4 2 LOWERBD NONBASIC 4 San Francisco Boston 71 99999999 0 . . 0 0 45 5 3 LOWERBD NONBASIC 5 Honolulu Chicago 105 99999999 0 1 . 0 0 . 1 1 KEY_ARC BASIC 6 Boston Heathrow London 88 99999999 0 . 1 0 0 12 11 5 LOWERBD NONBASIC 7 New York Heathrow London 65 99999999 0 . 1 1 65 . 12 6 KEY_ARC BASIC 8 Atlanta Heathrow London 76 99999999 0 . 1 0 0 . 13 7 KEY_ARC BASIC 9 Honolulu Los Angeles 68 99999999 0 1 . 1 68 . 3 1 KEY_ARC BASIC 10 Chicago New York 56 99999999 0 . . 0 0 49 6 2 LOWERBD NONBASIC 11 San Francisco New York 48 99999999 0 . . 0 0 11 7 3 LOWERBD NONBASIC 12 Los Angeles New York 44 99999999 0 . . 1 44 . 8 4 KEY_ARC BASIC 13 Honolulu San Francisco 75 99999999 0 1 . 0 0 . 2 1 KEY_ARC BASIC                   177