Journal of Physics: Conference

Series

PAPER • OPEN ACCESS You may also like

- The impact of road infrastructure on
Mathematical model of highways network regional development in South
Labuhanbatu Regency, North Sumatra
optimization Province, Indonesia
R P Tanjung, A Purwoko and R A Lubis

- The Trips Assignment Influence of Freight

To cite this article: R L Sakhapov et al 2017 J. Phys.: Conf. Ser. 936 012032 Vehicle Network System on the Need for
Fuel Consumption in Internal - Regional
Juang Akbardin, Danang Parikesit,
Bambang Riyanto et al.

- Empirical study of long-range connections

View the article online for updates and enhancements. in a road network offers new ingredient for
navigation optimization models
Pu Wang, Like Liu, Xiamiao Li et al.

This content was downloaded from IP address 103.171.163.188 on 20/05/2024 at 22:48

ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

Mathematical model of highways network optimization

R L Sakhapov1 , R V Nikolaeva , M H Gatiyatullin and M M Makhmutov

,2,3 2 2 2

Kazan State University of Architecture and Engineering, 420043, Kazan, Zelenaya

2

str., 1, Russia

3
E-mail: [email protected]

Abstract. The article deals with the issue of highways network design. Studies show that the
main requirement from road transport for the road network is to ensure the realization of all the
transport links served by it, with the least possible cost. The goal of optimizing the network of
highways is to increase the efficiency of transport. It is necessary to take into account a large
number of factors that make it difficult to quantify and qualify their impact on the road
network. In this paper, we propose building an optimal variant for locating the road network on
the basis of a mathematical model. The article defines the criteria for optimality and objective
functions that reflect the requirements for the road network. The most fully satisfying condition
for optimality is the minimization of road and transport costs. We adopted this indicator as a
criterion of optimality in the economic-mathematical model of a network of highways. Studies
have shown that each offset point in the optimal binding road network is associated with all
other corresponding points in the directions providing the least financial costs necessary to
move passengers and cargo from this point to the other corresponding points. The article
presents general principles for constructing an optimal network of roads.

Keywords: road network, road transport, correspondence points, mathematical model, route,
optimization

1. Introduction
The availability of a reliable and efficient transport system is an important factor in the development
of the economy of any country. Today, transport is an important part of the world economy, as it is a
material carrier between states. Presence of a well-developed transport system is one of the important
factors of attracting people and production and is an important advantage for locating productive
forces, which gives an integration effect.
The dominant type of transport around the world is automobile, which is rapidly growing every
year. The importance of the road network can also be judged by the share of the total volume of
passenger and freight traffic carried out by automobiles. Studies of foreign scientists have shown that
road transport is one of the largest contributions to budget revenues. For example, road user taxes and
fees in the US amounted to $ 78 billion in 1994 (6.2 percent of federal revenues of the state budget)
and $ 33 billion in the United Kingdom in 1995-96 (of which only $ 10 billion was spent on roads).
The share of the transport system in the main production assets of Russia is 27%, and a significant
share of transportation services in the gross domestic product is 8%. Net financial flows from the road
sector tend to be positively correlated with economic development [10].
1
To whom any correspondence should be addressed.

Content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution
of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI.
Published under licence by IOP Publishing Ltd 1
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

