Routing a vehicle through city traffic by the time-optimal dynamic path

Abstract

The key goal of this study is to synchronize traffic flows, optimize the use of the transport arteries throughout the city, prevent congestion, and follow each vehicle to its destination to minimize time spent on the trip. As a result, the total time spent by cars on the road will be significantly reduced, and environmental conditions will improve accordingly.

The object of the study is a city's transportation network, represented as a weighted oriented nonplanar multigraph (WONM). The key advantage of using the graph theory to build optimal routes is based on the following considerations: 1) the graph theory has developed many algorithms for finding optimal routes (Dijkstra algorithm, Floyd-Warshall algorithm, A-star algorithm, etc.); 2) the graph theory is used as the theoretical and practical basis of logistical systems, including urban traffic. To build a route in such a multigraph an A-star algorithm has been used, which establishes an optimal time (t-optimal) route between two selected vertices of graph.

The study offers a realistic prospect for solving the problem of congestions through the use of a special software algorithm oriented towards establishing optimal routes and using graphs to represent the city's transportation network.

The fundamental issue is the representation of the city's transport network in the form of an electronic map and the display of GPS-identifiers of vehicles involved in traffic on this map. The "city traffic → electronic map" representation makes it possible to obtain data as to the level of congestion in the transport network. The use of an electronic city map allows the GPS coordinates of each vehicle to be projected onto it. Thus, the city's transport network is under the full control of the transportation management center (TMC), which has a real opportunity to interact with each vehicle and constantly adjust its route, choosing the t-optimal one. The route adjustment is carried out via General Packet Radio Service (GPRS) channel in the form of voice commands as in conventional GPS navigation. However, the specifics are as follows: 1) the navigation is carried out online; 2) t-optimal routes are plotted, taking into account the traffic situation at any given time.

Thus, a large-scale transportation urban traffic network and an associated computer program has been developed. This is an applied project, and its results can be used to effectively regulate traffic in megacities in order to minimize the travel time of each vehicle along a selected route.