# An Approximate Dynamic Programming Approach to Vehicle Platooning
Coordination in Networks

Xi Xiong , Maonan Wang , Dengfeng Sun , Li Jin , 111Corresponding author:
<EMAIL_ADDRESS>Key Laboratory of Road and Traffic Engineering, Ministry
of Education, Tongji University, Shanghai, ChinaSchool of Science and
Engineering, The Chinese University of Hong Kong, Shenzhen, ChinaSchool of
Aeronautics and Astronautics, Purdue University, USA.UM Joint Institute and
the Department of Automation, Shanghai Jiao Tong University, China.

###### Abstract

Platooning connected and autonomous vehicles (CAVs) provide significant
benefits in terms of traffic efficiency and fuel economy. However, most
existing platooning systems assume the availability of pre-determined plans,
which is not feasible in real-time scenarios. In this paper, we address this
issue in time-dependent networks by formulating a Markov decision process at
each junction, aiming to minimize travel time and fuel consumption. Initially,
we analyze coordinated platooning without routing to explore the cooperation
among controllers on an identical path. We propose two novel approaches based
on approximate dynamic programming, offering suboptimal control in the context
of a stochastic finite horizon problem. The results demonstrate the
superiority of the approximation in the policy space. Furthermore, we
investigate platooning in a network setting, where speed profiles and routes
are determined simultaneously. To simplify the problem, we decouple the action
space by prioritizing routing decisions based on travel time estimation. We
subsequently employ the aforementioned policy approximation to determine speed
profiles, considering essential parameters such as travel times. Our
simulation results in SUMO indicate that our method yields better performance
than conventional approaches, leading to potential travel cost savings of up
to $40\%$. Additionally, we evaluate the resilience of our approach in
dynamically changing networks, affirming its ability to maintain efficient
platooning operations.

Index terms: Vehicle platooning, Multi-agent systems, Approximate dynamic
programming, Bellman equation.

##  1 Introduction

Connected and autonomous vehicles (CAVs) are rapidly advancing due to recent
progress in artificial intelligence and wireless communication. Platooning
enables vehicles to travel together with very small inter-vehicle headways,
resulting in improved traffic efficiency and fuel economy, particularly for
heavy-duty vehicles [1, 2]. A typical platoon management system comprises
three hierarchies: the vehicle layer, junction layer, and network layer. While
previous efforts have primarily concentrated on the vehicle layer, focusing on
microscopic longitudinal and lateral control schemes [3, 4, 5, 6], recent
research has explored coordinated platooning at the junction and network
layers to minimize travel costs [7, 8]. However, a common limitation of this
research is the assumption that itinerary plans are static and not responsive
to real-time conditions.

To enhance the platoon management system, it is crucial to integrate real-time
responsiveness into the itinerary planning process, which holds the potential
for improving resource utilization and overall system performance. In this
paper, we mainly focus on scalable platooning coordination in time-dependent
networks, employing an approximate dynamic programming approach. Fig. 1
illustrates the platooning coordination at a highway junction. The solid red
lines represent detectors that span the road segment, enabling the collection
of trip information such as destinations, locations and arrival times. These
data can be shared through a communication infrastructure such as a 5G
cellular network. The edges in the diagram are divided into two distinct
sections: the coordinating zone and the cruising zone. Within the coordinating
zone, detectors transmit the trip information to the virtual controller
located at the junction. The primary role of the virtual controller is to
determine whether the current CAV should merge with the CAV ahead to form a
platoon. Upon passing the junction, the newly formed platoon proceeds to
travel together in the cruising zone, with the following vehicle benefiting
from fuel economy advantages resulting from reduced air resistance. The
platooning strategy is closely tied to path planning in networks, as we focus
on the balance between travel time and fuel consumption. To facilitate
effective cooperation among controllers, we develop an approximate dynamic
programming approach for platooning coordination in time-dependent networks.
This approach enables effective coordination mechanisms and address the
challenges associated with real-time strategies.

Figure 1: Platooning coordination at a highway junction.

Previous research on platooning coordination in networks has predominantly
focused on off-line planning, where all trips are announced before the
planning phase. For small-scale cases, exact solutions have been proposed,
while heuristic methods have been devised to tackle larger instances [8].
Larson et al. [9] were the pioneers in studying scalable coordination by
introducing distributed controllers throughout a road network. Their work was
subsequently extended in [10]. In another study, Larson et al. [11] proved
that the network-level platooning problem was NP-hard and proposed integer
linear programming formulations for instances where deadlines are discarded.
Abdolmaleki et al. [12] formulated the problem as a minimum concave-cost
network flow problem and designed an outer approximation algorithm for solving
a mixed-integer convex minimization reformulation. Nourmohammadzadeh and
Hartmann [13] focused on the platooning problem with individual deadlines for
vehicles and employed a Genetic Algorithm to find solutions for larger
instances. Van de Hoef et al. [14] proposed a combinatorial optimization
approach that combines plans involving only two vehicle to solve the
platooning problem and developed a heuristic algorithm for larger instances.
Luo and Larson [15] proposed an iterative route-then-schedule heuristic for
centralized planning, which exhibited rapid convergence to high-quality
solutions. Furthermore, researchers have addressed practical constraints such
as communication systems, travel time uncertainties behavioral-instability
issues, and mandatory breaks for drivers [16, 17, 18, 19]. However, these
approaches assume a priori knowledge of all vehicles’ trip schedules,
disregarding the fact that platoons often split and recombine, leading to
changes in the system’s state [8]. To the best of our knowledge, this paper
represents the first effort to consider dynamic planning, where decisions need
to be made as vehicles are en-route.

We formulate the problem over a multi-origin-destination (O-D) network. When a
CAV enters a junction’s coordinating zone, the controller receives the trip
information to determine speed profiles and optimal routes. To tackle this
junction-level coordination, we adopt a Markov decision process (MDP)
framework. At each junction, the state comprises headways and destinations,
while the action involves selecting the optimal path and assigning a speed.
Our primary objective is to minimize the system-level cost, which encompasses
travel time and fuel consumption. In our formulation, we account for the
presence of mixed-autonomy traffic, which aligns with the setting explored in
[20]. Furthermore, we incorporate a non-linear cost function to capture the
impact of dynamic flows on travel cost, similar to the model presented in
[12].

In this paper, we first analyze coordinated platooning without routing, aiming
to explore the cooperation among controllers on an identical path. It is
difficult to find exact solutions resulting from the interdependencies among
controllers’ decisions. To address this, we propose two general approaches
based on dynamic programming for suboptimal control in the context of a
stochastic finite horizon problem. The first approach involves approximating
cost functions by incorporating the cost estimations of adjacent vertices
obtained from a dynamic programming equation. In the second approach, we
constrain the policy to lie within a given parametric class, involving travel
times and cruising distances. Additionally, we compare the performance of the
two methods in the simulation platform, and the results demonstrate the
superiority of the approximation in the policy space.

Based on the analysis presented above, we study real-time coordinated
platooning in time-dependent networks, where the controller at each junction
determines speed profiles and routes simultaneously. To simplify the problem
structure, we decouple the hybrid action space, giving priority to the routing
decision based on the observation that vehicles generally prefer to minimize
their travel time [10]. The speed profiles for platooning are determined
through the aforementioned approximation in the policy space, considering
relevant parameters such as travel times and cruising distances. Furthermore,
we evaluate our approach using the Nguyen-Dupuis network in the simulation
platform. The results demonstrate that our method outperforms conventional
methods, with remarkable reductions in travel costs of up to $40\%$ during
heavy congestion periods. Additionally, we assess the performance of our
method in dynamically changing networks by simulating edge disconnections, and
the results indicate its ability to effectively react to such changes and
maintain efficient platooning operations. The main contributions of this paper
are summarized as follows:

  1. 1.

We formulate a MDP framework for junction-level coordination aimed at
minimizing travel costs consisting of travel time and fuel consumption.

  2. 2.

We study coordination without routing to analyze coordination among
controllers and propose two general approaches based on dynamic programming
for suboptimal control. The simulation results affirm the superiority of the
approximation in the policy space.

  3. 3.

We decouple the action space for real-time coordination in networks. This
approach prioritizes the routing decision with travel time estimation while
employing the aforementioned policy approximation to determine speed profiles.
The simulation results demonstrate the efficiency and resiliency of our
approach.

