Example 6.9 Minimize Total Delay in a Network

The following example is taken from the user’s guide of GINO (Liebman et al. 1986). A simple network of five roads (arcs) can be illustrated by the path diagram:

Figure 6.11 Simple Road Network

The five roads connect four intersections illustrated by numbered nodes. Each minute vehicles enter and leave the network. Arc refers to the road from intersection to intersection , and the parameter refers to the flow from to . The law that traffic flowing into each intersection must also flow out is described by the linear equality constraint

In general, roads also have an upper capacity, which is the number of vehicles which can be handled per minute. The upper limits can be enforced by boundary constraints

Finding the maximum flow through a network is equivalent to solving a simple linear optimization problem, and for large problems, PROC LP or PROC NETFLOW can be used. The objective function is

and the constraints are

The three linear equality constraints are linearly dependent. One of them is deleted automatically by the PROC NLP subroutines. Even though the default technique is used for this small example, any optimization subroutine can be used.

proc nlp all initial=.5;
   max y;
   parms x12 x13 x32 x24 x34;
   bounds x12 <= 10,
          x13 <= 30,
          x32 <= 10,
          x24 <= 30,
          x34 <= 10;
   /* what flows into an intersection must flow out */
   lincon x13 = x32 + x34,
          x12 + x32 = x24,
          x24 + x34 = x12 + x13;
   y = x24 + x34 + 0*x12 + 0*x13 + 0*x32;
run;

The iteration history is given in Output 6.9.1, and the optimal solution is given in Output 6.9.2.