Example 7.1 Shortest Path Problem :: SAS/OR(R) 12.1 User's Guide: Mathematical Programming Legacy Procedures

Example 7.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 Output 7.1.1 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.

Output 7.1.1: 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

Shortest Path Problem

How to get Hawaiian Pineapples to a London Restaurant

NOTE: Number of nodes= 8 .

NOTE: Number of arcs= 13 .

NOTE: Number of iterations performed (neglecting any constraints)= 5 .

NOTE: Of these, 3 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 7.1.2 shows that the best route for the pineapples is from Honolulu to Los Angeles to New York to Heathrow London.

Output 7.1.2: 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