The remaining sections of this paper are organized as follows. In Section 2,
we present the modeling of platooning coordination and formulate the Markov
decision process to handle coordination at junctions. In Section 3, we focus
on the analysis of coordinated platooning without routing across a cascade of
junctions. In Section 4, we address the consideration of coordinated
platooning and adaptive routing concurrently within networks. In Section 5, we
summarize the conclusions and propose several directions for future work.

##  2 Modeling and Formulation

In this section, we first introduce the modeling of scalable platooning
coordination and microscopic car-following models, and then present the
problem definition.

###  2.1 Modeling

####  2.1.1 Platooning coordination in networks

Consider a directed network $G=(V,E)$ with vertices $V$ and edges $E$. The
number of vertices is represented as $N=|V|$, while the number of edges is
denoted as $L=|E|$. We define a vertex $\nu\in V$ with more than two edges as
a junction. Let $e_{ij}$ denote the road segment connecting vertex $\nu_{i}$
and vertex $\nu_{j}$. Initially, our focus lies on the platooning coordination
at these junctions, where virtual controllers situated at the junctions
determine the formation of platoons. Fig. 2 shows a simple network with
platooning coordination. There is a coordinating zone $D_{1}$ before each
junction. The red points denote the detectors at the start of each $D_{1}$,
which can collect trip information such as destinations, locations and arrival
times. After each junction, vehicles travel in platoons or alone in the
cruising zone $D_{2}$. An edge is therefore divided into 2 segments: the
coordinating zone $D_{1}$ and the cruising zone $D_{2}$. In practice, $D_{1}$
is much less than $D_{2}$ due to limited communication capabilities.

Figure 2: Platooning coordination in a simple network

When vehicle $k$ enters the coordinating zone of vertex $\nu_{i}$, the time of
entry $t^{k}_{i}$ and its destination $d^{k}$ are transmitted to the virtual
controller at vertex $\nu_{i}$. The controller then determines whether vehicle
$k$ merges with its leading vehicle $k-1$ based on kinematic information from
both vehicles. We assume that the nominal speed in the network is $v_{0}$.
When the controller instructs vehicle $k$ to merge with vehicle $k-1$, vehicle
$k$ will adjust its speed to meet with vehicle $k-1$ at vertex $\nu_{i}$, then
they will travel in groups in the following cruising zone. We make the
practical assumption that vehicle $k$ will not directly influence the movement
of vehicle $k-1$. Additionally, vehicle $k$ will travel in the coordinating
zone with a reference speed from the controller when it is instructed to
travel alone.

In network-level coordination, the controller at each junction determines
speed profiles and routes simultaneously. When the controller at vertex
$\nu_{i}$ instructs vehicle $k$ to merge with vehicle $k-1$, vehicle $k$
traverses vertex $\nu_{i}$’s coordinating zone with the constant speed
$v_{i}^{k}$ from $t_{i}^{k}$, and then meets with vehicle $k-1$ at vertex
$\nu_{i}$. After the junction, vehicle $k$ follows vehicle $k-1$ on edge
$e_{ij}$, which was determined when vehicle $k-1$ entered vertex $\nu_{i}$’s
coordinating zone, until the newly formed platoon enters the coordinating zone
of vertex $\nu_{j}$ at $t_{j}^{k}$. We assume that all information can be
shared through the communication infrastructure along the highway system. A
network-level coordination framework is introduced in Section 4 to facilitate
cooperation among controllers.

####  2.1.2 Microscopic car-following models

We consider the microscopic car-following model Intelligent Driver Model (IDM)
developed by Treiber [21]. The vehicle dynamics of positions and velocities in
IDM are shown as

$\displaystyle\dot{q}_{k}=\frac{\mathrm{d}q_{k}}{\mathrm{d}t},$
$\displaystyle\dot{v}_{k}=\frac{\mathrm{d}v_{k}}{\mathrm{d}t}=a\left(1-\left(\frac{v_{k}}{v_{0}}\right)^{\delta}-\left(\frac{s^{*}\left(v_{k},\Delta
v_{k}\right)}{s_{k}}\right)^{2}\right),$

where $q_{k}$ is the position of vehicle $k$ at time step $t$, and $v_{k}$ is
the vehicle speed. $s^{*}\left(v_{k},\Delta
v_{k}\right)=s_{0}+v_{k}T+\frac{v_{k}\Delta v_{k}}{2\sqrt{ab}}$, and $v_{0}$,
$s_{0}$, $T$, $a$ and $b$ are the parameters. We use $\tau_{l}$ and $\tau_{f}$
to represent headways for the leading vehicle and the following vehicle
respectively. In practice, $\tau_{f}$ is much smaller than $\tau_{l}$ due to
small intra-platoon headways.

The controller at vertex $\nu_{i}$ instructs vehicle $k$ to travel with a
constant speed $v_{i}^{k}$ over the coordinating zone $D_{1}$, and then its
movements are decided by the IDM over the cruising zone $D_{2}$. The platoon
formation in $D_{2}$ is determined by the headway of catching up $\tau_{c}$
and the intra-platoon headway $\tau_{f}$. When the headway of a vehicle is
smaller than $\tau_{c}$, it will adjust its speed until its headway is less
than $\tau_{f}$. In addition, the split process is defined by the headway
$t_{s}$, which denotes the time until a vehicle that keeps a headway larger
than $\tau_{f}$ from its leading vehicle is split off [22].

###  2.2 Problem definition

We consider a Markov decision process (MDP) for junction-level platooning
coordination. Vehicle $k$ enters vertex $\nu_{i}$’s coordinating zone at
$t^{k}_{i}$. We assume that $\\{t_{i}^{k}:k=1,2,\ldots\\}$ is a renewal
process with a probability density function $g(x)$, and the inter-arrival time
is $x_{i}^{k}=t_{i}^{k}-t_{i}^{k-1}$. The state is $s^{k}_{i}=[h^{k}_{i}\quad
d^{k}\quad d^{k-1}\quad e^{k-1}_{ij}]$, where the predicted headway
$h^{k}_{i}$ denotes the time used to catch up with the leading vehicle.
$d^{k}$ is the destination of vehicle $k$, and $e^{k-1}_{ij}$ denotes the
assigned edge for vehicle $k-1$ at $t^{k-1}_{i}$. The action is
$a^{k}_{i}=[u^{k}_{i}\quad e^{k}_{ij}]$, where $e^{k}_{ij}$ denotes the
assigned edge for vehicle $k$, and $u^{k}_{i}$ is the time reduction for
vehicle $k$, which can be converted into the reference speed $v^{k}_{i}$ over
the coordinating zone by $v^{k}_{i}=\frac{D_{1}}{D_{1}/v_{0}-u^{k}_{i}}$. The
deterministic relationship between vehicle $k$ and vehicle $k-1$ is therefore,
$h^{k}_{i}=x^{k}_{i}+u^{k-1}_{i}$, which indicates that current vehicle’s
predicted headway is determined by the time reduction of its leading vehicle.
Furthermore, $h^{k}_{i}$ is larger than $x^{k}_{i}$ when the controller
instructs vehicle $k-1$ to accelerate. Note that the speed over the
coordinating zone $v^{k}_{i}$ is not affected by the IDM model.

Vehicle $k$ follows the routing decision from the controller at vertex
$\nu_{i}$ and travels on edge $e^{k}_{ij}$ until it enters the coordinating
zone of the adjacent vertex $\nu_{j}$ at time $t^{k}_{j}$, then detectors at
vertex $\nu_{j}$’s coordinating zone collect the arrival time and fuel
consumption of vehicle $k$. We consider the travel cost $c^{k}_{i}$ consisting
of travel time $\Delta t^{k}_{ij}=t^{k}_{j}-t^{k}_{i}$ and fuel consumption
$\Delta F^{k}_{ij}$ between vertex $\nu_{i}$ and vertex $\nu_{j}$. The total
cost for vehicle $k$ on edge $e_{ij}$ is defined as

$\displaystyle c^{k}_{i}$ $\displaystyle=w_{1}\Delta t^{k}_{ij}+w_{2}\Delta
F^{k}_{ij}$ (1)
$\displaystyle=w_{1}\left(t^{k}_{j}-t^{k}_{i}\right)+w_{2}\int_{t^{k}_{i}}^{t^{k}_{j}}(1-\eta\mathbbm{1}_{u_{i}^{k}=h_{i}^{k}})r(v_{t})dt,$

