Introduce

Modeling of Urban Traffic Flows Using the Concept of Multilayer Graph by Methods of Game Theory

Anastasiya Ivanova

Alexey Kovalenko

alexey.gavrilovich.kovalenko@rambler.ru 0 Samara, Samara University , Russia

373 382

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 background. To find the optimal solution, we develop a model of the city as a multilayer graph. By a solution we understand the state of equilibrium in the model. Methods are used cyclic linking to solve this problem.

game theory modeling of road networks Nash equilibrium theory of hydraulic networks traffic flows urban areas

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 environment 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 infrastructure facilities of the city: accommodation sleeping areas, industrial areas, office buildings, 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 downtime transport in traffic jams.

Formulation of the Problem 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. 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 incoming 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. An analogous scheme operates for the entry and exit points of the city it is shown in Fig. 3. It is thus apparent that the structure described above in urban traffic can be well reflected 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 common 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 corresponding 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 ) 

   min,(1, 2 , 3 ,... ,..., I )    k ,  I   kI ( 1 ) 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 continuum in nature. In accordance with this assumption Qij -flows are divided into arbi trarily small value currents xij .

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 negative 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 x  s  1  s  v

s  ws .  ( 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 parabola 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 maximize his speed w  wmax 1 1 x xmax  2 . It follows that the time of motion on function  (x)  1 1 1 x  in Fig.4 for visibility. the section of the network is expressed by the following relationship:  (x)  2 min 1 1 x xmax , where min – is a minimum time movement section in the case that value of the flow through it is equal to zero. We present graph of the

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 vV 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 vertexsink j for each pair (i, j). These flows are decomposed into separate currents and are distributed over the network; as a result we obtain an arc flow qivj for each arc vV. 3.2

Splitting Traffic Flows to Layers

qi0 (i0 ) .

Let the vertex i0 be the source of a flow for some set of other vertexes. Incoming in vertex iE flows are denoted as qi(i0), incoming in vertex i0E are denoted as

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: The vertex i0 is represented by expression 4:

 xv (i0 )  vV  (i)

 xv (i0 )  qi (i0 ), i  E vV  (i) qi0 (i0 )  

 qi (i0 ) iE\{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 ): i0E

 X v  vV  (i)

 X v   qi (i0 ), vV  (i) i0E i  E ( 3 ) ( 4 ) ( 5 ) 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 i0E, 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 4.1

Analysis of a Single-layer System 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 finding the admissible initial flows in the network and converting these flows to an equilibrium 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. 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 characteristic function in the form signCu (v) : 0, if v  C 1, v  C, if the direction of the arc coincides with the direction  signCu (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  signCu (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 denote 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 consequently 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

vV signCu (v) v xv   0 .

It is called Kirchhoff's second rule in the theory of hydraulic networks. Its verbal formulation: ( 6 ) ( 7 ) "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 ):

NBu ( )   signCu (v) v xv  signCu (v) .

vV ( 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 constructed 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 of the function signCu (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 ( )  NBu0 ( )  NBu ( )  NBu ( ) , 0 The first part NBu ( ) consists of terms with v, such that signCu (v) =0. The second  part NBu ( ) consists of terms with v, such that signCu (v) =1 . The third part  NBu ( ) consists of terms with v, such that signCu (v) = -1. 1. It is obvious, that NBu0 ( )  0 . 2. NBu  ( ) 

 v (xv  ) . Inasmuch as  v (x )  0 is increasing along the x vV , signu (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 vV , signu (v)1 (xv ),   

min vV , signu (v)1 (xmax  xv ) 3. Similarly, we find that NBu  ( ) is increasing.  [  ,  ] ( 10 ) where   

max vV , signu (v)1 xv  xmax,   

min x vV , signu (v)1 v 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 distribution 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 initial 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.

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 . Electronic Gazette , ( 43 ), 121 - 134 . ( 2014 ) // Ховавко, И. Ю. Экономический анализ московских пробок . Государственное управление. Электронный вестник, (43) , 121 - 134 . ( 2014 )

3. Loginovskiy , O.V. , Shinkarev , A. A Evolution of Cities Traffic Supervision and Management 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 )