Sage Journals: Discover world-class research

Abstract

In this paper, we propose a novel cost function to be embedded in a distributed algorithm for cooperative rerouting of connected and automated vehicles (CAVs) in urban networks. The computation is performed by intersection units managing the portion of the network for which they are in charge by sending updated routes to follow to the CAVs there. Moreover, the intersection units communicate among each other to be updated on the situation of the (in general nonhomogeneous) links of the network. The proposed approach allows the decomposition of the problem into subproblems, which are resolved distributively with little information exchange. The problems are constructed to obtain a fair compromise between user equilibrium and system optimum, taking advantage of the strengths and coping with the limitations of both. We 1) show the results obtained by running simulations with CAVs on the Sioux Falls network compared with a baseline scenario; 2) analyze the results obtained with different penetration rates of CAVs; and 3) provide a sensitivity analysis to investigate how parameters in our approach affect the results of the experiments.

Keywords

operations traffic flow theory and characteristics traffic flow automated vehicles connected vehicles cooperative

Connected and automated vehicles (CAVs) are becoming a reality and, together with opportunities ( 1 – 5 ), challenges arise likewise, including, for example, how to integrate CAVs with human-driven vehicles, guarantee connectivity, and develop CAV real-time planning and control strategies ( 6 , 7 ). Among such challenges is vehicle routing, that is, determining a proper route for the CAVs to follow. Route search and planning have been widely researched, considering their use in spatial data management and location-based social services, and multimodal route planning in transportation systems ( 8 , 9 ).

A comparative study of vehicle route planning in smart cities is presented by Nha et al. ( 10 ). Route planning is a specific type of vehicle routing problem: the former aims to find a route between two locations (origin and destination), whereas the latter focuses on serving several customers by several vehicles. As a consequence of the definition of the two problems, whereas vehicle routing problems are generally proven to be NP-hard ( 11 ), route planning is solvable by optimal methods. Nha et al. identified three categories of algorithm in this research: 1) optimal, 2) heuristic, and 3) hybrid algorithms. Optimal algorithms guarantee to find the global optimal solution through the exploration of the whole set of available solutions; examples of such methods include the Dijkstra algorithm and incremental graphs. Heuristic-based approaches explore a subset of the available solutions and usually find an approximate optimal solution with qualities close to those of the global optimal one; examples include A*, genetic algorithms, ant colony optimization, and tabu search ( 12 , 13 ). Finally, hybrid algorithms leverage the strengths of both of the previous approaches: an example of a hybrid method could apply a combination of Dijkstra- and genetic algorithms.

In the research by Taha and AbuAli, the authors consider the problem of routing from a broader perspective, including vehicular communication, sensing, localization, Internet of Things, computing, and machine learning ( 14 ). They also present a review of route planning metrics, outlining their evolution from the traditional distance/time/cost to metrics that are more relevant to vehicle autonomy such as scenery and safety. Such discussions have expanded to encompass the complexity of route planning in the presence of autonomous vehicles, and how this complexity can be managed. Finally, they highlight the necessity for considering traffic management during events or emergencies, so that both traffic management directives and autonomous intervehicle collaboration might lead to safer and faster resolutions of congestion.

Other major efforts focus on the optimization of multiobjective routing problems. In a study by Zajac and Huber, the authors offer an overview of which application-oriented, multiobjective routing problems are treated and which trade-offs are investigated ( 15 ). Algorithmic approaches are analyzed with regard to their fitness assignment strategy, namely how the multiple objectives are handled, and their search strategy to solve the problem. A rich classification is presented, based on the objective types: 1) related to flows/tours (such as distance, reliability, environment, health risk, military risk); 2) related to nodes/arcs/edges (such as comfort, time to destination, customer cost); and 3) related to resources (such as facilities, transportation goods, goods).

Most of the previous approaches aim at minimizing a, so to speak, user-centered cost, which usually depends on factors such as the time from the origin to the destination, speed, and waiting time for every single vehicle. In this regard, an interesting concept was proposed in Menelaou et al.’s research to minimize traffic congestion through continuous-time route reservations with travel time predictions ( 16 ). Nevertheless, the current fastest/shortest routes are not always the most appropriate to follow, as pointed out by Li et al.: the authors propose a double rewarded value iteration network to model current and future states and learn the experienced drivers’ routing decisions based on their estimation of traffic trends ( 17 ). This is to take advantage of the knowledge of experienced drivers about the topology and traffic trends of the roads they are traversing. On the other hand, only a few works address the routing problem by affecting the macroscopic traffic variables, thus minimizing traffic congestion considering current measurements of the density, volume, and mean speed of the traffic. For example, Wuthishuwong and Traechtler use a discrete consensus algorithm to coordinate autonomous agents and redistribute the traffic through rerouting ( 18 ). However, the latter type of approach typically operates under the assumption that the intersections lie in a network of roads with a common fundamental diagram, which is not realistic.

A crucial point in this context is understanding whether and how the adoption of a system optimum (SO) solution (i.e., minimizing only network-level objectives) affects the behavior of an urban network with CAVs and what is its role in relation to the user equilibrium (UE) solution (i.e., minimizing only user-level objectives). A comprehensive review is offered by Morandi, who discusses possible ways of bridging the gap between the two optima ( 19 ). Specifically, UE results from a user-centered traffic assignment in which each user self-interestedly chooses the most convenient route. When the equilibrium is reached, all users sharing the same origin and destination will experience the same travel time, therefore, guaranteeing respect for fairness. However, the UE generally does not minimize the system’s total performance. On the other hand, the SO results from a systemwide traffic assignment in which drivers are routed on the network in such a way that the total travel time is minimized. However, if SO is achieved, some users may experience travel times that are higher than other users traveling from the same origin to the same destination, which may be considered unfair.

Chen et al. developed a route control scheme to achieve the SO of a network by controlling a portion of CAVs in an attempt to demonstrate the potential of automated vehicles as control actuators for improving traffic network performance ( 20 ). Their results show that a minimum control ratio can be identified. Furthermore, they propose a joint route control for CAVs and pricing for an uncontrolled vehicles scheme that demonstrate the synergistic effect of the joint scheme on reducing the minimum control ratio and the financial burden on travelers. A multiclass model dynamic traffic assignment is developed by Ngoduy et al. to equally distribute the total queues over the links while considering explicitly the variations in capacity and backward wave speeds ( 21 ). The results show that the introduction of automated vehicles changes the traffic flow dynamics. This leads to a reduction in the spillback and total system travel time—even more so with increased penetration rates and total demands when heavy traffic congestion occurs.

The aforementioned studies analyzing SO assume the presence of a central unit to handle the load of information and yield the optimal solution. Therefore, they focus on redefining the optimization problem to favor its scalability and tractability. On the other hand, a distributed approach might be utilized instead. The impact of distributed dynamic routing under different market penetration rates of CAVs and congestion levels on urban roads is investigated by Alfaseeh et al., in an agent-based traffic simulation study of downtown Toronto’s network ( 22 ). The results show that the higher the market penetration rates of CAVs—especially in the case of highly congested urban networks—the higher the average speed, the lower the mean travel time, and the higher the throughput. More research work in the field of distributed routing has been proposed, especially exploiting the VANET technology ( 23 ). Examples of the latter are found in Mostafizi et al., in which the authors propose a decentralized routing framework with a heuristic algorithm, considering the travel speed to be inversely proportional to the number of vehicles in the roads ( 24 ); in a study by Sun et al., proposing ant colony optimization on vehicles at intersections, broadcasting messages to build multihop links ( 25 ); in a study by Mahajan et al. in which intelligent vehicles cooperate by delegating virtual agents to share their planned future routes with roadside agents ( 26 ); in Yao et al.’s research, adopting a distributed routing strategy using past vehicle traces via the hidden Markov model to predict the vehicles’ future positions and the packet transmission probability for a specific mobile destination ( 27 ); and in Lin et al.’s study in which the authors propose a moving zone-based routing protocol that divides the network into multiple moving zones formed by vehicles, grouped and led by a “captain” vehicle, which have the same movement model ( 28 ). In all the previous research, however, there are limitations, including performance not considering the actual traffic situation of the network, or being too inclined toward UE that congestion might effortlessly arise.