where $w_{1}$ is the value of time, and $w_{2}$ is the fuel price. The
following vehicle in a platoon can save a fraction $\eta\in(0,1)$ of the fuel
consumption due to reduced air resistance, which only occurs when vehicle $k$
merges with its leading vehicle, i.e., $u_{i}^{k}=h_{i}^{k}$. $r(v_{t})$ is
the fuel rate depending on the vehicle speed $v_{t}$. Equation (1) states the
trade-off between benefits of platooning over $D_{2}$ and the increased cost
due to acceleration over $D_{1}$.

The objective is to minimize travel cost in networks. At vertex $\nu_{i}$,
$\mathbf{\mathcal{S}}_{i}$ denotes the state space, $\mathbf{\mathcal{A}}_{i}$
denotes the action space, and
$\mathbf{\mathcal{C}}_{i}:\mathbf{\mathcal{S}}_{i}\times\mathbf{\mathcal{A}}_{i}\rightarrow\mathbb{R}$
is the travel cost on $e_{ij}$. When vehicle $k$ enters the coordinating zone
of vertex $\nu_{i}$, the controller executes an action
$a^{k}_{i}\in\mathbf{\mathcal{A}}_{i}$ according to the state
$s^{k}_{i}\in\mathbf{\mathcal{S}}_{i}$, and receives the cost
$c^{k}_{i}\in\mathbf{\mathcal{C}}_{i}$ when vehicle $k$ enters vertex
$\nu_{j}$’s coordinating zone. We need to find the optimal policy
$\pi_{i}^{*}:\mathbf{\mathcal{S}}_{i}\rightarrow\mathbf{\mathcal{A}}_{i}$ such
that $a_{i}^{k}\sim\pi_{i}^{*}(\cdot|s_{i}^{k})$ to minimize the accumulative
cost from vertex $\nu_{i}$ to destinations. Note that the optimality of
$\pi_{i}^{*}$ relies on optimal policies of subsequent vertices. The network-
wide policy is therefore
$\pi^{*}=\left\\{\pi_{1}^{*},\pi_{2}^{*},\ldots,\pi_{N}^{*}\right\\}$.

##  3 Coordinated platooning without routing

In this section, we discuss the platooning coordination without routing to
analyze the interaction among controllers. It is difficult to find exact
solutions due to the interdependencies among controllers’ decisions. To
address this, we propose two general approaches using approximate dynamic
programming for suboptimal control in the context of a stochastic finite
horizon problem. The numerical results show that the approach using
approximation in the policy space can improve data-efficiency without loss of
the coordination performance, which will be extended to the network-level
coordination considering platooning and routing in Section 4.

###  3.1 Coordination over a cascade of junctions

We study coordinated platooning over a cascade of junctions to analyze the
interaction among controllers. Fig. 3 presents the road segment with $N$
junctions. Each junction is equipped with a virtual controller, and red points
denote the start of the coordinating zone of the mainline and on-ramps. When
vehicle $k$ enters the coordinating zone of vertex $\nu_{i}$,
$i=1,2,\ldots,N$, the controller at vertex $\nu_{i}$ determines whether
vehicle $k$ merges with its leading vehicle $k-1$ based on $h_{i}^{k}$. The
flow on the mainline is $f_{m}$, and the flow on the ramp of vertex $\nu_{i}$
is $f_{ri}$. Let $\mathbf{\mathcal{H}}_{i}$ denote the state space at vertex
$\nu_{i}$, and $\mathbf{\mathcal{U}}_{i}$ is the action space. The optimal
policy is
$\mu_{i}^{*}:\mathbf{\mathcal{H}}_{i}\rightarrow\mathbf{\mathcal{U}}_{i}$ such
that $u_{i}^{k}\sim\mu_{i}^{*}(\cdot|h_{i}^{k})$.

Figure 3: Coordinated platooning over a cascade of junctions.

We assume that the travel speed is related to the traffic density on the road
segment, which in turn affects both travel time and fuel consumption. We
propose two general approaches for coordinated platooning considering time-
dependent traffic flows: (i) approximation in the value space, and (ii)
approximation in the policy space. The first approach is data-driven and
employs the framework of dynamic programming. Since we only consider the
predicted headway $h_{k}$ as the decision variable, the polynomial regression
is utilized to approximate the cost function. As for the second approach, we
directly approximate the platooning policy with estimated travel times. In the
following subsections, we will introduce both approaches and compare the
numerical results obtained from each.

###  3.2 Approximation in the value space

Let $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})$ be the expected cost from vertex
$\nu_{i}$ to the destination with the predicted headway $h_{i}^{k}$ and the
action $\xi_{i}^{k}\in\mathcal{U}_{i}=\\{0,1\\}$, where $\xi_{i}^{k}=1$
denotes the merging case with $u_{i}^{k}=h_{i}^{k}$, while $\xi_{i}^{k}=0$
represents that vehicle $k$ keeps its original speed $v_{0}$ over the
coordinating zone. The expected cost $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})$ can be
expressed as

$\displaystyle
J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})=\mathbb{E}\left[c_{i}^{k}+c_{i+1}^{k}+\cdots+c_{N}^{k}\right],$

where $c_{i}^{k},i=1,2,\ldots,N$, is the travel cost from vertex $\nu_{i}$ to
vertex $\nu_{i+1}$. $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})$ can be estimated within
the framework of dynamic programming,

$\displaystyle
J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})=\mathbb{E}\left[c_{i}^{k}+\min_{\xi_{i+1}^{k}}J_{i+1}^{*}(h_{i+1}^{k},\xi_{i+1}^{k})\right],$
(2)

where $h_{i+1}^{k}$ is the predicted headway of vehicle $k$ arriving at vertex
$\nu_{i+1}$, and $\xi_{i+1}^{k}$ is the action at vertex $\nu_{i+1}$. When
vehicle $k$ enters the coordinating zone of vertex $\nu_{i+1}$, it returns the
travel cost from vertex $\nu_{i}$ to vertex $\nu_{i+1}$, and the estimated
cost from vertex $\nu_{i+1}$ to its destination.

When $\xi_{i}^{k}=1$, we approximate $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})$ with a
nonlinear polynomial function,

$\displaystyle
J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})\approx\beta_{0}+\beta_{1}h_{i}^{k}+\cdots+\beta_{n}(h_{i}^{k})^{n}+\epsilon_{i}^{k},$
(3)

where $n$ is the degree, $\beta_{0},\beta_{1},\ldots,\beta_{n}$ are the
parameters, and $\epsilon_{i}^{k}\sim N(0,\sigma^{2})$ is the random error.
Consider $l$ vehicles arriving at vertex $\nu_{i}$ before vehicle $k$ , i.e.,
vehicles $k-1,k-2,\ldots,k-l$, the observed state consisting of vehicle $k$
and previous $l$ vehicles can be expressed as the matrix notation,

$\displaystyle\mathbf{H}_{i}^{k}=\left[\begin{matrix}1&h_{i}^{k}&(h_{i}^{k})^{2}&\cdots&(h_{i}^{k})^{n}\\\
1&h_{i}^{k-1}&(h_{i}^{k-1})^{2}&\cdots&(h_{i}^{k-1})^{n}\\\
1&h_{i}^{k-2}&(h_{i}^{k-2})^{2}&\cdots&(h_{i}^{k-2})^{n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&h_{i}^{k-l}&(h_{i}^{k-l})^{2}&\cdots&(h_{i}^{k-l})^{n}\end{matrix}\right].$

Note that vehicles $k-1,k-2,\ldots,k-l$ are all with the merging action. The
corresponding cost can be denoted as,

$\displaystyle\mathbf{J}_{i}^{k}=\left[\begin{matrix}J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})&J_{i}^{*}(h_{i}^{k-1},\xi_{i}^{k-1})&\cdots&J_{i}^{*}(h_{i}^{k-l},\xi_{i}^{k-l})\end{matrix}\right]^{\mathsf{T}}.$

Hence, the $l+1$ regression equations in the matrix form can be expressed by,