The road network is a complex, large-scale system. The road network is the basis for the
functioning of the economy and society through the movement of people, goods and services. At
present, in most developed countries of the world, there is a serious imbalance in supply and demand
in the transport sector: traffic volumes, especially in large megacities, are approaching the limits of the
capacity of existing highways, and sometimes surpass them in rush hour [11,15].
From the economic point of view, the construction of the road network should be based on the
basic topology of the network, the demand of the users of the road network and the cost of its
construction. Equilibrium occurs when the number of trips between the corresponding departure points
(for example, the place of residence, the place of work) and the points of arrival (place of work,
residence) are equal to the demand for travel taking into account the cost policy [9].
The study of the road network has been developed at the intersection of various fields of
knowledge - physics, mathematics, economics, operating systems research, transportation processes,
etc. Measurements, observations and modeling of individual processes in the transport sector and the
totality of demographic and socioeconomic relations are important for the development of a transport
infrastructure development strategy [4,8].
A consequence of the difficulty of optimizing the road network is a certain imbalance between the
results of scientific research and mathematical calculations, on the one hand, and the practically
observed results, on the other. That’s why today we have various approaches to mathematical
modeling and a sufficiently large number of software products modeling transport flows.
In recent years, successful mathematical and computational methods have been developed to
formulate the model of a dynamic transport system. Many of them generalize traditional statistical
methods; advanced and realistic models use a traffic simulator, traffic flow dynamics. The number of
software products for the dynamic transport systems, which are sufficiently tested in the developed
countries of the world, includes: DYNASMART [2], Dynameq [7], AIMSUN [1]. Creating models of
transport systems in these programs is a rather cumbersome task that involves the presence of a large
number of elements and requires a long process of calibrating hundreds or thousands of coefficients.
The purpose of this article is to present a network of highways in the form of a mathematical model
and to select the necessary conditions for optimizing the road network. The road network is
represented as a set of corresponding points (departure and arrival points) connected by a set of routes.
As a result of its use, it is possible to reduce the task of optimizing the road network to a multitude of
similar tasks of distributing the transport flow between two nodes along the routes and obtaining the
equilibrium distribution of the transport stream in an explicit form. In turn, the explicit form of such
distributions will make it possible to substantially reduce the time spent on computations.

2. Fundamental solutions, concepts and models of road networks

The road network model is the basis for solving many transport tasks, such as optimal network
planning, improvement of traffic organization, optimization of public transport routes system, etc.
In 1952, Wardrop suggested that any transport system after a certain time comes to an equilibrium
state and formulated two principles of the equilibrium distribution of traffic flows [12]. According to
the first principle, "the travel time for all used routes is the same for all participants of the traffic, and
less time that any participant will spend changing their route," and according to the second, "the
average travel time is minimal."
Beckmann, McGuire, and Winsten (1956) were first who mathematically formulated these
conditions [13]. Specifically, Beckmann, McGuire, and Winsten (1956) established an equivalence
between transport network equilibrium conditions that argue that all paths connecting a pair of
correspondent points will have equal and minimum travel times (or costs) [13]. Consequently, in this
case, the equilibrium of the transport network can be obtained by solving the problem of mathematical
programming [4]. This approach allowed to formulate, analyze and then solve the transport problem
on the basis of actual transport networks.
Dafermos and Sparrow (1969) came up with terms "optimization-user" and "optimization-system"
for the transport network [14]. These terms distinguish two situations, in the first situation, users act

2
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

unilaterally in their own interests when choosing routes, in the second situation, users choose the
optimal routes from a public point of view, taking into account the minimum cost in the transport
system. Fig. 1 presents the two behavioral principles underlying transport networks.

Optimization - User Optimization - system

The principle of user equilibrium: The principle of optimality of the system:

The transport costs of users when traveling The maximum total cost of a trip using
along the route between the corresponding the route between the corresponding
points are leveled and minimal points is equalized and minimal

Figure 1. Behavioral principles of transport networks

Traditional methods of transport planning, including methods of network design, focus on

improving mobility based on parameters such as speed and travel time. However, a mobile-oriented
approach to transportation planning can stimulate the demand for travel and lead to congestion [3].
While mobility planning can increase the availability of the network, the availability of planning
extends the range of possible solutions compared to the mobile-oriented strategy [6]. One of the
obstacles is the lack of methods to solve the problem of accessibility directly, rather than mobility in
transporting the network design.
In this situation, the goal of optimizing the transport network is to determine the shortest
distance between the corresponding points. The road network should be planned in such a way as to
minimize travel time and financial costs in the transport system.

3. Requirements for the optimal location of the road network