In this work, we propose a novel cost function be integrated in a cooperative real-time rerouting algorithm for CAVs to obtain an efficient redistribution of the flows in an urban network. The function is constructed so that the algorithm solution leans toward a UE as long as possible, while still coping with the overall system performance for volumes of vehicles. Moreover, we argue its predisposition to be solved in a distributed fashion. In what follows, we present the proposed methodology and how it relates to the formulation of the UE and SO problems. Then, we show the results obtained by 1) running a simulation in which we tested our methodology compared with a baseline on the Sioux Falls network; 2) analyzing the results obtained considering different penetration rates; and 3) performing a sensitivity analysis. Finally, we summarize our work and suggest directions for future research.

Methodology

In this section, we underline the proposed methodology, starting from the framework and assumptions, followed by presentation of the cost function to be utilized by a routing algorithm, in this case, its utilization in the Dijkstra algorithm ( 29 ).

Framework and Assumptions

We considered a network of intersections connecting links, where each link is characterized by a potentially different fundamental diagram. We assumed the presence of intersection unit devices (IUs) able to communicate with each other and with the CAVs. We defined a route to be followed by a CAV as the sequence of intersections (or, interchangeably, IUs) to drive through from an origin intersection to a destination intersection. Despite the so-defined route not being realistic since CAVs do not have origins and destinations exactly at intersections, we retained this definition for the sake of simplicity and will consider necessary modifications in future developments. Figure 1 gives a practical example of the network considered. The role of the IUs is to sense the presence of the CAVs within their area of competence and/or be informed by them via communication to reinforce the reliability of the sensed data. Furthermore, the IUs communicate and propagate information among each other to make sure that each of them has an updated “situation” of the network, which is described by the number of vehicles driving on each link at a given time. Other information about the links in the network is necessary, namely the capacity volume and density (i.e., number of vehicles at capacity), and the jam density (i.e., maximum number of vehicles). The latter, in general, result from a fundamental diagram that is different for each link and is, for example, uploaded to the IUs beforehand, therefore offline, or estimated online via available techniques such as that presented by Tajdari and Roncoli ( 30 ). The IUs update and deliver the route to be followed by every CAV within its range, which encompasses the vehicles within its inflowing links driving toward the IU itself. The CAVs can employ their communication capabilities to inform an IU when arriving within its area of competence, as already mentioned. Moreover, the CAVs will receive the updated route and actuate some techniques to track thereof. The tracking techniques are not the object of this study, but they can, for example, address intersection coordination and minimization of the error to the reference route as in Vitale and Roncoli’s research ( 31 – 33 ).

Figure 1.

The network considered. The white circles represent the IUs, which are placed at the intersections.

Applicability and Limitations

The positive outcome of the proposed method is influenced by the possibility of successfully installing the IUs in the appropriate locations. In this paper, to simplify presentation of the strategy, we have assumed that there is an IU for each intersection and they are capable of communicating with other IUs and CAVs and sensing the vehicles. However, different positions in the network could be explored, given that they still provide useful (for the proposed method) information and are able to communicate. This scenario is the subject of investigation in the research community and did not seem to pose a problem for the implementation of our technique ( 34 , 35 ). Moreover, continuous advances are being introduced in the field of vehicular communication, considering the currently available technologies and ongoing research about communication via, for example, dedicated short-range communication (DSRC/IEEE 802.11p), Wi-Fi, 5G, and beyond ( 36 – 38 ). For these reasons, we believed that the proposed distributed algorithm represented a realistic implementation and deployment option.

Proposed Cost Function

Consider an intersection (where an IU is placed) computing the route of a vehicle from such an intersection to its destination. According to the algorithm in use, the next IU is $l$ , whereas $j$ is the following IU after $l$ . Define a matrix $N$ containing the most recent values of the number of vehicles on each link, a matrix $N^{C}$ containing the values of a critical number of vehicles (i.e., the number of vehicles for which the traffic is flowing at capacity) on each link according to their fundamental diagram, and a matrix $N^{J}$ containing the number of vehicles at full congestion, that is, when traffic flow stops completely, a matrix $V$ containing the most recent values of mean speed on each link, and a matrix $L$ containing the value of the length of each link. Matrices $N$ (used as a proxy for the density), $N^{C}$ (relating to the critical density), and $V$ are uploaded beforehand and updated via communication with the surrounding IUs. Then, we define the cost function from $l$ to $j$ , namely $c_{lj}$ , as

\begin{matrix} c_{lj} : = d_{l} + \frac{L_{lj}}{V_{lj}} (Φ^{σ} (κ_{1}, N_{lj}, N_{lj}^{C}) \\ + Φ^{τ} (V_{lj}, L_{lj}, Φ^{σ} (κ_{1}, κ_{2} N_{lj}^{C}, N_{lj}^{C}), V_{lj}^{F}, \\ Φ^{σ} (κ_{1}, N_{lj}^{J}, N_{lj}^{C}), N_{lj}^{J}, N_{lj}^{C})) . \end{matrix}

(1)

The first term, $d_{l}$ , is the current—that is, affected by the current traffic situation—cost to $l$ . The second term is

Φ^{σ} (κ_{1}, N_{lj}, N_{lj}^{C}) = \frac{1}{1 + e^{- κ_{1} (N_{lj} - N_{lj}^{C})}},

(2)

where the subscripts $l$ and $j$ refer to the link examined and $Φ^{σ} (\cdot)$ is a sigmoid function centered at the capacity $N_{lj}^{C}$ whose skew is determined by the constant factor $κ_{1}$ . Such a formulation allows the assignment of a low cost for driving through Link $(l, j)$ while accommodating a low number of vehicles (less than the critical number) and a high cost otherwise (i.e., in congestion). The third term is

\begin{matrix} Φ^{τ} (\cdot) = Φ_{1}^{τ} (V_{lj}, L_{lj}, Φ^{σ} (κ_{1}, κ_{2} N_{lj}^{C}, N_{lj}^{C})) \frac{L_{lj}}{V_{lj}^{F}} \\ + Φ_{2}^{τ} (Φ^{σ} (κ_{1}, N_{lj}^{J}, N_{lj}^{C}), V_{lj}, L_{lj}, \\ Φ^{σ} (κ_{1}, κ_{2} N_{lj}^{C}, N_{lj}^{C}), N_{lj}^{J}, N_{lj}^{C}) {(N_{lj} - N_{lj}^{C})}^{2}, \end{matrix}

(3)

namely, a function scaling the time needed to drive through Link $(l, j)$ by an opportune factor, $κ_{2}$ , to give more or less importance with respect to the $Φ^{σ} (\cdot)$ function. Specifically,

Φ_{1}^{τ} (\cdot) = \frac{V_{lj}}{L_{lj}} Φ^{σ} (κ_{1}, κ_{2} N_{lj}^{C}, N_{lj}^{C})

(4)

allows a higher weight to be assigned to the time needed to drive through Link $(l, j)$ with respect to the number of vehicles. The function $Φ_{1}^{τ} (\cdot)$ scales the time so that it intersects $Φ^{σ} (\cdot)$ at $κ_{2} N_{lj}^{C}$ , that is, $κ_{2}$ times the critical number. Before $κ_{2} N_{lj}^{C}$ the travel time cost matters more than the traffic situation, whereas after such a value the traffic situation cost prevails. On the other hand, the function