$\displaystyle\mathbf{J}_{i}^{k}=\mathbf{H}_{i}^{k}\boldsymbol{\beta}_{i}^{k}+\boldsymbol{\epsilon}_{i}^{k},$

where
$\boldsymbol{\beta}_{i}^{k}=\left[\begin{matrix}\beta_{0}&\beta_{1}&\cdots&\beta_{n}\end{matrix}\right]^{\mathsf{T}}$
denotes the parameter term.
$\boldsymbol{\epsilon}_{i}^{k}=\left[\begin{matrix}\epsilon_{i}^{k}&\epsilon_{i}^{k-1}&\cdots&\epsilon_{i}^{k-l}\end{matrix}\right]^{\mathsf{T}}$
represents the error term. By utilizing the least squared error approach in
the matrix form [23], the estimated parameter term assuming $n<l+1$ is,

$\displaystyle\hat{\boldsymbol{\beta}}_{i}^{k}=\left((\mathbf{H}_{i}^{k})^{\mathsf{T}}\mathbf{H}_{i}^{k}\right)^{-1}(\mathbf{H}_{i}^{k})^{\mathsf{T}}\mathbf{J}_{i}^{k}.$

Then we can rewrite Equation (2) by,

$\displaystyle
J_{i}^{*}(h_{i}^{k},\xi_{i}^{k},\hat{\boldsymbol{\beta}}_{i}^{k})=\mathbb{E}\left[c_{i}^{k}+\min_{\xi_{i+1}^{k}}J_{i+1}^{*}(h_{i+1}^{k},\xi_{i+1}^{k})\right],$

where $\min_{\xi_{i+1}^{k}}J_{i+1}^{*}(h_{i+1}^{k},\xi_{i+1}^{k})$ also
consists of the merging action and non-merging action for vehicle $k$.

When $\xi_{i}^{k}=0$, $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})$ is not related to
$h_{i}^{k}$ since the travel cost does not depend on the predicted headway. We
use the average cost of previous $y+1$ vehicles to represent the estimated
cost,

$\displaystyle
J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})\approx\frac{1}{y+1}\sum_{j=0}^{y}\left[c_{i}^{k-j}+\min_{\xi_{i+1}^{k-j}}J_{i+1}^{*}(h_{i+1}^{k-j},\xi_{i+1}^{k-j})\right],$

where the previous $y+1$ vehicles are all with non-merging action. The
proposed algorithm for parametric cost approximation with polynomials is shown
in Algorithm 1.

Algorithm 1 Parametric cost approximation with polynomials.

1:Initialization of $J_{i}^{*}(h_{i},0)$; Initialization of
$\boldsymbol{\beta}_{i}$; The polynomial degree $n$; Number of merging
vehicles $l>n-1$; Number of non-merging vehicles $y$.

2:Optimal platooning policy $\mu_{i}^{*}$;

3:Vehicle $k$ enters the coordinating zone of vertex $\nu_{i+1}$

4:$\xi_{i+1}^{k}\leftarrow\arg\\!\min_{\xi_{i+1}^{k}}J_{i+1}^{*}(h_{i+1}^{k},\xi_{i+1}^{k})$

5:$\hat{J}_{i+1}^{k}\leftarrow\min_{\xi_{i+1}^{k}}J_{i+1}^{*}(h_{i+1}^{k},\xi_{i+1}^{k})$

6:Update vertex $\nu_{i}$ with $c_{i}^{k}$ and the estimated cost

7:if $\xi_{i}^{k}=0$ then

8:
$\tilde{J}_{i+1}^{k}\leftarrow\min_{\xi_{i+1}^{k-j}}J_{i+1}^{*}(h_{i+1}^{k-j},\xi_{i+1}^{k-j})$

9:
$J_{i}^{*}(h_{i}^{k},\xi_{i}^{k})\leftarrow\frac{1}{y+1}\sum_{j=0}^{y}\left[c_{i}^{k-j}+\tilde{J}_{i+1}^{k}\right]$

10:else

11: $J_{i}^{*}(h_{i}^{k},\xi_{i}^{k},\boldsymbol{\beta}_{i}^{k})\leftarrow
c_{i}^{k}+\hat{J}_{i+1}^{k}$

12:
$\hat{\boldsymbol{\beta}}_{i}^{k}\leftarrow\left((\mathbf{H}_{i}^{k})^{\mathsf{T}}\mathbf{H}_{i}^{k}\right)^{-1}(\mathbf{H}_{i}^{k})^{\mathsf{T}}\mathbf{J}_{i}^{k}$

13:end if

14:Output the optimal policy $\mu_{i}^{*}$ such that

15:if $\arg\\!\min_{\xi_{i}}J_{i}^{*}(h_{i},\xi_{i})=1$ then

16: $\mu_{i}^{*}(h_{i})=h_{i}$

17:else

18: $\mu_{i}^{*}(h_{i})=0$

19:end if

###  3.3 Approximation in the policy space

Typically, we can use the relative cost instead of absolute values in Equation
(1),

$\displaystyle RC_{i}^{k}=-w_{1}u_{i}^{k}+w_{2}(\Delta F_{1}-\Delta F_{2}),$

where $\Delta F_{1}$ is the increased fuel during $D_{1}$ due to speed
adaption,

$\displaystyle\Delta F_{1}=\alpha
D_{1}\left(\frac{D_{1}}{D_{1}/v_{0}-u_{i}^{k}}\right)^{2}-\alpha
D_{1}{v_{0}}^{2},$ (4)

where $\alpha$ is the coefficient of increased fuel with speed and travel
distance. $\Delta F_{2}=\eta\phi D_{2}$ arises when $u_{i}^{k}=h_{i}^{k}$,
where $\phi$ denotes the fuel efficiency. When vehicle $k$ is not instructed
to merge with its leading vehicle, i.e., $u_{i}^{k}<h_{i}^{k}$, we have
$\Delta F_{2}=0$. The relative cost for vehicle $k$ is,

$\displaystyle RC_{i}^{k}=\begin{cases}-w_{1}u_{i}^{k}+w_{2}\left(\Delta
F_{1}-\eta\phi D_{2}\right)&u_{i}^{k}=h_{i}^{k},\\\
-w_{1}u_{i}^{k}+w_{2}\Delta F_{1}&u_{i}^{k}<h_{i}^{k}.\end{cases}$ (5)

The optimal policy $\mu^{*}(h)$ for the junction-level coordination under
general arrival processes is a threshold-based policy such that

$\displaystyle\mu^{*}(h)=\begin{cases}h&h\leq\theta,\\\
c&h>\theta,\end{cases}$ (6)

where $\theta$ is the threshold, and $c$ is the time reduction [24] . The
$k$th vehicle would merge with its leading vehicle $k-1$ if the predicted
headway $h_{k}$ is less than the threshold $\theta$; otherwise vehicle $k$
should slightly decelerate in anticipation with constant time reduction $c$ in
anticipation of further subsequent vehicles to merge. Furthermore, $\theta$
and $c$ in Equation (6) can be computed by solving the following system of
equations under Poisson arrivals with $g(x)=\lambda e^{-\lambda x}$,

$\displaystyle\begin{cases}Z-e^{\lambda(1-\gamma)\theta}\biggl{(}\int_{c}^{\theta}e^{-\lambda(1-\gamma)t}\left(G^{{}^{\prime}}(t)-\lambda
G(t)\right)\mathrm{d}t\\\
+\left(Z+G(0)\right)e^{-\lambda(1-\gamma)c}\biggl{)}=0,\\\ G(\theta)+\gamma
Z-Z=0,\\\ G^{{}^{\prime}}(c)-\lambda
G(c)+\lambda(1-\gamma)\left(Z+G(0)\right)=0,\end{cases}$ (7)

where $\lambda$ is the arrival rate, $\gamma$ is the discount factor, and
$G^{{}^{\prime}}(u)$ is the derivative of $G(u)$,

$\displaystyle G(u)=$ $\displaystyle w_{1}u+w_{2}\biggl{(}\alpha
D_{1}{v_{0}}^{2}-\alpha D_{1}\left(\frac{D_{1}}{D_{1}/v_{0}-u}\right)^{2}$
$\displaystyle+\eta\phi D_{2}\biggl{)},$

where $G(u)$ denotes the merging cost when $u<D_{1}/{v_{0}}$. When we consider
multiple junctions in Fig. 3, the Poisson process can be utilized to
approximate vehicle arrivals at vertex $\nu_{i}$ since headways within a
platoon are much smaller than inter-arrival times.