The location, density and composition of the road network form under the influence of numerous
factors, which can be conditionally divided into three groups: economic, social and natural. When
designing roads, taking these factors into account leads to the need for a quantitative assessment of
their impact. The variety of these factors makes this assessment difficult. The question arises of
identifying the most significant factors that determine the development of the road network. For the
construction of the optimal version of the road network, it is necessary to investigate the influence of
each factor on the result of the solution. It is impossible to conduct such studies in real conditions,
because for this it is necessary to firstly build roads and only then to make a comparison. In such
cases, studies can be carried out on mathematical models. The mathematical model will allow
describing the process under study in the form of equations and inequalities.
When creating a mathematical model of the road network, it is necessary to first of all determine
the criterion of optimality and to choose an objective function that reflects the requirements for the
road network in the design.
To model a transport network it’s necessary to have:
• cartographic material; Usually these are large-scale maps, since they allow you to measure with
great accuracy the distances between points;
• information on the location of the main objects of the transport system and its environment
(depending on the task to be solved: load-forming and load-absorbing enterprises, residential areas,
places of employment, etc.);
• additional information from municipal and road organizations in the form of a list of streets with a
characteristic of their carriageway;

3
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

• Information on the organization of traffic, i.e., traffic management schemes at intersections,

squares and traffic intersections, as well as information on various traffic restrictions associated with
established road signs.

4. Structure of the road network

To describe the structure of the transport network we apply graph theory, where the transport network
is represented as an oriented graph consisting of a set of successively numbered vertices and a set of
consecutively numbered edges (arcs) symbolizing the elements and their connections. The graph G
modeling the road network must necessarily be tied, so that there is always a path from any vertex to
any other vertex. Numbers characterizing the links of such a graph usually express the length of the
route, time or cost of travel.
Let’s introduce the notation: m is the set of successively numbered nodes of the graph G; Z is the
set of sequentially numbered arcs of the graph G; I is the set of nodes that are the departure points, i ⊆
m; J is the set of nodes that are arrival points, j ⊆ m; It is assumed that i∩j = ∅; Mij is the set of routes
between the departure points i ∈ I and the arrival points j ∈ J.
The graph F modeling the road network is determined by the set of vertices and the set of pairs of
vertices, between which there is a link (Fig. 2).

1 i

Figure 2. Model of road network graph

The task in this case is to decide: to include the k -th link in the projected network or not to include.
The number of links of the k -th type is indivisible and can take only two values: 0 and 1. The
definition of the unknown links of the road network (Zk) must satisfy the condition:

Z k = 0;1 (k = 1,2,3,...) , (1)

or
ì1, if arc Î Z is on the route Mij
Zk = í . (2)
î 0, in the other case

Let’s suppose, to take the minimum of road costs as a criterion of optimality (costs for
construction, maintenance and repair of the road network). In this case, the optimal option will be met
by the network with the least total length, for which the amount of travel costs is minimal:

åD l
k
k k = min , (3)

where:
Dk – road costs associated with the construction, maintenance and repair of the road network;
lk – length of road network;

4
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

k – number of sections (links of the road network).

If the road network is required to reduce the cost of transport work or the travel time of passengers
or cargo, the only solution that meets these requirements is to ensure all transport links by independent
roads along the shortest path, i.e. direct connection between each of the corresponding points
(departure and arrival points). The solution of the problem is to determine the unknown routes
between the points i and j (Мij) satisfying the following condition:

M ij ³ (i = 1,2,3,..., m; j = 1,2,3,..., m ) , (4)

for which transport operation on the route ij (Pij) or connection time between i and j (tij) will be
minimal:
åå
Pij = min ,
i j
(5)

åå t i j
ij = min . (6)

Considering the complexity and practical limitations of numerical programming, combinatorial

analysis methods can be used in solving such problems, viewing different combinations of variable
values, but only a reasonably selected part of possible combinations.
The realization of transportation with the lowest possible financial costs corresponds to the
reduction in the costs of the means of production consumed in transport, and the criterion for assessing
the optimality in the design of the road network corresponds to the general criterion of optimality for
the economy of the country. This most fully satisfies the condition of optimality of the minimum
financial costs, changing with the change in the outline of the network:
åå
i
Еij = min ,
j
(7)

where åå Е
i j
ij - total financial costs, i. e. costs associated with the construction, maintenance and