Φ_{2}^{τ} (\cdot) = {\begin{matrix} 0, & if N_{lj} < N_{lj}^{C} \\ \frac{Φ^{σ} (κ_{1}, N_{lj}^{J}, N_{lj}^{C}) - \frac{V_{lj}}{L_{lj}} Φ^{σ} (κ_{1}, κ_{2} N_{lj}^{C}, N_{lj}^{C})}{{(N_{lj}^{J} - N_{lj}^{C})}^{2}} & otherwise \end{matrix}

(5)

allows us to consider the travel time cost as a square function and rescale it so that it will meet the sigmoid function at the full congestion number of vehicles. Note that at full congestion (i.e., when $N_{lj} = N_{lj}^{J}$ ), the denominator in Equation 5 cancels out when replaced in Equation 3 and, since $V_{lj}$ goes to 0, the only nonnull term is $Φ^{σ} (κ_{1}, N_{lj}^{J}, N_{lj}^{C})$ in Equation 5, namely the value defined by the sigmoid function at full congestion.

Note that, in the total cost (Equation 1), whereas the second element allows a load-sharing process among the links, the third one takes into account the time needed to traverse a link. Both the terms $Φ^{σ}$ and $Φ^{τ}$ are then multiplied by the term $L_{lj} / V_{lj}$ , that is, the current time needed to drive through Link $(l, j)$ . This latter multiplication has the purpose of modifying the amplitude of the two functions (both would otherwise be at most 1) and providing a better cost assignment to the links, particularly when they are in a congested state. The constants $κ_{1}$ and $κ_{2}$ play an important role in tuning the algorithm to lean toward the user or the system optima. The idea behind this formulation is to let the CAVs give higher importance to following the UE as long as the number of vehicles is sufficiently lower than the critical value (see Figure 2 for a clarification of the shape of these two functions).

Figure 2.

The two main cost terms, $Φ^{σ} (\cdot)$ and $Φ^{τ} (\cdot)$ , for different values of $κ_{1}$ and $κ_{2}$ .

Application to the Dijkstra Algorithm

The algorithm run by the IUs is a modified version of the Dijkstra algorithm ( 29 ), in which we modify the cost function by considering Equation 1. Although it would be possible to utilize other shortest-path routing algorithms employing the proposed cost, in the present study we focused on Dijkstra, owing to its popularity and proven optimality, leaving the investigation of other algorithms as a future research direction. A CAV driving toward an intersection communicates with the relative IU as soon as it is within its communication range (and/or is sensed by the IU itself). At this point, and at every time instant thereafter, the IU runs Algorithm 1 (rerouting algorithm) for the CAV until it exits its range. The input needed for the algorithm to run includes the network graph $G$ , the set of IUs (nodes), $I$ , the set of links (edges), $E$ , the origin, $o$ , which is the next intersection that will be visited by the CAV (i.e., the IU itself), the destination, $d$ , which is the last intersection that the CAV wishes to visit through its route, $N$ , $N^{C}$ , $V$ , and $L$ , as defined above. After every periodical measurement, the IUs spread the information to the other IUs, together with a timestamp, so that each of them has an estimation of the most recent traffic situation. The algorithm follows the classical steps of the Dijkstra algorithm in which the initialization requires the distance to the origin to be 0, the distance to the other intersections to be infinity for every intersection, such a distance to be added in a queue, and the predecessor list to be null (Lines 1 to 5). Unless the queue is empty, the least distant to the origin neighbor (Intersection $l$ ) is chosen and removed from the queue (Lines 6 to 8). For all the neighbors, $j$ , of the latter (Line 9), the cost is computed as the summation of the three terms as previously introduced (Line 10).

Algorithm 1 Rerouting algorithm.
Require: $G (I, E), o, d, N, N^{C}, V, L$ Ensure: $P$ 1: $d_{o} \leftarrow 0$ 2: for all $i \in I \ o$ do 3: $d_{i} \leftarrow \infty$ 4: $Q . add (i, d_{i})$ 5: $P_{i} \leftarrow null$ 6: while $Q \neq \emptyset$ do 7: $l \leftarrow argmi n_{i \in Q} {d_{i}}$ 8: $Q \leftarrow Q \ l$ 9: for all $(l, j) \in E$ do 10: $c_{lj} \leftarrow d_{l} + \frac{L_{lj}}{V_{lj}} (Φ^{σ} (\cdot) + Φ^{τ} (\cdot))$ $▹$ as in Eq. (1) 11: if $c_{lj} < d_{j}$ then 12: $d_{i} \leftarrow C_{ij}$ 13: $P_{j} \leftarrow l$ 14: if just entered or exited then 15: Update $N_{lj}$ 16: Update $V_{lj}$

Algorithm 1 Rerouting algorithm.

Require:

G (I, E), o, d, N, N^{C}, V, L

Ensure:

P

d_{o} \leftarrow 0

2: for all

i \in I \ o

do
3:

d_{i} \leftarrow \infty

Q . add (i, d_{i})

P_{i} \leftarrow null

6: while

Q \neq \emptyset

do
7:

l \leftarrow argmi n_{i \in Q} {d_{i}}

Q \leftarrow Q \ l

9: for all

(l, j) \in E

do
10:

c_{lj} \leftarrow d_{l} + \frac{L_{lj}}{V_{lj}} (Φ^{σ} (\cdot) + Φ^{τ} (\cdot))

▹

as in Eq. (1)
11: if

c_{lj} < d_{j}

then
12:

d_{i} \leftarrow C_{ij}

13:

P_{j} \leftarrow l

14: if just entered or exited then
15: Update

N_{lj}

16: Update

V_{lj}

The remainder of the algorithm updates the least distant neighbor and sets the predecessor (Lines 11 to 13). Finally, if the CAV has just entered or exited Link $(l, j)$ (Line 14), the number of vehicles on the Link $(l, j)$ is updated (Line 15) and the mean speed is updated according to its fundamental diagram, $f_{lj}^{D} (N_{lj})$ (Line 16). In particular, consider the $i^{th}$ CAV entering the Link $(l, j) \in r_{i}$ , where $r_{i}$ is the route of CAV $i$ , at time $t$ . Define $T$ as a sufficiently large number to be used as the time horizon. Then the update on the situation of the link is

N_{lj} (t, \dots, T) = N_{lj} (t) + 1, if N_{lj} (t) < N_{lj}^{J} (t)

(6)

V_{lj} (t, \dots, T) = f_{lj}^{D} (N_{lj} (t)),

(7)

which is evaluated every time a vehicle requests to enter the Link $(l, j)$ , either from outside, that is, for entering the network itself, or traveling from another link of the network $(x, l)$ . Similarly, the update rule for CAV $i$ when exiting Link $(l, j)$ is

\begin{matrix} N_{lj} (t + 1, \dots, T) = N_{lj} (t + 1) - 1, \\ if (\exists (j, x) \in r_{i} and N_{jx} (t) < N_{jx}^{J} (t)) or ∄ (j, x) \in r_{i} \end{matrix}

(8)

V_{lj} (t + 1, \dots, T) = f_{lj}^{D} (N_{lj} (t + 1)) .

(9)

Note that the increased update in Equations 6 and 7 takes place immediately at time $t$ to avoid conflicts with multiple CAVs entering, whereas the decreased update in Equations 8 and 9 takes place at the following instant, $t + 1$ , for the same reason. The updates are set until $T$ so that they hold even for the following instants where the CAVs are neither entering nor exiting a new link.

Given the nature of the proposed solution, with the possibility that every IU takes care of the CAVs within its respective range while communicating to achieve better performances, we can conclude that this algorithm falls in the category of distributed routing ( 24 – 28 ) via sharing of the vehicle load among the links in the urban network.

User Equilibrium and System Optimum

In the following, we provide the UE and SO problem formulation definitions as widely employed ( 19 ) and highlight how they relate to our methodology.

UE is defined as

\begin{matrix} \min \sum_{(ij) \in E} \int_{0}^{x_{ij}} t_{ij} (ω) d ω \\ s . t . x_{ij} = \sum_{c \in C} \sum_{k \in K_{c}} a_{ij}^{kc} y_{c}^{k} \forall (i, j) \in E \\ d_{c} = \sum_{k \in K_{c}} y_{c}^{k} \forall c \in C \\ x_{ij} \geq 0 \forall (i, j) \in E \\ y_{c}^{k} \geq 0 \forall c \in C \forall k \in K_{c}, \end{matrix}

(10)

where the cost function is the sum over all the links of the integral between 0 and the link flow, $x_{ij}$ , of the link latency function containing the travel time, $t_{ij}$ . Note that this is equivalent to summing the free-flow travel time and the additional time, which is an increasing function of the flow of vehicles, and resembles the cost (Equation 3) where the first element scales the free-flow travel time and the second one scales an increasing function of the number of vehicles. Variable $y_{c}^{k}$ represents the flow of the origin–destination pair, $c$ , on path $k$ . The first constraint bounds the arc flows, $x_{ij}$ , to the flow of the paths passing through Link $(i, j)$ using the incidence matrix, $a_{ij}^{kc}$ . In our method, this is guaranteed by the Dijkstra algorithm exploring the neighbors, therefore the actual connected links. The second constraint guarantees demand satisfaction, which, in our algorithm, is trivially achieved by allowing all the vehicles to enter and drive their way from origin to destination. The last two constraints guarantee positive traffic flows, which, in our algorithm, is trivially achieved by ensuring that the vehicles are driving forward.

SO is defined as

\begin{matrix} \min \sum_{(ij) \in E} x_{ij} t_{ij} (x) \\ s . t . x_{ij} = \sum_{c \in C} \sum_{k \in K_{c}} a_{ij}^{kc} y_{c}^{k} \forall (i, j) \in E \\ d_{c} = \sum_{k \in K_{c}} y_{c}^{k} \forall c \in C \\ x_{ij} \geq 0 \forall (i, j) \in E \\ y_{c}^{k} \geq 0 \forall c \in C \forall k \in K_{c}, \end{matrix}

(11)

where the cost function is the sum over all the links of their latency function multiplied by their flow. As an analogy to our method, consider travel time, $t_{ij}$ , and flow, $x_{ij}$ , as functions of the density (or number of vehicles) on Link $(i, j)$ and a typical fundamental diagram (e.g., the triangular one). Travel time will be roughly constant for a specified number of vehicles less than or equal to the critical one, then it will increase indefinitely toward infinity as congestion forces the vehicles to slow down and eventually stop. Flow will increase as the number of vehicles increases until reaching capacity, after which it will start decreasing (typically more slowly) toward zero because of the congestion. Multiplying these two values means having an increasing function up to the critical number of vehicles, then a theoretical multiplication, infinity by zero, should be resolved. To do so, let us assume a triangular fundamental diagram in which the relationship among the density, $k$ , the flow, $q$ , and mean speed, $v$ , is defined as $q = kv$ . To simplify the calculations, consider the travel time, $t$ , as the inverse of the mean speed, $v$ , by letting the space traveled be of unitary length, without loss of generality. Consider also the capacity flow, $q_{c}$ , the critical density, that is, the density for which the traffic is flowing at capacity, $k_{c}$ , and the jam density, $k_{j}$ , then the fundamental diagram is

q = {\begin{matrix} q_{c} \frac{k}{k_{c}}, & for 0 \leq k \leq k_{c} \\ q_{c} (1 - \frac{k - k_{c}}{k_{j} - k_{c}}), & for k_{c} \leq k \leq k_{j}, \end{matrix}

(12)

whereas the travel time is $\frac{k}{q}$ . Therefore, for $0 \leq k \leq k_{c}$ , the flow increases from 0 to $q_{c}$ , the time is constant, $\frac{k_{c}}{q_{c}}$ , and the multiplication time by flow increases. On the other hand, for $k_{c} \leq k \leq k_{j}$ , the flow decreases from $q_{c}$ to 0, the time increases from $\frac{k_{c}}{q_{c}}$ to infinity, and the multiplication time by flow is $\frac{k}{q_{c} (1 - \frac{k - k_{c}}{k_{j} - k_{c}})} q_{c} (1 - \frac{k - k_{c}}{k_{j} - k_{c}})$ tending toward $k$ .

For this reason, the proposed method incorporates the cost function (Equation 1) that rapidly increases until the critical number and then continues to increase slowly while tending toward a constant value that, for convenience, is set to 1 before being multiplied by the factor $L_{lj} / V_{lj}$ . The constraints in Equation 11 are the same as in Equation 10, and therefore already argued to be met by the proposed methodology.

Signalized Traffic Networks

If the network contains intersections that are equipped with traffic signals, there are some considerations to be made. First of all, this would affect the way travel time is computed in the cost function, and in particular in Equation 3. Second, the vehicle speed–number relation may need modification depending on the type of control method in use.

Recalling the review of approaches at signalized intersections carried out in Wang et al. ( 39 ), signalized traffic control can be classified into 1) fixed-time control, 2) actuated control, and 3) adaptive control. Fixed-time control is achieved using historical traffic averages over a given period of the day and repeated throughout that period, whereas actuated control senses arrivals on the active approach, altering (slightly) the green time duration based on the presence of vehicles. Consequently, these types of control do not cause major changes to any demand fluctuation or dynamic variation. Therefore, since the signal settings could be integrated into the estimated capacities, thus reflected in the fundamental diagram, our methodology is applicable without relevant modifications to this scenario.