We have evaluated vehicle arrivals for vertex $\nu_{2}$ in Fig. 3.
$f_{m},f_{r1},f_{r2}$ are all assumed to be Poisson arrivals with arrival
rates $\lambda_{m}=\lambda_{r1}=108$ veh/h, $\lambda_{r2}=180$ veh/h, and the
number of vehicle arrivals $N_{m}=N_{r1}=500$ veh, $N_{r2}=1000$ veh. The
headways within a platoon $h_{0}$ are assumed to be $0.5$ s, and the nominal
speed $v_{0}=24$ m/s. The edge between vertex $\nu_{1}$ and vertex $\nu_{2}$
is $31$ km consisting of $D_{2}=30$ km and $D_{1}=1$ km. The threshold-based
policy in Equation (6) is utilized at vertex $\nu_{1}$ for platooning
coordination with $D_{2}=30$ km. Fig. 4 shows the empirical density of inter-
arrival time at vertex $\nu_{2}$. The majority of inter-arrival time is the
headway within a platoon, and the probability density function shows that the
Poisson process can be utilized to approximate vehicle arrivals at vertex
$\nu_{2}$. Since $h_{0}$ is much smaller than $x_{i}^{k}$ and accounts for the
majority of inter-arrival times, Poisson process can be used to approximate
vehicle arrivals at each vertex when $f_{m},f_{r1},f_{r2},\ldots f_{rN}$ all
follow Poisson arrivals, thus Equation (7) can be used to calculate the
threshold-based policy at each vertex.

Figure 4: Empirical density of CAV’s inter-arrival time at vertex $\nu_{2}$.

Furthermore, $\eta\phi D_{2}$ in Equation (3.3) denotes the fuel reduction
over the cruising zone. However, it assumes that $D_{2}$ is constant at a
single-junction, which is not realistic in time-dependent networks. We utilize
the framework of dynamic programming to update the travel time from vertex
$\nu_{i}$ to its destination,

$\displaystyle\Delta
T_{i}^{k}=\chi\left(U_{i}^{k}+T_{i+1}^{k}-T_{i}^{k}\right),$ (8)

where $T_{i}^{k}$ is vehicle $k$’s estimated travel time from vertex $\nu_{i}$
to the destination, $U_{i}^{k}$ is the real travel time from vertex $\nu_{i}$
to $\nu_{i+1}$, and $T_{i+1}^{k}$ is the estimated travel time from vertex
$\nu_{i+1}$ to the destination. When vehicle $k$ enters the coordinating zone
of vertex $\nu_{i+1}$, it returns $U_{i}^{k}$ and $T_{i+1}^{k}$ to update
$T_{i}^{k}$, and $\chi$ is the update rate. We employ this approach to update
travel times in time-dependent networks since $U_{i}^{k}$ is the real travel
time. Additionally, we utilize this approach to estimate the cruising distance
by $\hat{D}_{i}^{k}=\frac{r(\overline{v}_{i}^{k})T_{i}^{k}}{\phi}$, where
$\overline{v}_{i}^{k}=D_{2}/T_{i}^{k}$ is average speed over $D_{2}$. To
estimate the arrival rate $\lambda_{i}^{k}$ when vehicle $k$ enters the
coordinating zone of $\nu_{i}$, we utilize the $M$-step discounted previous
headways, which helps account for flow fluctuation,

$\displaystyle\hat{\lambda}_{i}^{k}=\Big{[}(1-\psi)\sum_{m=0}^{M-1}\psi^{m}x_{i}^{k-m}\Big{]}^{-1},$
(9)

where $\psi$ is the discount factor of inter-arrival times. Therefore, we can
use Equation (7) to determine the coordination policy with estimated
parameters,

$\displaystyle\mu_{i}^{*}(h_{i}^{k},\hat{D}_{i}^{k},\hat{\lambda}_{i}^{k})=\begin{cases}h_{i}^{k}&h_{i}^{k}\leq\theta_{i}^{k},\\\
c_{i}^{k}&h_{i}^{k}>\theta_{i}^{k},\end{cases}$ (10)

where $\theta_{i}^{k}$ and $c_{i}^{k}$ can be computed using $\hat{D}_{i}^{k}$
and $\hat{\lambda}_{i}^{k}$. The proposed algorithm for approximation in the
threshold-based policy is shown in Algorithm 2.

Algorithm 2 Approximation in the threshold-based policy.

1:The cruising distance $D_{2}$ at vertex $\nu_{i}$; The fuel rate function
$r(v)$; The fuel efficiency $\phi$; The reward function $G(u)$; The discount
factor of inter-arrival times $\psi$; Number of discounted steps $M$;

2:Optimal platooning policy $\mu_{i}^{*}$;

3:Vehicle $k$ enters the coordinating zone of vertex $\nu_{i}$

4:$\hat{\lambda}_{i}^{k}\leftarrow\Big{[}(1-\psi)\sum_{m=0}^{M-1}\psi^{m}x_{i}^{k-m}\Big{]}^{-1}$

5:$\hat{D}_{i}^{k}\leftarrow\frac{r(\overline{v}_{i}^{k})T_{i}^{k}}{\phi}$

6:Determine $\theta_{i}^{k}$ and $c_{i}^{k}$ with $\hat{\lambda}_{i}^{k}$ and
$\hat{D}_{i}^{k}$ using Equation (7)

7:if $h_{i}^{k}\geq\theta_{i}^{k}$ then

8: $\mu_{i}^{*}(h_{i}^{k})=c_{i}^{k}$

9:else

10: $\mu_{i}^{*}(h_{i}^{k})=h_{i}^{k}$

11:end if

12:Update the previous vertex $\nu_{i-1}$ with $U_{i-1}^{k}$ and $T_{i}^{k}$
$\Delta
T_{i-1}^{k}\leftarrow\chi\left(U_{i-1}^{k}+T_{i}^{k}-T_{i-1}^{k}\right)$

###  3.4 Numerical results

We consider the platooning coordination over two consecutive junctions in the
Simulation of Urban MObility (SUMO) [25], as shown in Fig. 5. The coordinating
distance $D_{1}$ is set to be $1$ km for both junctions, and the cruising
distances for vertices $1$ and $2$ are both set to be $30$ km. When a CAV
enters the coordinating zone, the controller at the vertex determines whether
the current CAV merges with the CAV ahead based on the predicted headway.
Green vehicles in Fig. 5 denote CAVs in a platoon, red vehicles are CAVs
traveling alone, and yellow points represent detectors collecting vehicle
arrival times. The desired headway for the leading vehicle in a platoon
$\tau_{l}$ is $7.5$ s, and the following CAVs’ movements are determined by the
platoon management function Simpla in SUMO to keep a small headway.

Figure 5: SUMO platform for platooning over two consecutive junctions.

When a CAV enters the coordinating zone, it returns the travel cost on the
edge and the expected travel cost from the current vertex to its destination.
The cost in the simulation consists of fuel consumption and travel time. The
fuel rate $f$ (L/s) is related to the travel speed $v$ (m/s), and can be
derived using the empirical data in SUMO: $f=3.51\times
10^{-7}v^{3}+4.07\times 10^{-4}v$. The fraction of fuel saving compared with
traveling alone $\eta$ can be up to $21\%$ for smaller headways within a
platoon. We follow the setting in [10] and assumes a $10\%$ fuel reduction
rate. The update rate $\chi$ is set to be $1.0$ since we neglect the
normalization effect during the travel time estimation. Other nominal values
are shown in Table 1. We consider traffic flows consisting of CAVs and non-
CAVs. The Greenshield’s model is utilized to simulate the macroscopic speed-
density relationship, $v_{e}=v_{0}\left(1.0-k_{e}/k_{j}\right)$, where $k_{e}$
is the density on the edge, and $k_{j}$ is the jam density. Let
$k_{c}={k_{j}}/{2}$ be the critical density. The speed $v_{e}$ is used to
limit the CAV or platoon speed on the edge. Non-CAVs are used to simulate the
congestion effect, and the penetration rate of CAVs $\zeta$ is set to be
$1/6$.

