# Hub-Based Platoon Formation: Optimal Release Policies and Approximate
Solutions

Alexander Johansson, Ehsan Nekouei, Xiaotong Sun,
Karl Henrik Johansson, and Jonas Mårtensson The work by A. Johansson, K. H.
Johansson and J. Mårtensson was partially supported by Horizon 2020 through
the project ENSEMBLE, the Strategic Vehicle Research and Innovation Programme,
the Knut and Alice Wallenberg Foundation by a Wallenberg Scholar Grant, and
the Swedish Research Council through the Distinguished Professor Grant
2017-01078. The work by E. Nekouei is supported by the start-up grant 7200658
from City University of Hong Kong.A. Johansson, K. H. Johansson and J.
Mårtensson are with the Integrated Transport Research Lab and Division of
Decision and Control, School of Electrical Engineering and Computer Science,
KTH Royal Institute of Technology, Stockholm, Sweden., SE-100 44 Stockholm,
Sweden. Emails: {alexjoha, kallej<EMAIL_ADDRESS>X. Sun is with the Thrust
of Intelligent Transportation, the Hong Kong University of Science and
Technology (Guangzhou), China., and the Department of Civil and Environmental
Engineering, the Hong Kong University of Science and Technology, Hong Kong
SAR, China. Email<EMAIL_ADDRESS>E. Nekouei is with the Department of
Electrical Engineering, City University of Hong Kong, Hong Kong. Email:
<EMAIL_ADDRESS>Manuscript submitted November 09, 2023

###### Abstract

This paper studies the optimal hub-based platoon formation at hubs along a
highway under decentralized, distributed, and centralized policies. Hubs are
locations along highways where trucks can wait for other trucks to form
platoons. A coordinator at each hub decides the departure time of trucks, and
the released trucks from the hub will form platoons. The problem is cast as an
optimization problem where the objective is to maximize the platooning reward.
We first show that the optimal release policy in the decentralized case, where
the hubs do not exchange information, is to release all trucks at the hub when
the number of trucks exceeds a threshold computed by dynamic programming. We
develop efficient approximate release policies for the dependent arrival case
using this result. To study the value of information exchange among hubs on
platoon formation, we next study the distributed and centralized platoon
formation policies which require information exchange among hubs. To this end,
we develop receding horizon solutions for the distributed and centralized
platoon formation at hubs using the dynamic programming technique. Finally, we
perform a simulation study over three hubs in northern Sweden. The profits of
the decentralized policies are shown to be approximately $3.5\%$ lower than
the distributed policy and $8\%$ lower than the centralized release policy.
This observation suggests that decentralized policies are prominent solutions
for hub-based platooning as they do not require information exchange among
hubs and can achieve a similar performance compared with distributed and
centralized policies.

###### Index Terms:

Platoon coordination, optimal control, transport planning, cyber-physical
systems, simulation.

##  I Introduction

###  I-A Motivation

In the truck platooning technology, a set of trucks drive with small inter-
vehicular distances. Typically, a human driver maneuvers the lead truck in a
platoon, while automated driving systems maneuver the follower trucks. The
truck platooning technology reduces the operational cost of road
transportation by lightening drivers’ workload. The fuel consumption level of
the follower trucks in a platoon reduces due to the small inter-vehicular
distances between trucks. Thus, the truck platooning technology results in
significant environmental benefits. For instance, energy savings of
approximately $10\%$ for follower trucks have been reported in the literature
based on experimental data [1, 2, 3, 4, 5]. Other benefits of truck platooning
include increased road capacity and safety and reduced travel time [6, 7, 8].
All these potential benefits motivate the investigations of different
platooning architectures and business models, _e.g._ , see, [9, 10, 11].

###  I-B Related work

(a) Hub-corridor with $H$ hubs

(b) Section of a hub-corridor including hubs $h-1$ and $h$

Figure 1:  (a) A hub-corridor with $H$ hubs in a transportation network, and
(b) the section of a hub-corridor including hubs $h-1$ and $h$ where
coordinators make platoon release decisions

Platoon coordination is a central part of the truck platooning technology.
Here, platoon coordination refers to the decision-making of which trucks
should form a platoon depending on their travel time schedules and their
geographical locations. Trucks can merge into platoons on the road by
adjusting their speeds. For example see [12, 13, 14, 15]. One drawback of on-
road platoon formation is their complexity level, as they require trucks to
speed up or slow down to merge into platoons on the roads. Such maneuvers
might be challenging to perform depending on the surrounding traffic
conditions. Another drawback of on-road platoon formation is that the
surrounding traffic may be disturbed by the platoon formation or may disturb
the platoon formation. An alternative platoon formation approach is hub-based
platoon formation. Hubs are locations along highways where trucks can stop and
wait for others to form platoons, _e.g.,_ freight terminals, gas stations,
parking places, tolling stations, and harbors. Under this approach, a platoon
coordinator decides on the departure time of trucks from the hubs; the trucks
which leave a hub simultaneously form a platoon. Platoon formation at a single
hub when the coordinator knows trucks’ arrival schedules to the hub was
considered in [16, 17, 18]. In [19, 20], the authors studied the agent-based
platoon formation at multiple hubs in a transportation network, where trucks
individually decide their departure times from hubs. In the agent-based
approaches, the trucks are required to share their arrival schedules at hubs
with each other. In [21], the authors studied platoon formation at multiple
hubs when the decision-making of which platoons should form was distributed on
coordinators at the hubs. In the above-mentioned work, the trucks are required
to share their arrival schedules with the coordinators at the hubs.

Transportation firms or individual truckers may need to keep their arrival
times private for privacy or competitive reasons. For example, the arrival
times may be sensitive information for a transportation firm or a trucker to
share, as a competitor may use this information to take the firm’s customers
by offering earlier deliveries. Thus, the arrival schedules may not always be
available to the platoon coordinator. Platoon formation at a single hub when
the trucks’ arrivals are unknown to the hub coordinator in advance was studied
in [22, 23], where the truck arrival process was modeled by a sequence of
independent and identically distributed random variables. This paper also
considers a platoon formation problem with unknown arrivals but for multiple
connected hubs instead of a single hub, as in [22, 23]. Our paper advances the
state-of-the-art by developing efficient decentralized platoon formation
policies, where the coordinator at each hub takes into account the downstream
hubs’ policies when computing its platoon release policy. Thus, the platoon
formation problem in this paper becomes a multi-agent decentralized control
problem. We finally refer the reader to [24, 25] for extensive reviews on
platoon coordination strategies.

###  I-C Contributions

In this paper, we study the platoon formation in a set of hubs, as shown in
Fig. 1a. In our set-up, each hub is equipped with a platoon coordinator, as
shown in Fig. 1b, which decides the departure time of trucks from the hubs.
The trucks that leave a hub at the same time form a platoon. We first develop
the optimal release policies in the decentralized case as shown in Fig. 2a,
where each coordinator only has access to the history of observed arrivals at
its hub, the coordinators do not share any information with each other, and
the arrival schedules of trucks are not known _a priori_. We next develop
coordination strategies in the distributed and centralized cases. In the
distributed case, each coordinator has access to the release decisions of its
preceding hub, whereas in the centralized case, the coordinators share their
release decisions with each other and the arrival schedules of trucks are
known by the coordinators.

(a) Decentralized coordination

(b) Distributed coordination

(c) Centralized coordination

Figure 2: Coordination under different information structures

The main contributions in this paper are as follows:

  * •

We investigate the structure of the optimal decentralized release policy at a
hub when its truck arrivals, _i.e._ , the number of trucks arriving at the
hub, are independent over time. Here, we show that a thresholding release
policy is optimal. That is, it is optimal for the coordinator to release all
the trucks located at the hub when the number of trucks is more than a
threshold which is computed by dynamic programming (DP). We use this result to
develop approximate thresholding decentralized release policies in cases where
truck arrivals are not independent over time by approximating the truck
arrivals as independent.

  * •

We study the structure of the optimal decentralized release policy at a hub
when the truck arrivals to its preceding hub are independent over time and the
preceding hub follows an optimal release policy. We show that the optimal
decentralized release policy, in this case, is in the form of a threshold
policy which depends on a variable capturing the state of the preceding hub
and can be computed using DP. This result is used to develop approximate
thresholding decentralized release policies in cases where truck arrivals at
the preceding hub are not independent over time by approximating the truck
arrivals at the preceding hub as independent.

  * •

We propose solutions for the distributed and centralized cases, which are
receding horizon solutions computed by DP.

  * •

We perform a simulation study for hub-based platoon formation along a highway
in Sweden, where the decentralized release policies are compared with the
distributed and centralized release policies. The simulation study shows that
the performance gap between the decentralized release policies and the
distributed and centralized release policies is less than $8\%$. This
observation indicates that the decentralized policies are potential solutions
for hub-based platooning since they do not require communication between hubs
and achieve a similar performance compared with distributed and centralized
policies.

###  I-D Outline

The outline of this paper is as follows. In Section II, the system model of
the hub-corridor is formulated, including the arrival process and the platoon
release problem at each hub. In Section III, the decentralized platoon release
problem at a hub is studied under an independent-arrival assumption. In
Section IV, we also study the decentralized platoon release problem at a hub,
but under the assumption that the preceding hub has independent arrivals and
follows the developed release policy in Section III. In Section V, release
policies for distributed and centralized cases are developed. In Section VI,
the proposed release policies are evaluated in a simulation study over a hub-
corridor along a Swedish highway. Finally, the paper is concluded in Section
VII.

##  II System model

We consider a set of hubs in a transportation network, as shown in Fig. 1a,
where trucks can wait for other trucks and form platoons. Examples of hubs
include drivers resting areas, gas stations, and harbors. In our set-up, each
hub has a platoon coordinator that decides whether the available trucks at the
hub will depart as a platoon or wait for more trucks to join. We refer to the
set of hubs located along a highway as a hub corridor, which is represented by
the thick line in Fig. 1a. The grey lines in Fig. 1a represent roads used by
trucks to join or leave the hub-corridor. The hubs are enumerated as $1$ to
$H$.

Consider the section of the hub-corridor that includes hubs $h-1$ and $h$, as
shown in Fig. 1b. The coordinator at hub $h$ decides how many trucks to
release from the hub at each time step. The released trucks depart from the
hub in the form of a platoon. Let $u_{t}^{h}\in\mathbb{Z}_{\geq 0}$ denote the
number of trucks released by the coordinator at hub $h$ at time step $t$. The
state of a hub is defined as the number of trucks located at the hub. We use
$n^{h}_{t}\in\mathbb{Z}_{\geq 0}$ to denote the state of hub $h$ at time step
$t$. The state of each hub changes dynamically based on the truck arrivals and
the release decisions, as indicated in Fig. 1b. The state of hub $h$ has the
following dynamics

$\displaystyle n^{h}_{t+1}$
$\displaystyle=n^{h}_{t}-u^{h}_{t}+x^{h}_{t+1}+\theta^{h}_{t+1},$ (1)

where $\theta^{h}_{t}\in~{}\mathbb{Z}_{\geq 0}$ is the number of trucks that
were released as a platoon at hub $h-1$ and arrive at hub $h$ at time step
$t$, and $x^{h}_{t}\in\mathbb{Z}_{\geq 0}$ is the number of trucks that join
the hub-corridor via hub $h$ at time step $t$. The state variable $n^{h}_{t}$
is a realization of the random variable denoted $N^{h}_{t}$.

######  Remark.

Note that the trucks that arrive at the hub $h$ at time step $t$ can be
divided into two groups. The first group is the trucks released as a platoon
at hub $h-1$ and arrive at hub $h$. We denote the number of trucks in this
group by $\theta^{h}_{t}$. The second group of trucks is those that enter the
hub-corridor via hub $h$. The number of trucks in this group is denoted by
$x^{h}_{t}$. For example, in Fig. 1a, the trucks labeled with $A$ and $B$ join
the hub-corridor via the second hub, and the trucks labeled with $C$ and $D$
which arrive at the second hub were released by the first hub as a platoon. In
practice, the coordinator at hub $h$ can distinguish between these two groups
of trucks by requiring the second group of trucks to send an acknowledgment
message to the hub coordinator when they join the corridor. Thus, if the
coordinator at hub $h$ does not receive a message from a truck, it knows that
the truck was released from hub $h-1$.

We assume that the truck arrivals are unknown to the coordinators _a priori_.
This is realistic if carriers or trucks keep their routes and schedules
private or when the travel times are uncertain. To capture the uncertainty in
the number of trucks arriving at hubs, the arrival variables $x^{h}_{t}$ and
$\theta^{h}_{t}$ are assumed to be realizations of random variables denoted
$X^{h}_{t}$ and $\Theta^{h}_{t}$, respectively. Throughout the paper, we
assume that the random variables $X^{h}_{0},X^{h}_{1},...$ are independent as
these trucks have not been participating in a platoon formation process at a
preceding hub, but the independent arrival assumption will in general not hold
for the truck arrivals at hub $h$ that have been released at hub $h-1$. The
dependency between the hubs $h-1$ and $h$ captures that a truck that is
released at the hub $h-1$ may exit the highway before reaching the hub $h$. We
use $l^{h}$ to denote the likelihood of any truck exiting the highway between
the hubs. Moreover, recall that the state variable $n_{t}^{h}$ is a
realization of the random variable $N_{t}^{h}$, and the release decision
$u_{t}^{h}$ is a mapping from $n_{t}^{h}$. Thus, the release decision
$u_{t}^{h}$ can also be viewed as a random variable denoted by $U_{t}^{h}$.

The platoon release problem in the hub-corridor is defined as

$\displaystyle\underset{\begin{subarray}{c}\\{\mu_{0}^{h},\dots,\mu_{T}^{h}\\}_{h}\end{subarray}}{\text{max}}$
$\displaystyle\text{E}\Big{[}\sum_{h=1}^{H}\sum_{t=0}^{T}R^{h}\big{(}N_{t}^{h},U_{t}^{h}\big{)}\Big{]},$
(2)

where $T$ is the time horizon, and $R^{h}(n_{t}^{h},u_{t}^{h})$ denotes the
reward of the coordinator of hub $h$ for releasing $u_{t}^{h}$ trucks when its
state is $n_{t}^{h}$. This reward can include the total cost-saving due to a
platoon of length $u_{t}^{h}$ as well as the waiting cost of
$n_{t}^{h}-u_{t}^{h}$ trucks at the hub. The release decision $u_{t}^{h}$ is
computed using the release policy $\mu_{t}^{h}$ based on the available
information to the coordinator at hub $h$, at time step $t$.

In this paper, we assume that the reward function $R^{h}(n_{t}^{h},u_{t}^{h})$
is convex in $u_{t}^{h}$ and $n_{t}^{h}$. An important example of the reward
function is the following convex piecewise-linear form:

$R^{h}(n_{t}^{h},u_{t}^{h})=\max\Big{(}0,b^{h}(u_{t}^{h}-1)\Big{)}-c(n_{t}^{h}-u_{t}^{h}),$
(3)

where the first term is the platooning profit for releasing $u_{t}^{h}$ trucks
that form a platoon with $u_{t}^{h}-1$ follower trucks and $b^{h}$ is the
profit per follower truck. The second term is the cost for having
$n_{t}^{h}-u_{t}^{h}$ trucks waiting at the hub, and $c$ is the waiting cost
per truck.

This paper focuses on decentralized solutions to the platoon release problem
in (2), where the release decisions at each hub only depend on its local state
and information. Computing the optimal decentralized release policies in (2)
becomes prohibitively difficult as the number of hubs increases. The
difficulty in computing an optimal decentralized solution to the problem (2)
arises because of the nested information structure of the hubs; each hub has
to use its history of observed arrivals to estimate the history of all other
hubs’ observed arrivals and history of release decisions, and note, the
variations of possible histories of observed arrivals and release decisions
are numerous even for a few hubs. We refer the reader to [26, 27] for works on
decentralized optimal control under nested information structures. To solve
this problem, in this paper, we decompose the optimization problem in (2) into
$H$ sub-problems, one for each hub. In the rest of the paper, we will explore
different decentralized solutions to the platoon release problem based on our
decomposition approach.

######  Remark.

During off-peak hours when trucks are unaffected by congestion, the travel
times have low variability, and assuming that travel times are deterministic
and known a priori is justified. However, travel times may be uncertain during
peak hours, and the travel times between hubs can then be modeled as
stochastic. Our set-up can be used to study platoon formation under both
deterministic and stochastic travel-time scenarios.

######  Remark.

The reward function in the convex piecewise-linear form in (3) is accurate if
the incremental platooning profit is equal for each follower truck in a
platoon and deterministic and constant over the day. Moreover, the cost of
waiting at the hub is linear and the same for all trucks. These assumptions
may not hold due, for example, to the influence of factors such as traffic
conditions and heterogeneous truck properties. However, our reward function in
(3) can be applied to a case with heterogeneous trucks where trucks have
different platooning benefits. One way is to use the average platooning
benefit of the trucks in our problem formulation. The reward function can also
be extended to capture the impact of traffic by letting the platooning benefit
be a time-varying (deterministic) signal where the benefit is low during peak
hours and low during off-peak hours.

##  III Decentralized release policy:
single-hub approach

In this section, we propose a solution for the decentralized platoon release
problem in (2) by decomposing it into $H$ decoupled sub-problems, where each
hub maximizes its own reward from platooning and irrespective of the decision-
making behavior of other hubs. The decentralized platoon release problem at
hub $h$ is

$\displaystyle\underset{\mu_{0}^{h},\dots,\mu_{T}^{h}}{\text{max}}$
$\displaystyle\text{E}\Big{[}\sum_{t=0}^{T}R^{h}\big{(}N_{t}^{h},U_{t}^{h}\big{)}\Big{]},$
(4)

where the objective is to maximize the reward of hub $h$ from platooning. In
the next subsection, we study the structure of the optimal release policy at a
hub, under the single-hub approach, when its truck arrivals are independent
over time. Later, we will use this result to derive an approximate solution
for the single-hub approach when truck arrivals are dependent over time.

###  III-A Independent arrival case

In this sub-section, we study the structure of the optimal release policy at
hub $h$ under the single-hub approach and its arrivals are independent over
time, that is, the random variables
$X_{0}^{h},\dots,X_{T}^{h},\Theta^{h}_{0},\dots,\Theta^{h}_{T}$ are assumed to
be independent. Fig. 3 illustrates the single-hub approach. To study the
structure of the optimal release policy at hub $h$, we first derive the
Bellman optimality equation associated with the optimal release policy of hub
$h$. Using the Bellman’s principle of optimality, the optimal value function
associated with the state $n_{t}^{h}$ can be expressed as

$\displaystyle
V^{h}_{t}(n_{t}^{h})=\underset{u_{t}^{h}\in\mathcal{U}^{h}_{t}(n_{t}^{h})}{\text{max}}R^{h}(n_{t}^{h},u_{t}^{h})+$
$\displaystyle\hskip
99.58464pt\text{E}[V^{h}_{t+1}(n_{t}^{h}-u_{t}^{h}+X_{t+1}^{h}+\Theta^{h}_{t+1})],$

where the decision variable $u_{t}^{h}$ can take values in the set
$\mathcal{U}^{h}_{t}(n^{h}_{t})=\\{0,\dots,n^{h}_{t}\\}$ as the maximum number
of trucks to release is the number of trucks at the hub. The value function at
the terminal time step is
$V^{h}_{T}(n_{T}^{h})~{}=~{}R^{h}(n_{T}^{h},n_{T}^{h})$, which is the reward
for releasing the remaining trucks. The optimal value function can be computed
using standard dynamic programming (DP), and the optimal decision can then be
computed using the optimal value function. We omit to present the standard DP
algorithm but refer the reader to [28] for a detailed presentation of the
standard DP algorithm.

Figure 3: Single-hub model

The following theorem gives fundamental results of the structure of the
optimal release policy under the single-hub approach when the truck arrivals
are independent. The structural results significantly reduce the complexity of
computing the optimal policy.

######  Theorem 1.

Consider the decentralized platoon release problem in (4) when the truck
arrivals are independent. The following holds:

  * •

The value function $V_{t}^{h}(n_{t}^{h})$ is convex in $n_{t}^{h}$.

  * •

The optimal release decision $u_{t}^{h,*}$ takes values in the set
$\\{0,n_{t}^{h}\\}$.

Furthermore, if the reward function has the piecewise-linear form in (3), then
there exists a threshold $\rho^{h}_{t}\in\mathbb{Z}_{\geq 0}$ such that

$u_{t}^{h,*}=\begin{cases}n_{t}^{h}&\text{if }n_{t}^{h}\geq\rho^{h}_{t}\\\
0&\text{if }n_{t}^{h}<\rho^{h}_{t}.\\\ \end{cases}$

The threshold $\rho^{h}_{t}$ can be computed using dynamic programming.

###### Proof.

See Appendix A. ∎

According to Theorem 1, the optimal decision of the coordinator of the hub $h$
is to either to release all its truck or release no trucks. This property is
due to the convexity of the reward function, and significantly reduces the
search space of optimal release policies, thus leading to a light
computational load when solving the Bellman equation by DP. Moreover, a
release policy with the structure in Theorem 1 can be used as a low complexity
approximate release policy when the truck arrivals are dependent. In such
cases, the dependent arrivals can be approximated with an independent arrival
process. Then, an approximate release policy can be computed using the
structure of Theorem 1 and the approximated arrival process.

###  III-B Dependent arrival case

The independent arrival assumption in the previous sub-section is valid if hub
$h$ is the only hub in the hub-corridor or if all trucks join the corridor
using hub $h$. The arrivals at hub $h$ will be dependent if, for example, the
arriving trucks have participated in a platoon formation process at hub $h-1$.
In order to use the solution in Theorem 1 for the dependent arrival case, we
approximate the joint distribution of the truck arrival process with the joint
distribution of an independent arrival process. That is, we approximate the
random variables $\Theta^{h}_{0},\dots,\Theta^{h}_{T}$ as independent. An
approximate release policy can be computed, as in the previous subsection,
using the approximate arrival process with independent arrivals.

Algorithm 1 shows the procedure for computing the single-hub approximate
release policy, where for each hub $h$, one at a time, we first compute the
empirical distribution of its arrivals based on arrival data during several
episodes (each episode spanning over the time steps $0$ to $T$). To this end,
we divide the time steps $0$ to $T$ into $N$ intervals denoted
$\mathcal{T}_{0},\dots,\mathcal{T}_{N}$. Then, we approximate the distribution
of $\Theta^{h}_{t}$, for $t\in\mathcal{T}_{j}$, using the following equation

$\Pr(\Theta^{h}_{t}=\theta)=\frac{\sum\limits_{s\in\mathcal{T}_{j}}\sum\limits_{e\in\mathcal{E}}\boldsymbol{1}_{\theta^{h}_{s,e}=\theta}}{\sum\limits_{s\in\mathcal{T}_{j}}\sum\limits_{e\in\mathcal{E}}1},$
(5)

where the set of episodes is denoted $\mathcal{E}=\\{1,\dots,E\\}$ and $E$ is
the number of episodes, $\theta^{h}_{s,e}$ is the number of trucks in episode
$e$ that have traveled from hub $h-1$ and arrive at hub $h$ at time step $s$,
and $\boldsymbol{1}_{\theta^{h}_{s,e}=\theta}$ is the indicator function such
that $\boldsymbol{1}_{\theta^{h}_{s,e}=\theta}=0$ if
$\theta^{h}_{s,e}\neq\theta$ and $\boldsymbol{1}_{\theta^{h}_{s,e}=\theta}=1$
if $\theta^{h}_{s,e}=\theta$. We then use the empirical distributions of
$\Theta^{h}_{0}$, …, $\Theta^{h}_{T}$ to compute an approximate release policy
for hub $h$. Note that the empirical estimator can be applied to either
simulated or real arrival data and recall that the distributions of the random
variables $X_{0}^{h},...,X_{T}^{h}$ are independent as these trucks have not
participated in a platoon formation process at a preceding hub.

input : Distribution of $\\{X_{t}^{h}\\}_{t,h}$

output : Approximate release policies $\\{\mu_{t}^{h}\\}_{t,h}$

Generate $\\{x^{1}_{t,e}\\}_{t,e}$ using the distribution of
$\\{X^{1}_{t}\\}_{t}$

Compute optimal release policy $\\{\mu_{t}^{1}\\}_{t}$ using DP and Theorem 1

Compute the releases $\\{u_{t,e}^{1}\\}_{t,e}$ using $\\{\mu_{t}^{1}\\}_{t}$
and $\\{x^{1}_{t,e}\\}_{t,e}$ for each episode $e$

for  _$h=2,\dots,H$ _ do

Generate $\\{x^{h}_{t,e}\\}_{t,e}$ using the distribution of
$\\{X^{h}_{t}\\}_{t}$

Generate arrivals $\\{\theta^{h}_{t,e}\\}_{t,e}$ using
$\\{u_{t,e}^{h-1}\\}_{t,e}$ for each episode $e$

Approximate the distribution of $\\{\Theta^{h}_{t}\\}_{t}$ using (5)

Compute approximate release policy $\\{\mu_{t}^{h}\\}_{t}$ using DP and
Theorem 1

Compute the releases $\\{u_{t,e}^{h}\\}_{t,e}$ using $\\{\mu_{t}^{h}\\}_{t}$,
$\\{\theta^{h}_{t,e}\\}_{t,e}$ and $\\{x^{h}_{t,e}\\}_{t,e}$ for each episode
$e$

end for

Algorithm 1 Computation of the single-hub approximate release policies

##  IV Decentralized release policy:
two-hub approach

In this section, we propose a two-hub approach for the decentralized platoon
release problem in (2) where the release problem is decomposed into $H$
decoupled sub-problems. Under the two-hub approach, each hub finds its optimal
release policy based on the release policy of its preceding hub. In the
following subsections, we first study the structure of the optimal release
policy of a hub when its preceding hub has independent arrivals and the
preceding hub follows the release policy in Theorem 1. We will then derive an
approximate release policy for a hub when the arrivals to its preceding hub
are not independent in time.

###  IV-A Independent arrival case

In this sub-section, we study the structure of the optimal release policy at
hub $h$ when the arrivals to hub $h-1$ are independent in time and hub $h-1$
follows the optimal release policy in Theorem 1. The two-hub model is
illustrated in Fig. 4. The random variables
$\Theta^{h-1}_{0},\dots,\Theta^{h-1}_{T},X_{0}^{h-1},\dots,X_{T}^{h-1}$ are
the independent arrivals at hub $h-1$. The arrivals of trucks at hub $h$ from
hub $h-1$, _i.e.,_ denoted by the random variables
$\Theta^{h}_{0},\dots,\Theta^{h}_{T}$, are dependent in time since hub $h-1$
follows the optimal release policy in Theorem 1. The random variables
$X_{0}^{h},\dots,X_{T}^{h}$ are independent as the trucks that join the hub-
corridor using hub $h$ have not participated in a platoon formation process at
a preceding hub.

Figure 4: Two-hub model

To study the structure of the optimal release policy at hub $h$, we derive the
Bellman optimality equation. Using the Bellman’s principle of optimality, the
optimal value function can be expressed as

$\displaystyle V^{h}_{t}(n_{t}^{h},\pi^{h}_{t})=$ (6) $\displaystyle\hskip
14.22636pt\underset{u_{t}^{h}\in\mathcal{U}^{h}_{t}(n_{t}^{h})}{\text{max}}\
R^{h}(n_{t}^{h},u_{t}^{h})+$ $\displaystyle\hskip
34.14322pt\text{E}[V^{h}_{t+1}(n_{t}^{h}-u_{t}^{h}+X_{t+1}^{h}+\Theta^{h}_{t+1},\pi^{h}_{t+1}],$

where $\pi^{h}_{t}~{}=~{}\\{\pi^{h}_{t,j}\\}_{j\in\mathbb{Z}_{\geq 0}}$, and
$\pi^{h}_{t,i}$ is defined as

$\pi^{h}_{t,i}=\Pr(D_{t-k^{h}}^{h-1}=i|\Theta^{h}_{0}=~{}\theta^{h}_{0},\dots,\Theta^{h}_{t}=~{}\theta^{h}_{t}),$
(7)

where $D_{t-k^{h}}^{h-1}=N_{t-k^{h}}^{h-1}-U_{t-k^{h}}^{h-1}$ is the number of
trucks at hub $h-1$ at time step $t-k^{h}$ after releasing, and $k^{h}$ is the
travel time between the hubs $h-1$ and $h$. Thus, $\pi^{h}_{t,i}$ is the
likelihood that $i$ trucks are at hub $h-1$ after releasing at time step
$t-k^{h}$ given the observed arrivals at hub $h$. The variable
$\pi^{h}_{t+1}=\\{\pi^{h}_{t+1,j}\\}_{j\in\mathbb{Z}_{\geq 0}}$ can be
computed recursively as

$\pi^{h}_{t+1,j}=\frac{\sum_{i\geq
0}\pi^{h}_{t,i}p^{h}_{t,ij}r^{h}_{t,ij}(\theta^{h}_{t+1})}{\sum_{i,j\geq
0}\pi^{h}_{t,i}p^{h}_{t,ij}r^{h}_{t,ij}(\theta^{h}_{t+1})},$ (8)

where $p^{h}_{t,ij}=\Pr(D_{t-k^{h}+1}^{h-1}=j|D_{t-k^{h}}^{h-1}=i)$ and
$r^{h}_{t,ij}(\theta^{h}_{t+1})~{}=~{}\Pr(\Theta^{h}_{t+1}=\theta^{h}_{t+1}|D_{t-k^{h}+1}^{h-1}=j,D_{t-k^{h}}^{h-1}=i)$.
The probabilities $p^{h}_{t,ij}$ and $r^{h}_{t,ij}(\theta^{h}_{t+1})$ are
determined by the truck arrival distributions, the likelihood of leaving the
corridor between the hubs, and the release policy of hub $h-1$, and their
precise forms are given in Appendix B. The optimal value function at the
terminal time step is
$V^{h}_{T}(n_{T}^{h},\pi^{h}_{T})~{}=~{}R^{h}(n_{T}^{h},n_{T}^{h})$.

The Bellman optimality equation in the form of (6) is difficult to solve by DP
since $\pi^{h}_{t}$ is a continuous variable. In the rest of this subsection,
we will derive the structure of the optimal value function and the optimal
release policy that allows us to easily solve the Bellman optimality equation
by DP. To this end, let $w_{t}^{h}\in\mathbb{Z}_{\geq 0}$ denote the number of
time steps since a non-zero truck arrival at hub $h$ from hub $h-1$, which can
be computed recursively as

$w_{t+1}^{h}=\begin{cases}w_{t}^{h}+1&\text{if }\theta^{h}_{t+1}=0\\\
0&\text{if }\theta^{h}_{t+1}\neq 0.\end{cases}$

######  Theorem 2.

Consider the decentralized platoon release problem at hub $h$ when the truck
arrivals at hub $h-1$ are independent over time and its coordinator follows
the release policy in Theorem 1. Then, the following statements hold:

  * •

The optimal value function only depends on $n_{t}^{h}$ and $w_{t}^{h}$.

  * •

The value function $V_{t}^{h}(n_{t}^{h},w_{t}^{h})$ is convex in $n_{t}^{h}$.

  * •

The optimal release decision $u_{t}^{h,*}$ takes values in the set
$\\{0,n_{t}^{h}\\}$.

Furthermore, if the reward function has the piecewise-linear form in (3), then
there exists a threshold $\rho^{h}_{t}(w_{t}^{h})$, such that

$u_{t}^{h,*}=\begin{cases}n_{t}^{h}&\text{if
}n_{t}^{h}\geq\rho^{h}_{t}(w_{t})\\\ 0&\text{if
}n_{t}^{h}<\rho^{h}_{t}(w_{t}).\\\ \end{cases}$

The threshold $\rho^{h}_{t}(w_{t}^{h})$ can be computed using dynamic
programming.

###### Proof.

See Appendix C. ∎

Theorem 2 implies that the optimal release policy of hub $h$ in the two-hub
approach can be computed by solving the Bellman optimality equation using
standard DP using $w_{t}^{h}$ instead of $\pi^{h}_{t}$. Note that
$\pi^{h}_{t}$ is a continuous random variable which significantly complicates
the computation of the optimal policy using DP. However, based on Theorem 2,
the optimal release policy can be computed by using $w_{t}^{h}$ which is a
discrete variable. This significantly facilitates the computation of the
optimal policy. Theorem 2 also indicates that similar structural results
continue to hold for the optimal release policy as those in Theorem 1 when the
arrivals at hub $h-1$ are independent and the coordinator at hub $h-1$ follows
a release policy with the structure in Theorem 1. This result is useful as it
limits the candidate optimal release policies when seeking an optimal release
policy by DP.

###  IV-B Dependent arrival case

The two-hub solution in the previous subsection is optimal under the
assumptions that the arrivals at the preceding hub $h-1$ are independent and
its coordinator follows the release policy in Theorem 1. The independent-
arrival assumption at hub $h-1$ is valid if hub $h-1$ is the first hub in the
corridor. In this subsection, we propose an approximate two-hub solution for
hub $h$ by approximating the joint distribution of the arrival process at hub
$h-1$ using independent arrivals. That is, we approximate the random variables
$\Theta^{h-1}_{0},\dots,\Theta^{h-1}_{T}$ as independent. The approximate
distribution allows us to use Theorem 2 to obtain an approximate release
solution for the dependent case. The approximate two-hub release policy at hub
$h$ is computed using the approximate arrival distribution at hub $h-1$ and
DP, as explained in the previous subsection.

Algorithm 2 shows the procedure for computing the two-hub approximate release
policy, where for each hub $h$, we first compute the empirical distribution of
the arrivals at hub $h-1$ using equation (5). The empirical distribution of
the arrivals is then used as an approximation of the arrival distribution at
hub $h-1$. The empirical distribution of
$\Theta^{h-1}_{0},\dots,\Theta^{h-1}_{T}$ is used to compute an approximate
release policy for hub $h$.

input : Distribution of $\\{X_{t}^{h}\\}_{t,h}$

output : Approximate release policies $\\{\mu^{h}_{t}\\}_{t,h}$

Generate $\\{x^{1}_{t,e}\\}_{t,e}$ using the distribution of
$\\{X^{1}_{t}\\}_{t}$

Compute optimal release policy $\\{\mu^{1}_{t}\\}_{t}$ using DP and Theorem 1

Generate releases $\\{u_{t,e}^{1}\\}_{t,e}$ using $\\{\mu^{1}_{t}\\}_{t}$ and
$\\{x^{1}_{t,e}\\}_{t,e}$ for each episode $e$

Generate $\\{x^{2}_{t,e}\\}_{t,e}$ using the distribution of
$\\{X^{2}_{t}\\}_{t}$

Compute optimal release policy $\\{\mu^{2}_{t}\\}_{t}$ using DP and Theorem 2

for  _$h=3,\dots,H$ _ do

Generate $\\{x^{h}_{t,e}\\}_{t,e}$ using the distribution of
$\\{X^{h}_{t}\\}_{t}$

Generate arrivals $\\{\theta^{h-1}_{t,e}\\}_{t,e}$ using
$\\{u_{t,e}^{h-2}\\}_{t,e}$

Approximate distribution of $\\{\Theta^{h-1}_{t}\\}_{t}$ using (5)

Compute approximate release policy $\\{\mu^{h}_{t}\\}_{t}$ using DP and
Theorem 2

Generate releases $\\{u_{t,e}^{h-1}\\}_{t,e}$ using $\\{\mu^{h-1}_{t}\\}_{t}$,
$\\{\theta^{h-1}_{t,e}\\}_{t,e}$ and $\\{x^{h-1}_{t,e}\\}_{t,e}$ for each
episode $e$

end for

Algorithm 2 Computation of the two-hub approximate release policies

##  V Distributed and centralized release policies

In this section, we propose distributed and centralized release policies,
which will be used as benchmarks in Section VI to evaluate the performance of
the proposed decentralized release policies and investigate the value of
communication among hubs. Under the distributed release policy, each
coordinator informs its proceeding coordinator in the hub-corridor about its
release decisions. Under the centralized release policy, coordinators share
their release decisions and have _a priori_ knowledge of their arrivals.

###  V-A Distributed case

In the distributed case, the coordinator at each hub receives the release
decisions of its preceding hub and computes its release decisions using a
receding horizon solution with $L$ time steps as the horizon. The distributed
release policy requires communication links between hubs which will require
installation and maintenance, whereas the decentralized release policies do
not require communication among hubs. Let
$\mathcal{M}^{h}_{t}=\\{u^{h-1}_{t-k^{h}+1},\dots,u^{h-1}_{t-k^{h}+L}\\}$
denote the release decisions of hub $h-1$ which are known by hub $h$ at time
step $t$. Then, the Bellman optimality equation for hub $h$ can be expressed
as

$\displaystyle
V^{h}_{s}(n_{s}^{h},\mathcal{M}^{h}_{t})=\underset{u_{s}^{h}\in\mathcal{U}^{h}_{s}(n_{s}^{h})}{\text{max}}\
R(n_{s}^{h},u_{s}^{h})+$ $\displaystyle\hskip
56.9055pt\text{E}[V^{h}_{s+1}(n_{s}^{h}-u_{s}^{h}+X_{s+1}^{h}+\Theta^{h}_{s+1},\mathcal{M}^{h}_{t})|\mathcal{M}^{h}_{t}],$

for $s=t,\dots,t+L-1$, and the value function at the terminal time step of the
horizon is $V^{h}_{t+L}(n_{t+L}^{h})=R^{h}(n_{t+L}^{h},n_{t+M}^{h})$. The
Bellman optimality equation is solved recursively by DP. Then, the computed
release decision for time step $t$ is implemented, while the set of releases
at the preceding hub and the computed release decisions for time steps
$t+1,\dots,t+L$ are updated at the next step.

###  V-B Centralized case

In the centralized case, the coordinator at each hub computes its release
decisions using a receding horizon solution where the arrivals within the
horizon of $L$ time steps are known. The arrivals are known as the
coordinators sharing their release decisions in the centralized case, and the
trucks inform the coordinators about their arrivals beforehand. The
centralized release policy requires knowledge of the schedule and the route of
trucks and communication between hubs. However, the decentralized release
policies do not rely on any information exchange between hubs. The set of
information available to the coordinator of hub $h$ at time step $t$ is
denoted as
$\mathcal{N}^{h}_{t}=\\{x^{h}_{t+1},\dots,x^{h}_{t+L},\theta^{h}_{t+1},\dots,\theta^{h}_{t+L}\\}$.
The Bellman optimality equation used by the coordinator at hub $h$ to compute
the release decision at time step $t$ is expressed as

$\displaystyle
V^{h}_{s}(n_{s}^{h},\mathcal{N}^{h}_{t})=\underset{u_{s}^{h}\in\mathcal{U}^{h}_{s}(n_{s}^{h})}{\text{max}}\
R(n_{s}^{h},u_{s}^{h})+$ $\displaystyle\hskip
99.58464ptV^{h}_{s+1}(n_{s}^{h}-u_{s}^{h}+x_{s+1}^{h}+\theta^{h}_{s+1},\mathcal{N}^{h}_{t}),$

for $s=t,\dots,t+L-1$, and the value function at the terminal time step of the
horizon is $V^{h}_{t+L}(n_{t+L}^{h})=R^{h}(n_{t+L}^{h},n_{t+L}^{h})$. The
Bellman optimality equation is solved recursively by DP, and similar to the
distributed case, the release decision for time step $t$ is implemented, while
the set of information and the release decisions for time steps
$t+1,\dots,t+L$ are updated at the next time step.

##  VI Simulation study

In this section, we perform a simulation study over a hub-corridor with three
hubs in northern Sweden. We first explain the simulation setup, including the
hub locations and arrival distributions. Then, we study the performance of the
developed coordination solutions under deterministic travel times, which is
accurate if the impact from surrounding traffic on the highway is ignored. We
also study the impact of uncertainty in travel times between the hubs on the
performance of the coordination policies.

###  VI-A Setup

Fig. 5 shows a hub corridor between Luleå and Sundsvall in northern Sweden.
The hubs are located near the cities Luleå, Skellefteå, Umeå, and the hub-
corridor ends near the city of Sundsvall, Sweden. The length of the road
segments connecting the hubs are $131$ km, $136$ km, and $263$ km, and we
assume that trucks travel with a speed of $80$ km/h under free-flow
conditions. To obtain realistic arrival distributions for the trucks that join
the corridor, we use the real data shown in Fig. 6 which were collected during
two working days in 2018–2019 by the Swedish Transport Administration [29].
This figure shows the average hourly truck count on roads that connect to each
hub location in Fig. 5 (excluding the roads connecting Luleå, Skellefteå,
Umeå, and Sundsvall).

Figure 5: Three-hub-corridor along a highway in Sweden. Figure 6: The average
hourly truck count on roads connecting to Luleå, Skellefteå, and Umeå
(excluding roads connecting Luleå, Skellefteå, Umeå, and Sundsvall). The data
was collected by the Swedish Transport Administration [29].

In our simulations, we assume that the number of trucks joining the corridor
using hub $h$ at time $t$, _i.e._ , $X_{t}^{h}$ is Poisson distributed with a
time-varying mean. More precisely,
$X^{h}_{t}\sim\text{Poisson}(\lambda^{h}_{t})$, for $t=~{}0,\dots,T$, where
the mean of the process, _i.e._ , $\lambda^{h}_{t}$, is set according to the
data in Fig. 5. The time step length is set to one minute in the simulations.
We will study the performance of the proposed decentralized policies under
both known travel-times and uncertain travel-times.

We use the reward function in (3) for our simulations, where the platooning
benefit ($b^{h}$) is $10\%$ fuel consumption reduction for the follower
trucks. The cost of fuel is assumed to be $5$ SEK/km in our simulations. The
waiting cost per truck in our simulations is equal the hourly driver cost,
which is around 200 SEK/h [30], or approximately $c=3.33$ SEK per time step.
The following results are generated by $50$ Monte Carlo simulations.

###  VI-B Deterministic travel times scenario

In this subsection, we study the performance of different platoon release
policies in the deterministic travel time scenario where the travel times
between hubs are known _a priori_ and set to the free-flow travel times. Fig.
7 shows the (hourly) average reward in a period of 24 hours under different
release policies. According to this figure, the decentralized two-hub solution
generally results in a higher average hourly reward than the decentralized
single-hub solution. This is because the former policy takes the arrival
process and release behavior of its preceding hub into account. Fig. 7 also
shows that the distributed and centralized release policies outperform the
decentralized release policies by a small margin. This indicates that the
performance loss due to the decentralized structure of the one-hub and two-hub
solutions is relatively small.

(a) First hub

(b) Second hub

(c) Third hub

Figure 7: Profits as a function of time. In the simulations, the likelihood of
any released truck to leave the corridor before the next hub is set to
$l^{h}=0.5$.

Fig. 8 shows the (hourly) average number of released trucks and its standard
deviation for each hub. The number of released trucks is referred to as
release size in this figure. According to this figure, more trucks are
released on average under the decentralized two-hub policy than the
decentralized single-hub policy. The standard deviation of the release sizes
is also higher for the decentralized two-hub policy. The increased variability
in release sizes is due to that the threshold for the decentralized two-hub
policy depends on the variable $w_{t}^{h}$, _i.e.,_ the number of time steps
since a non-zero arrival was observed, as shown in Theorem 2. Fig. 8 also
shows that the distributed and centralized policies generally have larger
release sizes and higher standard deviations than the decentralized policies.
This implies that the centralized and distributed policies are more efficient
in forming platoons than the decentralized policies.

(a) First hub

(b) Second hub

(c) Third hub

Figure 8: Platoon length and its standard deviation as a function of time. In
the simulations, the likelihood of any released truck to leave the corridor
before the next hub is set to $l^{h}=0.5$.

Fig. 9 shows the average daily reward generated at the hubs as a function of
the variable $l^{h}$, _i.e._ , the likelihood that a truck leaves the hub-
corridor before reaching the next hub in the hub-corridor. Based on this
figure, the daily reward decreases as the variable $l^{h}$ increases. This is
because the trucks will visit fewer hubs on average as $l^{h}$ becomes large,
reducing the number of trucks participating in platoons. Moreover, Fig. 9
shows that the difference between the decentralized and distributed policies
is small when $l^{h}$ becomes large. This figure also shows that the
centralized release policy achieves higher rewards even when $l^{h}$ is high.
The largest difference between the decentralized and centralized policies is
$8\%$ and occurs at $l^{h}=0.8$.

###  VI-C Uncertain travel times scenario

In this subsection, we will study the impact of travel-time uncertainty on the
performance of different release policies. To this end, we model the travel
times between the hubs as truncated Gaussian distributed random variables with
the free-flow travel times between hubs as the mean of the distribution. The
standard deviation of the travel times is varied to study the impact of travel
time uncertainty. Fig. 10 shows the average daily reward of the hubs as a
function of the standard deviation of the travel-times. According to Fig. 10,
the reward slightly decreases with increased uncertainty in travel times. The
performance loss of decentralized policies is less than $2\%$ when the
standard deviation of the travel-time is $10$ minutes. Also, the performance
loss of the distributed and centralized policies is less than $5\%$ when the
standard deviation of the travel time is $10$ minutes.

Figure 9: Total profit as a function of the likelihood of any released truck
to leave the corridor before the next hub. Figure 10: Total profit as a
function of the standard deviation of the travel times. In the simulations,
the likelihood of any released truck to leave the corridor before the next hub
is set to $l^{h}=0.5$.

##  VII Conclusion and future work

This paper studied the platoon release problem in a hub-corridor, in which
release times at hubs are coordinated to form platoons. We focused on the
decentralized case without communication between coordinators, where the
release decisions are based on statistical information of truck arrivals.
Under this information structure, we proposed two different decentralized
release policies. The first decentralized release policy was shown to be
optimal when its arrivals from the preceding hub are independent. The second
decentralized release policy is shown to be optimal when the preceding hub has
independent arrivals and follows an optimal release policy. In order to
evaluate the value of communication among hubs, we also proposed distributed
and centralized release policies.

A simulation study of a hub-corridor with three hubs in Sweden was performed
to compare the proposed release policies and evaluate the value of sharing
information. The simulation study showed that the decentralized release
policies achieved profits close to that of the distributed and centralized.
More precisely, the profits of the decentralized policy was less than $3.5\%$
and $8\%$ lower than of the distributed and centralized, respectively. This
suggests that a viable platooning system can be obtained without sharing truck
routes and schedules across the system, which may otherwise be one of the
bottlenecks for platoon cooperation among different transportation companies.
Moreover, the simulations showed that the likelihood of leaving the system
between hubs heavily affects the platoon profits of the proposed release
policies. For instance, when the likelihood of leaving the corridor between
hubs is high, the benefit of exploiting trucks from the preceding neighboring
hub is limited.

For future research, we aim to study platoon release problems in networks with
general typologies, expanding the line graph (hub-corridor) considered in this
paper. A possibility is to include platoon routing in the decision of the hub
coordinators. Another promising future research direction is to use
reinforcement learning to seek approximate solutions when the truck arrival
process is unknown. Furthermore, another avenue for future work is to
investigate if similar properties shown for the platoon release problem in
this paper hold when using a more realistic form of the reward function that,
for example, captures the influence of traffic and heterogeneous truck
properties. Final possible future extensions are to use a traffic simulator,
for example, SUMO, to model the travel time uncertainty in the simulation and
to include hub and road capacity constraints in the problem formulation.

##  Appendix A Proof of Theorem 1

Before providing the proof, we define

$G^{h}_{t}(n_{t}^{h},u_{t}^{h})=R^{h}(n_{t}^{h},u_{t}^{h})+\text{E}[V^{h}_{t+1}(n_{t}^{h}-u_{t}^{h}+X_{t+1}^{h}+\Theta^{h}_{t+1})],$

and note that

$V^{h}_{t}(n^{h}_{t})=\underset{u_{t}^{h}\in\mathcal{U}_{t}^{h}(n_{t}^{h})}{\text{max}}G^{h}_{t}(n_{t}^{h},u_{t}^{h}).$
(9)

First, assume that $V^{h}_{t+1}(n^{h}_{t+1})$ is convex in $n^{h}_{t+1}$.
Then, since convexity is preserved under affine maps and positively weighted
summations, we have that
$\text{E}[V^{h}_{t+1}(n^{h}_{t}-u^{h}_{t}+X_{t+1}^{h}+\Theta^{h}_{t+1})]$ is
convex in both $n^{h}_{t}$ and $u^{h}_{t}$. Therefore,
$G^{h}_{t}(n^{h}_{t},u^{h}_{t})$ is also convex in both $n^{h}_{t}$ and
$u^{h}_{t}$. Consider then the relaxed version of the maximization problem in
(9) with the decision space $[0,n_{t}^{h}]$ instead of
$\mathcal{U}_{t}^{h}(n_{t}^{h})=\\{0,\dots,n_{t}^{h}\\}$. The relaxed
maximization problem is of a convex function over a compact and convex set.
Therefore, the maximizer is at one of the boundary points of the relaxed
decision space $[0,n_{t}^{h}]$, see [31] for proof. Since the boundary points
of $[0,n_{t}^{h}]$ are elements in $\mathcal{U}_{t}^{h}(n_{t}^{h})$, the
maximizer of the maximization problem in (9) is also one of these two boundary
points. That is, the optimal release decision $u_{t}^{h,*}$ takes values in in
the set $\\{0,n^{h}_{t}\\}$. By this fact we have that

$\displaystyle
V^{h}_{t}(n^{h}_{t})=\underset{}{\text{max}}\\{G^{h}_{t}(n^{h}_{t},0),G_{t}(n^{h}_{t},n^{h}_{t})\\},$

which is convex in $n^{h}_{t}$ since $G^{h}_{t}(n^{h}_{t},0)$ and
$G^{h}_{t}(n^{h}_{t},n^{h}_{t})$ are convex functions in $n^{h}_{t}$ and the
maximizer of two convex functions is convex. Finally,
$V^{h}_{T}(n^{h}_{T})=R^{h}(n^{h}_{T},n^{h}_{T})$ is convex by assumption.
Thus, $V^{h}_{t}(n^{h}_{t})$ is convex for all $t\leq T$ by induction.
Conclusions in first part of Theorem 1 follow.

In the second part of Theorem 1, we assume the piecewise-linear form of
$R^{h}(n_{t}^{h},u_{t}^{h})$ in (3). Then we have for $n^{h}_{t}\geq 1$ that

$G^{h}_{t}(n^{h}_{t},n^{h}_{t})=n^{h}_{t}b^{h}+F_{t},$

where $F_{t}=-b^{h}+\text{E}[V^{h}_{t+1}(X_{t+1}^{h}+\Theta^{h}_{t+1})]$ and

$G^{h}_{t}(n^{h}_{t},0)=-cn^{h}_{t}+\text{E}[V^{h}_{t+1}(n^{h}_{t}+X_{t+1}^{h}+\Theta^{h}_{t+1})].$

Since the optimal release decision $u_{t}^{h,*}$ takes values in the set
$\\{0,n^{h}_{t}\\}$, we have that $u_{t}^{h,*}=n^{h}_{t}$ if and only if

$\displaystyle\Delta(n^{h}_{t})$
$\displaystyle=G^{h}_{t}(n^{h}_{t},n^{h}_{t})-G^{h}_{t}(n^{h}_{t},0)$ (10)
$\displaystyle=n^{h}_{t}b^{h}+F+cn^{h}_{t}-\text{E}[V^{h}_{t+1}(n^{h}_{t}+X_{t+1}^{h}+\Theta^{h}_{t+1})]\geq
0.$

To show that there exists a threshold $\rho^{h}_{t}$ such that
$u_{t}^{h,*}=n^{h}_{t}$ if and only if $n^{h}_{t}\geq\rho^{h}_{t}$, we show
that the optimal release decision is $u_{t}^{h,*}=n^{h}_{t}\geq 1$ (when the
number of trucks at hub $h$ is $n^{h}_{t}$) implies the optimal release
decision $u_{t}^{h,*}=n^{h}_{t}+1$ (when the number of trucks at hub $h$ is
$n^{h}_{t}+1$). To show this, it is sufficient to show that
$\Delta(n^{h}_{t})$ is non-decreasing in $n^{h}_{t}$. First, assume that there
exists a threshold $\rho^{h}_{t+1}$ such that $u_{t+1}^{h,*}=n^{h}_{t+1}$ if
and only if $n^{h}_{t+1}\geq\rho^{h}_{t+1}$. This implies that
$V^{h}_{t+1}(n^{h}_{t+1}+1)-V^{h}_{t+1}(n^{h}_{t+1})=b^{h}$ if
$n^{h}_{t+1}\geq\rho^{h}_{t+1}$. Since convex functions have increasing
differences it follows that

$V^{h}_{t+1}(n^{h}_{t+1}+1)-V^{h}_{t+1}(n^{h}_{t+1})\leq b^{h},$ (11)

for all $n^{h}_{t+1}$. Thus, equations (10) and (11) imply

$\displaystyle\Delta(n^{h}_{t}+1)-\Delta(n^{h}_{t})=$ $\displaystyle
b^{h}+c-\text{E}[V^{h}_{t+1}(n^{h}_{t}+1+X_{t+1}^{h}+\Theta^{h}_{t+1})]-$
$\displaystyle+\text{E}[V^{h}_{t+1}(n^{h}_{t}+X_{t+1}^{h}+\Theta^{h}_{t+1})]\geq
b^{h}+c-b^{h}>0.$

We regard the threshold $\rho^{h}_{T}=1$ at the terminal time step and the
conclusion in the second part of Theorem 1 follows by induction.

##  Appendix B Transition and observation probabilities

The optimal release policy at hub $h-1$ is in the form given in Theorem 1.
Consequently, there exist a set
$\mathcal{D}^{h-1}_{t-k^{h}}\subseteq\mathbb{Z}_{\geq 0}$ such that the
optimal release decision $u_{t-k^{h}}^{h-1,*}=n_{t-k^{h}}^{h-1}$ if
$n_{t-k^{h}}^{h-1}\in\mathcal{D}^{h-1}_{t-k^{h}}$ and otherwise
$u_{t-k^{h}}^{h-1,*}=0$. Then, for $i\notin\mathcal{D}^{h-1}_{t-k^{h}}$ and
$j\notin\mathcal{D}^{h-1}_{t-k^{h}+1}$, we have

$\displaystyle
p^{h}_{t,ij}\\!=\\!\\!\begin{cases}\Pr(X^{h-1}_{t-k^{h}+1}+i=j)&\text{if
}j\geq i\land j\neq 0\\\
\Pr(X^{h-1}_{t-k^{h}+1}+i\in\mathcal{D}^{h-1}_{t-k^{h}+1})&\text{if }i\neq
0\land j=0\\\ \Pr(X^{h-1}_{t-k^{h}+1}\in\mathcal{D}^{h-1}_{t-k^{h}+1}\lor
X^{h-1}_{t-k^{h}+1}\\!=\\!0)&\text{if }i=0\land j=0\\\
0&\text{else,}\end{cases}$

where the first case is when the number of trucks at hub $h-1$ after the
release decision is non-decreasing due to not releasing, the second case is
when the number of trucks at hub $h-1$ after the release decision becomes zero
due to releasing, and the third case is when the number of trucks at hub $h-1$
after the release decision remains zero due to releasing or no arrivals.
Furthermore, for $\theta\neq 0$ and $j=0$, we have

$\displaystyle r^{h}_{t,i0}(\theta)$ $\displaystyle=$
$\displaystyle\sum\limits_{n\in\mathcal{D}^{h-1}_{t-k^{h}+1}}\\!\\!\\!\\!\\!\\!\\!\\!\Pr(X^{h-1}_{t-k^{h}+1}+i=n)\Pr(\Theta^{h}_{t+1}=\theta|U^{h-1}_{t-k^{h}+1}=n)/p^{h}_{t,i0},$

where $\Pr(\Theta^{h}_{t+1}=\theta|U^{h-1}_{t-k^{h}+1}=n)$ is determined by
$l^{h}$, and for $\theta\neq 0$ and $j\neq 0$, we have
$r^{h}_{t,ij}(\theta)=0$.

##  Appendix C Proof of Theorem 2

The optimal release decision at hub $h-1$, that is $u_{t}^{h-1,*}$, takes
values in the set $\\{0,n_{t}^{h-1}\\}$, as shown in Theorem 1. Thus,
$r^{h}_{t,ij}(\theta^{h}_{t+1})=0$ for $j>0$ and $\theta^{h}_{t+1}\neq 0$.
This implies $\pi^{h}_{t+1,0}=1$ and $\pi^{h}_{t+1,j}=0$ for $j>0$ when
$\theta^{h}_{t+1}\neq 0$. That is, $\pi^{h}_{t}$ is reset to
$\pi^{h}_{t}=(1,0,\dots,0)$ when $\theta^{h}_{t}\neq 0$ and the number of time
steps since a non-zero arrival was observed (or more precisely $w^{h}_{t}$) is
the only variable affecting $\pi^{h}_{t}$. We can therefore write the bellman
equation as

$\displaystyle V_{t}(n_{t}^{h},w_{t}^{h})=$
$\displaystyle\underset{u_{t}^{h}\in\mathcal{U}^{h}_{t}(n_{t}^{h})}{\text{max}}R^{h}(n_{t}^{h},u_{t}^{h})+$
$\displaystyle\text{E}[V^{h}_{t+1}(n^{h}_{t}-u_{t}^{h}+X_{t+1}^{h}+\Theta^{h}_{t+1},w^{h}_{t+1})].$

The proof of the rest of Theorem 2 is similar to the proof of Theorem 1 and we
therefore omit most details but provide the step which is least trivial. If
$V^{h}_{t+1}(n_{n+1}^{h},w^{h}_{t+1})$ is convex in $n_{n+1}^{h}$, then
$\text{E}[V^{h}_{t+1}(n^{h}_{t}-u_{t}^{h}+X_{t+1}^{h}+\Theta^{h}_{t+1},w^{h}_{t+1})]$
is convex in $n^{h}_{t}$ and $u_{t}^{h}$, and by following similar steps as in
Appendix A, this implies that $V^{h}_{t}(n_{t}^{h},w^{h}_{t})$ is convex in
$n_{t}^{h}$. Then, $V^{h}_{t}(n_{t}^{h},w^{h}_{t})$ is convex for all $t\leq
T$ by induction since
$V^{h}_{T}(n_{T}^{h},w^{h}_{T})=R^{h}(n_{t}^{h},n_{t}^{h})$ is convex in
$n_{t}^{h}$. The remaining part of the proof follows similar steps as the
proof of Theorem 1 but including the state $w^{h}_{t}$ in the notations.

## References

  * [1] F. Browand, J. McArthur, and C. Radovich, “Fuel saving achieved in the field test of two tandem trucks,” Technical report, University of Sourthern California, 2004.
  * [2] A. Davila, E. del Pozo, E. Aramburu, and A. Freixas, “Environmental benefits of vehicle platooning,” in Symposium on International Automotive Technology 2013, jan 2013.
  * [3] A. Alam, B. Besselink, V. Turri, J. Mårtensson, and K. H. Johansson, “Heavy-duty vehicle platooning for sustainable freight transportation: A cooperative method to enhance safety and efficiency,” IEEE Control Systems Magazine, vol. 35, pp. 34–56, Dec 2015.
  * [4] S. Tsugawa, S. Jeschke, and S. E. Shladover, “A review of truck platooning projects for energy savings,” IEEE Transactions on Intelligent Vehicles, vol. 1, pp. 68–77, March 2016.
  * [5] R. Bishop, D. Bevly, L. Humphreys, S. Boyd, and D. Murray, “Evaluation and testing of driver-assistive truck platooning: Phase 2 final results,” Transportation Research Record, vol. 2615, no. 2615, pp. 11–18, 2017.
  * [6] P. A. Ioannou and C. C. Chien, “Autonomous intelligent cruise control,” IEEE Transactions on Vehicular Technology, vol. 42, pp. 657–672, Nov 1993.
  * [7] P. Fernandes and U. Nunes, “Platooning with IVC-enabled autonomous vehicles: Strategies to mitigate communication delays, improve safety and traffic flow,” IEEE Transactions on Intelligent Transportation Systems, vol. 13, pp. 91–106, March 2012.
  * [8] Y. Jo, J. Kim, C. Oh, I. Kim, and G. Lee, “Benefits of travel time savings by truck platooning in Korean freeway networks,” Transport Policy, vol. 83, pp. 37 – 45, 2019.
  * [9] R. Janssen, H. Zwijnenberg, I. Blankers, and J. de Kruijff, “Truck platooning,” Driving the, 2015.
  * [10] A. Chottani, G. Hastings, J. Murnane, and F. Neuhaus, “Distraction or disruption? Autonomous trucks gain ground in US logistics.” McKinsey Smith Co, http://https://www.mckinsey.com/industries/travel-transport-and-logistics/our-insights/distraction-or-disruption-autonomous-trucks-gain-ground-in-us-logistics, 2018.
  * [11] J. Axelsson, T. Bergh, A. Johansson, B. Mårdberg, P. Svenson, and V. Åkesson, “Truck platooning business case analysis,” 2020.
  * [12] 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.
  * [13] K. Liang, J. Mårtensson, and K. H. Johansson, “Heavy-duty vehicle platoon formation for fuel efficiency,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, pp. 1051–1061, April 2016.
  * [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, pp. 102–112, Jan 2018.
  * [15] 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.
  * [16] 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.
  * [17] N. Boysen, D. Briskorn, and S. Schwerdfeger, “The identical-path truck platooning problem,” Transportation Research Part B: Methodological, vol. 109, pp. 26 – 39, 2018.
  * [18] R. Larsen, J. Rich, and T. K. Rasmussen, “Hub-based truck platooning: Potentials and profitability,” Transportation Research Part E: Logistics and Transportation Review, vol. 127, pp. 249 – 264, 2019.
  * [19] A. Johansson, E. Nekouei, K. H. Johansson, and J. Mårtensson, “Strategic hub-based platoon coordination under uncertain travel times,” IEEE Transactions on Intelligent Transportation Systems, 2021.
  * [20] T. Bai, A. Johansson, K. H. Johansson, and J. Mårtensson, “Event-triggered distributed model predictive control for platoon coordination at hubs in a transport system,” in 2021 60th IEEE Conference on Decision and Control (CDC), pp. 1198–1204, 2021.
  * [21] A. Johansson, X. Sun, J. Mårtensson, and Y. Yin, “Real-time cross-fleet pareto-improving truck platoon coordination,” in 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pp. 996–1003, IEEE, 2021.
  * [22] A. Johansson, V. Turri, E. Nekouei, K. H. Johansson, and J. Mårtensson, “Truck platoon formation at hubs: An optimal release time rule,” IFAC-PapersOnLine, vol. 53, no. 2, pp. 15312–15318, 2020.
  * [23] A. Adler, D. Miculescu, and S. Karaman, Optimal Policies for Platooning and Ride Sharing in Autonomy-Enabled Transportation, pp. 848–863.  Cham: Springer International Publishing, 2020.
  * [24] A. K. Bhoopalam, N. Agatz, and R. Zuidwijk, “Planning of truck platoons: A literature review and directions for future research,” Transportation Research Part B, vol. 107, pp. 212–228, 2018.
  * [25] V. Lesch, M. Breitbach, M. Segata, C. Becker, S. Kounev, and C. Krupitzer, “An overview on approaches for coordination of platoons,” IEEE Transactions on Intelligent Transportation Systems, 2021.
  * [26] Y.-C. Ho et al., “Team decision theory and information structures in optimal control problems–part i,” IEEE Transactions on Automatic control, vol. 17, no. 1, pp. 15–22, 1972.
  * [27] A. Dave and A. A. Malikopoulos, “Decentralized stochastic control in partially nested information structures,” IFAC-PapersOnLine, vol. 52, no. 20, pp. 97–102, 2019.
  * [28] D. Bertsekas, Dynamic programming and optimal control: Volume I, vol. 4.  Athena scientific, 2012.
  * [29] The Swedish Transport Administration, “Road flow map.” https://vtf.trafikverket.se/SeTrafikinformation.  Accessed: 2021-01-13.
  * [30] Trafikanalys, Godstransporter i Sverige - en nulägesanalys Rapport 2016:7.  2016\.
  * [31] R. T. Rockafellar, Convex Analysis.  Princeton University Press, 1970.