In the case of adaptive control, such as the max-pressure controller ( 40 ), discussions might be more complex. A typical objective is to prioritize those links experiencing a higher volume of traffic (see Zhou and Roncoli [ 41 ]), which, in turn, implies their delay is increased (or average speed is increased). Therefore, it would be interesting to consider extending the cost function in Equation 1, and even derive and tune it by means of data-driven and reinforcement learning strategies, which are topical subjects in lines of research investigating the future traffic environment ( 42 ). Other possible approaches proposed in literature regard multicommodity routing (e.g., in De Souza et al. [ 43 ]). To implement a naive version of the latter, our methodology could take into account the speed constraint of each CAV and reroute it toward more appropriate links. Finally, it is worth investigating the possibility of our strategy being employed as an input to a signal timing algorithm, even running this in an iterative fashion, similar to, for example, Li et al. ( 44 ). Nevertheless, more in-depth research is required to investigate possible exploitation of the traffic signal cycle plans to modify the cost function.

Simulation Experiments

In this section, we present the results obtained by running a set of simulation experiments. First, we describe the setting, then we show the results for a baseline technique, namely a basic Dijkstra, where routes are computed considering the time needed to travel in free-flow, also known as an all-or-nothing strategy, therefore without checking the actual situation of the congestion, and those applying the proposed algorithm for comparison. Then, we investigate the behavior of the proposed algorithm with various penetration rates and perform a sensitivity analysis.

Experimental Settings

We adopted the widely employed Sioux Falls network (see, e.g., Zhou and Roncoli [ 41 ], Rahman and Hasan [ 45 ], Huang et al. [ 46 ], and Pel and Nicholson [ 47 ]), as illustrated in Figure 3 and described in Transportation Networks for Research ( 48 ), with minor modifications to adapt it to a more interesting and relevant scenario for this study. We retained all the information about the structure of the networks, that is, the same 24 nodes (corresponding to the positions of the IUs) and 76 links. However, the cited reference assumes the free-flow time needed to traverse a link (in minutes) to be equal to the length thereof (in miles). As a consequence, the free-flow speed is 60 mph for all the links. To make this more suitable for an urban environment, we considered the length of the links (between 2 and 10 mi) to be a tenth of the reported value. We also resized the density at capacity, or critical density, accordingly and set the capacity flow considering a triangular fundamental diagram, whereas the jam density was arbitrarily set to four times the critical density. Moreover, we set different values for the free-flow speed on the links, so that they resembled the maximum speed limits in the actual city that the network was an abstraction of. Table 1 shows the data utilized for the network. Despite the above-mentioned modifications, we kept the hourly number of trips as per the original values ( 48 ), here omitted for the sake of conciseness, which in total was 360,600. However, we only considersed vehicles entering the network within 10 min and ran the simulations for half an hour to ensure that all of them had exited. We generated vehicles in the network with random entering times, origins and destinations, in such a way as to meet the above-mentioned trips for each path. Ultimately, the total number of vehicles resulting from a 10-min demand was 59,898. For the sake of clarity of terminology, in what follows, we define the occupancy as $N_{lj} / N_{lj}^{J}$ , namely the ratio between the number of vehicles in a link and the number of vehicles at jam density on Link $(l, j)$ . Similarly, $N_{lj}^{C} / N_{lj}^{J}$ is the critical occupancy, at which the traffic is flowing at capacity, whereas $N_{lj}^{J} / N_{lj}^{J} = 1$ represents full occupancy, that is, indicating a fully congested link.