Table 1: Nominal parameters in the simulation. Parameter | Notation | Value
---|---|---
Fuel efficiency | $\phi$ | $32.2\ L/100km$
Nominal speed | $v_{0}$ | $24\ m/s$
Value of time | $w_{1}$ | $25.8\ \$/hour$
Fuel price | $w_{2}$ | $0.868\ \$/L$
Coordinating distance | $D_{1}$ | $1\ km$
Fraction of fuel saving | $\eta$ | $0.1$
Discount factor in the policy | $\gamma$ | $0.9$
Discount factor of arrival times | $\psi$ | $0.9$
Number of steps | $M$ | $50$
Update rate | $\chi$ | $1.0$

We generate 2000 CAVs to evaluate the coordination performance in the SUMO
platform. We compare the performance between parametric cost approximation
with polynomials and approximation in the threshold-based policy.
Additionally, we consider the case without platooning as the baseline. The
results in Fig. 6 show the ratio of the travel cost to the baseline cost with
the critical density. The smaller the critical density, the more likely the
road will be congested. We use the critical density as the variable instead of
the traffic flow since larger flow will increase the number of simulated
vehicles, thus increasing the computation burden. The results demonstrate that
using approximation in the threshold-based policy yields better performance
than parametric cost approximation with polynomials. Both curves indicate that
the ratio increases as the critical density increases, which shows that
platooning will have more benefits when the highway is congested. CAVs
traveling in platoons will lead to more density reduction, thus reducing
travel time and fuel consumption.

Figure 6: Ratio of the travel cost to the baseline cost with the critical
density.

In Fig. 6, we observe that when the critical density reaches $30$ veh/km/ln
(indicating heavily congested conditions), platooning yields a significant
travel cost reduction of over $50\%$ compared to the scenario without
platooning. Moreover, as the critical density exceeds $70$ veh/km/ln, we can
still achieve a notable reduction in travel cost of nearly $10\%$. It is worth
noting that the sensitivity of the cost ratio diminishes in density intervals
above $60$ veh/km/ln or below $50$ veh/km/ln. This reduced sensitivity arises
because the travel cost and the baseline cost exhibit minimal changes during
periods of heavy congestion or free flow traffic.

##  4 Coordinated platooning and adaptive routing

In this section, we delve into the study of coordination within networks,
encompassing coordinated platooning and adaptive routing at each junction. To
address the complexity of the problem, we decouple the action space by
prioritizing routing decisions based on travel time estimation. Subsequently,
we employ the aforementioned policy approximation to determine speed profiles,
considering parameters such as travel times and cruising distances. The
results in SUMO demonstrate the superior performance of our approach compared
to conventional methods. Additionally, we asses the resilience of our approach
in dynamically changing networks, affirming its ability to maintain efficient
platooning operations.

###  4.1 The approximate dynamic programming approach

Platooning coordination in networks consists of platooning and routing at each
vertex. We need to determine the action $a_{i}^{k}=[u_{i}^{k}\quad
e_{ij}^{k}]$ based on the state $s_{i}^{k}=[h_{i}^{k}\quad d^{k}\quad
d^{k-1}\quad e_{ij}^{k-1}]$ when vehicle $k$ enters the coordinating zone of
vertex $\nu_{i}$. To simplify the structure of the problem, we decouple the
action space and prioritize the routing decision $e_{ij}^{k}$ since most
drivers will not drive any more time than necessary [10]. Our approach
involves estimating travel times within the network using a dynamic
programming framework, allowing for the determination of the optimal path.
Subsequently, the platooning coordination is determined using the
approximation in the threshold-based policy, as described in Section 3. It is
important to note that the estimated travel times can be utilized to calculate
parameters within the threshold-based policy, facilitating efficient
platooning coordination.

Let $T_{i}(d^{k},j)$ denote the time that vertex $\nu_{i}$ estimates it takes
to travel from $\nu_{i}$ to the destination $d^{k}$ for vehicle $k$ by way of
vertex $\nu_{i}$’s adjacent vertex $\nu_{j}$. Similar to the approach for
packet routing in the communication networks [26], the dynamic programming
framework for updating travel times is shown as

$\displaystyle\Delta
T_{i}(d^{k},j)=\chi\left(U_{ij}^{k}+\min_{z\in\mathcal{N}_{j}}T_{j}(d^{k},z)-T_{i}(d^{k},j)\right),$
(11)

where $U_{ij}^{k}$ is the travel time from vertex $\nu_{i}$ to vertex
$\nu_{j}$ for vehicle $k$. $\mathcal{N}_{j}$ denotes adjacent vertices of
vertex $\nu_{j}$. When vehicle $k$ enters the coordinating zone of vertex
$\nu_{j}$, it returns $U_{ij}^{k}$ and vertex $\nu_{j}$’s estimate for the
time remaining in the trip $\min_{z\in\mathcal{N}_{j}}T_{j}(d^{k},z)$, which
can be used to update $T_{i}(d^{k},j)$. The routing decision $e_{ij}^{k}$ is
determined based on the adjacent vertex with minimum $T_{i}(d^{k},j)$. Note
that $T_{i}(d^{k},j)$ is updated in a large table instead of a continuous
function.

When vehicle $k$ and vehicle $k-1$ share a common path, the controller at the
junction determines the coordination process using the approximation in the
threshold-based policy. Fig. 7 shows the platooning formation and split for
vehicles with different destinations. Vehicle $k$ travels from the origin
$o^{k}$ to the destination $d^{k}$, and vehicle $k-1$ travels from the origin
$o^{k-1}$ to the destination $d^{k-1}$. The merging decision is made at vertex
$\nu_{i}$, and the split junction is vertex $\nu_{s}$. Vehicle $k$ and vehicle
$k-1$ share a common path $e_{c}$, which leads to the fuel reduction. The
estimated cruising distance $\hat{D}_{e_{c}}$ can be expressed as

$\displaystyle\hat{D}_{e_{c}}=\frac{1}{\phi}\left(r(\overline{v}_{i})T_{i}^{k}-r(\overline{v}_{s})T_{s}^{k}\right),$
(12)

where $T_{i}^{k}$ is the estimated travel time from vertex $\nu_{i}$ to its
destination $d^{k}$, and $T_{s}^{k}$ is the estimated travel time from vertex
$\nu_{s}$ to $d^{k}$. $\overline{v}_{i}$ denotes the average speed from vertex
$\nu_{i}$ to $d^{k}$, and $\overline{v}_{s}$ is the average speed from vertex
$\nu_{s}$ to $d^{k}$.

Figure 7: The platooning exists when vehicle $k$ and vehicle $k-1$ share a
common path.

$\hat{D}_{e_{c}}$ can be used to replace $D_{2}$ in $\Delta F_{2}=\eta\phi
D_{2}$ since the platooning only occurs on $e_{c}$. Furthermore, the
platooning policy at vertex $\nu_{i}$ can be approximated with the threshold-
based policy,

$\displaystyle
u_{i}^{k}=\begin{cases}h_{i}^{k}&h_{i}^{k}\leq\theta_{i}^{k},\\\
c_{i}^{k}&h_{i}^{k}>\theta_{i}^{k},\end{cases}$ (13)

where $\theta_{i}^{k}$ and $c_{i}^{k}$ can be calculated using Equation (7)
using $\hat{D}_{e_{c}}$ and $\hat{\lambda}_{i}^{k}$. The proposed algorithm
for coordinated platooning and adaptive routing is shown in Algorithm 3. When
vehicle $k$ enters the coordinating zone of vertex $\nu_{i}$, the controller
at vertex $\nu_{i}$ calculates the estimated arrival rate
$\hat{\lambda}_{i}^{k}$. We can use $T_{i}(d^{k},j)$ to determine the selected
edge $e_{ij}^{k}$ and the split vertex $\nu_{s}$. When vehicle $k$ and vehicle
$k-1$ do not share a common path, the time reduction $u_{i}^{k}=c_{i}^{k}$,
i.e., vehicle $k$ should slightly decelerate with $c_{i}^{k}$ to form a
platoon with its following vehicle. Note that $c_{i}^{k}$ is calculated using
the estimated cruising distance $\hat{D}_{i}^{k}$ from vertex $\nu_{i}$ to the
destination. When vehicle $k$ and vehicle $k-1$ share a common path, the
system of equations in Equation (7) can be utilized to calculate
$\theta_{i}^{k}$ and $c_{i}^{k}$ in the threshold-based policy. After
determining the routing and platooning at vertex $\nu_{i}$, $T_{p}(d^{k},i)$
at the previous vertex $\nu_{p}$ is updated using the dynamic programming
framework in Equation (11).

