Example 14.2 Network Flow and Delay

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

The five roads connect four intersections illustrated by numbered nodes. Each minute, $F$ vehicles enter and leave the network. The parameter $x_{ij}$ refers to the flow from node $i$ to node $j$. The requirement that traffic that flows into each intersection $j$ must also flow out is described by the linear equality constraint

\[  \sum _ i x_{ij} = \sum _ i x_{ji} \quad , \quad j=1,\ldots ,n  \]

In general, roads also have an upper limit on the number of vehicles that can be handled per minute. These limits, denoted $c_{ij}$, can be enforced by boundary constraints:

\[  0 \le x_{ij} \le c_{ij}  \]

The goal in this problem is to maximize the flow, which is equivalent to maximizing the objective function $f(x)$, where $f(x)$ is

\[  f(x) = x_{24} + x_{34}  \]

The boundary constraints are

$\displaystyle  0 \le  $
$\displaystyle  x_{12}, x_{32}, x_{34}  $
$\displaystyle  \le 10  $
$\displaystyle 0 \le  $
$\displaystyle  x_{13}, x_{24}  $
$\displaystyle  \le 30  $

and the flow constraints are

$\displaystyle  x_{13}  $
$\displaystyle  =  $
$\displaystyle  x_{32} + x_{34}  $
$\displaystyle x_{24}  $
$\displaystyle  =  $
$\displaystyle  x_{12} + x_{32}  $
$\displaystyle x_{12} + x_{13}  $
$\displaystyle  =  $
$\displaystyle  x_{24} + x_{34}  $

The three linear equality constraints are linearly dependent. One of them is deleted automatically by the optimization subroutine. The following notation is used in this example:

\[  X1=x_{12},~ ~  X2=x_{13},~ ~  X3=x_{32},~ ~  X4=x_{24},~ ~  X5=x_{34}  \]

Even though the NLPCG subroutine is used, any other optimization subroutine would also solve this small problem. The following code finds the maximum flow:

   proc iml;
      title 'Maximum Flow Through a Network';
      start MAXFLOW(x);
         f = x[4] + x[5];
         return(f);
      finish MAXFLOW;

      con = {  0.  0.  0.  0.  0.   .   . ,
              10. 30. 10. 30. 10.   .   . ,
               0.  1. -1.  0. -1.  0.  0. ,
               1.  0.  1. -1.  0.  0.  0. ,
               1.  1.  0. -1. -1.  0.  0. };
      x = j(1,5, 1.);
      optn = {1 3};
      call nlpcg(xres,rc,"MAXFLOW",x,optn,con);

The optimal solution is shown in the following output.

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
Active
Bound
Constraint
1 X1 10.000000 0 Upper BC
2 X2 10.000000 0  
3 X3 10.000000 1.000000 Upper BC
4 X4 20.000000 1.000000  
5 X5 0 0 Lower BC

Finding the maximum flow through a network is equivalent to solving a simple linear optimization problem, and for large problems, the LP procedure or the NETFLOW procedure of the SAS/OR product can be used. On the other hand, finding a traffic pattern that minimizes the total delay to move $F$ vehicles per minute from node 1 to node 4 includes nonlinearities that need nonlinear optimization techniques. As traffic volume increases, speed decreases. Let $t_{ij}$ be the travel time on arc $(i,j)$ and assume that the following formulas describe the travel time as decreasing functions of the amount of traffic:

$\displaystyle  t_{12}  $
$\displaystyle  =  $
$\displaystyle  5 + 0.1 x_{12} / (1 - x_{12}/10)  $
$\displaystyle t_{13}  $
$\displaystyle  =  $
$\displaystyle  x_{13} / (1 - x_{13}/30)  $
$\displaystyle t_{32}  $
$\displaystyle  =  $
$\displaystyle  1 + x_{32} / (1 - x_{32}/10)  $
$\displaystyle t_{24}  $
$\displaystyle  =  $
$\displaystyle  x_{24} / (1 - x_{24}/30)  $
$\displaystyle t_{34}  $
$\displaystyle  =  $
$\displaystyle  5 + x_{34} / (1 - x_{34}/10)  $

These formulas use the road capacities (upper bounds), and you can assume that $F=5$ vehicles per minute have to be moved through the network. The objective is now to minimize

\[  f =f(x)= t_{12} x_{12} + t_{13} x_{13} + t_{32} x_{32} + t_{24} x_{24} + t_{34} x_{34}  \]

The constraints are

$\displaystyle  0 \le  $
$\displaystyle  x_{12}, x_{32}, x_{34}  $
$\displaystyle  \le 10  $
$\displaystyle 0 \le  $
$\displaystyle  x_{13}, x_{24}  $
$\displaystyle  \le 30  $
$\displaystyle  x_{13}  $
$\displaystyle  =  $
$\displaystyle  x_{32} + x_{34}  $
$\displaystyle x_{24}  $
$\displaystyle  =  $
$\displaystyle x_{12} + x_{32}  $
$\displaystyle x_{24} + x_{34}  $
$\displaystyle  =  $
$\displaystyle  F = 5  $

In the following code, the NLPNRR subroutine is used to solve the minimization problem:

   proc iml;
      title 'Minimize Total Delay in Network';
      start MINDEL(x);
         t12 = 5. + .1 * x[1] / (1. - x[1] / 10.);
         t13 = x[2] / (1. - x[2] / 30.);
         t32 = 1. + x[3] / (1. - x[3] / 10.);
         t24 = x[4] / (1. - x[4] / 30.);
         t34 = 5. + .1 * x[5] / (1. - x[5] / 10.);
         f = t12*x[1] + t13*x[2] + t32*x[3] + t24*x[4] + t34*x[5];
         return(f);
      finish MINDEL;

      con = {  0.  0.  0.  0.  0.   .   . ,
              10. 30. 10. 30. 10.   .   . ,
               0.  1. -1.  0. -1.  0.  0. ,
               1.  0.  1. -1.  0.  0.  0. ,
               0.  0.  0.  1.  1.  0.  5. };

      x = j(1,5, 1.);
      optn = {0 3};
      call nlpnrr(xres,rc,"MINDEL",x,optn,con);

The optimal solution is shown in the following output.

Optimization Results
Parameter Estimates
N Parameter Estimate Gradient
Objective
Function
Active
Bound
Constraint
1 X1 2.500000 5.777778  
2 X2 2.500000 5.702479  
3 X3 5.09575E-18 1.000000 Lower BC
4 X4 2.500000 5.702480  
5 X5 2.500000 5.777778  

The active constraints and corresponding Lagrange multiplier estimates (costs) are shown in the following output.

Linear Constraints Evaluated at Solution
1 ACT 4.4409E-16 = 0 + 1.0000 * X2 - 1.0000 * X3 - 1.0000 * X5
2 ACT 4.4409E-16 = 0 + 1.0000 * X1 + 1.0000 * X3 - 1.0000 * X4
3 ACT 0 = -5.0000 + 1.0000 * X4 + 1.0000 * X5        

First Order Lagrange Multipliers
Active Constraint Lagrange
Multiplier
Lower BC X3 0.924702
Linear EC [1] 5.702479
Linear EC [2] 5.777778
Linear EC [3] 11.480257