Figure 3.

Sioux Falls network.

Table 1.

Sioux Falls Network Revisited as Used in this Paper

Origin	Destination	Capacity, vph	Length, mi	FF speed, mph	Origin	Destination	Capacity, vph	Length, mi	FF speed, mph
1	2	3,985	0.65	65	13	24	1,175	0.43	65
1	3	5,401	0.43	65	14	11	2,438	0.20	30
2	1	3,985	0.65	65	14	15	2,051	0.25	30
2	6	1,487	0.33	40	14	23	2,462	0.20	30
3	1	5,401	0.43	65	15	10	4,504	0.30	30
3	4	6,416	0.27	40	15	14	2,051	0.25	30
3	12	5,401	0.43	65	15	19	9,710	0.15	30
4	3	6,416	0.27	40	15	22	6,399	0.15	30
4	5	13,337	0.13	40	16	8	2,018	0.25	30
4	11	1,636	0.30	30	16	10	2,427	0.20	30
5	4	13,337	0.13	40	16	17	5,230	0.10	30
5	6	2,474	0.20	30	16	18	13,120	0.15	30
5	9	4,000	0.25	30	17	10	1,248	0.40	30
6	2	1,487	0.33	40	17	16	5,230	0.10	30
6	5	2,474	0.20	30	17	19	4,824	0.10	30
6	8	3,674	0.13	40	18	7	10,802	0.22	65
7	8	5,228	0.15	30	18	16	13,120	0.15	30
7	18	10,802	0.22	65	18	20	5,401	0.43	65
8	6	3,674	0.13	40	19	15	9,710	0.15	30
8	7	5,228	0.15	30	19	17	4,824	0.10	30
8	9	1,010	0.50	30	19	20	2,501	0.20	30
8	16	2,018	0.25	30	20	18	5,401	0.43	65
9	5	4,000	0.25	30	20	19	2,501	0.20	30
9	8	1,010	0.50	30	20	21	778	0.65	65
9	10	9,277	0.15	30	20	22	2,030	0.25	30
10	9	9,277	0.15	30	21	20	778	0.65	65
10	11	4,000	0.25	30	21	22	5,230	0.10	30
10	15	4,504	0.30	30	21	24	1,503	0.33	65
10	16	2,427	0.20	30	22	15	6,399	0.15	30
10	17	1,248	0.40	30	22	20	2,030	0.25	30
11	4	1,636	0.30	30	22	21	5,230	0.10	30
11	10	4,000	0.25	30	22	23	2,500	0.20	30
11	12	1,636	0.30	30	23	14	2,462	0.20	30
11	14	2,438	0.20	30	23	22	2,500	0.20	30
12	3	5,401	0.43	65	23	24	5,079	0.10	30
12	11	1,636	0.30	30	24	13	1,175	0.43	65
12	13	7,969	0.33	65	24	21	1,503	0.33	65
13	12	7,969	0.33	65	24	23	5,079	0.10	30

Note: vph = vehicles per hour; FF = free flow.

Comparison with a Baseline

For this simulation, we ran a baseline Dijkstra algorithm in which the links were chosen based on free-flow travel time without accounting for the actual situation of the network, and the proposed algorithm with parameters $κ_{1} = 1$ $κ_{2} = 1$ on the same scenario for comparison. Figure 4 shows the results obtained by running the baseline algorithm and the proposed algorithm on the Sioux Falls network. Figure 4a shows that the average occupancy was above the critical one, therefore in mild congestion, for roughly 500 s (from 100 to 600 s of the simulation horizon). Moreover, the maximum occupancy reached by any link in the network was equal to 1, namely fully congested, for about 1,300 s. On the other hand, Figure 4b shows an apparent lower maximum occupancy, which never reached full congestion. Moreover, the slightly higher average occupancy observed, especially in the first 300 s, demonstrated that more links accommodated more vehicles, which could be explained by 1) the rerouting of the vehicles toward other links, and 2) the possibility of accommodating more vehicles, since none of the links were highly congested. We highlight the results obtained, in particular, for Links 74, 73, 66, 69, and 62 in Figure 3, as these were among the most congested. Figure 5 shows the occupancy levels of the aforementioned links for both the baseline and proposed algorithm. For example, Figure 5a shows how Link 74 was especially congested, allowing the congestion to propagate backward to the other links. Figure 5b ascertains the lowering in occupancy levels, with Link 74 still exhibiting relatively high congestion, even if clearly lower than the baseline. We further investigated this aspect, by analyzing the fundamental diagram of such links: Figure 6 once again illustrates that only Link 74 reached higher levels of congestion, but was never fully congested. Figure 7 shows the occupancy levels aggregated in three categories: 1) links with a maximum speed of 30 mph, 2) links with a maximum speed of 40 mph, and 3) links with a maximum speed of 65 mph. Although Figure 7a shows how high levels of occupancy were reached in different links of the categories, Figure 7b shows how the congestion was much lower than in the baseline. Figure 8 illustrates the fundamental diagram for the links aggregated as before. Finally, Table 2 presents a comparison of the total travel time (TTT) and total delay (TD) for the baseline and proposed algorithm as compared to the free-flow TTT. The proposed algorithm achieved an improvement of 28.55% for TTT and 57.94% for TD.

Figure 4.

Occupancy averaged by the whole network and maximum occupancy reached by any link in the network for (a) the baseline and (b) the proposed algorithm simulation.

Figure 5.

Occupancy levels reached by Links 74, 73, 66, 69, and 62 for (a) the baseline and (b) the proposed algorithm simulation.

Figure 6.

Fundamental diagram (expressed as number of vehicles–flow) of Links 74, 73, 66, 69, and 62 for (a) the baseline and (b) the proposed algorithm simulation.

Figure 7.

Occupancy averaged and categorized into four groups: 1) links with maximum speed 30 mph, 2) links with maximum speed 40 mph, and 3) links with maximum speed 65 mph. Results for (a) the baseline and (b) the proposed algorithm simulation.

Figure 8.

Fundamental diagram (expressed as number of vehicles–flow) for the links aggregated into four groups: 1) links with maximum speed 30 mph, 2) links with maximum speed 40 mph, and 3) links with maximum speed 65 mph. Results for (a) the baseline and (b) the proposed algorithm simulation.

Table 2.

Total Travel Time (TTT) and Total Delay (TD) Reported in Seconds of the Baseline and Proposed Algorithm Compared with Free-Flow Driving, and Improvement Percentage of the Proposed Algorithm with Respect to the Baseline

	Free-flow	Baseline	Proposed	Improvement, %
TTT	3,162,540	6,234,352	4,454,651	28.55
TD	0	3,071,812	1,292,111	57.94

Penetration Rate

In the following, we discuss how different penetration rates, specifically the percentage of vehicles that were CAVs, affected the behavior of our algorithm. To do so, we ran several simulations in which we randomly sampled the vehicles according to a given percentage of CAVs following the proposed algorithm, while the others followed the baseline algorithm, therefore they behaved like human-driven vehicles whose drivers had knowledge of the physical characteristics of the network (length of the links and maximum speed) but had no information about the possible congestion building up there. The parameters in use were $κ_{1} = 1$ and $κ_{2} = 0.5$ . Figure 9 shows the time period of the maximum occupancy reached by any link shrinking as the penetration rate increased, with minor improvements for percentages higher than 70%. Figure 10 shows how the TTT and TD changed as the penetration rate increased. It is interesting to note that, for this choice of parameters, any percentage of penetration rate >0 exhibited lower TTT and TD as compared to not having any CAVs. However, the best performance was obtained for a penetration rate of 50%, whereas a higher one slightly increased the two metrics under investigation. These results suggested that increasing the number of CAVs would make the network so cooperative that the CAVs would be willing to drive a little longer to reduce congestion.