Algorithm 3 The approximate dynamic programming for coordinated platooning and
adaptive routing.

1:Vehicle $k$’s destination $d^{k}$; Vehicle $(k-1)$’s destination $d^{k-1}$;
The fuel rate function $r(v)$; The fuel efficiency $\phi$; The reward function
$G(u)$; The discount factor of arrival times $\psi$; Number of discounted
steps $M$;

2:Optimal edge $e_{ij}^{k}$ and the time reduction $u_{i}^{k}$;

3:Vehicle $k$ enters the coordinating zone of vertex $\nu_{i}$

4:$\hat{\lambda}_{i}^{k}\leftarrow\Big{[}(1-\psi)\sum_{m=0}^{M-1}\psi^{m}x_{i}^{k-m}\Big{]}^{-1}$

5:Determine $e_{ij}^{k}$ and $\nu_{s}$ using $T_{i}(d^{k},j)$

6:if $\nu_{s}=\nu_{i}$ then

7:
$\hat{D}_{i}^{k}\leftarrow\frac{r(\overline{v}_{i}^{k})\hat{T}_{i}^{k}}{\phi}$

8: Determine $\theta_{i}^{k}$ and $c_{i}^{k}$ with $\hat{\lambda}_{i}^{k}$ and
$\hat{D}_{i}^{k}$

9: $u_{i}^{k}=c_{i}^{k}$

10:else

11:
$\hat{D}_{e_{c}}\leftarrow\frac{1}{\phi}\left(r(\overline{v}_{i})T_{i}^{k}-r(\overline{v}_{s})T_{s}^{k}\right)$

12: Determine $\theta_{i}^{k}$ and $c_{i}^{k}$ with $\hat{\lambda}_{i}^{k}$
and $\hat{D}_{e_{c}}$

13: if $h_{i}^{k}\geq\theta_{i}^{k}$ then

14: $u_{i}^{k}=c_{i}^{k}$

15: else

16: $u_{i}^{k}=h_{i}^{k}$

17: end if

18:end if

19:Update $T_{p}(d^{k},i)$ at the previous vertex $\nu_{p}$

20:$\Delta
T_{p}(d^{k},i)\leftarrow\chi\left(U_{pi}^{k}+\min_{z\in\mathcal{N}_{i}}T_{i}(d^{k},z)-T_{p}(d^{k},i)\right)$

###  4.2 Numerical Results

We evaluate our approach in the Nguyen-Dupuis network shown in Fig. 8. To
simulate the microscopic vehicle dynamics, we employ the IDM car-following
model, while the macroscopic Greenshield’s model captures the congestion
effect resulting from the mixed-autonomy traffic. The network comprises 13
vertices and 19 edges, consisting of 2 origins and 2 destinations. The red
points in Fig. 8 represent the detectors strategically placed to collect trip
information, which can be shared through the network with the communication
infrastructure. When a vehicle enters the coordinating zone of a junction, the
controller will determine the appropriate routes and speed profiles. It will
then proceed to update the time table at the previous junction, ensuring
coordinated platooning operations throughout the network.

Figure 8: Platooning coordination in the Nguyen-Dupuis network.

We generate 500 CAVs for each origin-destination (O-D) pair with the Poisson
arrival process, where the arrival rate is set to be $216$ veh/hr. The
penetration rate of CAVs $\zeta$ is set to be $1/10$. To improve the
computation efficiency in SUMO, $D_{1}$ is set to be $500$ m and the distance
of all edges is $2000$ m. Other parameters are the same as those in Table 1.
We compare our approach with other methods under different critical densities:

1\. Baseline: each CAV travels alone its shortest path and no platoon is
formed at the junction. CAVs will keep the original speed during the
coordinating zone.

2\. Policy A: we refer to the coordinated platooning framework in [10]. Each
vehicle is assumed to travel alone its shortest path. A platoon is formed only
when the merging benefits outweigh the costs of traveling alone. The
platooning decision is made using the policy in [27], where only acceleration
is allowed in the coordinating zone.

3\. Policy B: our proposed approximate dynamic programming framework for
coordinated platooning and adaptive routing.

Fig. 9 shows the relationship between the average cost and the critical
density, where the average cost is obtained by dividing the total cost by the
number of CAVs. The results show that the average cost will increase when the
road is prone to congestion with smaller critical densities. Both Policy A and
policy B can reduce travel cost compared with the baseline. Furthermore, our
proposed policy B yields better performance than policy A, especially when the
critical density is less than $60$ veh/km/ln. If the highway is congested, the
dynamic programming framework can be used for adaptive routing with travel
time estimation instead of traveling alone the shortest distance. The
threshold-based policy in Equation (13) yields better performance than the
policy in [27] since deceleration is considered in the merging process.
Compared with policy A, our proposed method can reduce the travel cost by up
to $40\%$ when the critical density approximates $35$ veh/km/ln. Policy A and
policy B achieve almost the same performance when the critical density
approximates $20$ veh/km/ln since the road is heavily congested even though
our method can adaptively choose the optimal path. When the critical density
is greater than $70$ veh/lm/ln, policy A and policy B can also have similar
performance since the highway is under free flow traffic.

Figure 9: Performance comparison among different policies.

We also evaluate our approach under different O-D demands, which are
represented by traffic flows between origins and destinations. The results in
Fig. 10 indicate that the average cost increases with the average flow since
more vehicles in the network will decrease the travel speed, thus increasing
the travel time and fuel consumption. Note that the curve slope diminishes
when the flow is less than $200$ veh/hr, resulting from the reduced density
with platoons.

Figure 10: Average cost with different origin-destination demands.

###  4.3 Resiliency in dynamically changing networks

We evaluate the resilience of our approach in dynamically changing networks by
disconnecting edges during simulation. The platooning simulation is
implemented in the SUMO platform with our proposed approach. The total
simulation time is $4000$ s. We manually disconnect edge $18$ during
$1000-2000$ s and resume the traffic after that. Fig. 11(a) displays the
average speed for all edges at $700$ s before the disconnection. Light green
color indicates a high average speed and low edge density, as observed in
edges $5$ and $7$. In contrast, dark blue color represents greater density, as
seen in edges $1$ and $18$. The optimal path between origin $1$ and
destination $2$ includes the edges $2-18-11$. Fig. 11(b) depicts the average
speed for all edges at $1600$ s. After the disconnection, more vehicles choose
to travel on edges $5$, $8$ and $14$, indicating that our dynamic programming
approach for travel time estimation can react to such changes and is able to
continue routing traffic efficiently.

(a) $T=700$ s.

(b) $T=1600$ s.

Figure 11: The average speed for all edges before and after the disconnection
of edge $18$.

In Fig. 12, we specifically focus on edges $1$, $2$, $17$ and $18$ to
illustrate the average speed variations throughout the simulation. Edge $18$
is disconnected during $1000-2000$ s, resulting in an average speed of $24$
m/s during this period. Note that edges $1$ and $2$ serve as alternate routes
for vehicles to reach their destinations, and their average speed exhibit
opposite directions. During the disconnection period, both edge $2$ and $17$
show similar patterns but with a delay of $120$ s, as edge $17$ serves as the
only downstream option for vehicles on edge $2$ after the disconnection. This
observation demonstrates the adaptability and effectiveness of our approach in
reacting to disruptions within the network.

Figure 12: The average speed for edges $1$, $2$, $17$, and $18$.

To demonstrate the real-time platooning strategy under varying traffic flows,
we select two junctions within the network. Fig. 13 shows threshold and C
values with estimated traffic flows at vertices $8$ and $5$. The plots in Fig.
13(a) and Fig. 13(c) indicate that the threshold curve and the flow curve
exhibit opposite directions of change. Furthermore, Fig. 13(b) reveals that
the C value curve and the flow curve at vertex $8$ also show opposite trends.
Conversely, Fig. 13(d) demonstrates that the C value curve and the flow curve
at vertex $5$ exhibit similar trends, resulting from the longer cruising
distance at that vertex. Additionally, C values at vertex $5$ are much smaller
than those at vertex $8$, resulting in a larger gap between the threshold and
the C value at vertex $5$. Consequently, vertex $5$ allows for more platooning
due to benefits associated with longer cruising distances.

