Example 5.9: Minimize Total Delay in a Network

The NLP Procedure

Example 5.9: Minimize Total Delay in a Network

The following example is taken from the user's guide of GINO (Liebman, Lasdon, Schrage, & Waren, 1986). A simple network of five roads (arcs) can be illustrated by the path diagram:

$\begin{picture} (300.,120.) \put(160.,60.){\circle{10.}} \put(157.,57.)1 \put(20... ...){\vector(1,0)5} \put(245.,60.){\dashbox{2.}(35,0)} \put(290.,60.)F\end{picture}$

Figure 12: Simple Road Network

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

$\sum_i x_{ij} = \sum_i x_{ji} , j=1, ... ,n .$

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

$0 \le x_{ij} \le c_{ij} , i,j=1, ... ,n .$

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

maxf = x₂₄ + x₃₄

and the constraints are

$0 \le x_{12}, x_{32}, x_{34} \le 10$

$0 \le x_{13}, x_{24} \le 30$

x₁₃ = x₃₂ + x₃₄

x₁₂ + x₃₂ = x₂₄

x₁₂ + x₁₃ = x₂₄ + x₃₄

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 optimal solution follows.

PROC NLP: Nonlinear Maximization

Iteration		Restarts	Function Calls	Active Constraints	Objective Function	Objective Function Change	Max Abs Gradient Element	Ridge	Ratio Between Actual and Predicted Change
1	*	0	2	4	20.25000	19.2500	0.5774	0.0313	0.860
2	*	0	3	5	30.00000	9.7500	0	0.0313	1.683

Optimization Results
Iterations	2	Function Calls	4
Hessian Calls	3	Active Constraints	5
Objective Function	30	Max Abs Gradient Element	0
Ridge	0	Actual Over Pred Change	1.6834532374

All parameters are actively constrained. Optimization cannot proceed.

Output 5.9.1: Iteration History

PROC NLP: Nonlinear Maximization

Optimization Results
Parameter Estimates
N	Parameter	Estimate	Gradient Objective Function	Active Bound Constraint
1	x12	10.000000	0	Upper BC
2	x13	20.000000	0
3	x32	10.000000	0	Upper BC
4	x24	20.000000	1.000000
5	x34	10.000000	1.000000	Upper BC

Output 5.9.2: Optimization Results Finding a traffic pattern that minimizes the total delay to move F vehicles per minute from node 1 to node 4 introduces nonlinearities that, in turn, demand nonlinear optimization techniques. As traffic volume increases, speed decreases. Let t_ij be the travel time on arc_ij and assume that the following formulas describe the travel time as decreasing functions of the amount of traffic:

t₁₂ = 5 + 0.1 x₁₂ / (1 - x₁₂/10)

t₁₃ = x₁₃ / (1 - x₁₃/30)

t₃₂ = 1 + x₃₂ / (1 - x₃₂/10)

t₂₄ = x₂₄ / (1 - x₂₄/30)

t₃₄ = 5 + .1 * x₃₄ / (1 - x₃₄/10)

These formulas use the road capacities (upper bounds), assuming F=5 vehicles per minute have to be moved through the network. The objective function is now

minf = t₁₂ x₁₂ + t₁₃ x₁₃ + t₃₂ x₃₂ + t₂₄ x₂₄ + t₃₄ x₃₄

and the constraints are:

$0 \le x_{12}, x_{32}, x_{34} \le 10$

$0 \le x_{13}, x_{24} \le 30$

x₁₃ = x₃₂ + x₃₄

x₁₂ + x₃₂ = x₂₄

x₂₄ + x₃₄ = F = 5

Again, just for variety, the default algorithm is used:

proc nlp all initial=.5;
   min y;
   parms x12 x13 x32 x24 x34;
   bounds x12 x13 x32 x24 x34 >= 0;
   lincon x13 = x32 + x34,  /* flow in = flow out */
          x12 + x32 = x24,
          x24 + x34 = 5;    /* = f = desired flow */
   t12 = 5 + .1 * x12 / (1 - x12 / 10);
   t13 = x13 / (1 - x13 / 30);
   t32 = 1 + x32 / (1 - x32 / 10);
   t24 = x24 / (1 - x24 / 30);
   t34 = 5 + .1 * x34 / (1 - x34 / 10);
   y = t12*x12 + t13*x13 + t32*x32 + t24*x24 + t34*x34;
run;

The optimal solution follows.