Figure 9.

Maximum and average occupancy as the penetration rate varies.

Figure 10.

Total travel time (TTT) and total delay (TD) as the penetration rate varies.

Human Drivers’ Route-Switching Behavior

In our simulation experiments, we assessed the performance of the proposed algorithm for different penetration rates of CAVs, considering a percentage of human-driven vehicles that behave according to the baseline (all-or-nothing) assignment strategy. Nevertheless, the latter is a simplistic assumption that does not take into account the route changes made by human drivers. In fact, the UE usually assumes that human drivers behave according to some rational precepts of an objective to optimize, such as travel time. Early research studies (49) elaborated on the boundedly rational UE in transportation systems, claiming that it is appropriate to introduce a stochastic UE, occurring when users can no longer improve their perceived utility, which now includes a random component, presumably because of perception errors and other sources of randomness in system performance or user behavior. The existence of such a newly defined equilibrium is not guaranteed and strongly depends on the specific rule followed by the users. Such a rule determines the degree of user satisfaction with the current situation and, therefore, the willingness to not change path if unforeseen delays are experienced. Such a degree of satisfaction, however, falls within a certain range of outcomes delimited by some threshold. In typical day-to-day scenarios, and under heavy congestion, users will be pushed to adjust their perception of satisfaction and modify their routes. Such a modification should be permanent so that users are not obliged to make decisions frequently and it might lead to a new equilibrium which is, however, not unique. Owing to these complications and high uncertainty, it is worth considering such behaviors to extend this work in the future.

Sensitivity Analysis

We conducted a sensitivity analysis to assess the behavior and highlight possible trade-offs that may arise between guaranteeing the dispersion of the traffic to lighten the network and lowering the time delays for the CAVs. In particular, we aimed to investigate the results for $κ_{1} = {0.01, 0.1, 1, 10}$ and $κ_{2} = {0, 0.25, 0.5, 0.75, 1, 1.25, 1.5, 1.75}$ . The simulations for the sensitivity analysis were performed considering the same setting as the previous ones.

Congestion and Travel Time

Figure 11 did not exhibit stark differences in the resulting occupancy while employing different parameters. We observed that, in general, higher $κ_{1}$ values led to the network discharging the vehicles later, as can be seen from the “tail” drawn by the occupancy levels that still lies below the critical value. This can be explained by a higher $κ_{1}$ entailing a steep skew of the sigmoid that tends toward a step function. Therefore, the cost fluctuated around the critical number of vehicles and such oscillations led to the links approaching the critical number without too strong a penalization until they were really close to it. On the other hand, as $κ_{2}$ increased, such a tail was less evident since the congestion dispersion mechanism was triggered later. Moreover, we noted that, for the same reason, the maximum occupancy was reached earlier and it was maintained for a slightly longer time. Figure 12 shows that the best results for TTT and TD were obtained for $κ_{2} \geq 1$ , as expected, since the congestion dispersion mechanism was delayed.

Figure 11.

Maximum and average occupancy as the pair $(κ_{1}, κ_{2})$ varies.

Figure 12.

Total travel time (TTT) and total delay (TD) as the pair $(κ_{1}, κ_{2})$ varies: (a) TTT and (b) TD.

Emissions

For a more comprehensive analysis of our method, we include some results about pollutant emissions. To this end, and in light of the previous sensitivity analysis, we chose $κ_{1} = 1$ and $κ_{2} = 1$ to show such emissions values. Recall that this pair of parameters represents a compromise between favoring the congestion dispersion and experiencing relatively lower (even though not the lowest) travel time. We employed the MOVES model ( 50 ), which is widely employed in literature ( 51 – 53 ). The MOVES model belongs to the class of average-speed emission models. Such models are generally defined via a function that maps the average speed in a certain road link to the average values of the local emissions, namely the mass of pollutant emitted per space unit and per vehicle ( 54 ). Figure 13 shows that the emissions formed a U-shaped function as speed varied with its minimum at around 65 mph. Table 3 shows the percentage reduction obtained by the proposed strategy of five of the most renowned harmful pollutants.

Figure 13.

Emissions values referring to greenhouse gases in carbon dioxide equivalent units $(C O_{2} e)$ , carbon monoxide (CO), particulate matter smaller than 2.5 $μ m$ $(P M_{2.5})$ , nitrogen oxide $(N O_{X})$ , and hydrocarbon (HC).

Table 3.

Total Emissions, Mean, and Standard Deviation of Single Emissions (g/mi) for the Baseline and Proposed Algorithm, and the Percentage of Improvement for the Different Pollutants

	Total	Mean	SD
CO₂e
Baseline	3.895·10⁷	6.503·10²	3.214·10²
Proposed	2.993·10⁷	4.997·10²	2.507·10¹
Improvement, %	23.16	23.16	92.20
CO
Baseline	2.135·10⁵	3.565·10⁰	1.554·10⁰
Proposed	1.691·10⁵	2.824·10⁰	0.155·10⁰
Improvement, %	20.79	20.79	90.06
$P M_{2.5}$
Baseline	3.465·10³	0.058·10⁰	0.027·10⁰
Proposed	2.628·10³	0.044·10⁰	0.006·10⁰
Improvement, %	24.16	24.16	77.97
$N O_{X}$
Baseline	8.632·10⁴	1.441·10⁰	0.591·10⁰
Proposed	6.994·10⁴	1.168·10⁰	0.035·10⁰
Improvement, %	18.98	18.98	94.08
HC
Baseline	1.080·10⁴	0.180·10⁰	0.129·10⁰
Proposed	7.004·10³	0.117·10⁰	0.016·10⁰
Improvement, %	35.13	35.13	88.01

Note: CO₂e = carbon dioxide equivalent; CO = carbon monoxide; PM_2.5 = particulate matter; NO_x = nitrogen oxide; HC = hydrocarbon; SD = standard deviation.

Applicability to Different Networks

Although our formulation implied the adjustment of a cost function based on some general properties of the network, namely the fundamental diagram of its links and related current number of vehicles and average speed, we determined that it would be interesting to conduct further research on the applicability of our method on networks with a different topology and evaluating the necessity of changing the parameters based on the findings. To investigate these issues, we employed a modified version of the Sioux Falls network to mimic the presence of a motorway along the Links 36, 32, 29, and 50 and in the opposite direction along the Links 55-48-27-33. We considered a free-flow speed of 65 mph and capacity of 7,000 vph on these links and deleted Links 10, 31, 25, 26, 22, 47, 34, 40, 28, 43, 30, 51, 49, and 52 to eliminate the intersections on the motorway. We also discarded traffic demand between the origin and destination nodes that did not match the new topology (e.g., vehicles departing from Node 10 and arriving at Node 16). The remaining settings were identical to those of the previous simulations with 10 min of vehicles entering the network for a total of 26,774 vehicles. Figure 14 shows that it took more than half an hour to discharge all the vehicles for the baseline algorithm. Figure 15 shows similar behaviors with respect to the previously obtained results, reinforcing the previous discussion about $κ_{1}$ and $κ_{2}$ choices. Finally, Figure 16, a and b , suggested a similar conclusion as regards TTT and TD.

Figure 14.

Occupancy averaged by the whole network and maximum occupancy reached by any link in the network for the baseline algorithm simulation on the modified topology network.

Figure 15.

Maximum and average occupancy as the pair $(κ_{1}, κ_{2})$ varies on the modified topology network.

Figure 16.

Total travel time (TTT) and total delay (TD) as the pair $(κ_{1}, κ_{2})$ varies on the modified topology network: (a) TTT and (b) TD.

Future Developments

We wish to summarize the future lines of research introduced by this paper. First of all, further investigation on the construction of the cost function is necessary. It would be particuarly interesting to evaluate a different factor to amplify the functions $Φ^{σ} (\cdot)$ and $Φ^{τ} (\cdot)$ other than using the current travel time example. The complexity lies in how this not only depends on Link $(l, j)$ it refers to, but also on the topology of the network, how many other links it is connected to, and so forth. For this purpose, it might be worth considering a more in-depth study employing centrality measures of the network ( 55 ).