repair of roads and with the movement of vehicles in the directions ij.
To meet the requirement (7), it is necessary and sufficient that at each of the directions of the
projected network, a possible minimum financial cost is provided, i.e. to:
Е1- 2 = min;ü
Е1-3 = min;ïï
... ïï
ý (8)
Е1- n = min;ï
... ï
ï
Е ij = min . ïþ
The validity of condition (8) can be proved in the following way. Let's say that there is an optimal
road network for which:
Е1-2 = min
Е1-3 = min
…
Е1-n = min
…
but Еij ¹ min.

If we replace the route for which Еij ¹ min, by such a route that Е´ij = min, then the sum of all
financial costs on the network will decrease by the amount:

5
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

D = Е ij - Е ij¢ , (9)
and it appears that:
åå Е ¢ < åå Е
i j
ij
i j
ij . (10)

It follows that for the case under consideration åå Е ¢ ¹ min

i j
ij the original proposal on the

optimality of the road network, for which at least one route Еij ¹ min, is incorrect.
Thus, unlike the original proposal, the road network can not be optimal if inequality (8) is not
respected.

5. Economic and mathematical model of road network optimization

The economic-mathematical model of a network of highways should be considered as a special case of
the model of optimization of a unified transport network.
On the basis of the above considerations, it seems possible to draw up a system of equations
characterizing the main regular relations between the formulated requirements of road transport and
the deployment of a network of highways:
åå Е = min; ij ü
Е ij = min;
ïï
F(l , Q , D , v ij , E ij ) = 0;
i j

ij ij ij ý, (11)
M ij ³ (i = 1,2,3,..., m; j = 1,2,3,..., m )ï
ïþ
where:
lij – route length between the corresponding points i and j;
Qij – traffic between the corresponding points i and j;
Dij – road costs that ensure the movement of vehicles in the direction;
Aij – transport costs in the same direction;
vij – average vehicle speed.

The system (11) reflects the basic necessary condition for optimal road networks and the general
principle of their construction in the mathematical formulation. Given mathematical model instructs
on ways of the decision of a problem contains: definition of road and transport expenses; Selection of
routes on which these costs are minimal, which leads to the fulfillment of the requirement expressed
by the first ratio. The penultimate ratio in the system indicates that there is a functional dependence on
a certain route between the objects of transportation, traffic speed, road and transport costs. The
solution of this dependence with respect to Eij, i.e. determination of total road and transport costs, is of
independent interest and is an essential element of the task as a whole.
The principal relationship between total costs and their road and transport components can be
represented by the equation:

Е ij = l ij (Dij + Aij ) . (12)

Considering the issue of optimal allocation of the road network, it is legitimate to assume that the
most loaded links of the network should first of all be selected in the optimal network. If, during the
selection of links, it becomes necessary to identify passenger transportations and consider them
separately, this will require additional calculations and new principles for constructing optimal binding
networks of roads.
The general principle of constructing the optimal binding network of roads is that any
corresponding point in the optimal connecting road network is connected to all other corresponding

6
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

points of the links, which ensure the least specific road and transport costs for moving goods from this
point to all other corresponding network points.
Drawing up a mathematical model of the road network, one should start from the following
limiting conditions:
• the optimal network must be a binder, i.e. must connect all without exception the corresponding
points (there must be at least one route between each pair of points);
• for various reasons, some link zk must be excluded from the construction of the optimal network
or, conversely, necessarily included in it.
This condition is expressed by equality (1), and the transport-operational level of the projected
network must be such that the speed v ij between points i and j can not be less than a certain
predetermined speed, the traffic intensity Nij is not more than N ij , the safety factor of traffic Кбij is not
less than К бij .
As a result, the economic-mathematical model for optimizing the road network can be represented
by the following system of equations and inequalities:
M ij ³ (i = 1,2,3,..., m; j = 1,2,3,..., m );ü
z k = 0;1; ï
ï
l ij
Lij = (Dij + Aij ); ï
ïï
Qij
ý. (13)
Lij = min; ï
åi åj Lij = min; ï
ï
ï
v ij ³ v ij ; N ij ³ N ij ; К б ij ³ К б ij ; þï
On the basis of the general principle, the task is reduced to the selection of such links, in which
routes would be formed, providing the lowest specific road and transport costs between any two
corresponding points.

