=Paper=
{{Paper
|id=Vol-1623/papertl3
|storemode=property
|title=Modeling of Urban Traffic Flows Using the Concept of Multilayer Graph by Methods of Game Theory
|pdfUrl=https://ceur-ws.org/Vol-1623/papertl3.pdf
|volume=Vol-1623
|authors=Anastasiya Ivanova,Alexey Kovalenko
|dblpUrl=https://dblp.org/rec/conf/door/IvanovaK16
}}
==Modeling of Urban Traffic Flows Using the Concept of Multilayer Graph by Methods of Game Theory==
https://ceur-ws.org/Vol-1623/papertl3.pdf
Modeling of Urban Traffic Flows Using the Concept
of Multilayer Graph by Methods of Game Theory
Anastasiya Ivanova, Alexey Kovalenko
1
Samara, Samara University, Russia
adi.hudojnik@gmail.com
alexey.gavrilovich.kovalenko@rambler.ru
Abstract. We consider the problem of distribution of traffic flows in an urban
area. We propose an optimization model, which is based on mathematical
methods of the theory of hydraulic networks and the theory of games back-
ground. To find the optimal solution, we develop a model of the city as a multi-
layer graph. By a solution we understand the state of equilibrium in the model.
Methods are used cyclic linking to solve this problem.
Keywords: game theory, modeling of road networks, Nash equilibrium, theory
of hydraulic networks, traffic flows, urban areas.
1 Introduce
Problems of engineering systems in urban areas and, in particular, road traffic systems
are well known [1]. Every citizen felt by them daily. As a consequence, the social
discontent of the population increases, economic costs are increasing, the environ-
ment is much worse, tourist and investment attractiveness of the city decreases [2]. It
is impossible to solve these problems only by using traffic management techniques
(regulation of the duration of a traffic signal, reverse line road, the use of systems of
determining traffic congestion in real time, limiting driving on specific roads for
heavy or private transport, road toll systems, and paid parking and etc. [3]). It is a
complex problem. One of the main reasons for this situation is the disparity between
the historical topology of the city, including the further incorrect layout of infrastruc-
ture facilities of the city: accommodation sleeping areas, industrial areas, office build-
ings, shops, etc., and the real demands of cities in the mobility of workforce [4]. The
structure of the city itself makes people to travel. But it is necessary transport model
for the correct layout of infrastructure entities and their integrated assessment [5,6].
The proposed model and methods based on game-theoretic approaches [7,8], and
models of hydraulic networks theory [9,10]. The research results contribute to the
development of game theory and its applications in the routing of traffic problems,
and can be applied in deciding on the reconstruction of the street and road network of
large cities in order to address the problem reduce of loss of time by reason of down-
time transport in traffic jams.
Copyright © by the paper's authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
374 A. Ivanova, A. Kovalenko
2 Formulation of the Problem
2.1 Problem Description
The city can be represented as a set of objects, including neighborhoods, (and smaller
objects, such as blocks, homes, businesses, office buildings, shops, points of entry and
exit the city, etc.) and vehicles runs between them, carrying people and different types
of goods. There are highways connecting all of these objects in the road network.
Highways can be divided into intervals within the intersections, points of entry and
exit of these objects. Let us assume that all objects attached to the points (places) of
entry and exit to the road of the quarters. Districts receive and produce transport
through these points, see the example Fig. 1.
Fig. 1. Entry and exit from the blocks
Arrows denote unilateral traffic lanes, circles represent points (places) of entry - exit
flow, and as a result, a merger and division of flow, since at the crossroads of all in-
coming flows merge into a single entity, after that they again divided on highways.
The general scheme of the process at the intersections is shown in Fig. 2.
Fig. 2. An example of a road crossroads
Modeling of Urban Traffic Flows 375
An analogous scheme operates for the entry and exit points of the city it is shown in
Fig. 3.
Fig. 3. Entry and exit from the city
It is thus apparent that the structure described above in urban traffic can be well re-
flected in the form of a digraph. Then the nodes of the graph are points of entry and
exit to the intersection, the entrance and exit of the quarters, and entry and exit to the
city. The arcs of the graph are the road sections connecting the vertices. The direction
of the arc of the graph determines the direction of flow.
Vertices containing incoming flow to the network are called sources and designated S,
vertices containing the effluent stream from the network are called sinks and denoted
T.
We assume the flow consists of separate currents, which are characterized by a com-
mon sink, that by the same movement in end vertex. Also assume that the current
transport units identical and uniformly move in an arc, but their speed on the different
arcs may be different. In some extent, the current can be represented by a moving
organized infinite column. The total value of the whole flow consisting of the set of
currents from vertex i to vertex j, is denoted by Qij. Path currents within the Qij are in
general different. Let us assume that each current is controlled a unit directing the
movement of this current (vehicle driver).
The set of all such entities constitute the set of players I. Strategy is a set corre-
sponding to each player I. Strategy is a path from the source i to the sink j taken
from the set of all paths, connecting these vertices. We denote such paths as χ. By
Φγ(ξ1, ξ2, ξ3,…, ξγ,…,ξ|I|) denote a mixed strategy of γ-th player. The criterion for each
entity is drive time from i to j. Then the target is minimization of movement time for
each vehicle, and thus for all the transport units of the current. Other players affect the
value of the criterion -th player if their paths crossed with a path of the -player.
They increase the flux density at the intersecting road segments, thereby reducing the
velocity and increasing the drive time on the road section, respectively.
Formalizing the assumptions described above, we have a game in normal form as a
result:
G I ; , I ; (1 , 2 ,3 ,... ,..., I )
(1)
min,(1 , 2 ,3 ,... ,..., I ) k , I
kI
376 A. Ivanova, A. Kovalenko
We will consider the equilibrium of this game as Nash equilibrium [7].
Later we will make another assumption that the set of players I is infinity and a con-
tinuum in nature. In accordance with this assumption Qij -flows are divided into arbi-
trarily small value currents x ij .
2.2 Analysis of the Flow on the Arc
Obviously, it is necessary that the velocity of movement of each player on the arc
tends to a maximum in order to the drive time all the path tends to a minimum. But
the value of the speed of the traffic participant is influenced by experiencing the nega-
tive impact of the other participants. They also tend to the choice of their movement
parameters to maximize speed. Increasing the flow reduces the velocity of the driver
under consideration that it increases of time spent in motion.
We consider the motion at only one arc, so that all the indices relating to arc omitted.
We introduce the following notation:
L - length of network section,
T - time traffic on the section of the network,
x - flow is quantity of vehicles that has passed through the road section per
unit of time,
- flux density is the number of cars per unit length on one-lane road,
s - number of lanes on the road,
w - the speed with which flow is moving,
wmax - the maximum speed of flow,
- the average length of a vehicle on one lane,
v - speed of the vehicle.
According to the definition of density, its value is =1/. The time during which the
vehicle will pass segment of the path in length is equal to =/v. The number of
vehicles per unit of time is equal k =1/. Consequently, the flow is defined as
1 v
x s s s ws . (2)
We assume that the speed and flux density is related to each other linearly dependent
w wmax max 1 (Greenshield’s formula), here w wmаx 1 mаx , which
is equivalent to max 1 w wmax . Substituting this expression into the formula 2
flow definition, we get x s w max 1 w wmax . The resulting function is a parabo-
la with branches pointing downwards. It reaches a maximum at w wmax / 2 , and
correspondingly xmax s wmax max 4 . Thus, we have obtained the maximum flow
that can be passed in the network.
Substituting instead its expression, we get w2 wmax w wmax s max x 0 . By
Vieta's formulas we obtain, taking into account the fact that each player tries to max-
imize his speed w wmax 1 1 x xmax 2 . It follows that the time of motion on
Modeling of Urban Traffic Flows 377
the section of the network is expressed by the following relationship:
( x) 2 min 1 1 x xmax , where – is a minimum time movement section
min
in the case that value of the flow through it is equal to zero. We present graph of the
function ( x) 1 1 1 x in Fig.4 for visibility.
Fig. 4. Graph of the function
3 The Concept of Multilayered Graph
3.1 The Concepts of Layers and Layer Balance Relations
Let G E, V , H be directed graph, Е and V are finite sets, Н is map H:V Е Е.
We define the elements of the set Е={e1,e2,e3,…} as the vertices of elements of
V={v1,v2,v3,…} as the arcs. For each arc vV we define a map H(v)=(h1(v), h2(v)),
where h1(v) is the beginning of arc v, h2(v) is the end of arc. We say that
V (i) v V | h2 (v) i is the set of incoming in i arcs and V (i) v V | h1 (v) i
is the set of outcoming from i arcs.
Values Qij are determined by the value flow from the vertex-source i to the vertex-
sink j for each pair (i, j). These flows are decomposed into separate currents and are
v
distributed over the network; as a result we obtain an arc flow qij for each arc vV.
3.2 Splitting Traffic Flows to Layers
Let the vertex i0 be the source of a flow for some set of other vertexes. Incoming in
vertex iE flows are denoted as qi(i0), incoming in vertex i0E are denoted as
qi0 (i0 ) . Taking into account equation (1), we say that complex of
S (i0 ) G; i0 ; qi (i0 ), i E; xv (i0 ), v V is called layer i0. Then we have for each
vertex:
378 A. Ivanova, A. Kovalenko
xv (i0 ) xv (i0 ) qi (i0 ), i E (3)
vV (i ) vV (i )
The vertex i0 is represented by expression 4:
qi0 (i0 ) qi (i0 ) (4)
iE \{i0 }
Relation (3) is the first Kirchhoff‘s rule of network.
X v xv (i0 ) is aggregated flow across the arc v. It follows from (2):
i0E
X v X v qi (i0 ), iE (5)
vV (i ) vV (i ) i0E
Without loss of generality, we assume that each vertex forms a layer. If some vertex i0
doesn’t have a layer, then the expression qi (i0 ) 0, i E is true for i0. Formulas (3)
and (4) hold for all i0E, for the case of the urban transport network. However, it
doesn’t follows from the formula (5) that formula (3) is true.
Note. Models single-layer transport systems themselves are a significant practical
value. The simplest examples of such problems are problem of the evacuation from
buildings, districts, cities, stadiums, etc., and problem of organization of the passage
of people in mass gathering places.
4 Analysis of a Single-layer System
4.1 Search Initial Allowable Flows Using Maximum Flow Problem in a
Network
In this section, we describe only a single layer of a multilayer graph for simplicity, so
the index i0 layer omitted. The main idea of the equilibrium search algorithm is find-
ing the admissible initial flows in the network and converting these flows to an equi-
librium state. Check the existence of admissible flows and their search can be carried
out using the maximum flow problem and the solving it by means of Ford–Fulkerson
algorithm, because the capacity of for each arc is limited
According to the maximum flow problem flow is passed from one initial vertex in one
end vertex. All network arcs have a predetermined capacity. We will add two dummy
vertices ii and kk to transform the problem into such a form. Let's connect dummy
vertex ii with the flow source i0. Its capacity is equal to qi0 (i0 ) . If sinks have got
capacity is equal to qi (i ) 0 then it are connected by arcs with kk-vertex. Then its
capacity is equal to qi (i ) correspondently.
Thus, we get the maximum flow problem in standard form. Is possible apply any of
the known algorithms for solving the problem.
Modeling of Urban Traffic Flows 379
If it was found that the maximum flow is less than the value of qi0 (i0 ) , the original
problem of single-layer hasn’t solutions as well as the general problem, respectively.
In this case, the minimum cut is outside of additional arcs.
If you find, that the maximum flow equals qi0 (i0 ) , then we get admissible flow. It is
reduced to a state of equilibrium by means invariant transformations.
4.2 Invariant Transformation Layer’s Flows
We consider an arbitrary the cycle C. Let's set an arbitrary direction bypass of the
cycle, coinciding with the direction of an arc belonging to u-cycle. We construct the
u
characteristic function in the form signC (v) :
0, if v C
1, v C,if the direction of the arc coincides with the direction
u (6)
signC (v ) of bypass of the cycle,
1, v C ,if the direction of the arc doesn't coincides with the
direction of bypass of the cycle.
Let xv, v V satisfy the relation (6). We take an arbitrary number of , for all v V ,
let set that xv xv signC
u
(v) , those, if the direction of the arcs cycle coincides
with the direction of bypass of cycle, then is added to the value of the flow xv; if
arcs direction opposite to the direction of bypass of the cycle, then from xv the flow is
deducted . Then xv , v V satisfy the relation (6).
4.3 Kirchhoff's Second Rule for Traffic Flows
We consider the a single layer the flow of traffic from the source at number i0 to the
stock at number j0. Let for this traffic flows diverge from the vertex i and converge at
the vertex j. Let some flows already course along the arcs and satisfies the first rule
of Kirchhoff. There are at least two paths of delivery of this flow from i to j, we de-
note them P1 and P2. Let us assume that time t1 at the first path was more than time t2
at the second path. Then part of the flow switch to the 2nd path. The flow at the 2nd
path will be increasing, and consequently time will be slowed down at the 2nd path.
At the same time the quantity of flow of the 1st path will be decreased and conse-
quently time will be reduced at the 1st path. Switching will stop when equality t1=t2
(or equivalently t1-t2=0) will be achieved. In its general form following equality must
hold
signC (v) v xv 0 .
u (7)
vV
It is called Kirchhoff's second rule in the theory of hydraulic networks. Its verbal for-
mulation:
380 A. Ivanova, A. Kovalenko
"In the state of equilibrium the sum of the time change of the flow over the cycle is
equal to zero"[5]
This equality does not hold for arbitrary flows. Using the invariant transformation
flows, we can write instead (8):
vV
v v C
u (v) x signu (v)
NBu ( ) signC . (8)
Then the problem of linking the cycle is to define such that NBu ( ) 0 .
4.4 Construction of the Spanning Tree, Fundamental System of Cycles
It is known that if the Kirchhoff‘s rule holds for the system of fundamental cycles,
then it holds for any graph from this cycle. The spanning tree is an arbitrary tree with
vertices coinciding with the vertices of the original graph G. The tree can be con-
structed using any suitable algorithm, such as Dijkstra's algorithm for constructing a
tree of shortest paths. Shortest routes are possible to take in terms of the lengths of
paths to the root. Arcs are outside of the tree is called a chord. Fundamental loop
formed by the chord and the arcs the tree. C(u) is a loop formed by the chord u. Each
cycle is set direction of the circuit, which coincides with the chord. The construction
u
of the function signC (v) for the cycle is easy.
4.5 Calculation of Border Changes of Argument’s the Function
We divide NBu ( ) into three past as: NBu ( ) NBu 0 ( ) NBu ( ) NBu ( ) ,
0
The first part NBu ( ) consists of terms with v, such that signC u
(v) =0. The second
part NBu ( ) consists of terms with v, such that signC u
(v) =1 . The third part
NBu ( ) consists of terms with v, such that signCu (v) = -1.
1. It is obvious, that NBu 0 ( ) 0 .
2. NBu ( ) v ( xv ) . Inasmuch as v ( x ) 0 is increasing along the x
vV , sign u (v ) 1
(see Fig. 4), that NBu ( ) 0 is increasing along the . For all
v V , signu (v) 1 holds 0 ( xv ) xmax , or xv xmax xv . Thus, we
have
[ , ], (9)
where max ( xv ), min ( xmax xv )
vV , signu ( v )1 vV , signu ( v )1
3. Similarly, we find that NBu ( ) is increasing.
Modeling of Urban Traffic Flows 381
[ , ] (10)
where max xv xmax , min xv
vV , signu (v )1 vV , signu (v )1
Of the cases examined, and formulas (7), (8) we see that the function NBu ( ) is
increasing and is defined on the interval [ , ] , where max( , ) ,
min( , ) .
5 Equilibrium Search Algorithm for the Urban Transport
System
These constructions give us the possibility of using algorithms such as the serial link
of cycles in order to find the state of equilibrium of a single layer. For example, we
find the arc, for which NBu (0) (quite small), if such an arc is not found, then we
stop linking layer of the arc, and solve the problem NBu ( ) 0 , and move on to the
implementation of the algorithm again. To search for multilayer systems arc, it should
be implemented across all layers and consequently within the layer.
6 Results and Discussions
Extensive experience solving problems of hydraulic network theory gives reason to
believe that the proposed approach is effective. For example, the solution flow distri-
bution problems of urban water supply networks, problems of urban the heat supply
network with the dimension of about 1000 vertices and about 1500 arcs for a time of
about 15 - 30 seconds for household personal computers gives reason to assume that
the flow distribution in the road network can be accomplished in a reasonable time.
The proposed algorithms allow the use of methods of parallelization to give ample
opportunities of using modern multi-processor computer systems.
We can call problematic factor for the use of this model is the complexity of the ini-
tial data collection, such as:
The flow-forming factors (place of residence, work, cultural and community
services, etc.)
The transport network characteristics (number and quality of roads and
streets, public transport, etc.)
The behavioral factors (population mobility, preferences in selecting routes
and modes of transportation, and others.)
On the other hand, for many large cities, these data have been collected and suitable
for processing.
382 A. Ivanova, A. Kovalenko
References
1. Kalimoldaev, M. Kovalenko, A., Myrzahmetov, M., Khachaturov, B. Water problems of
Central Asia: analysis methods for searching solutions to problems. Bulletin of the Samara
State University, 6 (117). 239-249 (2014) // Калимолдаев, М., Коваленко, А., Мырзах-
метов, М., Хачатуров, В. Водные проблемы центральной Азии: анализ, методы по-
иска путей решения проблем. Вестник Cамарского государственного университета,
6 (117). 239-249 (2014)
2. Hovavko, I.Y. Economic analysis of traffic jams in Moscow. Public administration. Elec-
tronic Gazette, (43), 121-134. (2014) // Ховавко, И. Ю. Экономический анализ
московских пробок. Государственное управление. Электронный вестник, (43), 121-
134. (2014)
3. Loginovskiy, O.V., Shinkarev, A.A Evolution of Cities Traffic Supervision and Manage-
ment Approaches Bulletin of SUSU 14(4), 57-58, (2014) //Логиновский, О. В., Шинка-
рев, А.. Развитие подходов к управлению и организации движения транспорта в
крупных городах. Bulletin of SUSU 14(4), 57-58, (2014)
4. Erhart, S. The causes and consequences of traffic jams in Budapest.Kozgazdasagi Szemle
(Economic Review), 5(54), 435-458 (2007)
5. Shvetsov, V.I, Aliev, A.S. Mathematical modeling of the load transport networks. M .:
URSS 64 (2003). // Швецов, В. И., Алиев, А. С. Математическое моделирование за-
грузки транспортных сетей. М.: УРСС. 64 (2003)
6. Smirnov, N.N., Kiselev, A.B., Nikitin, V.F., Kokoreva, A.V. Mathematical modeling of
motor traffic flows of continuum mechanics. Two-way traffic: a model of a T-junction, the
study of the impact of vehicles on rebuilding the capacity of the site magistrali.TRUDY
MIPT, 2 (4), 141 (2010) // Смирнов, Н. Н., Киселев, А. Б., Никитин, В. Ф., &
Кокорева, А. В Математическое моделирование движения автотранспортных пото-
ков методами механики сплошной среды. Двухполосный транспортный поток: мо-
дель Т-образного перекрестка, исследование влияния перестроений транспортных
средств на пропускную способность участка магистрали.ТРУДЫ МФТИ, 2(4), 141.
(2010)
7. Vasin, A.A., Morozov, V.V. Game theory and mathematical models of the economy
(manual). - M .: MAKS Press, 272 (2005) // Васин А.А., Морозов В.В. Теория игр и
модели математической экономики (учебное пособие). – М.: МАКС Пресс, 272
(2005)
8. Yalei, J. Research on Causes and Countermeasures to Urban Traffic Congestion Based on
Game Theory [J]. Journal of Lanzhou Jiaotong University,1, 031 (2007)
9. McCoy, E. L., Boast, C. W., Stehouwer, R. C., & Kladivko, E. J. Macropore hydraulics:
taking a sledgehammer to classical theory. Soil Processes and Water Quality, 303-348
(1994)
10. Merenkov, A.P., Hasilev, V.Y. Theory of Hydraulic Circuits .- M., Nauka, 278 (1985) //
Меренков А.П., Хасилев В.Я. Теория гидравлических цепей .- М., Наука, 278 (1985)