{'fraction_non_alphanumeric': 0.025398540934882464, 'fraction_numerical': 0.005268846257768171, 'mean_word_length': 4.698999230177059, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic origin-to-destination routing of wirelessly connected, autonomous vehicles on a congested network

Up-to-date information wirelessly communicated among vehicles can be used to select the optimal route between a given origin and destination. To elucidate how to make use of such information, simulations are performed for autonomous vehicles traveling on a square lattice of roads. All the possible routes between the origin and the destination (without backtracking) are of the same length. Congestion is the only determinant of delay. At each intersection, right-of-way is given to the closest vehicle. There are no traffic lights. Trip times of a subject vehicle are recorded for various initial conditions using different routing algorithms. Surprisingly, the simplest algorithm, which is based on the total number of vehicles on a route, is as good as one based on computing travel times from the average velocity of vehicles on each road segment.


Introduction
Wirelessly connected, autonomous vehicles offer the potential for better vehicle safety and improved traffic flow, among other benefits. [1][2][3][4][5][6][7][8] From a research perspective, these systems present an interesting challenge to determine how to exploit them in an optimal manner. One such topic is to find the fastest path between a given origin (O) and destination (D) amongst multiple routes with time varying congestion. Many papers [9][10][11][12] have been published on the "OD" problem, frequently with the emphasis on mathematical techniques, such as the Dijkstra algorithm [13], to find the fastest route in a computationally efficient way. In the presence of congestion, the fastest route might not be the shortest route. Researchers tend to use measurements of flow to estimate travel time on individual road segments. A common practice is to use a function (travel time as a function of flow) from the US Bureau of Public Roads. [14] The present paper is a report of simulations to determine the fastest OD route for autonomous vehicles with wireless connections navigating through congestion of their own making.
Wireless communication among vehicles can provide useful information. The simplest possibility is just broadcasting the number of vehicles on each link. The average velocity of vehicles on any link could also be provided. In this paper I consider how information from connected vehicles on a road network can be used to predict the optimal route for a given OD. The network studied is a square lattice of identical links (single lane, one way), so each route to be analyzed is the same length (assuming no north-bound to west-bound or east-bound to south-bound turns). Congestion is the only factor that determines travel time. Vehicles are taken to be identical, autonomous cars equipped with adaptive cruise control, which is consistent with the assumption of an ideal wireless connection. [15] The network is simple enough that enumerating paths is straightforward. The emphasis of this research is to use information from wireless connections about realistic congestion caused by many vehicles moving on the network, rather than a surrogate like flow at an intersection, when attempting to find optimal routes. The model is described in Sec. 2 of the paper. Simulations for different algorithms are compared in Sec.
3. The nature of the congestion through which the subject vehicle travels is also described in Sec. 3.
Conclusions and discussion are presented in Sec. 4.

The model
The goal is to discover routing algorithms that reduce the travel time from a given origin to a given destination in the presence of traffic congestion. Each vehicle is taken to be autonomous with wireless connection to the subject vehicle, whose trip times from origin to destination are recorded. Congestion occurs on the network of roadways when sufficient numbers of vehicles are present. Except for the subject vehicle, all vehicles travel on the roads with a non-zero probability to turn randomly at intersections. The road network is a square lattice of single-lane, one-way roads ( The periods for the periodic boundary conditions are for east-west roads and for north-south roads. Note that in the region < < there are no cross roads to cause congestion and similarly for < < . The destination of the subject vehicle is . The origin is at = 0, = .
Initially Two global algorithms are considered so that the predicted optimum path corresponds to the minimum value of where the sum is over the segments of the path. Note that a segment is two adjacent east-bound or north-bound links (more precisely, a segment includes the intersection in the middle, but not the two on the ends) and  Unexpectedly, the average of the velocity squared (not shown) is also fairly constant after the initial transient even though individual velocities vary from near zero to the speed limit . Because each vehicle is identical, this is equivalent to the kinetic energy of the system of vehicles remaining nearly constant. The system is not conservative, however, because kinetic energy is dissipated by individual vehicles when braking. The near constancy of the total kinetic energy further demonstrates that the system has reached a near steady state by 500 s.

7
That the V algorithm and the N algorithm give similar results can be understood by noting the correlation between the average velocity on a segment and the number of vehicles on segment as shown in Fig. 8. Fig. 9 shows the number of vehicles on east-bound segments and north-bound segments at various times for a typical simulation. The absence of large changes with time indicates why the static algorithm works almost as well as the dynamic algorithm to find the optimal route as depicted in Fig. 5.
Attempts to find a similar correlation between flow on a segment and the number of vehicles, and thus the travel time, were unsuccessful. Likewise, as Fig. 10 shows, there is no useful relationship between segment travel time = / and flow, which is given by . The number of cells in a segment is = 2 − 1. The data were calculated from the data used for Fig. 8.

Conclusions and discussion
Information provided by wirelessly connected vehicles about congestion on any potential route is shown to be useful for determining the route with the minimum travel time from the given origin to destination. In the scenario evaluated in this paper, all routes are equal in length and speed limit. The determining factor for trip times is the extent to which congestion has set in. In congested traffic, simulations demonstrate that choosing the route with the minimum number of vehicles is as good an indicator of the optimum route as using the average velocity of vehicles on each segment of a route to predict travel time. In some respects the N algorithm uses less information but performs as well as the more detailed V algorithm.
If routes are not of the same length, obviously the V algorithm would be the algorithm of choice.
However, if some of the potential routes are equal in length, only the route with the fewest vehicles needs to be considered for comparison to other routes (of different lengths). Because counting the number of vehicles on a segment is simpler than computing their average velocity, using a combination of algorithms reduces the complexity of the optimal route determination.  were calculated from the data used for Fig. 8.