6. Conclusion
The goal of optimizing the road network is to improve the efficiency of transport. The most fully
satisfying condition for optimality is the minimum financial costs associated with the construction,
maintenance and repair of the road network and the movement of vehicles along them. In the study,
this indicator was adopted as a criterion of optimality in the economic and mathematical model of the
road network. Therefore, the main requirement for the road network from the road transport side is to
ensure the realization of all the transport links served by it with the least cost required for this.
From the example considered, it can be concluded that the main condition for the optimal binding
networks of roads is the following: each corresponding point in the optimal connecting road network
is connected with all other corresponding points in the directions providing the least financial costs
necessary for moving passengers and cargo from this point to other corresponding points.
This also implies the general principle of constructing an optimal connecting road network, which
consists in the fact that any isolated point in the optimal connecting road network is connected to all
other corresponding points, which ensure the least financial costs for the movement of passengers and
goods from this point to all other corresponding Network point.
On the basis of the general principle, the task is to select such links, under which routes would be
created that would ensure road and transport costs between two corresponding points.

References
[1] Barcelo J and Casas J 2002 Dynamic Network Simulation with AIMSUN. International
Symposium Proceedings on Transport Simulation, Yokohama. Kluwer Academic Publishers

7
ICMSQUARE IOP Publishing
IOP Conf. Series: Journal of Physics: Conf. Series 1234567890
936 (2017) 012032 doi:10.1088/1742-6596/936/1/012032

[2] Florian M, Mahut M and Tremblay N 2005 Application of a simulation-based dynamic traffic
assignment model. In: Kitamura, R., Kuwahara, M. (Eds.), Simulation Approaches in
Transportation Analysis: Recent Advances and Challenges. Springer, New York, pp. 1–22
[3] Handy S 2005 Planning for accessibility: In theory and in practice. Access to destinations, pp.
131–147
[4] Krilatov A Yu Optimal strategies for traffic flow management on the transportation network
of parallel links Bulletin of St. Petersburg University. 2014, Vol. 10. № 2, pp. 120-129
[5] Ligthill M J, Whitham F R On kinetic waves. A theory of traffic flow on crowded roads. Proc.
of the Royal Society Ser. A. 1995, Vol. 229, No. 1178
[6] Litman T 2003 Measuring transportation: traffic, mobility and accessibility. ITE Journal, 73
(10), pp 28–32
[7] Mahmassani H S 2001 Dynamic network traffic assignment and simulation methodology for
advanced system management applications. Networks and Spatial Economics. 1 (3/4), pp.
267–292
[8] Nagel K, Wagner R, Woesler R Still flowing: Approaches to traffic flow and traffic jam
modeling, January 2, 2003
[9] Nagurney A 2004 Spatial Equilibration in Transport Networks, in Handbook of Transport
Geography and Spatial Systems, D. A. Hensher, K. J. Button, K. E. Haynes, and P. R. Stopher,
editors, Elsevier, Amsterdam, The Netherlands, pp. 583-608
[10] Sakhapov R L, Nikolaeva R V, Gatiyatullin M H and Makhmutov M.M. Risk management
model in road transport systems. Journal of Physics: Conference Series. 2016, Vol. 738. № 1,
pp. 1-10
[11] Volkov D O, Garichev S N, Gorbachev R A, Moroz N N Mathematic simulation of transport
network load with a view to assessing viability of building new types of network systems.
PROCEEDINGS MIPT. 2015, Vol. 7, № 3, pp. 69-77
[12] Wardrop J G Some theoretical aspects of road traffic research. Proc. Institution of Civil
Engineers. 1952, Vol. 2, рp. 325–378
[13] Beckmann, Martin, C. B. McGuire, and Christopher B. Winsten. Studies in the
Economics of Transportation. No. 226 pp. 1956.
[14] Dafermos, Stella C., and Frederick T. Sparrow. "The traffic assignment problem for
a general network." Journal of Research of the National Bureau of Standards B 73.2
(1969): 91-118.
[15] Sakhapov R.L., Absalyamova S.G. Integration of universities and business as the condition of
formation of the innovative economy. International Conference on Interactive Collaborative
Learning, ICL 2013 2013. pp. 189-191