(a) Threshold value at vertex $8$.

(b) C value at vertex $8$.

(c) Threshold value at vertex $5$.

(d) C value at vertex $5$.

Figure 13: Threshold and C values with estimated flows for vertices $8$ and
$5$.

##  5 Concluding Remarks

In this paper, we have investigated platooning in time-dependent networks
using an approximate dynamic programming framework. By formulating a Markov
decision process at each junction, our study focuses on minimizing travel time
and fuel consumption. We have analyzed platooning coordination without routing
and proposed two innovative approaches based on approximate dynamic
programming to address interdependencies among controllers’ decisions. The
results over a cascade of junctions have demonstrated the superiority of the
approximation in the threshold-based policy. Furthermore, we have extended our
study to encompass coordinated platooning and adaptive routing in networks. We
decouple the action space by prioritizing routing decisions with travel time
estimation. Subsequently, we employ the aforementioned approximation in the
threshold-based policy considering relevant parameters such as travel times to
determine speed profiles. Through simulations in the Nguyen-Dupuis network,
our approach has shown better performance compared with conventional methods.
Additionally, we asses the resilience of our approach in dynamically changing
networks by simulating edge disconnections, revealing its ability to maintain
efficient operations even under such conditions.

This work can be extended in several directions. First, incorporating a non-
linear function to approximate cost functions would enable the inclusion of
additional traffic information, such as density and flow. Second, the
interaction between CAVs and human-driven vehicles need to be analyzed and
addressed. Third, the utilization of traffic flow models, like the cell
transmission model (CTM), within the dynamic programming framework holds
potential for improving computation efficiency in time-dependent networks.

## Acknowledgments

This work was supported in part by C2SMART University Transportation Center,
NYU Tandon School of Engineering, NSFC Project 62103260, SJTU UM Joint
Institute, J. Wu & J. Sun Endowment Fund, and Fundamental Research Funds for
the Central Universities.

## References

  * [1] J. Axelsson, “Safety in vehicle platooning: A systematic literature review,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 18, no. 5, pp. 1033–1045, 2016.
  * [2] S. Tsugawa, S. Jeschke, and S. E. Shladover, “A review of truck platooning projects for energy savings,” _IEEE Transactions on Intelligent Vehicles_ , vol. 1, no. 1, pp. 68–77, 2016.
  * [3] L. Kong, M. K. Khan, F. Wu, G. Chen, and P. Zeng, “Millimeter-wave wireless communications for iot-cloud supported autonomous vehicles: Overview, design, and challenges,” _IEEE Communications Magazine_ , vol. 55, no. 1, pp. 62–68, 2017.
  * [4] Y. Zhou and S. Ahn, “Robust local and string stability for a decentralized car following control strategy for connected automated vehicles,” _Transportation Research Part B: Methodological_ , vol. 125, pp. 175–196, 2019.
  * [5] V. Turri, B. Besselink, and K. H. Johansson, “Cooperative look-ahead control for fuel-efficient and safe heavy-duty vehicle platooning,” _IEEE Transactions on Control Systems Technology_ , vol. 25, no. 1, pp. 12–28, 2016\.
  * [6] A. Talebpour and H. S. Mahmassani, “Influence of connected and autonomous vehicles on traffic flow stability and throughput,” _Transportation Research Part C: Emerging Technologies_ , vol. 71, pp. 143–163, 2016.
  * [7] J. Rios-Torres and A. A. Malikopoulos, “A survey on the coordination of connected and automated vehicles at intersections and merging at highway on-ramps,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 18, no. 5, pp. 1066–1077, 2016.
  * [8] A. K. Bhoopalam, N. Agatz, and R. Zuidwijk, “Planning of truck platoons: A literature review and directions for future research,” _Transportation research part B: methodological_ , vol. 107, pp. 212–228, 2018.
  * [9] J. Larson, C. Kammer, K.-Y. Liang, and K. H. Johansson, “Coordinated route optimization for heavy-duty vehicle platoons,” in _16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013)_. IEEE, 2013, pp. 1196–1202.
  * [10] J. Larson, K.-Y. Liang, and K. H. Johansson, “A distributed framework for coordinated heavy-duty vehicle platooning.” _IEEE Trans. Intelligent Transportation Systems_ , vol. 16, no. 1, pp. 419–429, 2015.
  * [11] E. Larsson, G. Sennton, and J. Larson, “The vehicle platooning problem: Computational complexity and heuristics,” _Transportation Research Part C: Emerging Technologies_ , vol. 60, pp. 258–277, 2015.
  * [12] M. Abdolmaleki, M. Shahabi, Y. Yin, and N. Masoud, “Itinerary planning for cooperative truck platooning,” _Available at SSRN 3481598_ , 2019.
  * [13] A. Nourmohammadzadeh and S. Hartmann, “The fuel-efficient platooning of heavy duty vehicles by mathematical programming and genetic algorithm,” in _Theory and Practice of Natural Computing: 5th International Conference, TPNC 2016, Sendai, Japan, December 12-13, 2016, Proceedings 5_. Springer, 2016, pp. 46–57.
  * [14] S. van de Hoef, K. H. Johansson, and D. V. Dimarogonas, “Fuel-efficient en route formation of truck platoons,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 1, pp. 102–112, 2017.
  * [15] F. Luo and J. Larson, “A repeated route-then-schedule approach to coordinated vehicle platooning: Algorithms, valid inequalities and computation,” _Operations Research_ , vol. 70, no. 4, pp. 2477–2495, 2022.
  * [16] A. Balador, A. Bazzi, U. Hernandez-Jayo, I. de la Iglesia, and H. Ahmadvand, “A survey on vehicular communication for cooperative truck platooning application,” _Vehicular Communications_ , p. 100460, 2022.
  * [17] W. Zhang, E. Jenelius, and X. Ma, “Freight transport platoon coordination and departure time scheduling under travel time uncertainty,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 98, pp. 1–23, 2017.
  * [18] X. Sun and Y. Yin, “Decentralized game-theoretical approaches for behaviorally-stable and efficient vehicle platooning,” _Transportation Research Part B: Methodological_ , vol. 153, pp. 45–69, 2021.
  * [19] M. Xu, X. Yan, and Y. Yin, “Truck routing and platooning optimization considering drivers’ mandatory breaks,” _Transportation Research Part C: Emerging Technologies_ , vol. 143, p. 103809, 2022.
  * [20] M. Segata, B. Bloessl, S. Joerer, F. Dressler, and R. L. Cigno, “Supporting platooning maneuvers through ivc: An initial protocol analysis for the join maneuver,” in _2014 11th Annual conference on wireless on-demand network systems and services (WONS)_. IEEE, 2014, pp. 130–137.
  * [21] M. Treiber and A. Kesting, “The intelligent driver model with stochasticity-new insights into traffic flow oscillations,” _Transportation research procedia_ , vol. 23, pp. 174–187, 2017.
  * [22] K.-Y. Liang, J. Mårtensson, and K. H. Johansson, “Heavy-duty vehicle platoon formation for fuel efficiency,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 4, pp. 1051–1061, 2015.
  * [23] E. Ostertagová, “Modelling using polynomial regression,” _Procedia Engineering_ , vol. 48, pp. 500–506, 2012.
  * [24] X. Xiong, J. Sha, and L. Jin, “Optimizing coordinated vehicle platooning: An analytical approach based on stochastic dynamic programming,” _Transportation Research Part B: Methodological_ , vol. 150, pp. 482–502, 2021.
  * [25] P. A. Lopez, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, and E. Wießner, “Microscopic traffic simulation using sumo,” in _The 21st IEEE International Conference on Intelligent Transportation Systems_. IEEE, 2018. [Online]. Available: https://elib.dlr.de/124092/
  * [26] J. A. Boyan and M. L. Littman, “Packet routing in dynamically changing networks: A reinforcement learning approach,” in _Advances in neural information processing systems_ , 1994, pp. 671–678.
  * [27] X. Xiong, E. Xiao, and L. Jin, “Analysis of a stochastic model for coordinated platooning of heavy-duty vehicles,” in _2019 IEEE Conference on Decision and Control_ , 2019.