Moreover, as already mentioned, to consider more realistic behaviors in the presence of human-driven vehicles, switching route patterns should be considered. In particular, defining or identifying the thresholds within which users would act in favor of the introduction of a boundedly rational UE could lead to the addition of new components in the proposed cost function.

Finally, it would be interesting to assess the resilience to communication delays, packet loss, and altered information exchange.

Conclusions

This study proposed a novel cost function applied to an algorithm for the rerouting of CAVs, showing its capacity to disperse traffic by constructing an appropriate cost function, which was then tested on a modified version of the Dijkstra algorithm. The cost function computed the cost to drive through a link between intersections, considering both the current travel time and the network situation given by the number of vehicles on each link. We designed our technique to be solved in a distributed fashion, allowing scalability at the cost of a small amount of data exchange.

We obtained convincing results for the effectiveness of the proposed algorithm as compared to a baseline technique in relation to both lowering congestion and decreasing the travel- and delay time for the CAVs. We investigated the results obtained with different CAV penetration rates, highlighting the trade-off between favoring system performance and lowering travel time by selecting opportune parameters of the proposed algorithm, since a higher percentage of CAVs would make the system so cooperative that self-interest would be dismissed. Furthermore, we conducted sensitivity experiments to shed light on how the algorithm parameters should be selected based on their ability to disperse traffic, and on the TTT and TD. Such analyses, carried out on two networks with different topologies, revealed similar patterns for the same sets of parameters. Selection of an appropriate set of parameters could be based on the main goal of the operation, namely, dispersing more traffic, anticipating congestion forming or worsening, or decreasing the current travel time, ignoring the effects on future congestion patterns. The different parameter choices did not lead to massive differences that undermined the validity of the proposed approach, on the contrary, all demonstrated massive improvements. Moreover, we further validated improvements in the performance of the proposed strategy by evaluating levels of emissions, which exhibited a substantial reduction with respect to the baseline.

Footnotes

Acknowledgements

The calculations presented were performed using the computer resources of the Aalto University School of Science “Science-IT” project.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: F. Vitale, C. Roncoli; data collection: F. Vitale; analysis and interpretation of results: F. Vitale, C. Roncoli; draft manuscript preparation: F. Vitale. C. Roncoli. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Academy of Finland project ALCOSTO (grant no. 349327).

ORCID iDs

Francesco Vitale

Claudio Roncoli

References

Gutesa

Lee

Besenski

Development and Evaluation of Cooperative Intersection Management Algorithm Under Connected and Automated Vehicles Environment. Transportation Research Record: Journal of the Transportation Research Board, 2021. 2675: 94–104.

Bush

B. W.

Vimmerstedt

Gonder

J. D.

Potential Energy Implications of Connected and Automated Vehicles: Exploring Key Leverage Points Through Scenario Screening and Analysis. Transportation Research Record: Journal of the Transportation Research Board, 2019. 2673: 84–94.

Ahmed

S. U.

Dey

K. C.

Fries

R. N.

Evaluation of Transportation System Resilience in the Presence of Connected and Automated Vehicles. Transportation Research Record: Journal of the Transportation Research Board, 2019. 2673: 562–574.

Sarker

Shen

Rahman

Chowdhury

Dey

Wang

Narman

H. S.

A Review of Sensing and Communication, Human Factors, and Controller Aspects for Information-Aware Connected and Automated Vehicles. IEEE Transactions on Intelligent Transportation Systems, Vol. 21, No. 1, 2019, pp. 7–29.

Elliott

Keen

Miao

Recent Advances in Connected and Automated Vehicles. Journal of Traffic and Transportation Engineering (English Edition), Vol. 6, No. 2, 2019, pp. 109–131.

Guanetti

Kim

Borrelli

Control of Connected and Automated Vehicles: State of the Art and Future Challenges. Annual Reviews in Control, Vol. 45, 2018, pp. 18–40.

Papamichail

Bekiaris-Liberis

Delis

A. I.

Manolis

Mountakis

K. S.

Nikolos

I. K.

Roncoli

Papageorgiou

Motorway Traffic Flow Modelling, Estimation and Control with Vehicle Automation and Communication Systems. Annual Reviews in Control, Vol. 48, 2019, pp. 325–346.

Rao

Pang

Chen

Fan

Route Search and Planning: A Survey. Big Data Research, Vol. 26, 2021, p. 100246.

Bast

Delling

Goldberg

Müller-Hannemann

Pajor

Sanders

Wagner

Werneck

R. F.

Route Planning in Transportation Networks. In Algorithm Engineering: Selected Results and Surveys ( Kliemann

Sanders

, eds.), Springer, Cham, Switzerland, 2016, pp. 19–80.

10.

Nha

V. T. N.

Djahel

Murphy

A Comparative Study of Vehicles’ Routing Algorithms for Route Planning in Smart Cities. Proc., First International Workshop on Vehicular Traffic Management for Smart Cities (VTM), Dublin, Ireland, November 20–20, 2012, IEEE, New York, pp. 1–6.

11.

Lenstra

J. K.

Kan

A. R.

Complexity of Vehicle Routing and Scheduling Problems. Networks, Vol. 11, No. 2, 1981, pp. 221–227.

12.

Russell

S. J.

Artificial Intelligence a Modern Approach. Pearson Education, Inc., Upper Saddle River, NJ, 2010.

13.

Hajlaoui

Guyennet

Moulahi

A Survey on Heuristic-Based Routing Methods in Vehicular Ad-Hoc Network: Technical Challenges and Future Trends. IEEE Sensors Journal, Vol. 16, No. 17, 2016, pp. 6782–6792.

14.

Taha

A.-E.

AbuAli

Route Planning Considerations for Autonomous Vehicles. IEEE Communications Magazine, Vol. 56, No. 10, 2018, pp. 78–84.

15.

Zajac

Huber

Objectives and Methods in Multi-Objective Routing Problems: A Survey and Classification Scheme. European Journal of Operational Research, Vol. 290, No. 1, 2021, pp. 1–25.

16.

Menelaou

Timotheou

Kolios

Panayiotou

C. G.

Polycarpou

M. M.

Minimizing Traffic Congestion Through Continuous-Time Route Reservations with Travel Time Predictions. IEEE Transactions on Intelligent Vehicles, Vol. 4, No. 1, 2018, pp. 141–153.

17.

Yuan

Zhang

Chen

Yang

A Traffic Prediction Enabled Double Rewarded Value Iteration Network for Route Planning. IEEE Transactions on Vehicular Technology, Vol. 68, No. 5, 2019, pp. 4170–4181.

18.

Wuthishuwong

Traechtler

Distributed Control System Architecture for Balancing and Stabilizing Traffic in the Network of Multiple Autonomous Intersections Using Feedback Consensus and Route Assignment Method. Complex & Intelligent Systems, Vol. 6, No. 1, 2020, pp. 165–187.

19.

Morandi

Bridging the User Equilibrium and the System Optimum in Static Traffic Assignment: A Review. 4OR-A Quarterly Journal of Operations Research, Vol. 22, 2024, pp. 89–119.

20.

Chen

Lin

Yin

Path Controlling of Automated Vehicles for System Optimum on Transportation Networks with Heterogeneous Traffic Stream. Transportation Research Part C: Emerging Technologies, Vol. 110, 2020, pp. 312–329.

21.

Ngoduy

Hoang

Watling

Multiclass Dynamic System Optimum Solution for Mixed Traffic of Human-Driven and Automated Vehicles Considering Physical Queues. Transportation Research Part B: Methodological, Vol. 145, 2021, pp. 56–79.

22.

Alfaseeh

Djavadian

Farooq

Impact of Distributed Routing of Intelligent Vehicles on Urban Traffic. Proc., IEEE International Smart Cities Conference (ISC2), Kansas City, MO, September 16–19, 2018, IEEE, New York, pp. 1–7.

23.

