ABSTRACT
In Urban traffic assignment, a road network is divided into several traffic areas by a path or a tree, known as network zoning. In this study, we focus on the problem of finding a path to divide a network into two sub-networks which results the ratio between the sum travel times of two sub-networks (traffic routing in each sub-network such that the sum of all travel times is minimized) and the minimum sum of all travel times in whole network is minimum. We define the ratio as zoning efficiency loss and such a path as a zoning vital path (ZVP for short) and show an algorithm for computing the ZVP.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2012.551.553
URL: https://scialert.net/abstract/?doi=itj.2012.551.553
INTRODUCTION
Suppose that in a given traffic network, with a latency function for each edge specifying the time needed to traverse the edge given its congestion. The network is divided into several sub-networks to practice traffic control, known as network zoning. In the past, some ideal principles of zoning had been studied: homogeneity, exclusiveness, uniqueness, completeness, equity of trip generation (Guo, 2010; ONeill, 1991; Ding et al., 1993). Most previous studies of network zoning rules were based on an important degree of nodes in a road network (Li, 2005). For a simple traffic network with no cut-edge and with one cut-edge, researcher consider network zoning about the traffic assignment and give a strategy to zoning network for the fraction regulation, analyze the regulation effectiveness ratio for the proposed strategy (Shi, 2009).
In this study, we give a new rule of network zoning about traffic assignment. Suppose a network, a rate of traffic between each pair of nodes and a latency function for each edge. How to finding a path to zoning the traffic network into two sub-networks efficiently? We define a different parameter-zoning efficiency loss-for measuring the efficiency loss for traffic zoning assignment which is the ratio between the sum travel times of two sub-networks (traffic routing in each sub-network such that the sum of all travel times is minimized, called as subsystem optimum) and that of a whole network (traffic routing in whole network such that the sum of all travel times is minimized, called as system optimum (Wardrop, 1952; Roughgarden and Tardos, 2002; Roughgarden, 2003). We call a path which results the minimal ratio as a zoning vital path (ZVP for short) and show an algorithm for finding the ZVP.
PROBLEM STATEMENT AND FORMULATION
Let G = (V, E) denote a directed planar network with vertex set V, edge set E and k origin-destination vertex pairs {o1, d1}, ..., {ok, dk}. Denote the set of oi-di paths as Pi and P = ∪iPi. A flow is a function f: P→R+, let:
The demand amount from oi to di is defined as ri. The latency function in each edge e ∈ E is denoted as Ie (x). The latency of a path P with respect to a flow f is defined as the sum of the latencies of the edges in the path, denoted by:
and the cost C (f) of a flow f in G is the total latency incurred by f. Now the problem is how to finding a path to zoning the traffic network G into two sub-networks G1 (V1, E1) and G2 (V2, E2) (V,∪V2 = V, E1∪E2 = E, E1∩E2 = Φ) efficiently?
In order to discuss this question, we make the following assumptions:
• | Flow can be separable |
• | Travelers who follow the decision of the traffic assignment manager |
• | Traffic routing in network so that the sum of all travel times is minimized, called as system optimum. The system optimum feasible flow in a whole network is a special case of the following non-linear program denoted by SO (Roughgarden and Tardos, 2002) |
(1) |
NLP: Model:
(2) |
Subject to:
(3) |
(4) |
The non-linear program of system optimum in a sub-network (each zone), denoted by ZO:
(5) |
NLPj: Model:
(6) |
Subject to:
(7) |
(8) |
where, {oil, dij} is origin-destination pairs in Gj, J = 1, 2. Pij is the set of path of {oij, dij} and rij is the demand flow of {oij, dij}.
If a traffic network G is divided into two sub-networks Gij (Vij, Eij) j = 1, 2 by a zoning path P1∈P, where, P = {P1}, l = 1, ..., n let El and Vl be the edge set and vertex set on Pl, respectively. Then the origin and destination of Pl must be in the boundary of G.
The difference between the number of E1 and E2 satisfied |*E1l|-|E2l| |≤|.
SOLVING THE ROAD NETWORK ZONING PROBLEM:
If there is no zoning, then traffic routing by SO in a whole network: find an assignment of traffic to paths in G so that the sum of all travel times is minimized, shown in Fig. 1a. If G is divided into G1 and G2 by P1, then traffic routing by ZO in each sub-network: find an assignment of traffic to paths in G1 and G2, respectively so that, the sum of all travel times is minimized in each sub-network, shown in Fig. 1b.
In Fig. 2, OD pairs in whole network as shown in Fig. 2a; after zoning by p1, OD pairs are divided into two parts and there are four cases as shown in Fig. 2b: (1) origin and destination in G1, such as {o1, d1}; (2) origin in G1 and destination in G2, such as {o2, d2}; (3) origin in G2 and destination in G1, such as {ok-1, dk-1}; (4) origin and destination in G2, such as {ok, dk}.
Fig. 1(a-b): | Zoning of a network before and after |
Fig. 2(a-c): | Zoning of OD pairs before and after in a network |
When the OD pair is not in the same sub network, like case 2, flow must go through a node on p1: Flow from origin oi was assigned to the path in G1, reach additional destination v1∈V1; then the flow from additional origin v1 is assigned to the path in G2 and reach destination d1, shown in Fig. 2c.
Definition 1: ρ is zoning efficiency loss parameter of zoning traffic assignment:
(9) |
where, f* is the flow of SO in G and fi is the flow of ZO in Gj, respectively.
Definition 2: A zoning path p* ∈ P = {pl} which results ρ* is a zoning vital path (ZVP for short), where, P is a set of zoning path, ρl is the zoning efficiency loss of a path pl.
Algorithm* for computing ZVP: {oji, dji} is origin-destination pairs in GJ by pl, let Oji = {oji} is origin set, Dji = {dji} is destination set. And is defined as a set of boundary nodes of G, b = 1, 2, ...m, edges between adjacent nodes in V" are defined as border edges, set E.
Step 1: | Compute all the node pair from set V. a = 1, 2, ...m-2; b = a + 2, ..., m |
Step 2: | Remove E from G, then compute all the path Pab between va and vb |
Step 3: | Compute pl satisfies| |E1l|-|E2l|≤ | |from Pab, record P = {pl} and vl ∈ Vl in each p ∈ Vll |
Step 4: | Set l = 1 |
Step 5: | Compute v ∈ Vl ∪D1l and Vl ∪D2l, record and |
Step 6: | Compute NLP1 and NLP2 by using the F-W Algorithm 8, respectively, record and on vl ∈ Vl |
Step 7: | Compute vl∪Oji, reset , respectively |
Step 8: | Undated |
Step 9: | Compute NLPj by using the F-W Algorithm, record and |
Step 10: | Compute |
Step 11: | Set l = l + 1, if l<n, then turn to step 6; otherwise turn to step 12 |
Step 12: | Compute NLP in G by using the F-W Algorithm and record , C* |
Step 13: | Compute: |
ρ* = min {ρ1, ρ2, ..., ρn} and the zoning vital path p*
CONCLUSIONS
For finding a path to zoning a traffic network efficiently, we propose a zone optimum model and define the zoning efficiency loss of zoning traffic assignment and the Zoning Vital Path (ZVP), then show an algorithm for finding the ZVP. This study still has some deficiencies. How to finding a tree to zoning a traffic network efficiently is one of the problems in the future research.
ACKNOWLEDGMENTS
The research is supported by Education Department Fund from Shaanxi Provence under Grants 11JK0980 and Principal Fund from Xian Technological University under Grants XGYXJJ0539.
REFERENCES
- Li, Z.L., 2005. Discussions on urban traffic zones. J. Transp. Syst. Eng. Inform., 6: 82-86.
Direct Link - Roughgarden, T., 2003. The price of anarchy is independent of the network topology. J. Comput. Syst. Sci., 67: 341-364.
CrossRefDirect Link