Urban Dynamic Traffic Assignment model and algorithm according to the dynamic
traffic demanding which are the core of the intelligent transportation theory.
Because of the complexity of the road traffic system and the dynamic assignment
of real-time property, they make traffic assignment a series of problems. In
1956, Beckman puts forward the calculation traffic equilibrium state of integral
transform which form the important foundation of urban traffic balance theory
and then appear a series of related research, but most are static traffic distribution
model (Lian and Gao, 2005). In dynamic traffic assignment,
Barthelemy M based on the number of referral traffic in order to determine the
distribution network, discussed the characteristics of scale-free network flow
distribution and the scaling relation between node degree and flow (Barthelemy,
2004). Dobson et al. (2003) was put forward
Cascade model which was based on probability flow and has analyzed the Cascade
mode which effect on failure scale which existed the critical point. Then according
to the efficiency of the edge the changes of thought during the process of node
failure also the characteristics of dynamic distribution flow in complex network
(Crucitti et al., 2004). Lee
et al. (2011) analyzed the traffic spread rules in complex network
and the congested influence which was caused by network topological structure
and proposed the control strategy about how to eliminate the traffic congestion.
Overall, at present the existing dynamic traffic assignment researches mostly based on ideal hypothesis conditions which can analyze the effect of all kinds of traffic parameters on traffic flow and find out characteristics of various types of traffic distribution, but there is rarely have accurate calculation of flow distribution model. But in the actual traffic control engineering, the traffic flow assignment needs a precise quantitative index so as to offer specific flow rate or signal lights control. Therefore, it is very beneficial for us to study precise model of dynamic traffic flow assignment model to realize the traffic control engineering.
The study will first apply the network equilibrium theory (Chen
et al., 2011) into dynamic traffic flow assignment which Using Leaky
Bucket Controller and Network Calculus. The traffic flow rate distribution and
path delay is exchanged to be a series of mathematical operations, finally use
simple greedy algorithm to balance traffic delay and get traffic assignment.
The model aims at a short time dynamic analyzing, propose a traffic flow calculation
model called T-S Constrained Model to solve congestion. The simulation results
show that the model effectively solves the heavy traffic, has a better convergence
property in balancing the traffic flow and can advance traffic capacity of road
TRAFFIC FLOW ASSIGNMENT PROBLEM
Description of the simulated problem: The dynamic traffic flow control
system within a citys road network is built to ensure an efficient traffic
flow, because in the event that the traffic is not managed properly, congestion
could occur which affects the traffic seriously. This article focuses on how
to dynamically manage a heavily congested road way, to dissipate the traffic
within the congested region in a short period of time. At the same time to solve
the current state of congestion and balance traffic delay and assure the assigned
cars can reach in the core area in an effective time.
The transmission process of road traffic network is similar with computer networks. In recent years, the theory of complex networks for urban transportation research provides a new perspective. Domestic and overseas scholars using complex network theory achieve many Research results in the traffic network dynamics behavior analysis, traffic network cascade failure, traffic jams communication and transportation network evolution modeling, etc. But the main achievements are analysis of urban traffic network structure on the network traffic, expenses and the influence of the obstruction and there is rarely have accurate calculation model which can utilize to practice traffic engineering.
Using wireless network multimedia application transmission theory and combining with traffic network transmission characteristics, we apply the network equilibrium theory into dynamic traffic flow assignment. Using network calculus we analyze the route service ability of roadways, incorporate the complexity of the road elements into unified mathematical model called D-R Constrained Model and deduce the path of assigned path in a bounded delay. It will get to meet the max allowable rate in effective delay-limited constraints and provide delay-rate constraint dynamic traffic flow assignment model so as to offer accurate mathematical flow assignment solutions.
THE PROBLEM THEORY
Leaky bucket controller: Network nodes' traffic control of communication
flows makes the network node cache space does not overflow and the transmission
of data is guaranteed. In Fig. 1, node traffic control as
the leaky bucket, a bucket which the capacity is σ, discharge rate is ρ,
we must control the traffic flows so that communication storage x(t) won't be
overflow from the bucket in any time. If the reaching of the traffic won't cause
an overflow, called traffic R (t) satisfy the control of leaky bucket which
the parameters is (σ, ρ).
Theorem 1: If the communication stream R(t) is controlled by the leaky
bucket which parameter is (σ, ρ), then R(t) will constraint by the
reach curve α(t) = σ+ρt.
Network calculus is a set of theory of analyzing packet switching network queuing
system. Different from traditional queuing theory, Network calculus theory mainly
studies packet switching network performance to secure border rather than stable
state of the average performance.
|| Leaky bucket controller
The central theme of the theory is to utilize minimum plus algebra and maximum
plus algebra to transform a complex, non-linear network system into a linear
system which is easier to analyze. This theory has been widely utilized by various
network performance benchmark tools and resource distribution solutions, as
well as many others. To ensure that network calculation is used primarily to
analyze the guaranteed availability of services under the worst case scenario.
When ensuring service guarantee which are all of the data flow from the source
node group to destination node(host, routers etc.) forward can satisfy the demanding
performance index such as bandwidth, time delay and traffic, etc. Reaching curve
and service curve is to determine core model which is in the network calculation
theory and to describe streams of data flow characteristics and server service
capacity characteristics. Based on this, ensuring network calculation may analyze
the delay in the network group, the output of the flow characteristics server
and network elements of the buffer size and performance indicators. Network
data delay definition: Given a stream which will be restrained by arrival curve
when enter the system, when through the system ,the system provides service
curve β(t) so that the communication stream delay d(t) at any time satisfies
formula (1),which h(α, β) also known as standard deviation between
α and β curves:
PATH ANALYSIS OF SERVICE CAPABILITIES
We think congestion happens when the sections share is larger than a certain
value and we will take the real-time dynamic route guidance strategy. In order
to make the traffic flow of current congestion section S meet the Leaky Bucket
Controller which parameter is (σ, ρ),then R (t)<σ-x (t0)+ρt.σ.
is the vehicle's maximum capacity of the sections, x (t0)is the number
of vehicles in initial time during the time t. ρ is the rate of the section
which the vehicle out of. In this project, the sections shares in each period
are obtained by sensor. In order to simplify the formula, we reduce the formula
σ-x (t0) to the capacity of vehicle φ (t0)in
current section that means the arrived cars meet the curve r (t)<φ (t0)+ρt
and we call:
|| Traffic flow distribution
Current road S divides traffic stream R(t) into m of small streams R1(t), R2(t),..., Rm(t) through route guidance, show in Fig. 2.
Every traffic flows speed is ρi, there are:
For any path i, assuming the path has n sections, each section provides some
service capabilities for traffic flow. Shown in Fig. 4, the
service curves which are provided by every road section are: .
According to the network calculus theorem, the series service curve in path
i which is provided by the n middle sections is
For any passage of the section, we can assumed that section provides rate-delay
service curve for traffic flow no matter use which signal control algorithm
and the curve can be used as a service guarantees for traffic flow (Mao
et al., 2006). Thus, the service curve formula (3) which is provided
by each sub-section is:
Among them, Vij is the designed speed of road section, Vij the time which the vehicle delayed in this road.
The series service curve βi (t) of path i can be calculated according to the characteristics of rate-delay function. Show in Formula (4):
The delay of vehicle which passes every road section j in path i are divided into two part: the one is the vehicle's travel time: Ri, the other one is the vehicle's waiting time: Wi. Every path i runs n sections, the time of vehicles in each section is:
Lij is the length of section j, Vij is the designed speed of current section. So the time of vehicles in path i is:
For a stable queuing system, the upper bound of queuing delay is the maximum
heavy interval (Chang, 1994; Si et
al., 2009). So, the queuing time delay of data stream which constrained
by the curve can be represented as: α (t) = φ (t0)+ρt
So, the mutable time delay of path i meet the formula:
Overview the formula (5) and (6), we can get the time delay upper bound of path I:
DELAY-RATE CONSTRAINED DTFA MODEL
We take the dynamic real-time assignment model in congested section. If the congestion occurs when you in the way of the peak destination, we take the D-R Constrained Model for the congested section. To make sure every divided section has the same traffic capacity and guarantee the through efficiency of each section, the key to the induced algorithm is to balance the time delay of each traffic flow in divided section and assuming the longest time delay Δ of each divided traffic flow in a reasonable time, then:
So we can get:
Among them, ρi is the constrained average speed of arrival
stream and it is the maximum allowable flow rate of the path at the same time.
We can see from the formula that when the service rate of the path is larger,
the speed of the data which satisfy the required delay is greater.
So, we can analyze the total data stream in current congested section:
The constrained speed of total data stream which get into the current congested section can not exceed a certain threshold value, otherwise that will result in a back of vehicles on the road, adding the path time delay exceeds the limited value Δ. That is, using the red light to control the traffic w in order to control the speed of traffic in current congested section.
To ensure the path induced diversion keep the same traffic capacity, to meet the requirements of the delay in premise, we should reduce the difference between each path as much as possible and we attribute the path capacity allocation problem to the following planed optimization problem:
Because of the above problem is NP-hard problem, we propose greedy algorithm
to solve it. Described as follows in detail:
||Section length L, designed speed of section V, the upper delay
of path Δ, the signal cycle C, the split λ, the acquisition probability
||The entry speed of each path after the traffic distribution ρi
||Calculate the upper bound of constrained speed ρi in each
||In order to stream out the congestion vehicles and maintain
the vehicles forward by the designed speed in a cycle time, then L (1-K)
+VC<ρC, then calculate the discharge rate ρ
||Set the constrained speed of each path proportionally according to the
upper limit value:
||For the allocation plan (ρ1, ρ2,
ρm), we calculate the time delay upper bound of each path
according to the formula 7:
||For these two paths which have the maximum and minimum
time delay upper bound, adjusting each constrained speed ρi,
but can not exceed each limited value so that the delay inequality:
can be reduced between paths
||Repeat the step (5) until the:
can not be reduced
THE SIMULATION EXPERIMENT
We take the traffic network which was forward with 21 sections to simulate,
the experimental data is from the reference (Wang et
al., 2010), setting up the congested roads in all directions of the
heart land, because the multiple loops of the road network, we selected 3, 5,
8 diffluent path and three different congested situations to have a test, compare
the before and after adjustment delay changes. From the simulation results,
we can see the average time delay was generally lower after assignment, in the
aspect of balancing traffic flow and resolve congestion, we enhance the capacity
of road, shown in Fig. 3.
||Comparison of average delay in 3 road situation of different
The more path involve in the assignment, the better the convergence of the algorithm is and the lower the average time delay of diversion is and the time delay will converge towards the balanced direction, shown in Fig. 4. But for multiple diffluent paths, if the driving range differs so much, the time delay of each road is difficult to converge to a specified value, it will stay in a value.
When we take 8 diffluent paths, the different congested status values before
and after adjustment, we can see in Fig. 5 severe congestion
delays can converge to a better delay value which can improve that it can disperse
congestion, but that will also sacrifice some sections delay value in
mild congestion, in order to balance the traffic flow, we should to adjust different
sections to achieve better level in whole.
|| The value comparison of 3/5/8 diffluent paths after adjusting
|| The comparison of 8 paths congested situation
This project aimed at dynamic traffic flow assignment in congestion section of traffic network, in a period of time to complete the assignment of high-load flow in congested section and balance the delay in each diffluent path so that the vehicles which are participate in shunting can reach in central area in a limited time. Its the first time to come up with applying network equilibrium theory in wireless network, combined with the transmission characteristics of the transport network, applying the network equilibrium theory into dynamic traffic flow assignment. Using the network calculus theory to analyze the section service capacity of the road, combining the complex road elements into unified mathematical model, deducing the delay upper value of diversion path and getting the biggest flow rate which is in a delay-limited constraints, come up with Delay-Rate Constraint dynamic traffic flow assignment model, giving the accurate flow distribution program. Simulation test is in different number of diversion paths, different delay situation of different road network, the average time delay was generally lower after adjusting , congestion delays of each path can converge to a better delay value in the condition of our model, the congested section can reach a better shutting effect when there are many diversion paths and the each path can reach in central area in a limited time.
This study was supported by Projects of International Cooperation and Exchanges NSFC No. 2010DFB90460, Science and Technology Planning Project of Jiangxi Province No. 20111BDH80030.