Al-Sultan

Al-Doori

M. M.

Al-Bayatti

A. H.

Zedan

A Comprehensive Survey on Vehicular Ad Hoc Network. Journal of Network and Computer Applications, Vol. 37, 2014, pp. 380–392.

24.

Mostafizi

Koll

Wang

A Decentralized and Coordinated Routing Algorithm for Connected and Autonomous Vehicles. IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 8, 2021, pp. 11505–11517.

25.

Sun

Zhang

Guizani

Intersection Fog-Based Distributed Routing for V2V Communication in Urban Vehicular Ad Hoc Networks. IEEE Transactions on Intelligent Transportation Systems, Vol. 21, No. 6, 2019, pp. 2409–2426.

26.

Mahajan

Hegyi

Hoogendoorn

S. P.

van Arem

Design Analysis of a Decentralized Equilibrium-Routing Strategy for Intelligent Vehicles. Transportation Research Part C: Emerging Technologies, Vol. 103, 2019, pp. 308–327.

27.

Yao

Wang

Chen

Wang

V2X Routing in a VANET Based on the Hidden Markov Model. IEEE Transactions on Intelligent Transportation Systems, Vol. 19, No. 3, 2017, pp. 889–899.

28.

Lin

Kang

Squicciarini

Gurung

Tonguz

MoZo: A Moving Zone Based Routing Protocol Using Pure V2V Communication in VANETs. IEEE Transactions on Mobile Computing, Vol. 16, No. 5, 2016, pp. 1357–1370.

29.

Dijkstra

E. W.

A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269–271. https://doi.org/10.1007/BF01386390.

30.

Tajdari

Roncoli

Online Set-Point Estimation for Feedback-Based Traffic Control Applications. IEEE Transactions on Intelligent Transportation Systems, Vol. 24, No. 10, 2023, pp. 10830–10842.

31.

Vitale

Roncoli

Reference Tracking Optimization with Obstacle Avoidance Via Task Prioritization for Automated Driving. IEEE Transactions on Intelligent Transportation Systems, Vol. 25, No. 2, 2024, pp. 1200–1214.

32.

Vitale

Roncoli

Distributed Formation Control for Managing CAV Overtaking and Intersection Maneuvers. IFAC-PapersOnLine, Vol. 55, No. 13, 2022, pp. 198–203.

33.

Vitale

Roncoli

An MPC-Based Task Priority Management Approach for Connected and Automated Vehicles Reference Tracking with Obstacle Avoidance. Proc., European Control Conference (ECC), Delft, Netherlands, June 29–July 2, 2021, IEEE, New York, pp. 813–819.

34.

Guerna

Bitam

Calafate

C. T.

Roadside Unit Deployment in Internet of Vehicles Systems: A Survey. Sensors, Vol. 22, No. 9, 2022, p. 3190.

35.

Karunathilake

Förster

A Survey on Mobile Road Side Units in VANETs. Vehicles, Vol. 4, No. 2, 2022, pp. 482–500.

36.

Singh

P. K.

Nandi

S. K.

Nandi

A Tutorial Survey on Vehicular Communication State of the Art, and Future Research Directions. Vehicular Communications, Vol. 18, 2019, p. 100164.

37.

Cheng

Huang

Chen

Vehicular Communication Channel Measurement, Modelling, and Application for Beyond 5G and 6G. IET Communications, Vol. 14, No. 19, 2020, pp. 3303–3311.

38.

Noor-A-Rahim

Liu

Lee

Ali

G. M. N.

Pesch

Xiao

A Survey on Resource Allocation in Vehicular Networks. IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 2, 2020, pp. 701–721.

39.

Wang

Sanner

Abdulhai

A Critical Review of Traffic Signal Control and A Novel Unified View of Reinforcement Learning and Model Predictive Control Approaches for Adaptive Traffic Signal Control. arXiv preprint arXiv:2211.14426, 2022.

40.

Varaiya

Max Pressure Control of a Network of Signalized Intersections. Transportation Research Part C: Emerging Technologies, Vol. 36, 2013, pp. 177–195.

41.

Zhou

Roncoli

A Scalable Vehicle Assignment and Routing Strategy for Real-Time On-Demand Ridesharing Considering Endogenous Congestion. Transportation Research Part C: Emerging Technologies, Vol. 139, 2022, p. 103658.

42.

Wang

Yang

Liang

Liu

A Review of the Self-Adaptive Traffic Signal Control System Based on Future Traffic Environment. Journal of Advanced Transportation, Vol. 2018, 2018, p. 1096123.

43.

De Souza

Carlson

R. C.

Müller

E. R.

Ampountolas

Multi-Commodity Traffic Signal Control and Routing with Connected Vehicles. IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 5, 2020, pp. 4111–4121.

44.

Mirchandani

Zhou

Solving Simultaneous Route Guidance and Traffic Signal Optimization Problem Using Space-Phase-Time Hypernetwork. Transportation Research Part B: Methodological, Vol. 81, 2015, pp. 103–130.

45.

Rahman

Hasan

Data-Driven Traffic Assignment: A Novel Approach for Learning Traffic Flow Patterns Using a Graph Convolutional Neural Network. arXiv preprint arXiv:2202.10508, 2022.

46.

Huang

Qian

Z. S.

Optimal Deployment of Alternative Fueling Stations on Transportation Networks Considering Deviation Paths. Networks and Spatial Economics, Vol. 15, 2015, pp. 183–204.

47.

Pel

A. J.

Nicholson

A. J.

Network Effects of Percentile-Based Route Choice Behavior for Stochastic Travel Times Under Exogenous Capacity Variations. Proc., 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), The Hague, Netherlands, October 6–9, 2013, IEEE, New York, pp. 1864–1869.

48.

Transportation Networks for Research Core Team. Transportation Networks for Research. https://github.com/bstabler/TransportationNetworks. Accessed June 22, 2023.

49.

Mahmassani

H. S.

Chang

G.-L.

On Boundedly Rational User Equilibrium in Transportation Systems. Transportation Science, Vol. 21, No. 2, 1987, pp. 89–99.

50.

Agency

U. E. P.

Motor Vehicle Emission Simulator (MOVES) 2010 User Guide. 2010. https://www.nrc.gov/docs/ML1127/ML112720505.pdf.

51.

Mohammadi

Vosough

Roncoli

User-based transit signal priority in a connected vehicle environment accounting for schedule delays and environmental impacts. TRBAM-23-03456. In 102nd Annual Meeting of the Transportation Research Board, Washington, D.C., 2023.

52.

Guo

Chen

Stuart

Zhang

A Systematic Overview of Transportation Equity in Terms of Accessibility, Traffic Emissions, and Safety Outcomes: From Conventional to Emerging Technologies. Transportation Research Interdisciplinary Perspectives, Vol. 4, 2020, p. 100091.

53.

Perugu

Emission Modelling of Light-Duty Vehicles in India Using the Revamped VSP-Based MOVES Model: The Case Study of Hyderabad. Transportation Research Part D: Transport and Environment, Vol. 68, 2019, pp. 150–163.

54.

Ferrara

Sacone

Siri

Freeway Traffic Modelling and Control, Vol. 585. Springer, Cham, Switzerland, 2018.

55.

Bullo

Lectures on Network Systems, 1.6 ed. Kindle Direct Publishing, 2022. https://fbullo.github.io/lns.

Cooperative Traffic Dispersion through Rerouting of Connected and Automated Vehicles in Urban Networks

Abstract

Keywords

Methodology

Framework and Assumptions

Applicability and Limitations

Proposed Cost Function

Application to the Dijkstra Algorithm

User Equilibrium and System Optimum

Signalized Traffic Networks

Simulation Experiments

Experimental Settings

Comparison with a Baseline

Penetration Rate

Human Drivers’ Route-Switching Behavior

Sensitivity Analysis

Congestion and Travel Time

Emissions

Applicability to Different Networks

Future Developments

Conclusions

Footnotes

Acknowledgements

Author Contributions

Declaration of Conflicting Interests

Funding

ORCID iDs

References