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.
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; O’Neill, 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 P’1∈P’, where, P’ = {P’1}, l = 1, ..., n let E’l and V’l be the edge set and vertex set on P’l, respectively. Then the origin and destination of P’l 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 P’1, 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 p’1, 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 p’1: Flow from origin oi was assigned to the path in G1, reach additional destination v’1∈V’1; then the flow from additional origin v’1 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’ = {p’l} 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 p’l.
Algorithm* for computing ZVP: {oji, dji} is origin-destination
pairs in GJ by p’l, let Oji = {oji}
is origin set, Dji = {dji} is destination set. And
| Step 1: | Compute all the node pair |
| Step 2: | Remove E” from G, then compute all the path Pab between v”a and v”b |
| Step 3: | Compute p’l satisfies| |E1l|-|E2l|≤ | |from Pab, record P’ = {p’l} and v’l ∈ V’l in each p ∈ V’ll |
| Step 4: | Set l = 1 |
| Step 5: | Compute v ∈ V’l ∪D1l and V’l
∪D2l, record |
| Step 6: | Compute NLP1 and NLP2 by using the F-W Algorithm
8, respectively, record |
| Step 7: | Compute v’l∪Oji, reset |
| Step 8: | Undated |
| Step 9: | Compute NLPj by using the F-W Algorithm, record |
| 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 |
| 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 Xi’an Technological University under Grants XGYXJJ0539.