An Algorithm for Traffic Equilibrium Flow with Capacity Constraints of Arcs

Zhi Lin

College of Sciences, Chongqing Jiaotong University, Chongqing, China.

DOI: 10.4236/jtts.2015.54022                

Abstract

In the traffic equilibrium problem, we introduce capacity constraints of arcs, extend Beckmann’s formula to include these constraints, and give an algorithm for traffic equilibrium flows with capacity constraints on arcs. Using an example, we illustrate the application of the algorithm and show that Beckmann’s formula is a sufficient condition only, not a necessary condition, for traffic equilibrium with capacity constraints of arcs.

Keywords

The Traffic Equilibrium Problem with Capacity Constraints of Arcs, Equilibrium Flow, Algorithm, Capacity of Arc, Saturated Path

1. Introduction

In [1] , Wardrop introduced the traffic equilibrium problem and proposed a scalar equilibrium principle. In [2] , Beckmann et al. gave a mathematical programming problem that was equivalent to Wardrop’s traffic equilibrium problem. Using Beckmann’s work, it is possible to find the traffic equilibrium flow if the cost function is a scalar. In [3] , Chen and Yen generalized Wardrop’s equilibrium principle to a (weak) vector equilibrium principle. In [4] [5] , we extended the vector equilibrium principle to capacity constraints along arcs and derived existence and stability results for (weak) vector equilibrium flows. In this paper, we introduce the traffic equilibrium problem with capacity constraints of arcs (TEPCCA), extend Beckmann’s transformation to cover capacity constraints along arcs, and give an algorithm for traffic equilibrium flows with capacity constraints of arcs for scalar cost functions. As an example, we illustrate the algorithm and show that Beckmann’s transformation is a sufficient condition only, not a necessary condition, for traffic equilibria with capacity constraints of arcs. For other results with respect to traffic equilibrium with capacity constraints of arcs, we refer to [6] , and for other results with respect to algorithms of equilibrium flows, we refer to [7] -[9] and the references therein.

For a traffic network, let V denote the set of nodes, E the set of directed arcs, and W the set of origin- destination O-D pairs. For each, let denote the set of available paths joining O-D pair ω and denote

by. Let denote the demand vector, with denoting the traffic

demand on O-D pair ω. For each, the arc flow. For each and,

let denote the traffic flow on path k.

is said to be a path flow (flow). Clearly, for, , where if arc a belongs to

path k, otherwise, thus. Let denote the capacity vector, where denotes the capacity of flow on arc a. A traffic network is usually denoted by. For each arc, the flow on arc a needs to satisfy the capacity constraint:, and for each, the flow f needs to satisfy the demand constraint:. A flow f satisfying the demand and capacity constraints is called a feasible path flow (a feasible flow for short). Let

.

In this paper, we assume that for each, the demand is fixed and. It is easy to verify that A is convex and compact. For each, let be the cost on arc a, and for each, the cost along path k is assumed to be the sum of all arc costs along k, i.e.,.

2. Preliminaries

For the following definitions, see [4] [5] .

Definition 2.1. Assume that a flow.

1) for, if, then a is said to be a saturated arc of flow f, otherwise a nonsaturated arc of flow f.

2) for, if there exists a saturated arc a of flow f such that a belongs to path k, then k is said to be

a saturated path of flow f, otherwise a nonsaturated path of flow f.

Definition 2.2. (Equilibrium principle with capacity constraints of arcs). A flow is said to be in equilibrium if,

f is said to be an equilibrium flow or solution of the TEPCCA. A TEPCCA is usually denoted by.

3. A Generalization of Beckmann’s Formula

For the TEPCCA, construct the following mathematical programming problem Q:

The above formula is a generalization of Beckmann’s formula. The next theorem shows that each solution of the generalization of Beckmann’s formula is an equilibrium flow for.

Theorem 3.1. Consider the TEPCCA. Assume that for each, is continuous on, then the flow is in equilibrium if f solves the mathematical programming problem Q.

Proof. Set and. The Kuhn-Tucker conditions for the problem Q are:

where and are Lagrange multipliers. Since for each, is continuous on, we have

When path k is a nonsaturated path of flow f, for each, we have. Note that, we have. Thus,

Hence, when k is a nonsaturated path, we have, i.e.,

and when k is a saturated path, we have, i.e.,

In other words, if paths k is a nonsaturated path, then, and if paths k such that, then. Thus, for and j is a nonsaturated path, then, otherwise, which implies that, a contradiction. By Definition 2.2, the proof is finished.

From the generalization of Beckmann’s formula, it is easy to construct an algorithm to calculate the equilibrium flow for the TEPCCA.

4. An Algorithm for the Traffic Equilibrium Flow with Capacity Constraints of Arcs

