The research aims to create technology to improve the capacity of urban transport networks. An algorithm for constructing an optimal route for each vehicle in a large city has been developed with a route correction in real time in accordance with the dynamics of changes in the traffic situation. Technically, the procedure for regulating vehicle flows is carried out by automating traffic control at each intersection and road sections between neighboring intersections. This allows a traffic management center (TMC) to monitor an entire transport network of the megacity in real time, as well as to accompany each vehicle along the route, which has set its origindestination coordinates. An implementation of the intelligent traffic regulation process is based on the use of graph modeling of the urban transport network and the use of an A-star algorithm to navigate the optimal route. A computer program written in Java performs the named procedure. Technically, the process of control and regulation of urban traffic is that the TMC transmits voice commands to each driver along the route with the destination declared by the driver, as it is in regular GPS navigation. The peculiarity is that the program analyzes the dynamic traffic situation throughout the city. As a result, there is a constant update of the travel routes of each vehicle, taking into account traffic situation at a particular moment in time in accordance with the traffic situation. The consequence of this process will be the disappearance or a significant reduction in congestion on urban highways. The final result of the research is the synchronization of traffic flows and an optimal use of transport arteries throughout the city. In addition, the probability of traffic will be significantly reduced. It is also significant that each driver in such traffic regulation scenario will arrive at his destination in the shortest possible time. oriented multigraph, GPS navigation, A-star algorithm, optimal route, Java program, intelligent ORSID: 0000-0002-0286-297X (P.Nikolyuk ); 0000-0003-2474-7697(T.Nescorodieva); 0000-0003-3841-7373(E.Fedorov ); 0000-0003-1134-
Traveling a vehicle in a big city anywhere on the globe is a big problem. The name of the problem is traffic jams on urban transport arteries. Moreover, an urgency of the problem is growing every year due to a sharp increase in the number of cars on city streets. At the same time, the capacity of urban roads remains practically unchanged. In this respect it is important to note that modern technologies aimed at solving urban transport problems are not capable of improving the traffic situation in megacities today. We are talking about a variety of modern technologies for managing urban traffic, including GPS navigation, which only states the fact of traffic problems with a delay – post factum.
2020 Copyright for this paper by its authors.
To solve the problem due to its complexity and the need to consider technological and managerial factors, a systematic approach is required. In the technological aspect, this work solves the formulated problem by using a special algorithm in combination with technical means of organizing urban traffic. The study lays the foundations of an automated intelligent system (AIS) for vehicle traffic regulation in large city. The task of such AIS is to navigates the optimal routes for each car that participates in city traffic and interacts with the TMC. In comparison with other means of elimination of congestions the offered approach allows to prevent their formation. In general, the study is a fundamentally new approach to solving the problem of organizing the movement of vehicles in large cities.
In the managerial aspect, to implement the technology in the real structure of the municipal economy, it is proposed to implement a sequence of processes that will reduce organizational risks.
The known solutions to the problem of transport collapse of megacities relate to technical aspects, while the issues of their implementation remain out of the attention of researchers. This approach limits the possibilities of commercialization of the research results and significantly reduces the probability of their use in a practice of municipal government.
Consequently, the urgency of work in solving transport problems of cities is due to: development of an algorithm for coordinating the movement of vehicles, the implementation of which prevents the occurrence of critical traffic situations in big cities; the inclusion of technical and organizational processes in the range of issues under study, which is due to the use of a systematic approach and the need to reduce the cost of introducing technical; the lack of significant modernization of the city's transport infrastructure with significant investment; in the context of directing significant resources of large cities to fight the pandemic, this factor will help accelerate the implementation of the proposed technical solution; the possibility of two-vector scaling of work results – both in the direction of increasing the number of tracked vehicles, and in the direction of decreasing them; the above indicates that the proposed algorithm for generating optimal routes for a car to the size of a transport network is promising and, thus, expands the range of cities for the implementation of the proposed automated traffic management system.
An investigation of networks of different nature, in particular neural, allows to make predictions,
including for urban transport networks [
Special attention is paid to the choice of optimal routes in the urban transport network, as this issue is
key in terms of urban traffic strategy. In particular, the study [
Principles of operation of transport networks should be explored in different modes. Particular
attention in this regard should be paid to the overloaded mode, which causes traffic. It is the dynamics of
the transition between different phases of traffic devoted to the study [
The authors [
The optimization of urban traffic processes is based on a separate city intersection. The intersection
itself is the main cause of congestion on urban transport networks. The main challenge in this sense is to
maximize a throughput of this type of facility. Many researchers pay attention to this problem. Let us
dwell on the analysis of the results of work [
As a result of the implementation of the named steps, there will be a complete synchronization of traffic flows, which will lead to a fundamentally new quality and, consequently, to a disappearance of congestion (or sharp reduction) in the transport network. This will allow each driver to arrive to their destination in a shortest possible time. Thus, urban traffic is transformed into a fundamentally new state.
The aim of the study is to create the basic elements of technology that will stabilize city traffic and transfer it to a qualitatively new state. The frequency of congestion will be minimized, and each vehicle will arrive at its destination in the shortest possible time.
To achieve the stated goal, the following tasks were set: to create a model of urban transport network in a form of the weighted non-planar multigraph with dynamically loaded edges (arcs); to automate each intersection, which involves the installation in the roadway of special sensors that detect cars leaving the lanes or, conversely, entering theirs; to navigate optimal routes to each vehicle participating in city traffic; implement the transfer of sensor data to TMC; to implement the work of the software algorithm in real time, which will allow timely monitoring of changes in urban traffic – this fact fundamentally distinguishes the procedure proposed in this study from existing urban transport navigation systems.
So, we will formulate the basic principles of the development: the city transport network is presented in the form of an weighted oriented non-planar multigraph; each arc of the above-mentioned graph simulates a lane that runs between adjacent city intersections and receives a weight, the value of which corresponds to the load of the vehicle of this lane in the real road situation; the weights of the arcs of the described multigraph are obtained as a result of the use of special sensors that detect wheel pairs intersecting these sensors, built into a roadway at each intersection; the above-mentioned scales are dynamic values that correspond to the dynamics of changes in real urban traffic, which monitors the congestion of the transport network on each elementary road segment – on the lane; the obtained model is used for navigating the optimal routes for all vehicles that have ordered such services.
Piezo-crystalline sensors [
It have been done for effective work of the computer program [
ℎ . Let ℎ ℎ entering the section of the road that runs from intersection A to intersection B. Suppose we are talking about cars that are along the horizontal section of the road (in Fig. 3 that are cars 1 and 2). Certainly, these vehicles could travel in the direction of intersection B during the green light at intersection A. The value ℎ ℎ
represents the number of vehicles leaving the lane of a section of the road AhBh in different
directions, allowed by traffic rules, during a burning of a green phase of the traffic light at the intersection
B. Each lane at this intersection, as seen in Fig. 3 is equipped with its own sensor to separate registration
of the groups of the vehicles moving on their own routes. On the section of the road AhBh vehicles could
relocate to select the optimal route, which is calculated using a program that operates on the TMC [
is the total number of cars (more precisely a number of car’ wheel pairs)
⁄( ℎ ℎ )) ℎ ℎ → min.
In this condition f represents a number of lanes forming a route of each vehicle; is geometric length of a road section between adjacent intersections, an index of which is h.
Graph modeling of an urban transport network allows a use of various algorithms developed in graph theory. In this case, a use of the A * -algorithm is most appropriate in relation to solving the problem – navigating a route in a graph between two given vertices (on the other hand – between the origindestination positions of the route).
This algorithm navigates an optimal route (in our case, this route is time-optimal) and has a slight algorithmic complexity of type O (N) too, where N is the amount of input data. The action of such (1) algorithm leads to the analysis of the function f (n) = g (n) + h (n), where g (n) is the distance from the origin position of the vehicle to the intermediate vertex n; h (n) is the heuristic distance taken in a straight line from an intermediate vertex of the graph to the destination position.
The channel “Vehicle ↔ TMC” works in real time, constantly updating data as to a load of the road
sections between adjacent intersections, taking into accounts the results obtained from the road sensors.
Next, the TMC based on the operation of the program [
The next method of the program navigates the route between b1_2 and b11_10 lanes (in Fig.3 these lanes are highlighted) on Appendix 2. Method used A-star algorithm looks as follows on Appendix 3.
It is fundamental moment that interaction between each vehicle and TMC occurs both in real time and in a mode of constant route correction. This function realizes computer programs, which navigate the optimal (on time) routes for each vehicle. As a result, every vehicle driver receives instructions, such as those presented below:
Course-1: [b1_2-Broad street, a3_7-Valley street, b7_10-Trump street, a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course-2: [a3_7-Valley street, b7_10-Trump street, a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course-3: [b7_10-Trump street, a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course-4: [a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street] Course-5: [a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street] Course6: [a10_11-Apple street, b11_10-Apple street] Course-7: [b11_10-Apple street]
The peculiarity of this result is that the route consists only from selected lanes. In this case, each new Course starts from the second position of the previous Course. The program constantly updates the route: as soon as the vehicle crosses an input sensor, the program on the TMC calculates the updated route. Thus, the actual route of our hypothetical vehicle will look like this:
b1_2-Broad street → a3_7-Valley street → b7_10-Trump street → a10_9-Kennedy street → a9_10-Kennedy street → a10_11-Apple street → b11_10-Apple street.
Presented above result is a fundamental feature of the investigation. It allows to navigate dynamic routes that track a dynamic of changes in urban traffic. Presented above program is characterized the spectra of fundamental peculiarities, which consist in constant updating of a route by means of intercepting the result of the previous calculation. In this regard, it should be noted that each previous Course is associated with the next one. Another words, the result of the calculation in a next step intercepts the second position of the previously calculated route (these key positions are highlighted above).
The quality of the technology is assessed at the stage of its implementation, so this stage must be given due attention. The implementation of the proposed algorithm in a real environment requires a use of modern management tools – project management methodology, the theory of constraints and considering the practices of managing a transport infrastructure of cities. Then the effectiveness of the technology can be considered as a tuple:
= { 1, 2, 3}, (2) where PMp1 – a set of methods of project management, MPIp2 – a set of practices of transport infrastructure management, TOCp3 – a set of the methods of the constraints theory.
It is important that the elements of the tuple (2) are interconnected by common resources – performers, time parameters, funds and tangible assets. To solve a problem of optimal control of an implementation and operation of TMC, which implements algorithms according to relations (1), it is reasonable to apply the provisions of the theory of distribution design mechanisms (another name – the theory of economic mechanisms – TEM). TEM is the theoretical basis of modern microeconomics and allows to combine in a single model all the processes occurring in a complex transport management system of the metropolis, namely: testing the technology of optimization of many vehicle routes in a transport environment of large scale; development of a project to implement technology in a real environment of a big city; project implementation while minimizing resource conflicts and coordination of the interests of participants in a process, in the spectrum of which are economic (fuel savings for each vehicle owner), environmental (reduction of CO2 emission), social (timely arrival of ambulances, rescuers, police), etc. Adherence to consistency will reduce organizational risks.
Note also that the proposed technology is easily consolidated into urban transport infrastructure. Technically, you only need to connect the terminals of the sensors mounted at intersections to the traffic light control system.
1. Created a real multigraph model that reproduces the transport network of the neighborhood area of Toronto (Fig. 1). Moreover, all existing lanes are modeled considering the directions of traffic in each of these lanes. Each edge of the graph receives a weight that changes dynamically according to changes in traffic.
2. A method of using piezocrystalline sensors mounted in each intersection has been implemented, which has allowed a registration of traffic flows between all neighboring intersections. This means that entire transport network of the city (in terms of its vehicle load) is under the control of TMC. This system, thus, monitors all changes in traffic and calculates the dynamic optimal routes for each vehicle, relevant to each time moment. This circumstance gives possibility to avoid congestion.
3. The research implemented a software module [
4. Procedure has been created to use data taken from sensors mounted at each city intersection. The research assumes the transfer of such data to the TMC by using an existing network that controls an operation of traffic lights. This allows to organically and without significant costs to implement the proposed technology.
5. The research proposes a scheme for the transfer of designed routes from TMC to vehicle drivers. This procedure is used of GPS-navigation technology. However, the technology introduced in the study is characterized by the fact that it works in real time based on real data. This allows responding in a timely manner to changes in urban traffic, thus avoiding congestion. In this sense, the initiated traffic control procedure is fundamentally different from the strategy of modern urban GPS-navigation.
Appendix 1. Listing 1.
import java.util.*; public class Astar { /* the next constructor creates some node of the graph, presented in Fig. 2 */ static Node a1_2 = new Node("a1_2-Liberty avenue", 962); /*the next method creates interactions between adjacent nodes*/ public static void initGraph() {
Random k = new Random(); int L2_1 = 320; double ra2_1 = 1 + (double) k.nextInt(5) * L2_1; double rb2_1 = 1 + (double) k.nextInt(5) * L2_1; double rc2_1 = 1 + (double) k.nextInt(5) * L2_1; a1_2.adjacencies = new Edge[]{ new Edge(b2_1, ra2_1), new Edge(b2_1, rb2_1), new Edge(c2_1, rc2_1),};