For the TEPCCA, because there are usually many paths in, implying that there are many variable in the generalization of Beckmann’s formula, it is often difficult to compute its solution. Note that there are many paths for which the flow is zero in an equilibrium flow. If we delete these from K, it does not cause any change in the equilibrium flow. For this season, we construct the following algorithm to compute the equilibrium flow with capacity constraints of arcs. Assume that for each, is continuous on.

Step 1. Find a feasible flow and denote by. Let.

Step 2. Solve the restricted problem:

We obtain solution. For each O-D pair, denote by, where denotes the cost of path l when flow is on the network.

Step 3. After deleting all saturated arcs of the flow in the network, we compute its shortest path for each O-D pair. For each O-D pair, let = {: l is a shortest path for and }.

Step 4. If, go to Step 5; otherwise let and go to Step 2.

Step 5. The equilibrium flow is for the TEPCCA and stop.

The following example shows the calculation process of the algorithm.

Example 4.1. Consider the TEPCCA (see Figure 1), where

, , ,

, ,

and

For O-D pair: contains paths, , , and, and for O-D pair: contains paths, , and.

Let, where denotes the flow on path. Thus, we have

.

Next, we compute the equilibrium flow with capacity constraints of arcs.

1) It is easy to verify that

.

. Let.

2) Solve the restricted problem:

We obtain solution. For O-D pair, , and for O-D pair,.

Figure 1. A traffic network.

3) There is no saturated arc of flow in the network. For O-D pair, it is easy to verify that the shortest path is, whereas for O-D pair, the shortest path is. Note that

,

thus.

4) Since, let and solve the restricted problem:

We obtain solution. For O-D pair, , and for O-D pair,.

5) After deleting saturated arc of flow in the network. For O-D pair, it is easy to verify that the shortest path is, whereas for O-D pair, the shortest path is. Note that

,

thus.

6) Since, let and solve the restricted problem:

We obtain solution. For O-D pair, , and for O-D pair,.

7) After deleting saturated arc of flow in the network. For O-D pair, it is easy to verify that the shortest path is, whereas for O-D pair, the shortest path is. Note that

, thus.

8) Because, the equilibrium flow is, hence stop.

Note that

Thus the generalization of Beckmann’s formula Q is:

It is easy to verify that is the solution of the generalization of Beckmann’s formula Q. Clearly, f is an equilibrium flow for the TEPCCA.

Note that is also an equilibrium flow for the TEPCCA, but it is not a

solution of the generalization of Beckmann’s formula Q, i.e., Theorem 3.1 is a sufficient condition only, not a necessary condition.

Acknowledgements

This work was supported by National Natural Science Foundation of China (Grant No. 11271389).

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Wardrop, J. (1952) Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institute of Civil Engineers, Part II, 1, 325-378. http://dx.doi.org/10.1680/ipeds.1952.11362
[2]	Beckmann, M.J., McGuire, C.B. and Winsten, C.B. (1956) Studies in the Economics of Transportation. Yale University Press, New Haven.
[3]	Chen, G.Y. and Yen, N.D. (1993) On the Variational Inequality Model for Network Equilibrium [Internal Report 3. 196 (724)]. Department of Mathematics, University of Pisa.
[4]	Lin, Z. (2010) The Study of Traffic Equilibrium Problems with Capacity Constraints of Arcs. Nonlinear Analysis: Real World Applications, 11, 2280-2284. http://dx.doi.org/10.1016/j.nonrwa.2009.07.002
[5]	Lin, Z. (2010) On Existence of Vector Equilibrium Flows with Capacity Constraints of Arcs. Nonlinear Analysis, 72, 2076-2079. http://dx.doi.org/10.1016/j.na.2009.10.007
[6]	Xu, Y.D. and Li, S.J. (2014) Vector Network Equilibrium Problems with Capacity Constraints of Arcs and Nonlinear Scalarization Methods. Applicable Analysis: An International Journal, 93, 2199-2210. http://dx.doi.org/10.1080/00036811.2013.875160
[7]	Chiou, S.W. (2010) An Efficient Algorithm for Computing Traffic Equilibria Using TRANSYT Model. Applied Mathematical Modelling, 34, 3390-3399. http://dx.doi.org/10.1016/j.apm.2010.02.028
[8]	Xu, M., Chen, A., Qu, Y. and Gao, Z. (2011) A Semismooth Newton Method for Traffic Equilibrium Problem with a General Nonadditive Route Cost. Applied Mathematical Modelling, 35, 3048-3062. http://dx.doi.org/10.1016/j.apm.2010.12.021
[9]	Chen, A., Zhou, Z. and Xu, X.D. (2012) A Self-Adaptive Gradient Projection Algorithm for the Nonadditive Traffic Equilibrium Problem. Computers & Operations Research, 39, 127-138. http://dx.doi.org/10.1016/j.cor.2011.02.018