# Optimizing Two-Truck Platooning with Deadlines

Wenjie Xu, Titing Cui, and Minghua Chen  The work presented in this paper was
supported in part by a General Research Fund from Research Grants Council,
Hong Kong (Project No. 14207520), an InnoHK initiative, The Government of the
HKSAR, and Laboratory for AI-Powered Financial Technologies. W. Xu is with
École Polytechnique Fédérale de Lausanne, Lausanne CH-1015, Switzerland.T. Cui
is with Joseph M. Katz Graduate School of Business, University of Pittsburgh,
Pittsburgh, PA 15260, USA.M. Chen is with School of Data Science, City
University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong, Kowloon, Hong
Kong.The first two authors are co-primary authors. A part of the work was done
when all the three authors were with The Chinese University of Hong Kong.
Corresponding author: Minghua Chen (minghua.chen@cityu.edu.hk).

###### Abstract

We study a transportation problem where two heavy-duty trucks travel across
the national highway from separate origins to destinations, subject to
individual deadline constraints. Our objective is to minimize their total fuel
consumption by jointly optimizing path planning, speed planning, and
platooning configuration. Such a two-truck platooning problem is pervasive in
practice yet challenging to solve due to hard deadline constraints and
enormous platooning configurations to consider. We first leverage a unique
problem structure to significantly simplify platooning optimization and
present a novel formulation. We prove that the two-truck platooning problem is
weakly NP-hard and admits a Fully Polynomial Time Approximation Scheme
(FPTAS). The FPTAS can achieve a fuel consumption within a ratio of
$(1+\epsilon)$ to the optimal (for any $\epsilon>0$) with a time complexity
polynomial in the size of the transportation network and $1/\epsilon$. These
results are in sharp contrast to the general multi-truck platooning problem,
which is known to be APX-hard and repels any FPTAS. As the FPTAS still incurs
excessive running time for large-scale cases, we design an efficient dual-
subgradient algorithm for solving large-/national- scale instances. It is an
iterative algorithm that always converges. We prove that each iteration only
incurs polynomial-time complexity, albeit it requires solving an integer
linear programming problem optimally. We characterize a condition under which
the algorithm generates an optimal solution and derive a posterior performance
bound when the condition is not met. Extensive simulations based on real-world
traces show that our joint solution of path planning, speed planning, and
platooning saves up to $24\%$ fuel as compared to baseline alternatives.

###### Index Terms:

Energy efficiency, Timely truck transportation, Path planning, Speed planning,
Platooning, Algorithm, Optimization

##  I Introduction

Heavy-duty trucks, transporting freights across national highways, play a
critical role in society’s economic development. It is reported that the U.S.
trucking industry hauled around $80\%$ of all freight tonnage and brought in
792 billion U.S. dollars as revenue in 2019 [1]. This number would rank 18th
if measured against the country’s GDP [2]. Meanwhile, the trucking industry is
also responsible for a large fraction of the world’s energy consumption and
greenhouse gas emissions. For example, in the U.S., with only 4% of the
vehicle population, heavy-duty trucks account for $18\%$ energy consumption of
the entire transportation sector and $5\%$ of the greenhouse gas emission [1].
In addition, fuel cost corresponds to $24\%$ of the total operational cost in
the trucking industry in 2019 [3]. These alerting observations, together with
that the global freight activity is predicted to increase by a factor of 2.4
by 2050 [4], make it critical to develop effective solutions for improving
fuel efficiency of truck transportation.

Truck platooning, where two or more trucks travel in convoy with small
headway, is a promising fuel-saving approach. It is made possible in practice
by the novel semi-automated driving technology, also referred to as the
Cooperative Adaptive Cruise Control (CACC) system [5, 6, 7]. Similar to what
racing cyclists exploit, trucks traveling in a platoon experience a reduction
in air drag, which translates into lower fuel consumption. Many studies, e.g.,
[8, 9, 10, 11, 12], suggest up to 20% fuel saving for the non-leading vehicles
in a platoon. Meanwhile, platooning also allows vehicles to drive closer than
otherwise at the same speed, improving traffic throughput [13] and even
safety. To date, platooning has received significant attention from private
fleets and commercial carriers [14].

However, it is algorithmically non-trivial to capitalize the platooning
potential to minimize the convoy’s total fuel consumption. First, it requires
exploring three distinct design spaces: path planning, speed planning, and
platooning configuration. Path planning and speed planning are well-recognized
mechanisms for saving fuels by optimizing the driving paths and the speed
profiles over individual road segments. Real-world studies show up to 21% fuel
saving by driving at fuel-economic speeds along an optimized path [15].
Meanwhile, platooning configurations define the road segments for platooning
and the trucks to participate in each platoon. In other words, it describes
where and when a set of the trucks form and end a platoon. It adds another
layer of combinatorial structure to the design space.

Second, the problem becomes even more complicated when we consider
transportation deadlines for individual trucks. Freight delivery with time
guarantee is common in truck operation; see examples and discussions in [16,
17]. As estimated by the U.S. Federal Highway Administration (FHWA) [18], an
unexpected delay can increase freight cost by 50% to 250%. The operator needs
to keep track of the time spent so far and the remaining time budget for
individual trucks, when optimizing over the design space discussed above, to
ensure on-time arrival at destinations. Such a 4-way coupling among path
planning, speed planning, platooning configuration, and deadline creates a
unique challenge. Indeed, the problem of minimizing fuel consumption for
multiple platooning trucks is shown to be APX-hard in general [19], and it
admits no polynomial-time algorithm with a fuel consumption within a constant
ratio to the minimum, unless $\mathbf{P}=\mathbf{NP}$ [20, 21].

TABLE I: Summary of existing studies on minimizing fuel consumption for truck
transportation with platooning.

Existing Study | Path Planning | Speed Planning | Platooning | Deadline | Approach | Bound∗
---|---|---|---|---|---|---
[21, 22, 23, 24] | ✗ | ✓ | ✗ | ✓ | Convex optimization | ✗
[25] | ✗ | ✓ | ✓ | ✓ | Distributed method | ✗
[26] | ✓ | ✗ | ✓ | ✗ | Hub heuristic | ✗
[20] | ✓ | ✗ | ✓ | ✓ | Integer programming (IP) | ✗
[27] | ✓ | ✓ | ✓ | ✓ | K-set clustering + IP | ✗
[28] | ✗ | ✗ | ✓ | ✓ | Mixed integer programming | ✓
[29] | ✓ | ✗ | ✓ | ✓ | Iterative heuristic | ✗
This work | ✓ | ✓ | ✓ | ✓ | Dual-based optimization | Posterior

∗: Entries in the column represent whether there is a guaranteed performance
gap to the optimal. Usually, performance bounds are independent to the
solutions obtained by the algorithm and can be computed beforehand. Meanwhile,
posterior performance pounds are solution dependent and can be computed after
the solution is obtained.

Existing studies. Previous researches on truck platooning optimization mostly
consider either speed planning for given paths or path planning with a set of
constant speeds. Assumed all the trucks drive on their shortest or pre-
specified paths, the authors of [21, 22, 24] obtain the optimal speed profiles
for each truck by solving a series of convex optimization problems. The
authors in [23] and [30] use a similar technique to solve a fixed-path
platooning problem. When the traveling speed on each road segment is fixed,
the path planning in the platooning problem is often formulated as an integer
linear programming (ILP) problem [20, 27, 31, 32, 33]. In [20, 27, 31],
heuristics such as the best-pair algorithms are proposed to solve the ILP in
the platooning problem. Meanwhile, [32] and [33] apply genetic algorithms to
path planning. [28] employs a mixed-integer programming model to study the
platooning of trucks along an identical path but with different time windows
and maximum platooning length. The studies in [27, 34] consider the platooning
optimization with discrete speeds for individual edges, which can be modeled
as a path planning problem by introducing multiple parallel edges between the
starting and ending nodes of original edges, each with a constant (and
different) speed.

Other related studies include [35, 36, 37, 38, 29]. [35] formulates a Markov
decision process to optimize coordination of vehicle platooning at highway
junctions. [36] presents a new platoon formation strategy that optimizes the
platooning number and configuration of heterogeneous vehicles in a single
route. [37] proposes a macroscopic model to analyze the probability
distribution of the length of platoons, for a given traffic demand. [38]
develops an analytical model to investigate the impacts of platoon size. [29]
develops a heuristic iterative procedure to optimize the routes and departure
schedules for the general k-platooning problem under deadline constraints,
without speed planning involved. The heuristic iterative procedure may not
converge or have performance guarantee. In comparison, in this paper, we
explore the full design space, to jointly optimize continuous speed planning,
path planning, and platooning configuration, for a popular two-truck
platooning problem. The iterative procedure in our scheme is a dual
subgradient algorithm that guarantees to converge to the dual optimal, and we
provide a posterior performance bound for it. We refer readers to [39] for a
comprehensive overview of studies related to coordinated platooning
optimization.

Table I summarizes existing studies on fuel consumption minimization in truck
platooning.

Contributions. In this paper, we focus on a prevalent two-truck platooning
scenario where two heavy-duty trucks travel across the national highway from
separate origins to destinations [40, 41, 42, 43, 44]. Two-truck platooning is
not only the mainstream of current platooning practice [42], but it also
incurs minimum safety concern for the surrounding traffic sharing the roads
[40] [43] [41].

To our best knowledge, this is the first work in the literature to minimize
total fuel consumption for truck transportation by simultaneously optimizing
path planning, speed planning, and platooning configuration, subject to
individual deadline constraints. We also consider departure coordination,
where trucks can strategically wait at the origins for proper schedule
alignment to form an efficient platoon later. We make the following
contributions.

$\rhd$ In Sec. II, we present a novel formulation for the two-truck platooning
problem of minimizing fuel consumption subject to individual deadline
constraints, taking into account the entire design space of path planning,
speed planning, and platooning configuration. Our formulation is built upon an
elegant problem structure that significantly simplifies the platooning
optimization. We leverage the formulation to prove that the two-truck
platooning problem is _weakly_ NP-hard and admits a Fully Polynomial Time
Approximation Scheme (FPTAS). It guarantees to return an approximate and
feasible solution, whose fuel consumption is no large than $(1+\epsilon)$
times the minimum for any $\epsilon>0$, with a time complexity polynomial in
the size of the transportation network and $1/\epsilon$. These results are in
sharp contrast to the general multi-truck platooning problem that is APX-hard
and repels any FPTAS [20, 21], suggesting that the two problems are
fundamentally different.

$\rhd$ While the FPTAS works effectively for small-/medium- scale problem
instances, it may still incur excessive running time for large-scale problem
instances in practice. We thus develop an efficient dual-based algorithm for
national-scale problem instances in Sec. III. It is an iterative algorithm
that always converges. Further, we prove that each iteration only incurs
polynomial time complexity, albeit it requires solving an integer linear
programming problem optimally. We characterize a condition under which the
algorithm generates an optimal solution and derive a posterior performance
bound when the condition is not satisfied.

$\rhd$ In Sec. IV, we carry out extensive numerical experiments using real-
world traces over the U.S. national highway system. The results show that our
algorithm obtains close-to-minimum fuel consumption for the two-truck
platooning problem and achieves up to $24\%$ fuel saving as compared to
baseline alternatives adapted from state-of-the-art schemes.

We conclude and discuss future work in Sec. VI.

##  II Model and Problem Formulation

###  II-A System Model

We model a national highway network as a directed graph $G\triangleq(V,E)$.
Each edge $e\in E$ represents a road segment with homogeneous grade, surface
type, and environmental conditions. Each node $v\in V$ denotes an intersection
or connecting point of adjacent road segments. We define $N\triangleq|V|$ as
the number of nodes and $M\triangleq|E|$ as the number of edges. For each
$e\in E$, we use $D_{e}>0$ to denote its length and $r_{e}^{l}>0$ (resp.
$r_{e}^{u}$) to denote the minimum (resp. maximum) driving speed.

There are mainly three types of truck fuel consumption models [45]: (i) first-
principle white-box models, e.g., the kinematics model based on the Newton’s
second law [46, 47, 48, 49, 23, 24, 50]; (ii) black-box models based on
fitting a mathematical function to real-world data, e.g., [51, 52, 53, 54, 55,
56, 57, 58]; (iii) grey-box models that lie between the two models, e.g.,
[59]. White-box models are developed by using domain knowledge in physical and
chemical processes relevant to fuel consumption. It is most accurate and
allows one to investigate tuning internal physical/chemical processes for
higher fuel efficiency. However, the white-box model usually has a large
number of parameters and can be expensive to obtain. On the contrary, the
black-box model is less accurate than the white-box model, does not allow
internal-process tuning, but has fewer parameters to determine.

For our purpose of minimizing fuel consumption and similar to existing eco-
routing studies, we only need to model the (external) speed to fuel-
consumption relationship, instead of the whole physical model with internal
process tuning. As such, black-box models suffice, and they are easier to
construct than white-box models. Indeed, the particular black-box model used
in our simulation only has four parameters, and the model predicts the fuel
consumption pretty well [60, Fig. 5].

To proceed, we define function
$f_{e}(r_{e}):[r_{e}^{l},r_{e}^{u}]\to\mathbb{R}^{+}$ as the _(instantaneous)
fuel consumption rate_ for the truck traveling over $e$ at speed $r_{e}$
111This paper considers the setting where the two trucks have identical fuel
consumption rate functions. For example, they are the same model and carry the
same truckload weight. Our analysis and solution can also be extended to the
case with heterogeneous fuel consumption rate functions. . It is well
understood that $f_{e}(r_{e})$ can be modeled as a strictly convex function
over the speed range $[r_{e}^{l},r_{e}^{u}]$; see e.g., [60, 61] with
justifications. Many existing works [62, 63, 64, 65, 66, 67, 68, 69] also use
polynomial functions to model the _fuel consumption rate_
$f_{e}\left(\cdot\right)$. Following the practice, in this paper, we assume
that $f_{e}\left(\cdot\right)$ is a strictly convex polynomial function. As a
result, according to Jensen’s inequality, driving at a constant speed is most
fuel-economic inside a road segment. Thus, without loss of optimality, it
suffices to consider trucks traveling at constant speeds over individual road
segments [60, 61]. The fuel consumption due to acceleration and deceleration
between consecutive road segments is negligible as compared to that of driving
over individual segments222The speed transition spans over only several
hundred feet [70], while trucks travel on a road segment for several miles or
longer (3.1 miles on average in the US national highway network as shown in
Sec. IV). It is reported in [61] that the fuel usage due to acceleration and
deceleration between consecutive road segments is less than $0.5\%$ of the
total fuel consumption.. For ease of discussion, we further define the _fuel
consumption function_ for a truck to traverse $e$ as

$c_{e}(t_{e})\triangleq t_{e}\cdot f_{e}\left({D_{e}}/{t_{e}}\right),\forall
t_{e}\in[t_{e}^{l},t_{e}^{u}],$ (1)

where $t_{e}$ is the travel time of the truck and
$t_{e}^{l}\triangleq{D_{e}}/{r_{e}^{u}}$ and
$t_{e}^{u}\triangleq{D_{e}}/{r_{e}^{l}}$ are the minimum and maximum travel
duration, respectively. We note that $c_{e}(\cdot)$ is strictly convex over
$[t_{e}^{l},t_{e}^{u}]$ as its second-order derivative
$c^{\prime\prime}(t_{e})=f^{\prime\prime}\left({D_{e}}/{t_{e}}\right){D_{e}^{2}}/{t_{e}^{3}}$
is positive. The function has taken into account the influence of road grade,
surface type, truck weight, and environment conditions. We define the
_platooning fuel consumption function_ when the two trucks platoon on road
segment $e$ as

$\displaystyle c_{e}^{p}(t_{e})=$ $\displaystyle 2(1-\eta)c_{e}(t_{e}),$ (2)

where $\eta\in(0,1)$ is the average fuel-saving ratio and it usually takes
value around 0.1 [25, 26, 20]. Thus when the two trucks platoon at the same
speed, they jointly save a $2\eta$ fraction of total fuel as compared to
driving separately. Note that this model focuses on the total fuel saving; the
leading and following trucks can still have different fuel saving performance.
Similar to [26, 20], we assume constant fuel-saving rate ratio. More
sophisticated fuel models can be derived from Newton’s second law, e.g., those
in [5, 21, 23], and the fuel-saving rate can be speed-dependent [23]. For
these model, it can be verified that the corresponding platooning fuel
consumption function is still convex and our approach can be applied directly.

We consider the scenario of two-truck platooning with deadlines. Each truck is
associated with a task, denoted by
$(s_{i},d_{i},\alpha_{s}^{i},\beta_{s}^{i},\alpha_{d}^{i},\beta_{d}^{i})$,
$i=1,2$. Here $s_{i}$ and $d_{i}$ are origin and destination for truck $i$,
respectively. The pickup window $[\alpha_{s}^{i},\beta_{s}^{i}]$ defines the
time period for pickup at $s_{i}$, and the delivery window
$[\alpha_{d}^{i},\beta_{d}^{i}]$ represents the time period for delivery at
$d_{i}$. We define the traveling time window of truck $i$ ($i=1,2$) as
$\left[T_{s}^{i},T_{d}^{i}\right]$, where $T_{s}^{i}\triangleq\alpha_{s}^{i}$
and $T_{d}^{i}\triangleq\beta_{d}^{i}$ are the earliest departure time and the
latest arrival time, respectively.

Figure 1: The flow chart of our overall solution.

###  II-B To Platoon or not to Platoon

It may not always be feasible for the two trucks to platoon without missing
deadlines. Even if it is, it may not necessarily save fuel when compared to
driving separately. Given a general two-truck platooning instance, we follow
the procedure shown in Fig. 1 to obtain a fuel-minimizing solution. We first
compute the optimized total fuel consumption of two trucks driving separately,
by applying the single-truck algorithm [60] to separately optimize the path
and speed planning of individual trucks. Next, we apply the polynomial-time
Algorithm 2 proposed in Appendix VII-D to check the feasibility of two-truck
platooning under individual deadlines. If infeasible, the two trucks can only
drive separately. We output the separate-driving solutions computed in the
first step. Otherwise, we solve the feasible two-truck platooning problem with
our proposed algorithm to be discussed later. Afterward, we compare the
platooning solution and the separate-driving solution and output the one with
lower fuel consumption.

With the above understanding, in the rest of the paper, we focus on the
feasible two-truck platooning instances.

###  II-C An Elegant Problem Structure and Insights

The conventional formulation of the multi-truck platooning problem introduces
a large number of binary variables, each indicating whether a group of trucks
platoon over a road segment or not. The formulated problem has a combinatorial
structure and is challenging to solve. Indeed, it is APX-hard333A problem is
APX-hard if it is NP-hard and cannot be approximated within an arbitrary
constant factor $(\geq 1)$ in polynomial time unless $\mathbf{P}=\mathbf{NP}$.
and admits no FPTAS444In particular, the authors in [26] show that the multi-
truck platooning problem can be reduced to the Steiner tree problem, which is
known to be APX-hard and no FPTAS exists [71, 19].. Interestingly, the
following lemma reveals an elegant structure of the feasible two-truck
platooning problem, which allows us to significantly simplify the problem
formulation.

######  Lemma 1.

For any feasible two-truck platooning instance, there exists an optimal
solution in which the two trucks platoon only once.

###### Proof.

The proof is presented in Appendix VII-B. ∎

Figure 2: An illustration of our two-truck platooning problem decomposition.

Lemma 1 covers the observation in [26] as a special case without deadline
constraints and speed planning. It implies that without loss of optimality, we
can focus on solutions in which the two trucks form a platoon only once. This
structure significantly reduces the number of platooning configurations to
consider, leading to a new formulation that admits efficient algorithms. In
particular, applying Lemma 1, we divide the two-truck platooning problem into
merging and splitting points selection problem and the following five sub-
problems:

  1. 1.

pre-platooning path and speed planning for truck 1;

  2. 2.

pre-platooning path and speed planning for truck 2;

  3. 3.

in-platooning path and speed planning for truck 1 and 2;

  4. 4.

post-platooning path and speed planning for truck 1;

  5. 5.

post-platooning path and speed planning for truck 2.

We denote the five decomposed paths by sub-path 1/2/3/4/5, respectively; see
Fig. 2 for an illustration. For ease of presentation, we denote the set
$\left\\{1,...,k\right\\}$ as $\mathbb{N}_{k}$. We introduce binary variables
$x_{e}^{i},e\in E,i\in\mathbb{N}_{5}$ for path planning, where

$x_{e}^{i}=\left\\{\begin{array}[]{lr}1,\quad\text{if edge }e\text{ is
selected by the sub-path }i;\\\ 0,\quad\text{otherwise.}\end{array}\right.$

We also introduce non-negative variables $t_{e}^{i}$ to denote the travel time
of the (corresponding) trucks over edge $e$ on the sub-path $i$. Furthermore,
we use binary variables $y_{v}$ and $z_{v}$ to indicate whether the two trucks
start and finish platooning at node $v\in V$, respectively.

###  II-D Problem Formulation

For simplicity of presentation, we define
$\vec{x}\triangleq(x_{e}^{i},i\in\mathbb{N}_{5})_{e\in E}$,
$\vec{y}\triangleq(y_{v})_{v\in V}$, $\vec{z}\triangleq(z_{v})_{v\in V}$,
$\vec{t}\triangleq(t_{e}^{i},i\in\mathbb{N}_{5})_{e\in E}$, and
$\mathcal{T}\triangleq\big{\\{}\vec{t}:t_{e}^{l}\leq t_{e}^{i}\leq
t_{e}^{u},\forall e\in E,i\in\mathbb{N}_{5}\big{\\}}$. We define $\mathcal{P}$
as the feasible set of $\left(\vec{x},\vec{y},\vec{z}\right)$ as follows:

$\displaystyle\mathcal{P}\triangleq\Big{\\{}$
$\displaystyle\left(\vec{x},\vec{y},\vec{z}\right)\big{|}\;\;x_{e}^{i},y_{v},z_{v}\in\\{0,1\\},\forall
e\in E,i\in\mathbb{N}_{5},v\in V,$
$\displaystyle\sum_{e\in\textbf{Out}(v)}x_{e}^{1}-\sum_{e\in\textbf{In}(v)}x_{e}^{1}=\textbf{1}_{v=s_{1}}-y_{v},\forall
v\in V,$
$\displaystyle\sum_{e\in\textbf{Out}(v)}x_{e}^{2}-\sum_{e\in\textbf{In}(v)}x_{e}^{2}=\textbf{1}_{v=s_{2}}-y_{v},\forall
v\in V,$
$\displaystyle\sum_{e\in\textbf{Out}(v)}x_{e}^{3}-\sum_{e\in\textbf{In}(v)}x_{e}^{3}=y_{v}-z_{v},\forall
v\in V,$
$\displaystyle\sum_{e\in\textbf{Out}(v)}x_{e}^{4}-\sum_{e\in\textbf{In}(v)}x_{e}^{4}=z_{v}-\textbf{1}_{v=d_{1}},\forall
v\in V,$
$\displaystyle\sum_{e\in\textbf{Out}(v)}x_{e}^{5}-\sum_{e\in\textbf{In}(v)}x_{e}^{5}=z_{v}-\textbf{1}_{v=d_{2}},\forall
v\in V,$ $\displaystyle\sum_{v\in V}y_{v}=1,\sum_{v\in V}z_{v}=1\Big{\\}},$
(3)

where $\textbf{Out}(v)$ and $\textbf{In}(v)$ are the set of outgoing edges and
incoming edges of node $v$, respectively. $\textbf{1}_{\left\\{*\right\\}}$ is
an indicator variable taking value 1 if the statement $*$ is true and 0
otherwise. The first five constraints in $\mathcal{P}$ are the flow
conservation requirements for the 5 sub-paths. The constraints on $y_{v}$ and
$z_{v}$ restrict the solution to platoon only once.

We now model the deadline constraints and speed planning. The speed planning
is done by adjusting the travel time $t_{e}^{i}$ for individual edge $e$. To
increase fuel efficiency, we consider departure coordination where trucks can
strategically wait at the origins to properly align the schedule to form an
efficient platoon later. Consequently, the two trucks start to platoon from
the merging point at time

$\displaystyle\max$ $\displaystyle\left\\{T_{s}^{1}+\sum_{e\in
E}t_{e}^{1}x_{e}^{1},\;\;T_{s}^{2}+\sum_{e\in E}t_{e}^{2}x_{e}^{2}\right\\}.$
(4)

The two expressions in the bracket are the arrival times at the merging point
of the two trucks, without departure coordination. If one term in the bracket
is smaller than the other, the corresponding truck waits at the origin or a
nearby rest area to synchronize the arrival time at the merging point. Without
loss of generality, we ignore the cost of strategic waiting at the origin. It
can be incorporated into our model by adding a dummy waiting edge at the
origin with a designated cost function. To simplify the formulation later, we
define

$\displaystyle\delta_{1}(\vec{t},\vec{x})=$ $\displaystyle
T_{s}^{1}+\sum_{e\in E}t_{e}^{1}x_{e}^{1}+\sum_{e\in
E}t_{e}^{3}x_{e}^{3}+\sum_{e\in E}t_{e}^{4}x_{e}^{4}-T_{d}^{1},$ (5a)
$\displaystyle\delta_{2}(\vec{t},\vec{x})=$ $\displaystyle
T_{s}^{2}+\sum_{e\in E}t_{e}^{2}x_{e}^{2}+\sum_{e\in
E}t_{e}^{3}x_{e}^{3}+\sum_{e\in E}t_{e}^{4}x_{e}^{4}-T_{d}^{1},$ (5b)
$\displaystyle\delta_{3}(\vec{t},\vec{x})=$ $\displaystyle
T_{s}^{1}+\sum_{e\in E}t_{e}^{1}x_{e}^{1}+\sum_{e\in
E}t_{e}^{3}x_{e}^{3}+\sum_{e\in E}t_{e}^{5}x_{e}^{5}-T_{d}^{2},$ (5c)
$\displaystyle\delta_{4}(\vec{t},\vec{x})=$ $\displaystyle
T_{s}^{2}+\sum_{e\in E}t_{e}^{2}x_{e}^{2}+\sum_{e\in
E}t_{e}^{3}x_{e}^{3}+\sum_{e\in E}t_{e}^{5}x_{e}^{5}-T_{d}^{2}.$ (5d)

It is straightforward to verify that truck 1 meets its deadline if and only if
$\delta_{1}(\vec{t},\vec{x})\leq 0$ and $\delta_{2}(\vec{t},\vec{x})\leq 0$.
Similarly, truck 2 meets deadline if and only if
$\delta_{3}(\vec{t},\vec{x})\leq 0$ and $\delta_{4}(\vec{t},\vec{x})\leq 0$.

To this end, we formulate the feasible two-truck platooning problem as
follows:

$\displaystyle\min\quad$
$\displaystyle\sum_{i\in\mathbb{N}_{5}\backslash\left\\{3\right\\}}\sum_{e\in
E}c_{e}(t_{e}^{i})x_{e}^{i}+\sum_{e\in E}c_{e}^{p}(t_{e}^{3})x_{e}^{3}$ (6)
$\displaystyle\mathrm{s.t.}\quad$
$\displaystyle\delta_{j}(\vec{t},\vec{x})\leq 0,j\in\mathbb{N}_{4};$ (7) var.
$\displaystyle\left(\vec{x},\vec{y},\vec{z}\right)\in\mathcal{P},\vec{t}\in\mathcal{T}.$

The objective in $Eq.~{}\eqref{equ:objective}$ is the total fuel consumption
of the two trucks. $Eq.~{}\eqref{equ:deadlines}$ describes their deadline
constraints. $\mathcal{P}$ restricts the variables so that the two trucks
platoon only once. Compared to the conventional formulation, our formulation
in $Eq.~{}\eqref{equ:deadlines}$ leverages Lem. 1 to simplify the optimization
of platooning configuration, by only considering solutions that platoon only
once. Further, the formulation only involves four deadline constraints. We
show in Sec. III that this structure significantly simplifies the design of
the dual-based algorithm.

###  II-E Hardness

It is not surprising that the two-truck platooning problem is challenging to
solve due to its combinatorial structure and multiple deadline constraints.
Meanwhile, it is easier than the general multi-truck counterpart.

######  Theorem 1.

The two-truck platooning problem in $Eq.~{}\eqref{equ:objective}$ is NP-hard,
but only in the weak sense. In particular, there is a Fully Polynomial Time
Approximation Scheme (FPTAS) for the two-truck platooning problem that
achieves $\left(1+\epsilon\right)$ approximation ratio
$\left(\forall\epsilon>0\right)$ with a time complexity of
$\mathcal{O}\left(N^{6}/\epsilon^{4}\right)$.

###### Proof.

See Appendix VII-C.

∎

Thm. 1 and its proof show that the two-truck platooning problem is weakly NP-
hard and admits an FPTAS. This is in sharp contrast to the general multi-truck
platooning problem (even without speed planning), which is APX-hard and repels
any FPTAS. Consequently, there exists a pseudo-polynomial time algorithm to
solve the two-truck platooning problem exactly. Further, one can trade
optimality loss for running time by using the FPTAS derived in the proof. It
guarantees to return an approximate and feasible solution to the two-truck
platooning problem, whose fuel consumption is within a ratio of $(1+\epsilon)$
to the optimal for any $\epsilon>0$, with a time complexity of
$\mathcal{O}\left(N^{6}/\epsilon^{4}\right)$. The FPTAS allows us to solve
small-scale two-truck platooning instances efficiently. Meanwhile, it may
still incur excessive running time for solving large-scale instances. In the
next section, we introduce a dual-subgradient algorithm for solving
large-/national- scale instances.

##  III An Efficient Dual-Subgradient Algorithm

In this section, we design an efficient dual-subgradient algorithm for solving
a partially-relaxed dual problem of the two-truck platooning problem, in which
only a subset of the constraints are relaxed. While a fully-relaxed dual
problem is always convex, the partially-relaxed one is not. Indeed, it is
still a combinatorial problem and can be challenging to solve. As a key
contribution, we explore the problem structure to show that it can be solved
optimally in polynomial time by a dual-subgradient algorithm. We derive a
posterior bound on the optimality gap when a feasible primal solution is
recovered from the dual optimal solution. We resort to the separate-driving
solution when no feasible primal solution is recovered.

###  III-A The Dual of the Two-truck Platooning Problem

We relax the deadline constraints in $Eq.~{}\eqref{equ:deadlines}$ and obtain
the following Lagrangian function

$\displaystyle L\left(\vec{x},\vec{y},\vec{z},\vec{t},\vec{\lambda}\right)$
$\displaystyle=\sum_{i\in\mathbb{N}_{5}\backslash\left\\{3\right\\}}\sum_{e\in
E}c_{e}\left(t_{e}^{i}\right)x_{e}^{i}+\sum_{e\in
E}c_{e}^{p}\left(t_{e}^{3}\right)x_{e}^{3}$
$\displaystyle\qquad+\sum_{i\in\mathbb{N}_{4}}\lambda_{i}\delta_{i}\left(\vec{t},\vec{x}\right),$

where
$\vec{\lambda}\triangleq\left(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}\right)$
and $\lambda_{i}$ is the dual variable associated with the constraint
$\delta_{i}(\vec{t},\vec{x})\leq 0$. The corresponding dual problem is given
by

$\displaystyle\max\limits_{\vec{\lambda}\geq
0}D\left(\vec{\lambda}\right)\triangleq$
$\displaystyle\max\limits_{\vec{\lambda}\geq
0}\,\min\limits_{\left(\vec{x},\vec{y},\vec{z}\right)\in\mathcal{P},\vec{t}\in\mathcal{T}}L\left(\vec{x},\vec{y},\vec{z},\vec{t},\vec{\lambda}\right).$
(8)

Our idea is to solve this partially-relaxed dual problem optimally and recover
the corresponding primal solutions. At the first glance, the inner problem
seems challenging as it is still combinatorial (due to the structure of the
feasible set $\mathcal{P}$). To proceed, we re-express $D(\vec{\lambda})$ as
follows:

$\displaystyle\negthickspace D\left(\vec{\lambda}\right)$
$\displaystyle=h\left(\vec{\lambda}\right)+\underbrace{\min_{\underset{\in\mathcal{P}}{\left(\vec{x},\vec{y},\vec{z}\right)}}\sum_{i\in\mathbb{N}_{5}}\sum_{e\in
E}x_{e}^{i}\cdot\underbrace{\min_{t_{e}^{i}\in\left[t_{e}^{l},t_{e}^{u}\right]}g_{e}^{i}\left(\vec{\lambda},t_{e}^{i}\right)}_{\mbox{speed
optimization}}}_{\mbox{path and platooning optimization}},$ (9)

where
$h(\vec{\lambda})\triangleq\lambda_{1}\left(T_{s}^{1}-T_{d}^{1}\right)+\lambda_{2}\left(T_{s}^{2}-T_{d}^{1}\right)+\lambda_{3}\left(T_{s}^{1}-T_{d}^{2}\right)$
$+\lambda_{4}\left(T_{s}^{2}-T_{d}^{2}\right)$ is a linear function and
$g_{e}^{i}(\vec{\lambda},t_{e}^{i})$ is a generalized edge cost function given
by, for all $e\in E$,

$g_{e}^{i}\left(\vec{\lambda},t_{e}^{i}\right)=\begin{cases}c_{e}\left(t_{e}^{1}\right)+\left(\lambda_{1}+\lambda_{3}\right)t_{e}^{1},&i=1;\\\
c_{e}\left(t_{e}^{2}\right)+\left(\lambda_{2}+\lambda_{4}\right)t_{e}^{2},&i=2;\\\
c_{e}^{p}\left(t_{e}^{3}\right)+\left(\sum_{j\in\mathbb{N}_{4}}\lambda_{j}\right)t_{e}^{3},&i=3;\\\
c_{e}\left(t_{e}^{4}\right)+\left(\lambda_{1}+\lambda_{2}\right)t_{e}^{4},&i=4;\\\
c_{e}\left(t_{e}^{5}\right)+\left(\lambda_{3}+\lambda_{4}\right)t_{e}^{5},&i=5.\end{cases}$

The function $g_{e}^{i}(\vec{\lambda},t_{e}^{i})$, for all
$i\in\mathbb{N}_{5}$ and $e\in E$, is convex in $t^{i}_{e}$ as the sum of a
convex function and a linear function. As such, the speed optimization module
in $Eq.~{}\eqref{equ:dualfunction}$, one for each edge, can be solved in
polynomial time. For all $i\in\mathbb{N}_{5}$ and $e\in E$, define
$w_{e}^{i}(\vec{\lambda})\triangleq\min_{t_{e}^{i}\in\left[t_{e}^{l},t_{e}^{u}\right]}g_{e}^{i}(\vec{\lambda},t_{e}^{i})$
and $t^{i,*}_{e}(\vec{\lambda})$ as the optimal objective value and a
corresponding optimal solution, respectively. We further define
$\vec{t}^{\,*}(\vec{\lambda})\triangleq(t_{e}^{i,*}(\vec{\lambda}))_{i\in\mathbb{N}_{5},e\in
E}$. After obtaining $w_{e}^{i}(\vec{\lambda})$ for all $i\in\mathbb{N}_{5}$
and $e\in E$, the path and platooning optimization module in
$Eq.~{}\eqref{equ:dualfunction}$ amounts to a combinatorial integer linear
programming (ILP) problem:

$\displaystyle\min_{\left(\vec{x},\vec{y},\vec{z}\right)\in\mathcal{P}}$
$\displaystyle\sum_{i\in\mathbb{N}_{5}}\sum_{e\in
E}w_{e}^{i}\left(\vec{\lambda}\right)x_{e}^{i}.$ (10)

In general, ILP problems can be difficult to solve. Generic approaches such as
the branch-and-bound method incur high computational complexity and do not
scale well to large problem instances. As a key contribution, we show that one
can relax binary decision variables $\vec{x},\vec{y},\vec{z}$ into continuous
ones in $\left[0,1\right]$ and solve the resulting linear programming (LP)
problem without loss of optimality. Recall that $M$ is the number of edges.

######  Theorem 2.

There is no integrality gap between the ILP problem in
$Eq.~{}\eqref{eq:prob_ppo_ILP}$ and the corresponding relaxed LP problem.
Furthermore, the optimal solution to the former can be recovered from that to
the latter in $\mathcal{O}(M^{2})$ time.

###### Proof.

The idea is to show every optimal solution of the relaxed LP problem is a
convex combination of integer platooning solutions in $\mathcal{P}$. See
Appendix VII-E for the proof. ∎

Thm. 2 is an important result. It says we can obtain the optimal solution of
the path and platooning optimization problem in
$Eq.~{}\eqref{eq:prob_ppo_ILP}$, by solving its relaxed LP problem,
significantly reducing the computational complexity. Denote the optimal
solution of the ILP problem in $Eq.~{}\eqref{eq:prob_ppo_ILP}$ as
$\vec{x}^{\,*}(\vec{\lambda}),\vec{y}^{\,*}(\vec{\lambda}),\vec{z}^{\,*}(\vec{\lambda}).$

To this point, it is straightforward to verify that $\begin{aligned}
\delta_{i}(\vec{t}^{\,*}(\vec{\lambda}),\vec{x}^{\,*}(\vec{\lambda}))\end{aligned}$
is a subgradient of $D(\vec{\lambda})$ with respect to $\lambda_{i}$,
$i\in\mathbb{N}_{4}$. From the discussion above, it is clear that both
$\vec{t}^{\,*}(\vec{\lambda})$ and $\vec{x}^{\,*}(\vec{\lambda})$, hence
$\begin{aligned}
\delta_{i}(\vec{t}^{\,*}(\vec{\lambda}),\vec{x}^{\,*}(\vec{\lambda}))\end{aligned}$,
can be computed in polynomial time. This allows us to develop an efficient
dual-subgradient algorithm for solving the problem in
$Eq.~{}\eqref{equ:dualprob}$.

###  III-B The Dual-Subgradient Ascent Algorithm

The dual-subgradient algorithm is an iterative algorithm for updating the dual
variables towards optimality. Specifically, given $\vec{\lambda}[k]$ as the
dual variables after the $k$-th iteration (initially, $\vec{\lambda}[0]$ takes
arbitrary non-negative values), the algorithm updates the dual variables as
follows: for all $i\in\mathbb{N}_{4}$,

$\displaystyle\lambda_{i}\left[k+1\right]=$
$\displaystyle\lambda_{i}\left[k\right]+\phi_{k}\left[\delta_{i}\left(\vec{t}^{\,*}\left(\vec{\lambda}\left[k\right]\right),\vec{x}^{\,*}\left(\vec{\lambda}\left[k\right]\right)\right)\right]_{\lambda_{i}\left[k\right]}^{+},$
(11)

where $\vec{t}^{\,*}\left(\vec{\lambda}\left[k\right]\right)$ and
$\vec{x}^{\,*}\left(\vec{\lambda}\left[k\right]\right)$ can be computed in
polynomial time by solving the speed optimization and path and platooning
optimization modules in $Eq.~{}\eqref{equ:dualfunction}$, respectively.
$\phi_{k}>0$ is the step size and function $[\mu]_{\nu}^{+}$ is defined as

$\displaystyle[\mu]_{\nu}^{+}$
$\displaystyle\triangleq\left\\{\begin{array}[]{ll}\mu,&\text{if }\nu>0;\\\
\max\\{\mu,0\\},&\text{otherwise.}\end{array}\right.$

1 Set $K$, $k\xleftarrow{}1$, and $\lambda_{i}[0]\xleftarrow{}0,\forall
i\in\mathbb{N}_{4}$

2 Set $k^{u}$ as $\mathrm{NULL}$

3 while  _ $k\leq K$_ do

4 Compute $\vec{t}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{x}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{y}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{z}^{*}\left(\vec{\lambda}[k]\right)$ by solving speed optimization, path
and platooning optimization modules in $Eq.~{}\eqref{equ:dualfunction}$.

5 Compute
$\delta_{i}\left(\vec{t}^{*}\left(\vec{\lambda}[k]\right),\vec{x}^{*}\left(\vec{\lambda}[k]\right)\right)$
by $Eq.~{}\eqref{equ:delta}$.

6 if  _$\delta_{i}^{*}(\vec{\lambda}[k])=0,\forall i\in\mathbb{N}_{4}$_ then

7 return $\vec{t}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{x}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{y}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{z}^{*}\left(\vec{\lambda}[k]\right)$

8

9

10 if  _$\delta_{i}^{*}(\vec{\lambda}[k])\leq 0,\forall i\in\mathbb{N}_{4}$_
then

11 Compute the fuel cost $\rho[k]$ of the solution
$\vec{t}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{x}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{y}^{*}\left(\vec{\lambda}[k]\right)$,
$\vec{z}^{*}\left(\vec{\lambda}[k]\right)$

12 if  _$k^{u}$ is $\mathrm{NULL}$ or $\rho[k]\leq\rho[k^{u}]$_ then

13 $k^{u}\xleftarrow{}k$

14

15

16

17 Update $\lambda_{i}[k+1]$ according to $Eq.~{}\eqref{equ:dualDyna}$,
$\forall i\in\mathbb{N}_{4}$. $k\xleftarrow{}k+1$

18

19if  _$k^{u}$ is not $\mathrm{NULL}$_ then

20 $k^{*}\xleftarrow{}k^{u}$

21 else

22 $k^{*}\xleftarrow{}K$

return $\vec{t}^{*}\left(\vec{\lambda}[k^{*}]\right)$,
$\vec{x}^{*}\left(\vec{\lambda}[k^{*}]\right)$,
$\vec{y}^{*}\left(\vec{\lambda}[k^{*}]\right)$,
$\vec{z}^{*}\left(\vec{\lambda}[k^{*}]\right)$.

Algorithm 1 A Dual subgradient algorithm for optimizing two-truck platooning
with deadlines.

The pseudo-code of the dual-subgradient algorithm is presented in Alg. 1.
Intuitively, the dual variables can be interpreted as the delay price. The
dual function can be interpreted as a generalized cost involving both the
delay and fuel expenses. Higher delay prices lead to shorter truck traveling
times, which help to capture deadlines. Meanwhile, higher delay prices also
result in higher fuel expense, as seen from the structure of the cost function
over individual edges, _i.e._ , $g^{i}_{e}(\vec{\lambda},t^{i}_{e})$. Alg. 1
can thus be understood as adjusting the dual variables according to the
subgradients, towards the condition of meeting the deadlines and minimizing
the fuel consumption. If Alg. 1 returns at line 1 and all the deadline
constraints are satisfied555We note that while the dual-subgradient algorithm
converges to the dual optimal (as discussed in the next subsection), the
deadline constraints may not be satisfied. Indeed, if all the deadline
constraints are satisfied at the dual optimal solution, the duality gap is
zero, and the dual optimal value is also primal optimal. In general, this may
not happen, and the duality gap is nonzero., then the corresponding primal
solutions are also feasible. Otherwise Alg. 1 returns at line 1. If some
deadlines are not met, we perform primal recovery by fixing the returned path
planning and platooning solution
$(\vec{x}^{*}(\vec{\lambda}(K)),\vec{y}^{*}(\vec{\lambda}(K)),\vec{z}^{*}(\vec{\lambda}(K)))$
and re-optimize the time to spent on individual edges. From the simulation
results reported in Sec. IV, we observe that such a procedure can recover
primary feasible solutions for most instances, with an average optimality gap
within 1% to the optimal. In the rare situation where the primal recovery
fails, we resort to the separate-driving solution discussed in Sec. IIII-B.

###  III-C Performance Analysis

####  III-C1 Convergence Rate

It is known that subgradient algorithms for solving fully-relaxed convex dual
problems converge at a rate of $\mathcal{O}\left(1/\sqrt{K}\right)$ [72]. A
similar understanding holds for ours for solving the partially-relaxed dual
problem in $Eq.~{}\eqref{equ:dualprob}$.

######  Theorem 3.

Let $D^{*}$ be the optimal dual value and $\bar{D}_{K}$ be the maximum dual
value observed until the K-th iteration by running Alg. 1. Then with step
sizes $\phi_{i}=1/\sqrt{{K}}$, $i\in\mathbb{N}_{K}$, there exists a constant
$\xi>0$ such that $D^{*}-\bar{D}_{k}\leq\xi/\sqrt{K}.$

###### Proof.

See Appendix VII-F. ∎

The constant $\xi$ depends on the network structure and the deadline
constraints. We refer interested readers to the proof for more detailed
discussions. Thm. 3 shows that we can achieve
$\mathcal{O}\left(1/\sqrt{K}\right)$ convergence rate by using a constant step
size. In practice, one may achieve faster convergence by using adaptive step
sizes [73].

####  III-C2 Complexity

The main computational complexity involved in Alg. 1 lies in solving the LP in
line 1, which is $\mathcal{O}((N+M)^{2.5})$ by the algorithm in [74]. Note
that $N$ is the number of nodes, $M$ is the number of edges in the graph, and
$\mathcal{O}(N+M)$ is the number of variables in the LP. Since the dual-
subgradient algorithm converges at a rate of $\mathcal{O}(1/\sqrt{K})$, the
overall time complexity for Alg. 1 to generate a dual solution within accuracy
$\epsilon>0$ to the optimal is $\mathcal{O}((N+M)^{2.5}/\epsilon^{2})$.

####  III-C3 Optimality Gap

We provide a posterior bound on the optimality loss when Alg. 1 returns a
feasible primal solution. Recall that $\vec{\lambda}[k^{*}]$ consists of the
dual variables upon Alg. 1 terminating after $K$ iterations and
$\delta_{i}(\vec{t}^{*}(\vec{\lambda}[k^{*}],\vec{x}^{*}(\vec{\lambda}[k^{*}]))$
is the corresponding dual subgradient.

######  Theorem 4.

If Alg. 1 returns a feasible solution $\bar{P}$, the optimality gap between
the cost of $\bar{P}$, denoted as $c(\bar{P})$, and the optimal cost, denoted
as $OPT$, is bounded as follows:

$c\left(\bar{P}\right)-OPT\leq\begin{cases}0,&\text{if
}\delta_{i}(\cdot)=0,\forall i\in\mathbb{N}_{4}\mbox{ and }\text{Alg.
\ref{alg:heuristic}}\\\ &\text{ returns in line
\ref{line:optima_returned}};\\\ B,&\mbox{otherwise}.\end{cases}$ (12)

where
$B=-\sum_{i=1}^{4}\lambda_{i}[k^{*}]\delta_{i}(\vec{t}^{\,*}(\vec{\lambda}[k^{*}]),\vec{x}^{\,*}(\vec{\lambda}[k^{*}]))\geq
0$.

###### Proof.

The proof is presented in Appendix VII-G. ∎

According to Thm. 4, if $\delta_{i}(\cdot)=0,\forall i\in\mathbb{N}_{4}$,
i.e., the deadlines for individual trucks are all met exactly, and thus Alg. 1
returns in the line 1, the obtained dual solution is optimal and the
corresponding primal solution is feasible and optimal. Otherwise, Alg. 1
returns in the line 1 and we can compute a posterior bound if the
corresponding primal solution is feasible. From the simulation results
reported in Sec. IV, we observe that for the cases that our algorithm returns
feasible primal solution, the computed posterior bounds are within $0.3\%$ to
the optimal, suggesting strong empirical performance of the proposed
algorithm. Meanwhile, it is clear that the bound holds for each iteration and
thus can be used to terminate the Alg. 1 earlier upon reaching a target
accuracy threshold. Specifically, one can calculate a posterior bound after
each iteration and terminate Alg. 1 if the bound is already lower than the
target threshold.

##  IV Performance Evaluation

We use real-world traces to evaluate the performance of our solutions. We
implement our algorithm in python and carry out numerical experiments on a
server cluster with 42 pieces of 2.4 GHz – 3.4 GHz Intel/AMD processors, each
equipped with 16GB – 96GB memory. We represent an instance of our platooning
problem by a tuple
$(s_{1},d_{1},T_{s}^{1},T_{d}^{1},s_{2},d_{2},T_{s}^{1},T_{d}^{2})$. We follow
the flow chart in Fig. 1 to obtain the solution for each instance.

_Transportation network and heavy-duty truck_. We construct the US national
highway network using the data from the Clinched Highway Mapping Project [75].
We focus on the eastern US section with $38,213$ nodes and $82,781$ road
segments. The average length of road segments is $3.1$ miles. Our simulated
trucks are both class-8 heavy-duty trucks Kenworth T800, each with a 36-ton
full load [76].

_Fuel consumption rate function_. First, we obtain the grade of each road
segment by querying the elevations provided by the Elevation Point Query
Service [77]. We then use the ADVISOR simulator [78] to collect fuel
consumption rate data for each road segment. Finally, we use the curve fitting
toolbox in MATLAB to fit the fuel consumption rate function of speed by a
3-order polynomial function. The same polynomial fuel consumption model was
also used in other literature of energy-efficient timely truck transportation;
see, e.g., [60, 79, 66, 67, 68, 69, 61].

_Platooning fuel consumption_. For the platooning problem, existing studies on
path-only optimization usually assume that the fuel-saving ratio is constant
[20, 27]. Studies on speed-only planning often assume the aerodynamic
coefficient in the fuel consumption model is reduced at a constant rate [21,
22, 24]. In our simulation, similar to [20, 27], we assume a speed-independent
average fuel saving rate for the two trucks, denoted as $\eta$ in
$Eq.~{}\eqref{platoonfunction}$. This is based on the understanding that (i)
the fuel saving rates for the leading and trailing vehicle can be different
and we are working with their average and (ii) existing studies, e.g., [80],
show that the impact of speed on platooning fuel saving rate is minor.
Further, our algorithm is applicable without any change as long as the
platooning fuel consumption function is convex over the speed on each edge. We
use $\eta=0.1$ in simulations.

_Origin-destination pairs_. There are few platooning traces available in the
public domain. We thus generate synthetic platooning instances from real-world
statistics as follows. We first obtain the real-world freight flow statistics
in the US ,from Freight Analysis Framework (FAF) [81]. For each origin or
destination of the recorded freight flow in FAF, we find the closest highway
node and manually set this node as the representative truck origin or
destination in our simulation. We then randomly sample the first truck origin-
destination $(s_{1},d_{1})$ by the freight weight from the origin to the
destination. We then calculate the shortest path’s distance $l_{1}$ from
$s_{1}$ to $d_{1}$. We set a radius lower bound ratio $\gamma_{l}$ and a
radius upper bound ratio $\gamma_{u}$. We then set the radius lower bound
$r_{l}=l_{1}\gamma_{l}$ and the radius upper bound $r_{u}=l_{1}\gamma_{u}$. We
then sample $s_{2}$ ($d_{2}$ resp.) from the nodes with distance between
$r_{l}$ to $r_{u}$ from the $s_{1}$ ($d_{1}$ resp.), uniformly at random. We
set $\gamma_{l}=0.1$ and $\gamma_{u}=0.5$. In our simulation, the average
distances from $s_{1}$ to $s_{2}$ and from $d_{1}$ to $d_{2}$ are 195 miles
and 188 miles, respectively.

TABLE II: Fuel saving performance of various platooning solutions, under different _shortest path overlapping ratios_.  Shortest path overlapping ratio | (0.0, 0.2) | (0.2, 0.4) | (0.4, 0.6) | (0.6, 0.8) | (0.8, 1.0)
---|---|---|---|---|---
P-Platooning platooning ratio (%) | 45.3 | 56.6 | 63.8 | 76.0 | 85.2
S-Platooning platooning ratio (%) | 3.3 | 29.6 | 50.2 | 69.7 | 84.7
Our Solution platooning ratio (%) | 43.9 | 56.8 | 63.4 | 75.4 | 85.2
Fuel Saving compared to P-Platooning (%) | 22.4 | 22.8 | 28.2 | 25.3 | 20.2
Fuel Saving compared to S-Platooning (%) | 4.3 | 2.6 | 1.2 | 0.8 | 0.2
Upper bound of our solution’s optimality gap (%) | 0.2 | 0.3 | 0.5 | 0.5 | 0.5

###  IV-A Two Platooning Baselines

We compare the performance of our dual-subgradient algorithm to two baseline
methods.

  * •

_Path planning with platooning (P-Platooning)._ The first one is based on path
planning with the speed of trucks on each edge fixed [20, 27]. The platooning
optimization can be formulated as an integer linear programming problem (ILP)
and solved by the state-of-the-art solver Gurobi. Specific to our setting, we
implement the P-Platooning baseline by setting the speed as the fastest speed
and then optimizing the driving paths with platooning consideration.

  * •

_Speed planning with platooning (S-Platooning)._ The second one is based on
speed planning. Similar to [21, 22, 24], we assume the two trucks travel on
their shortest paths. We consider the two trucks may platoon over the
overlapping road segments of the two shortest paths. We then optimize speed
planning with platooning in consideration subject to deadline constraints, by
fixing paths in our formulation in $Eq.~{}\eqref{equ:objective}$ and using
Gurobi to solve the revised problem.

We use the largest dual function value obtained from our dual subgradient
algorithm as a non-trivial lower bound to estimate the minimum fuel
consumption for evaluating optimality loss.

###  IV-B Performance Comparison to Platooning Baselines

Intuitively, by jointly exploiting the design space of path planning, speed
planning, and platooning configuration, we can achieve better performance than
only optimizing the path planning or the speed planning. We sample the second
origin-destination pair within $0.1-0.5$ times the shortest path distance of
the first distance pair. We define the platooning ratio as the average
fraction of platooning in driving distance, and the _Shortest Path Overlapping
Ratio (S.P.O.R.)_ as the ratio between the length of overlapping road segments
in shortest paths and the total length of two trucks’ shortest paths. We then
group the results according to the range of _the overlapping ratio._

We also introduce a new evaluating metric _platooning fuel saving achieving
ratio $P$_ defined as the ratio between
$\mathrm{OPT(Path,Speed)}-\textrm{Fuel(Platoon Solution)}$ and
$\mathrm{OPT(Path,Speed)}-\mathrm{OPT(Path,Speed,Platoon)}$.
$\mathrm{OPT(Path,Speed)}$ is the optimal fuel cost of path planning and speed
planning without platooning, Fuel(Platoon Solution) is the fuel cost of the
platoon solution to be evaluated and $\mathrm{OPT(Path,Speed,Platoon)}$ is the
optimal fuel cost of path planning and speed planning with platooning. We
obtain estimates of the optimal values by using the largest dual value
obtained from the dual subgradient algorithm. 666Specifically, we obtain the
approximated $\mathrm{OPT(Path,Speed})$ by using the dual based method in
[60]. We use the largest dual value obtained in our solution, which is within
$0.8\%$ to $\mathrm{OPT(Path,Speed,Platoon)}$, to approximate
$\mathrm{OPT(Path,Speed,Platoon)}$.

Figure 3: _Platooning fuel saving achieving ratio_ with different _Shortest
Path Overlapping Ratio_. The achieving ratio of S-Platooning decreases to
negative, as the overlapping ratio decreases. In contrast, our solution
attains an achieving ratio close to one consistently.

We simulate $1,495$ instances in total. Simulation results in Tab. II show
that on average, our solution saves $24\%$ (resp. $3\%$) fuel compared to the
P-Platooning (resp. S-Platooning) baselines. We observe that, empirically, our
solution’s fuel consumption is within less than $0.8\%$ to the lower bound of
minimum. The optimality loss of our solution is thus minor.

Furthermore, Fig. 3 shows that when _Shortest Path Overlapping Ratio_ is
small, the achieving ratio of S-Platooning is minor or even negative. In
contrast, our solution always achieve a high ratio close to one. This result
shows that our solution achieves almost the maximum fuel saving offered by
platooning.

###  IV-C The Benefits of Departure Coordination

In this experiment, we compare the solution with departure coordination to
that without departure coordination. Similar to the opportunistic driving idea
proposed in [79], allowing trucks to wait at the origins can create more
favorable platooning opportunity at a later time and thus benefit fuel saving.
This improves the fuel economy as long as the two trucks can still catch their
deadlines. To obtain the solution without departure coordination, we require
the two trucks to arrive at the merging point exactly the same time, _i.e._ ,
$T_{s}^{1}+\sum_{e\in E}t_{e}^{1}x_{e}^{1}=T_{s}^{2}+\sum_{e\in
E}t_{e}^{2}x_{e}^{2}$, and the other constraints are the same as in
$Eq.~{}\eqref{equ:deadlines}$. As for the solution with opportunistic driving,
we do not require arrival at the merging point exactly the same time. We use
similar dual-based procedures to optimize the path and speed planning for the
case without departure coordination.

Simulation results show that, with departure coordination, we save $5\%$ more
fuel as compared to the case without departure coordination. We also observe
that about $25\%$ of the instances that are feasible with departure
coordination become infeasible without departure coordination. Fig. 4 shows
that the normalized fuel cost with departure coordination is significantly
lower and decreases faster than that without departure coordination.
Meanwhile, we define the waiting time ratio as the ratio of waiting time to
the total trip time for the truck that performs departure coordination to
measure the extent of departure coordination. As shown in Fig. 4, the waiting
time ratio increases as the delay factor increases. This set of results
highlight that as the deadline increases, the time schedule is more flexible
for the trucks to form a favorable platoon for fuel saving, and departure
coordination is effective in capitalizing the fuel-saving potential.

Figure 4:  The average fuel cost normalized by the fuel cost of fastest path
solution decreases as the delay factor increases. The average waiting time
ratio for the waiting truck increases as delay factor increases.

###  IV-D Impact of Deadline

We now investigate the impact of deadlines. We define delay factor $\beta$ to
be the ratio between Deadline and Fastest Path’s Time Cost. We fix the radius
ratio lower bound to be $\gamma_{l}=0.1$ and the radius ratio upper bound to
be $\gamma_{u}=0.5$. Fig. 5 gives the fuel-saving performance of different
algorithms as the delay factor varies. It can be seen that our solution saves
a significant amount of fuel as compared to other solutions. It can also be
seen that as the delay factor increases, the fuel-saving contributed by speed
planning becomes larger. This matches our intuition that a larger delay factor
allows a bigger design space and thus larger fuel-saving potential for speed
planning. From Tab. III, we also observe that as the delay factor increases,
fuel-saving increases significantly but the ratio of platooning time to total
driving time does not increase much. It implies that the increased fuel saving
is mainly contributed by speed planning.

Figure 5: The average fuel cost normalized by the fuel cost of fastest path solution of different algorithms with different delay factor. It is again verified that our solution is very close to optimal solution.  TABLE III: Comparison of different solutions’ fuel saving percentage with different delay factors. The row ”Platooning” denotes the Platooning Time Percentage of our solution. It can be seen that there is a significant fraction of platooning time (more than $20\%$), which shows that platooning indeed contributes to fuel saving. Delay Factor | 1.3 | 1.5 | 1.7 | 1.9
---|---|---|---|---
P-Platooning (%) | 3.4 | 3.4 | 3.4 | 3.4
S-Platooning (%) | 17.9 | 22.7 | 25.0 | 25.9
Our solution (%) | 20.5 | 25.0 | 27.2 | 28.0
Platooning (%) | 35.5 | 37.3 | 38.1 | 37.8

We also compare our solution’s performance to S-Platooning in terms of
achieving platooning fuel saving potential, we also compare different
solutions’ approximated _platooning fuel saving achieving ratio_ as shown in
Fig. 6. We observe that S-Platooning’s achieving ratio is rather low,
sometimes even negative, indicating that the solution is worse than the
baseline without platooning. In contrast, our solution always achieve fuel
saving ratio close to 1.

Figure 6: _Platooning fuel saving achieving ratio_ under different delay
factors. Our solution consistently achieves a ratio close to one, while
S-platooning perform badly, even worse than the baseline without platooning.

##  V Discussion

###  V-A Computation time

We run all the instances (about 1500 in total) on a server cluster with 42
pieces of 2.4 GHz – 3.4 GHz Intel/AMD processors, each equipped with 16GB – 96
GB memory. The total solving time is about $6$ hours, less than 15 seconds for
one instance even by the most conservative estimate. On a personal computer
with Intel(R) Core(TM) i7-10610U processor and 16 GB RAM, it takes 10-20
minutes to solve one instance.

In Sec. III-C, we analyze the time complexity of our proposed algorithm, which
is $O((N+M)^{2.5}/\epsilon^{2})$ where $N$ is the number of nodes and $M$ is
the number of edges in the graph. In simulation, we observe that a large
fraction of the computation time is used in obtaining the dual value by
solving the relaxed problem in line 1 of Alg. 1, which contains two parts. The
first is solving a convex optimization problem for each edge. The second is a
linear programming with variable dimension proportional to the sum of number
of nodes and number of edges. Thus the computation time depends heavily on the
size of the graph. As such, one way to reduce the computation time is to prune
the nodes and edges that are far away from the origins and destinations of the
trucks, which are unlikely to appear in the optimal or near-optimal solution.

###  V-B Perfect and imperfect knowledge of traffic conditions

As the first step to optimize fuel consumption for two-truck platooning under
individual deadline constraints, we solve the fuel minimization problem under
the setting where traffic conditions are static and known. The obtained
solution is feasible and close to optimal when the static traffic condition
can be accurately estimated. They can also serve as benchmarks for existing or
future two-truck platooning solutions with imperfect static traffic
information.

Meanwhile, the real-world traffic conditions can also be time-varying. The
current formulation does not consider such variable traffic conditions. A
viable workaround is to recompute the solution periodically, e.g., once every
hour, using the latest traffic information. It is also conceivable to employ
the phase-based traffic model in [79] to incorporate variable traffic
conditions into our formulation. The obtained results can be benchmarks for
evaluating two-truck platooning solutions with imperfect time-varying traffic
information.

##  VI Conclusion and Future Work

This paper studies the two-truck platooning problem to minimize the total fuel
consumption while meeting individual deadlines by jointly optimizing path
planning, speed planning, and platooning configuration. We show that any
feasible two-truck platooning problem has an optimal solution in which the two
trucks platoon only once. With this understanding, we develop a new
formulation and show that the two-truck platooning problem is only weakly NP-
hard and admits an FPTAS. This contrasts with the general multi-truck
platooning problem, which is known to be APX-hard and thus repels any FPTAS.
We further design a dual-subgradient algorithm for solving large-/national-
scale problem instances. It is an iterative algorithm that always converges.
Each iteration involves solving a non-trivial integer linear problem
optimally, which we prove incurs only polynomial time complexity. We
characterize a sufficient condition under which the algorithm generates an
optimal solution. We characterize a posterior bound on the optimality gap when
the condition is not met. We use the real-world traces over the US national
highway system to demonstrate the performance of our algorithm. As compared to
the path-/speed- only baselines adapted from state-of-the-art schemes, our
algorithm achieves up to $24\%$ fuel saving (from path, speed planning and
platooning), with an average optimality gap no larger than $0.8\%$. The
results demonstrate the effectiveness of our approach. It is an interesting
direction to investigate how the approach in this paper can be extended to the
general k-truck platooning settings, by for example dividing the k trucks into
multiple groups of two and separately applying the approach to each group for
fuel consumption minimization.

## References

  * [1] American Truck Association  “ATA american trucking trends”  American Trucking Associations, 2020  URL: https://www.trucking.org/news-insights/ata-american-trucking-trends-2020
  * [2] World Bank  “Gross domestic product 2019”, 2019  URL: https://databank.worldbank.org/data/download/GDP.pdf
  * [3] N. Williams and D. Murray  “An Analysis of the Operational Costs of Trucking: 2020 Update”, 2020  URL: https://truckingresearch.org/wp-content/uploads/2020/11/ATRI-Operational-Costs-of-Trucking-2020.pdf
  * [4] International Energy Agency  “The Future of Trucks”, 2017  URL: https://www.oecd-ilibrary.org/content/publication/9789264279452-en
  * [5] A. Alam, J. Mårtensson and K.. Johansson  “Look-ahead cruise control for heavy duty vehicle platooning”  In _16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013)_ , 2013, pp. 928–935
  * [6] B. Besselink et al.  “Cyber–Physical Control of Road Freight Transport”  In _Proceedings of the IEEE_ 104.5, 2016, pp. 1128–1141
  * [7] V. Turri, B. Besselink and K.. Johansson  “Cooperative Look-Ahead Control for Fuel-Efficient and Safe Heavy-Duty Vehicle Platooning”  In _IEEE Transactions on Control Systems Technology_ 25.1, 2017, pp. 12–28
  * [8] C. Bonnet and H. Fritz  “Fuel Consumption Reduction in a Platoon: Experimental Results with two Electronically Coupled Trucks at Close Spacing”  In _SAE Technical Paper_ SAE International, 2000
  * [9] M.. Lammert et al.  “Effect of Platooning on Fuel Consumption of Class 8 Vehicles Over a Range of Speeds, Following Distances, and Mass”  In _SAE Int. J. Commer. Veh._ 7 SAE International, 2014, pp. 626–639
  * [10] A. Alam et al.  “Heavy-Duty Vehicle Platooning for Sustainable Freight Transportation: A Cooperative Method to Enhance Safety and Efficiency”  In _IEEE Control Systems Magazine_ 35.6, 2015, pp. 34–56
  * [11] P. Vegendla et al.  “Investigation of Aerodynamic Influence on Truck Platooning”  In _SAE Technical Paper: 2015-01-2895_ , 2015
  * [12] S. Tsugawa, S. Jeschke and S.. Shladover  “A Review of Truck Platooning Projects for Energy Savings”  In _IEEE Transactions on Intelligent Vehicles_ 1.1, 2016, pp. 68–77
  * [13] B. van Arem, C… van Driel and R. Visser  “The Impact of Cooperative Adaptive Cruise Control on Traffic-Flow Characteristics”  In _IEEE Transactions on Intelligent Transportation Systems_ 7.4, 2006, pp. 429–436
  * [14] S. Tsugawa, S. Kato and K. Aoki  “An automated truck platoon for energy saving”  In _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2011, pp. 4109–4114
  * [15] M.. Tunnell  “Estimating Truck-Related Fuel Consumption and Emissions in Maine: A Comparative Analysis for Six-Axle, 100,000 Pound Vehicle Configuration”  In _Proc. TRB Annual Meeting_ , 2011
  * [16] Amazon  “Place an Order With Guaranteed Delivery”  URL: https://www.amazon.com/gp/help/customer/display.html/ref=hp_left_v4_sib?ie=UTF8&nodeId=201117390
  * [17] B.. Ashby  “Protecting Perishable Foods during Transport by Truck”  U.S. Department of Agriculture, 2006  URL: https://www.ams.usda.gov/sites/default/files/media/TransportPerishableFoodsbyTruck%5C%5B1%5C%5D.pdf
  * [18] W. Mallett  “Freight Performance Measurement: Travel Time in Freight-Significant Corridors”  U.S. Federal Highway Administration, 2006  URL: https://ops.fhwa.dot.gov/freight/freight_analysis/perform_meas/fpmtraveltime/index.htm
  * [19] Doratha E. Drake and Stefan Hougardy  “On approximation algorithms for the terminal Steiner tree problem”  In _Information Processing Letters_ 89.1, 2004, pp. 15–18
  * [20] Jeffrey Larson, Todd Munson and Vadim Sokolov  “Coordinated platoon routing in a metropolitan network”  In _2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing_ , 2016, pp. 73–82
  * [21] S. van de Hoef, K.. Johansson and D.. Dimarogonas  “Fuel-optimal centralized coordination of truck platooning based on shortest paths”  In _2015 American Control Conference (ACC)_ , 2015, pp. 3740–3745
  * [22] Sebastian Van De Hoef, Karl Henrik Johansson and Dimos V. Dimarogonas  “Coordinating Truck Platooning by Clustering Pairwise Fuel-Optimal Plans”  In _2015 IEEE 18th International Conference on Intelligent Transportation Systems_ , 2015, pp. 408–415
  * [23] K. Liang, J. Mårtensson and K.. Johansson  “Heavy-Duty Vehicle Platoon Formation for Fuel Efficiency”  In _IEEE Transactions on Intelligent Transportation Systems_ 17.4, 2016, pp. 1051–1061
  * [24] S. van de Hoef, K.. Johansson and D.. Dimarogonas  “Fuel-Efficient En Route Formation of Truck Platoons”  In _IEEE Transactions on Intelligent Transportation Systems_ 19.1, 2018, pp. 102–112
  * [25] J. Larson, C. Kammer, K. Liang and K.. Johansson  “Coordinated route optimization for heavy-duty vehicle platoons”  In _16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013)_ , 2013, pp. 1196–1202
  * [26] E. Larsson, G. Sennton and J. Larson  “The vehicle platooning problem: Computational complexity and heuristics”  In _Transportation Research Part C: Emerging Technologies_ 60, 2015, pp. 258–277
  * [27] F. Luo, J. Larson and T. Munson  “Coordinated platooning with multiple speeds”  In _Transportation Research Part C: Emerging Technologies_ 90, 2018, pp. 213–225
  * [28] Nils Boysen, Dirk Briskorn and Stefan Schwerdfeger  “The identical-path truck platooning problem”  In _Transportation Research Part B: Methodological_ 109, 2018, pp. 26–39
  * [29] Fengqiao Luo and Jeffrey Larson  “A repeated route-then-schedule approach to coordinated vehicle platooning: Algorithms, valid inequalities and computation”  In _Operations Research_ INFORMS, 2021
  * [30] W. Zhang, E. Jenelius and X. Ma  “Freight transport platoon coordination and departure time scheduling under travel time uncertainty”  In _Transportation Research Part E: Logistics and Transportation Review_ 98, 2017, pp. 1–23
  * [31] Rune Larsen, Jeppe Rich and Thomas Kjær Rasmussen  “Hub-based truck platooning: Potentials and profitability”  In _Transportation Research Part E: Logistics and Transportation Review_ 127, 2019, pp. 249–264
  * [32] 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_ , 2016, pp. 46–57
  * [33] Abtin Nourmohammadzadeh and Sven Hartmann  “Fuel-efficient truck platooning by a novel meta-heuristic inspired from ant colony optimisation”  In _Soft Computing_ 23, 2018, pp. 1–14
  * [34] A. Nourmohammadzadeh and S. Hartmann  “Fuel Efficient Truck Platooning with Time Restrictions and Multiple Speeds Solved by a Particle Swarm Optimisation”  In _International Conference on Theory and Practice of Natural Computing_ , 2018, pp. 188–200
  * [35] Xi Xiong, Junyi Sha and Li Jin  “Optimizing coordinated vehicle platooning: An analytical approach based on stochastic dynamic programming”  In _Transportation Research Part B: Methodological_ 150, 2021, pp. 482–502
  * [36] Woo Jin Lee, Sung Il Kwag and Young Dae Ko  “The optimal eco-friendly platoon formation strategy for a heterogeneous fleet of vehicles”  In _Transportation Research Part D: Transport and Environment_ 90, 2021, pp. 102664
  * [37] Marcel Sala and Francesc Soriguera  “Capacity of a freeway lane with platoons of autonomous vehicles mixed with regular traffic”  In _Transportation Research Part B: Methodological_ 147, 2021, pp. 116–131
  * [38] Jiazu Zhou and Feng Zhu  “Analytical analysis of the effect of maximum platoon size of connected and automated vehicles”  In _Transportation Research Part C: Emerging Technologies_ 122 Elsevier, 2021, pp. 102882
  * [39] Anirudh Kishore Bhoopalam, Niels Agatz and Rob Zuidwijk  “Planning of truck platoons: A literature review and directions for future research”  In _Transportation Research Part B: Methodological_ 107, 2018, pp. 212–228
  * [40] Ricardo, TRL and TTR  “HEAVY VEHICLE PLATOONS ON UK ROADS”, 2014  URL: https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/637361/truck-platooning-uk-feasibility-study.pdf
  * [41] Carl Crane, Jennifer Bridge and Richard Bishop  “Driver Assistive Truck Platooning: Considerations for Florida State Agencies”, 2018  URL: https://fdotwww.blob.core.windows.net/sitefinity/docs/default-source/content/legislative/documents/datp.pdf?sfvrsn=971162d9_0
  * [42] Jack Roberts, Rick Mihelic and Mike Roeth  “CONFIDENCE REPORT: Two-Truck Platooning”, 2016  URL: https://nacfe.org/wp-content/uploads/2018/02/TE-Platooning-CR-FINAL-_0.pdf
  * [43] G. Janssen, J. Zwijnenberg, I. Blankers and J.. Kruijff  “Truck platooning: driving the future of transportation”, 2015  URL: http://resolver.tudelft.nl/uuid:778397eb-59d3-4d23-9185-511385b91509
  * [44] J. Andersson, C. Englund and A. Voronov  “Study of communication needs in interaction between trucks and surrounding traffic in platooning”, 2017  URL: https://www.drivesweden.net/sites/default/files/content/final_report_-_40016_submitted.pdf
  * [45] M. Zhou, H. Jin and W. Wang  “A review of vehicle fuel consumption models to evaluate eco-driving and eco-routing”  In _Transportation Research Part D: Transport and Environment_ 49 Elsevier, 2016, pp. 203–218
  * [46] L Cachón and E Pucher  “Fuel consumption simulation model of a CNG vehicle based on real-world emission measurement”, 2007
  * [47] J.. Heywood  “Internal combustion engine fundamentals”  McGraw-Hill Education, 2018  URL: https://www.accessengineeringlibrary.com/content/book/9781260116106
  * [48] Hesham A. Rakha et al.  “Virginia Tech Comprehensive Power-Based Fuel Consumption Model: Model development and testing”  In _Transportation Research Part D: Transport and Environment_ 16.7, 2011, pp. 492–503
  * [49] J.. Moskwa and J.. Hedrick  “Modeling and validation of automotive engines for control algorithm development”  In _Journal of Dynamic Systems, Measurement, and Control_ , 1992
  * [50] Ge Guo and Qiong Wang  “Fuel-Efficient En Route Speed Planning and Tracking Control of Truck Platoons”  In _IEEE Transactions on Intelligent Transportation Systems_ 20.8, 2019, pp. 3091–3103
  * [51] B. Saerens, H. Rakha, K. Ahn and E. Den Bulck  “Assessment of alternative polynomial fuel consumption models for use in intelligent transportation systems applications”  In _Journal of Intelligent Transportation Systems_ 17.4 Taylor & Francis, 2013, pp. 294–303
  * [52] E. Hellström, M. Ivarsson, J. Åslund and L. Nielsen  “Look-ahead control for heavy trucks to minimize trip time and fuel consumption”  In _Control Engineering Practice_ 17.2 Elsevier, 2009, pp. 245–254
  * [53] Sangjun Park et al.  “Development of fuel and emission models for high speed heavy duty trucks, light duty trucks, and light duty vehicles”  In _13th International IEEE Conference on Intelligent Transportation Systems_ , 2010, pp. 25–32
  * [54] K. Post, J.. Kent, J. Tomlin and N. Carruthers  “Fuel consumption and emission modelling by power demand and a comparison with other models”  In _Transportation Research Part A: General_ 18.3 Elsevier, 1984, pp. 191–213
  * [55] W.. Faris et al.  “Vehicle fuel consumption and emission modelling: an in-depth literature review”  In _International Journal of Vehicle Systems Modelling and Testing_ 6.3-4 Inderscience Publishers Ltd, 2011, pp. 318–395
  * [56] B. Piccoli, K. Han, T.. Friesz and T. Yao  “Estimating fuel consumption and emissions via traffic data from mobile sensors”  In _2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2013, pp. 472–477
  * [57] D… Leung and D.. Williams  “Modelling of motor vehicle fuel consumption and emissions using a power-based model”  In _Urban Air Quality: Measurement, Modelling and Management_ Springer, 2000, pp. 21–29
  * [58] K. Ahn, H. Rakha, A. Trani and M. Aerde  “Estimating vehicle fuel consumption and emissions based on instantaneous speed and acceleration levels”  In _Journal of Transportation Engineering_ 128.2 American Society of Civil Engineers, 2002, pp. 182–190
  * [59] L. Pelkmans et al.  “Development of a simulation tool to calculate fuel consumption and emissions of vehicles operating in dynamic conditions”, 2004
  * [60] L. Deng, M.. Hajiesmaili, M. Chen and H. Zeng  “Energy-Efficient Timely Transportation of Long-Haul Heavy-Duty Trucks”  In _IEEE Transactions on Intelligent Transportation Systems_ 19.7, 2018, pp. 2099–2113
  * [61] Qingyu Liu, Haibo Zeng and Minghua Chen  “Energy-Efficient Timely Truck Transportation for Geographically-Dispersed Tasks”  In _IEEE Transactions on Intelligent Transportation Systems_ 21.12, 2020, pp. 5148–5159
  * [62] Edward K Nam and Robert Giannelli  “Fuel consumption modeling of conventional and advanced technology vehicles in the physical emission rate estimator (PERE)”  In _US Environmental Protection Agency_ , 2005
  * [63] S. Ardenkani, Ezra Hauer and B. Jamei  “Traffic impact models”  In _Traffic Flow Theory: A State-of-the Art Report_ 7, 2001, pp. 7–24
  * [64] F. An and M. Ross  “MODEL OF FUEL ECONOMY WITH APPLICATIONS TO DRIVING CYCLES AND TRAFFIC MANAGEMENT”  In _Transportation Research Record_ , 1993
  * [65] Huanyu Yue  “MESOSCOPIC FUEL CONSUMPTION AND EMISSION MODELING”, 2008  URL: http://hdl.handle.net/10919/26695
  * [66] David Wenzhong Gao, Chris Mi and Ali Emadi  “Modeling and simulation of electric and hybrid vehicles”  In _Proceedings of the IEEE_ 95.4 IEEE, 2007, pp. 729–745
  * [67] Yu Marco Nie and Qianfei Li  “An eco-routing model considering microscopic vehicle operating conditions”  In _Transportation Research Part B: Methodological_ 55 Elsevier, 2013, pp. 154–170
  * [68] Emrah D., Tolga B. and Gilbert Laporte  “A comparative analysis of several vehicle emission models for road freight transportation”  In _Transportation Research Part D: Transport and Environment_ Elsevier, 2011
  * [69] Antti Lajunen  “Energy consumption and cost-benefit analysis of hybrid and electric city buses”  In _Transportation Research Part C: Emerging Technologies_ 38 Elsevier, 2014, pp. 1–15
  * [70] Guangchuan Yang, Hao Xu, Zhongren Wang and Zong Tian  “Truck acceleration behavior study and acceleration lane length recommendations for metered on-ramps”  In _International Journal of Transportation Science and Technology_ 5.2, 2016, pp. 93–102
  * [71] M. Bern and P. Plassmann  “The Steiner problem with edge lengths 1 and 2”  In _Information Processing Letters_ 32.4, 1989, pp. 171–176
  * [72] S. Boyd, L. Xiao and A. Mutapcic  “Subgradient Methods”  In _Lecture Notes of EE392o, Stanford University, Autumn Quarter_ , 2003  URL: https://web.stanford.edu/class/ee392o/subgrad_method.pdf
  * [73] M. Bazaraa and H.. Sherali  “On the choice of step size in subgradient optimization”  In _European Journal of Operational Research_ 7.4, 1981, pp. 380–388
  * [74] P. Vaidya  “Speeding-up Linear Programming Using Fast Matrix Multiplication”  In _Proceedings of the 30th Annual Symposium on Foundations of Computer Science_ , SFCS ’89  USA: IEEE Computer Society, 1989, pp. 332–337
  * [75] J.. Teresco  “The Clinched Highway Mapping (CHM) Project”  URL: http://cmap.m-plex.com/
  * [76] Kenworth  “Kenworth T800 vehicle”  URL: http://www.kenworth.com/trucks/t800
  * [77] U.S. Survey  “USGS Elevation Point Query Service”  URL: http://nationalmap.gov/epqs/
  * [78] T. Markel et al.  “ADVISOR: A SYSTEMS ANALYSIS TOOL FOR ADVANCED VEHICLE MODELING”  In _Journal of Power Sources_ 110 Elsevier, 2002, pp. 255–266
  * [79] W. Xu, Q. Liu, M. Chen and H. Zeng  “Ride the Tide of Traffic Conditions: Opportunistic Driving Improves Energy Efficiency of Timely Truck Transportation”  In _Proceedings of the 6th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation_ , 2019, pp. 169–178
  * [80] Brian McAuliffe, Mark Croken, Mojtaba Ahmadi-Baloutaki and Arash Raeesi  “Fuel-economy testing of a three-vehicle truck platooning system”, 2017
  * [81] Oak Ridge National Laboratory  “Freight Analysis Framework Version 5”  URL: https://faf.ornl.gov/faf5/
  * [82] Wikipedia contributors  “United States Numbered Highway System — Wikipedia, The Free Encyclopedia”, 2019  URL: https://en.wikipedia.org/wiki/United_States_Numbered_Highway_System
  * [83] U.S. of Transportation  “Average Daily Long-Haul Freight Traffic on the National Highway System: 2015 Map”, 2015  URL: https://ops.fhwa.dot.gov/freight/freight_analysis/nat_freight_stats/nhsavglhft2015.htm
  * [84] V. Vazirani  “Approximation algorithms”  Springer, 2001  URL: http://doi.org/10.1007/978-3-662-04565-7
  * [85] E.. Dijkstra  “A Note on Two Problems in Connexion with Graphs”  In _Numer. Math._ 1.1 Berlin, Heidelberg: Springer-Verlag, 1959, pp. 269–271
  * [86] M. Barbehenn  “A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices”  In _IEEE Transactions on Computers_ 47.2, 1998, pp. 263
  * [87] R. Hassin  “Approximation Schemes for the Restricted Shortest Path Problem”  In _Mathematics of Operations Research_ 17.1 INFORMS, 1992, pp. 36–42

##  VII Appendix

###  VII-A Platooning Example

Here, we introduce a simple example to illustrate the benefits of considering
all the design spaces in this paper. All the parameters of this simple example
are presented in Fig. 7. The comparison is summarized in Tab. IV.

Figure 7: A two-truck platooning instance with _instant fuel consumption rate defined as fuel consumption per unit time function_ $f_{e}(v)=4\cdot 10^{-4}v^{2}-6\cdot 10^{-3}v+1$, where $v$ is the driving speed on road segment $e$. _Then total fuel cost function_ for each edge is $c_{e}(t)=4\cdot 10^{-4}(D_{e}/t)^{2}-6\cdot 10^{-3}(D_{e}/t)+1$, where $D_{e}$ is the length of the road segment $e$ and $t$ is the driving time spent on $e$. The optimal speed on each edge is 50 mile per hour. The solid lines indicate the optimal platooning solution. | Shortest Path | Non-Departure Coordination | Departure Coordination
---|---|---|---
$\mathcal{P}_{1}$ | $s_{1}\rightarrow d_{1}$ | $s_{1}\rightarrow m\rightarrow p\rightarrow d_{1}$ | $s_{1}\rightarrow m\rightarrow p\rightarrow d_{1}$
$\mathcal{P}_{2}$ | $s_{2}\rightarrow d_{2}$ | $s_{2}\rightarrow m\rightarrow p\rightarrow d_{2}$ | $s_{2}\rightarrow m\rightarrow p\rightarrow d_{2}$
$\mathcal{V}_{1}$ | 50 | 63.25 $\rightarrow$ 50 $\rightarrow$ 50 | 50 $\rightarrow$ 50 $\rightarrow$ 50
$\mathcal{V}_{2}$ | 50 | 31.62 $\rightarrow$ 50 $\rightarrow$ 50 | 50 $\rightarrow$ 50 $\rightarrow$ 50
$\mathcal{T}_{1}$ | 30 | $3.16\rightarrow 20\rightarrow 7$ | $4\rightarrow 20\rightarrow 7$
$\mathcal{T}_{2}$ | 30 | $3.16\rightarrow 20\rightarrow 9$ | wait 2 hours $\rightarrow 2\rightarrow 20\rightarrow 9$
Average fuel cost | 51.00 | 49.62 | 49.30
Total fuel saving rate | N.A. | 2.7 % | 3.3%
TABLE IV: Optimal solutions for the two-truck platooning instance under
different scenarios. $\mathcal{P}_{1}$ (respectively $\mathcal{P}_{2}$) refers
to optimal paths for truck 1 (respectively truck 2); $\mathcal{V}_{1}$
(respectively $\mathcal{V}_{2}$) refers to optimal speeds on each edge for
truck 1 (respectively truck 2); $\mathcal{T}_{1}$ (respectively
$\mathcal{T}_{2}$) refers to optimal travel time on each edge for truck 1
(respectively truck 2). Compared to the shortest path solution, the total
fuel-saving rate for each truck is 3.3% when the platooning-fuel-saving rate
in a platoon is 10%. However, the total fuel-saving rate for each truck is
only approximately 2.7% when departure coordination is not allowed.

The average daily long-haul traffic intensity on the US national highway in
8(b) shows that most traffic concentrate on some main highways. Platooning is
likely to happen between these vehicles, therefore saves fuel.

(a)

(b)

Figure 8: (a) Illustration of the US national highway network [82]. (b)
Average daily long-haul traffic on the US national highway [83]. Thickness of
the lines indicates the traffic flow intensity.

###  VII-B Proof of Lemma 1

###### Proof.

Figure 9: Optimal solution where the two trucks platoon twice.

For simplicity of presentation, we use $P$ to denote a path, and $C(P)$ to
denote the total fuel cost on the path. As shown in Fig 9, let $P^{*}$ be an
optimal platoon routing with fuel cost $C(P^{*})$ in which there are two sub-
paths $P_{1}$ and $P_{2}$, and node $p_{1}$ is the splitting point of the
first platoon and node $m_{2}$ is the merging point of second platoon. We
assume the cost for traversing $P_{1}$ is $C(P_{1})$, and traversing $P_{2}$
is $C(P_{2})$. Without loss of generality, we may assume $C(P_{2})\leq
C(P_{1})$. In order to re-platoon at $m_{2}$, the time cost of traversing
$P_{1}$ and $P_{2}$ for the two trucks should be the same. So we can move the
truck running on $P_{1}$ to $P_{2}$ to form a platoon from $p_{1}$ to $m_{2}$.
This forms a new solution $P^{\prime}$. Then, we have

$C(P^{\prime})=C(P^{*})-\eta C(P_{1})+\eta C(P_{2})\leq C(S),$

since $C(P_{2})\leq C(P_{1})$. Since $P$ is the optimal platooning solution,
$C(P^{*})\leq C(P^{\prime})$, therefore, $C(P^{\prime})=C(P^{*})$. This
implies that if the two-truck platooning problem is feasible, there exists an
optimal platooning solution in which the two trucks platoon only once, and
never split and merge for a second time. ∎

###  VII-C Proof of Theorem 1

###### Proof.

Consider the setting where two trucks share the same origin, destination, and
pickup and delivery windows. Under this setting, it is clear that two trucks
platooning from the origin to the destination is optimal. The two-truck
platooning problem then reduces to the single truck fuel minimization problem
[60], which covers the classical restricted shortest path problem (RSP) as a
special case. Since RSP is NP-hard, the two-truck platooning problem is also
NP-hard in general.

Next, we show that the two-truck platooning is _weakly_ NP-hard. Specifically,
we design an FPTAS for the two-truck platooning problem that achieves
$(1+\epsilon)$ approximation ratio (for any $\epsilon>0$) with a time
complexity polynomial in the size of the transportation network and
$1/\epsilon$. The full details are in Appendix VII-H and we briefly discussed
the idea below.

We first design an FPTAS under the setting where the merging point and
splitting point of the platooning are given. Then we obtain an FPTAS for the
general setting by applying the same FPTAS to all possible
$\mathcal{O}(N^{2})$ combinations of merging and splitting points.

More specifically, given the merging point and splitting point, we design an
FPTAS using the standard rounding and scaling technique. The FPTAS consists of
two sub-procedures. First, we divide our two-truck platooning into five
separate RSP problems. For each of the RSP problems with speed planning, we
quantize the edge-e fuel-time function $c_{e}(t_{e})$ to be a staircase
function, where the number of stairs is determined by $\epsilon$. Meanwhile,
the fuel cost is scaled down with a function of $\epsilon$. Using dynamic
programming, we enumerate cost bounded minimum-travel-time paths till the
deadline is satisfied. Note that the time complexity is dominated by the
minimum cost and the cost coordination in the five RSP problems, which is
$\mathcal{O}(N^{4}/\epsilon^{4})$. Then we combine solutions for the five RSP
problems to meet individual deadlines and minimize total fuel cost. It can be
solved by enumerating all possible $\mathcal{O}(N^{2})$ combinations of
merging and splitting points. The overall time complexity is thus
$\mathcal{O}(N^{6}/\epsilon^{4})$. The existence of an FPTAS implies that the
two-truck platooning problem is NP-hard (but) in the weak sense [84]. ∎

###  VII-D Checking Feasibility of Two-truck Platooning Problem

By exploiting Lem. 1, we can efficiently check the feasibility of our problem
using Alg. 2.

1 Set FEASIBLE_FLAG=FALSE.

2 for  _merging node $v_{m}\in V$_ do

3 for  _splitting node $v_{s}\in V$_ do

4 Set the driving time on edge $e$ to be $t_{e}^{lb}$ and find the fastest
sub-path $p_{1}$ from $s_{1}$ to $v_{m}$, the fastest sub-path $p_{2}$ from
$s_{2}$ to $v_{m}$, the fastest sub-path $p_{3}$ from $v_{m}$ to $v_{s}$, the
fastest sub-path $p_{4}$ from $v_{s}$ to $d_{1}$, the fastest sub-path $p_{5}$
from $v_{s}$ to $d_{2}$.

5 Set $\tau_{i}\xleftarrow{}\sum_{e\in p_{i}}t_{e}^{lb},\forall
i\in\\{1,2,3,4,5\\}$

6 if  _$t_{d}^{1}+\tau_{1}+\tau_{3}+\tau_{4}\leq t_{a}^{1}$ and
$t_{d}^{2}+\tau_{2}+\tau_{3}+\tau_{4}\leq t_{a}^{1}$ and
$t_{d}^{1}+\tau_{1}+\tau_{3}+\tau_{5}\leq t_{a}^{2}$ and
$t_{d}^{2}+\tau_{2}+\tau_{3}+\tau_{5}\leq t_{a}^{2}$_ then

7 FEASIBLE_FLAG $\xleftarrow{}$TRUE

8 return FEASIBLE_FLAG

9

10 end if

11

12 end for

13

14 end for

return FEASIBLE_FLAG

Algorithm 2 Feasibility Check Algorithm of Two-truck Platooning Problem
$Eq.~{}\eqref{equ:objective}$

To find the shortest path, we can use the classical Dijkstra’s algorithm [85],
which has a worst-case time complexity of $\mathcal{O}\left(M+N\log N\right)$
[86]. Therefore, the worst case time complexity of Alg. 2 is
$\mathcal{O}\left(N^{2}\left(M+N\log N\right)\right)$.

###  VII-E Proof to Theorem 2

###### Proof.

The idea of the proof is simple. For any given optimal LP solution, we show
that it can be represented as a convex combination of ILP solutions.
Therefore, the main content of this proof is how to find the convex integer
decomposition for an optimal LP solution. In this proof, we use the fact that
the minimum fractional flow of an LP solution is unsplittable, and can be
represented as a fraction of an integer platooning solution. The main
difficulty is to find the merging and splitting points for the minimum
fractional flow in the LP solution. We use depth first search to find the
merging and splitting points corresponding to the minimum fractional flow,
whose time complexity is at most $\mathcal{O}(M)$. Then we remove the current
minimum fractional flow in the LP solution, and do the same thing for the
remaining flow. Eventually, we can decompose the whole LP solution into a
convex combination of integer platooning solutions at most $\mathcal{O}(M)$
steps of search-and-removal. Therefore, for an optimal LP solution, we can
recover an integer solution by selecting the most fuel saving solution in the
process in at most $\mathcal{O}(M^{2})$ time.

We first prove Lem. 2, which will later be used to prove Thm. 2.

######  Lemma 2.

$\forall\left(\vec{x}^{*},\vec{y}^{*},\vec{z}^{*}\right)$ that is an optimal
solution to the relaxed LP problem of the ILP shown in Eq. (10),
$\exists{\theta_{k}\in[0,1]}$, $k\in\mathbb{N}_{K}$ satisfying
$\sum\limits_{k\in\mathbb{N}_{K}}\theta_{k}=1$, such that,

$\displaystyle\left(\vec{x}^{*},\vec{y}^{*},\vec{z}^{*}\right)=\sum\limits_{k\in\mathbb{N}_{K}}\theta_{k}\left(\vec{x}^{k},\mathbf{1}_{v=v_{i_{k}}},\mathbf{1}_{v=v_{j_{k}}}\right),$
(13)

where
$\left(\vec{x}^{k},\mathbf{1}_{v=v_{i_{k}}},\mathbf{1}_{v=v_{j_{k}}}\right)$
is an integer solution to the original ILP problem with merging point
$v_{i_{k}}$ and splitting point $v_{j_{k}}$.

Here, we give a constructive proof to Lem. 2. We use $x^{*,i}_{e},e\in
E,i\in\mathbb{N}_{5}$($x^{k,i}_{e},e\in E,i\in\mathbb{N}_{5}$ resp.) to denote
the variable corresponding to edge $e$ and the sub-path $i$ in the solution
$\vec{x}^{*}$($\vec{x}^{k}$ resp.). We apply Alg. 3 to construct $\theta_{k}$
and their corresponding solutions. We iteratively select the minimum positive
$x_{e}^{i}$ as the coefficient $\theta_{k}$. To construct $\theta_{k}$’s
corresponding integer platooning solution, we execute $6$ searching procedures
step by step. If
$1=\tilde{i}\vcentcolon=\operatorname*{arg\,min}\limits_{i\in\mathbb{N}_{5}}\min\limits_{e\in
E,x_{e}^{i}>0}x_{e}^{i}$, the step-by-step searching procedure is shown as
Alg. 4, where we invoke $\mathrm{SEARCH}$ procedure to construct one sub-path.
For $\tilde{i}$ other than $1$, we can execute the searching procedure in the
same way except for some notation and order rearrangements.

To show that the construction procedure works, we need to show that the
procedure terminates in $\mathcal{O}(M^{2})$ time and when it terminates, the
output $\theta_{k}$ and corresponding solutions are what we desire. In every
step of the while loop in Alg. 3, there is at least one positive $x_{e}^{i}$
set to 0. Since there are at most $\mathcal{O}(M)$ positive $x_{e}^{i}$, the
while loop can be executed for at most $\mathcal{O}(M)$ steps. Within every
step of the while loop, a searching procedure is executed. In every step of
the while loop of Alg. 5, one edge is appended into the edge set $p$ and when
there are no new edges to be added, the procedure stops, so Alg. 5 takes time
$\mathcal{O}(M)$. To sum up, the construction procedure takes time
$\mathcal{O}(M^{2})$. And by the construction process, it naturally holds,

$\left(\vec{x}^{*},\vec{y}^{*},\vec{z}^{*}\right)=\sum\limits_{k\in\mathbb{N}_{K}}\theta_{k}\left(\vec{x}^{k},\mathbf{1}_{v=v_{i_{k}}},\mathbf{1}_{v=v_{j_{k}}}\right),$
(14)

1 Set $k\xleftarrow{}1$

2 Set $x_{e}^{i}\xleftarrow{}x_{e}^{*,i},\forall e\in E,i\in\mathbb{N}_{5}$
while  _true_ do

3 if  _$x_{e}^{i}=0,\forall e\in E,i\in[5]$_ then

4 $\mathrm{break}$

5 end if

6 $\tilde{e},\tilde{i}\xleftarrow{}\operatorname*{arg\,min}\limits_{e\in
E,i\in[5],x_{e}^{i}>0}{x_{e}^{i}}$

7 Set $\theta_{k}\xleftarrow{}x_{\tilde{e}}^{\tilde{i}}$ and construct it’s
corresponding solution
$\left(\vec{x}^{k},\mathbf{1}_{v=v_{i_{k}}},\mathbf{1}_{v=v_{j_{k}}}\right)$

8 Set
$x^{i}_{e}\xleftarrow{}x^{i}_{e}-\theta_{k}x^{k,i}_{e},y_{v_{i_{k}}}\xleftarrow{}y_{v_{i_{k}}}-\theta_{k},z_{v_{j_{k}}}\xleftarrow{}z_{v_{j_{k}}}-\theta_{k}$

9 $k$++

10 end while

Algorithm 3 Construct coefficients $\theta_{k}$ and their corresponding
integer solutions.

1
$p_{1},v_{1}\xleftarrow{}\mathrm{SEARCH}(\tilde{e},\tilde{i},\mathrm{{}^{\prime}BACKWARD^{\prime}})$

2
$p_{1}^{\prime},v_{2}\xleftarrow{}\mathrm{SEARCH}(\tilde{e},\tilde{i},\mathrm{{}^{\prime}FORWARD^{\prime}})$

3 $p_{1}\xleftarrow{}p_{1}\cup p_{1}^{\prime}$

4 Take $\tilde{e}_{2}\in\textbf{In}(v_{2})$ satisfying
$x_{\tilde{e}_{2}}^{2}\geq x_{\tilde{e}}^{1}$

5
$p_{2},v_{3}\xleftarrow{}\mathrm{SEARCH}(\tilde{e}_{2},2,\mathrm{{}^{\prime}BACKWARD^{\prime}})$

6 Take $\tilde{e}_{3}\in\textbf{Out}(v_{2})$ satisfying
$x_{\tilde{e}_{3}}^{3}\geq x_{\tilde{e}}^{1}$

7
$p_{3},v_{4}\xleftarrow{}\mathrm{SEARCH}(\tilde{e}_{3},3,\mathrm{{}^{\prime}FORWARD^{\prime}})$

8 Take $\tilde{e}_{4}\in\textbf{Out}(v_{4})$ satisfying
$x_{\tilde{e}_{4}}^{4}\geq x_{\tilde{e}}^{1}$

9
$p_{4},v_{5}\xleftarrow{}\mathrm{SEARCH}(\tilde{e}_{4},4,\mathrm{{}^{\prime}FORWARD^{\prime}})$

10 Take $\tilde{e}_{5}\in\textbf{Out}(v_{4})$ satisfying
$x_{\tilde{e}_{5}}^{5}\geq x_{\tilde{e}}^{1}$

11
$p_{5},v_{6}\xleftarrow{}\mathrm{SEARCH}(\tilde{e}_{5},5,\mathrm{{}^{\prime}FORWARD^{\prime}})$

12 Set $\theta_{k}\xleftarrow{}x_{\tilde{e}}^{1}$

13 Set $x^{k,i}_{e}\xleftarrow{}\mathbf{1}_{e\in p_{i}},e\in
E,i\in\mathbb{N}_{5}$ and
$v_{i_{k}}\xleftarrow{}v_{2},v_{j_{k}}\xleftarrow{}v_{4}$

Algorithm 4 Obtaining $\theta_{k}$ and its corresponding solution with
$\tilde{i}=1$.

1 while  _true_ do

2 Initialize the forward path’s edge set
$p\xleftarrow{}\left\\{\tilde{e}\right\\}$

3 while  _true_ do

4 if  _$s$ =’FORWARD’_ then

5 $v\xleftarrow{}\textbf{head}(\tilde{e})$

6 $\tilde{E}\xleftarrow{}\textbf{Out}(v)$

7

8 else

9 $v\xleftarrow{}\textbf{tail}(\tilde{e})$

10 $\tilde{E}\xleftarrow{}\textbf{Out}(v)$

11

12 end if

13 if  _$\exists e^{\prime}\in\tilde{E}$ such that $x_{e^{\prime}}^{i}\geq
x_{\tilde{e}}^{i}$ and ${e^{\prime}}\notin p$_ then

14 $p\xleftarrow{}p\cup\\{e^{\prime}\\}$

15 $\tilde{e}\xleftarrow{}e^{\prime}$

16

17 else

18 break

19 end if

20

21 end while

22

23 end while

Return$(p,v)$

Algorithm 5 $\mathrm{SEARCH}$($\tilde{e}$, $\tilde{i}$, $s$)

We use $G(\vec{x})$ to denote the objective function. Suppose the optimal
solution of the relaxed LP is
$\left(\vec{x}^{*},\vec{y}^{*},\vec{z}^{*}\right)=\left(\left(x_{e}^{*,1},x_{e}^{*,2},x_{e}^{*,3},x_{e}^{*,4},x_{e}^{*,5}\right)_{e\in
E},(y_{v}^{*})_{v\in V},(z_{v}^{*})_{v\in V}\right)$. And we define
$\vec{x}^{*,i}\coloneqq\left(x_{e}^{*,i}\right)_{e\in E}$.

We define $\vec{x}^{*,i}$($\vec{x}^{k,i},\forall k\in\mathbb{N}_{K}$ resp.) as
$(x^{*,i}_{e})$($x^{k,i}_{e},\forall k\in\mathbb{N}_{K}$ resp.), $\forall e\in
E,i\in\mathbb{N}_{5}$. By Lem. 2,
$\left(\vec{x}^{*},\vec{y}^{*},\vec{z}^{*}\right)$ can be decomposed into
convex combination of some basic platooning solutions.

$\displaystyle\vec{x}^{*}$
$\displaystyle=\left(\vec{x}^{*,1},\vec{x}^{*,2},\vec{x}^{*,3},\vec{x}^{*,4},\vec{x}^{*,5}\right)$
$\displaystyle=\sum_{k\in\mathbb{N}_{K}}\theta_{k}\left(\vec{x}^{k,1},\vec{x}^{k,2},\vec{x}^{k,3},\vec{x}^{k,4},\vec{x}^{k,5}\right).$

Since the objective function is linear in $\vec{x}$, we have

$\displaystyle G(\vec{x}^{*})$
$\displaystyle=G\left(\vec{x}^{*,1},\vec{x}^{*,2},\vec{x}^{*,3},\vec{x}^{*,4},\vec{x}^{*,5}\right)$
$\displaystyle=\sum_{k\in\mathbb{N}_{K}}\theta_{k}G\left(\vec{x}^{k,1},\vec{x}^{k,2},\vec{x}^{k,3},\vec{x}^{k,4},\vec{x}^{k,5}\right).$

So $\exists k^{*}$, such that $\theta_{k^{*}}>0$ and

$\displaystyle G\left(\vec{x}^{*}\right)\geq
G\left(\vec{x}^{k^{*},1},\vec{x}^{k^{*},2},\vec{x}^{k^{*},3},\vec{x}^{k^{*},4},\vec{x}^{k^{*},5}\right).$

We fix merging point and splitting point to be ${v}_{i_{k^{*}}}$ and
${v}_{j_{k^{*}}}$. By the linearity of objective function $G$ and optimality
of $\vec{x}^{*}$, we have that $\vec{x}^{k^{*},1}$ represents the shortest
path with respect to weight $(w_{{e}}^{1})_{e\in E}$ from $s_{1}$ to
$v_{i_{k^{*}}}$, $\vec{x}^{k^{*},2}$ represents the shortest path with respect
to weight $(w_{{e}}^{2})_{e\in E}$ from $s_{2}$ to $v_{i_{k^{*}}}$,
$\vec{x}^{k^{*},3}$ represents the shortest path with respect to weight
$(w_{{e}}^{3})_{e\in E}$ from $v_{i_{k^{*}}}$ to $v_{j_{k^{*}}}$,
$\vec{x}^{k^{*},4}$ represents the shortest path with respect to weight
$(w_{{e}}^{4})_{e\in E}$ from $v_{j_{k^{*}}}$ to $d_{1}$ and
$\vec{x}^{k^{*},5}$ represents the shortest path with respect to weight
$(w_{{e}}^{5})_{e\in E}$ from $v_{j_{k^{*}}}$ to $d_{2}$. Therefore,
$\left(\left(\vec{x}^{k^{*},1},\vec{x}^{k^{*},2},\vec{x}^{k^{*},3},\vec{x}^{k^{*},4},\vec{x}^{k^{*},5}\right),\left(\textbf{1}_{v=v_{i_{k^{*}}}},\textbf{1}_{v=v_{j_{k^{*}}}}\right)_{v\in
V}\right)$ is an ILP solution. Thus we have

$\displaystyle\mathrm{OPT}_{\mathrm{LP}}$
$\displaystyle=G\left(\vec{x}^{1,*},\vec{x}^{2,*},\vec{x}^{3,*},\vec{x}^{4,*},\vec{x}^{5,*}\right)$
$\displaystyle\geq
G\left(\vec{x}^{k^{*},1},\vec{x}^{k^{*},2},\vec{x}^{k^{*},3},\vec{x}^{k^{*},4},\vec{x}^{k^{*},5}\right)$
$\displaystyle\geq\mathrm{OPT}_{\mathrm{ILP}}.$

Thus we show that optimal value of LP is lower bounded by an ILP solution. So
$\mathrm{OPT}_{\mathrm{LP}}\geq\mathrm{OPT}_{\mathrm{ILP}}$ and naturally we
have $\mathrm{OPT}_{\mathrm{ILP}}\geq\mathrm{OPT}_{\mathrm{LP}}$. Eventually,
$\mathrm{OPT}_{\mathrm{ILP}}=\mathrm{OPT}_{\mathrm{LP}}$.

∎

###  VII-F Proof of Theorem 3

###### Proof.

We follow the proof from the discussion in [72, Section 3.3]. The essence of
the proof is that, for a given iteration budget $K$, the optimal constant step
size $\phi$ is proportional to $1/\sqrt{K}$. Similarly, the optimality gap of
the dual function is also proportional to $1/\sqrt{K}$. Let
$\vec{\lambda}^{*}$ denote the optimal dual variable.We define the norm of
$\vec{\lambda}^{*}$ as $R\triangleq\left\lVert\vec{\lambda}^{*}\right\rVert$
and $H\triangleq 12\left(\sum_{e\in
E}t_{e}^{ub}+\max\left\\{T_{d}^{1},T_{d}^{2}\right\\}-\min\left\\{T_{s}^{1},T_{s}^{2}\right\\}\right)$,
it is easy to verify that,

$R\geq\left\lVert\vec{\lambda}[0]-\vec{\lambda}^{*}\right\rVert=\left\lVert\vec{\lambda}^{*}\right\rVert=R,$
(15)

since $\vec{\lambda}[0]=\vec{0}$. Besides,

$H\geq\left\lVert\dot{\vec{\lambda}}\right\rVert.$ (16)

Furthermore, with the dual subgradient update procedure, we can derive that,

$\displaystyle\left\lVert\vec{\lambda}[i+1]-\vec{\lambda}^{*}\right\rVert^{2}=\left\lVert\vec{\lambda}[i]+\phi\dot{\vec{\lambda}}[i]-\vec{\lambda}^{*}\right\rVert^{2}$
$\displaystyle=\left\lVert\vec{\lambda}[i]-\vec{\lambda}^{*}\right\rVert^{2}+2\phi\dot{\vec{\lambda}}[i]^{T}\left(\vec{\lambda}[i]-\vec{\lambda}^{*}\right)+\phi^{2}\left\lVert\dot{\vec{\lambda}}[i]\right\rVert^{2}$
$\displaystyle\leq\left\lVert\vec{\lambda}[i]-\vec{\lambda}^{*}\right\rVert^{2}-2\phi\left(D^{*}-{D}_{i}\right)+\phi^{2}\left\lVert\dot{\vec{\lambda}}[i]\right\rVert^{2},$
(17)

where $D_{i}\triangleq D\left(\vec{\lambda}[i]\right)$. The last inequality
follows from the definition of subgradient, which gives
$D^{*}-{D}_{i}\leq\dot{\vec{\lambda}}[i]^{T}\left(\vec{\lambda}^{*}-\vec{\lambda}[i]\right)$.

By applying $Eq.~{}\eqref{inq:dual_rec}$ recursively, we get

$\displaystyle\left\lVert\vec{\lambda}[K+1]-\vec{\lambda}^{*}\right\rVert^{2}$
$\displaystyle\leq\left\lVert\vec{\lambda}[1]-\vec{\lambda}^{*}\right\rVert^{2}-2\phi\sum_{i=1}^{K}\left(D^{*}-{D}_{i}\right)$
$\displaystyle\quad+\phi^{2}\sum_{i=1}^{K}\left\lVert\dot{\vec{\lambda}}[i]\right\rVert^{2}.$
(18)

Using the fact that
$\left\lVert\vec{\lambda}[K+1]-\vec{\lambda}^{*}\right\rVert^{2}\geq 0$,
$\left\lVert\vec{\lambda}[1]-\vec{\lambda}^{*}\right\rVert^{2}\leq R$ and
$H\geq\left\lVert\dot{\vec{\lambda}}\right\rVert$, we have,

$2\phi\sum_{i=1}^{K}\left(D^{*}-{D}_{i}\right)\leq R^{2}+\phi^{2}KH^{2}.$ (19)

Since $D^{*}-{D}_{i}\geq D^{*}-\bar{D}_{K}$, we have

$D^{*}-\bar{D}_{K}\leq\frac{R^{2}+\phi^{2}KH^{2}}{2\phi K}.$ (20)

Therefore, with step sizes $\phi_{i}=1/\sqrt{{K}}$, $i\in\mathbb{N}_{K}$,
there exists a constant $\xi>0$ such that

$D^{*}-\bar{D}_{K}\leq\xi/\sqrt{K},$

where $\xi$ can be set to be $\frac{R^{2}+H^{2}}{2}$. ∎

###  VII-G Proof to Theorem 4

###### Proof.

First, we show the result for case 1. According to the weak duality, any dual
function value is a lower bound of the optimal cost $OPT$, namely it holds
that

$D(\vec{\lambda})\leq OPT.$

For case 1, the stop condition $\dot{\lambda}_{j}[k^{*}]=0$,$\forall
j\in\mathbb{N}_{4}$ implies that
$\delta_{i}^{*}(\vec{\lambda}[k^{*}])=0,\forall i\in\mathbb{N}_{4}$. The dual
function value $D(\vec{\lambda})$ will be

$D(\vec{\lambda})=c(\bar{P})+\sum_{j=1}^{4}\lambda_{j}[k^{*}]\delta_{i}^{*}(\vec{\lambda}[k^{*}])=c(\bar{P})\leq
OPT.$

where $\lambda_{j}[k^{*}]$ is the dual variable when the dual subgradient
algorithm stops. Since $\bar{P}$ is a feasible function for our two-truck
platooning problem, we have $c(\bar{P})\geq OPT$. Therefore $c(\bar{P})=OPT$,
we will get the optimal solution if the algorithm returns at line 1.

For case 2, by the same reasoning, we know $\bar{P}$ is a feasible solution,
$c(\bar{P})\geq D^{*}$, where $D^{*}$ is the optimal dual function value. By
weak duality, $D^{*}\leq OPT$. The optimality gap between $\bar{P}$ and the
optimal solution $OPT$ will be

$\displaystyle c(\bar{P})-OPT$ $\displaystyle\leq c(\bar{P})-D^{*}$
$\displaystyle\leq c(\bar{P})-D^{*}$
$\displaystyle=D(\vec{\lambda})-\sum_{j=1}^{4}\lambda_{j}[k^{*}]\delta_{j}-D^{*}$
$\displaystyle\leq-\sum_{j=1}^{4}\lambda_{j}[k^{*}]\delta_{j}$

The optimality gap between our solution $c(\bar{P})$ and the optimal solution
$OPT$ is bounded by the primal-dual gap, which is

$B=c(\bar{P}^{\prime})-D^{*}=-\sum_{j=1}^{4}\lambda_{j}[k^{*}]\delta_{j}.$

Note that $\bar{P}$ is feasible only when $\delta_{j}\leq 0$. ∎

###  VII-H FPTAS

In this section, we provide an FPTAS for the fixed merging point and splitting
point two-truck platooning problem, which is an extension of FPTASes proposed
in [87, 60, 61]. Like RSP, we observe that our two-truck platooning problem
also satisfies Bellman’s principle of optimality, and can be solved by dynamic
programming. In fact, when the merging point and splitting point are fixed,
our two-truck platooning problem can be divided into interdependent 5 RSP
problems. The difficulty for our two-truck platooning problem is that the
deadline constraints of the 5 RSP problems are coupled. So our two-truck
platooning problem is quite similar to the multi-task problem in [61] for
which the deadlines constraints are also interrelated. The only difference
between our two-truck platooning problem and the multi-task problem in [61] is
that the deadline constraints are not coupled sequentially. Therefore,
compared to the FPTAS proposed in Section 3 of [61], we can design our FPTAS
just by changing the coordination of traveling time for each RSP problem.

1 Set $S\xleftarrow{}\frac{L\epsilon}{N+1}$,
$\hat{U}\xleftarrow{}\lfloor{\frac{U}{S}}\rfloor+5(N+1)$,
$p_{test}\xleftarrow{}$ NULL

2 for  _$\forall e\in E$ , $\forall\hat{c}=1,2,...\hat{U}$_ do

3 $\hat{c}_{e}^{l}\xleftarrow{}\lceil c_{e}(t_{e}^{u})/S\rceil$,
$\hat{c}_{e}^{u}\xleftarrow{}\lceil c_{e}(t_{e}^{l})/S\rceil$

4 $t_{e}^{i}(\hat{c})\xleftarrow{}\left\\{\begin{aligned}
t_{e}^{l},&\quad\hat{c}\geq\hat{c}_{e}^{u};\\\
c_{e}^{-1}(\hat{c}S),&\quad\hat{c}_{e}^{l}\leq\hat{c}\geq\hat{c}_{e}^{u};\\\
+\infty,&\quad\hat{c}<\hat{c}_{e}^{l}.\end{aligned}\right.$

5

6 end for

7Set $g_{i}(v,0)\xleftarrow{}+\infty$, $\forall v\neq s_{i}$, $\forall
i\in\mathbb{N}_{5}$

8 Set $g_{i}(v,0)\xleftarrow{}0$, $\forall v=s_{i}$, $\forall
i\in\mathbb{N}_{5},\forall\hat{c}=1,2,...,\hat{U},\forall v\in V$

9 for  _$\forall i\in\mathbb{N}_{5},\forall\hat{c}=1,2,...,\hat{U},\forall
v\in V$_ do

10 $g_{i}(v,\hat{c})\xleftarrow{}g_{i}(v,\hat{c}-1)$

11 for  _$\forall e=(u,v)\in E$ , $\forall\bar{c}=1,...,\hat{c}$_ do

12
$g_{i}(v,\hat{c})\xleftarrow{}\min\big{\\{}g_{i}(v,\hat{c}),g_{i}(u,\hat{c}-\bar{c})\big{\\}}$

13

14 end for

15

16 end for

17for  _$\bar{c}_{1}$ = 1,…, $\hat{U}$_ do

18 for  _$\bar{c}_{2}$ = 1, …, $\hat{U}-\bar{c}_{1}$_ do

19 for  _$\bar{c}_{4}$ = 1, …, $\hat{U}-\bar{c}_{1}-\bar{c}_{2}$_ do

20 for  _$\bar{c}_{5}=1,...,\hat{U}-\bar{c}_{1}-\bar{c}_{2}-\bar{c}_{4}$_ do

21
$\bar{c}_{3}=\lfloor(\hat{U}-\bar{c}_{1}-\bar{c}_{2}-\bar{c}_{4}-\bar{c}_{5})/(2-2\eta)\rfloor$

22
$T_{1}\xleftarrow{}\max\big{\\{}g_{1}(d_{1},\bar{c}_{1}),g_{2}(d_{2},\bar{c}_{2})\big{\\}}+g_{3}(d_{3},\bar{c}_{3})+g_{4}(d_{4},\bar{c}_{4})$

23
$T_{2}\xleftarrow{}\max\big{\\{}g_{1}(d_{1},\bar{c}_{1}),g_{2}(d_{2},\bar{c}_{2})\big{\\}}+g_{3}(d_{3},\bar{c}_{3})+g_{5}(d_{5},\bar{c}_{5})$

24 if  _$t_{d}^{1}+T_{1}\leq t_{a}^{1}$ and $t_{d}^{2}+T_{2}\leq t_{a}^{2}$_
then

25 $p_{test}$ is defined by the solutions for the 5 RSP problems.

26

27 end if

28

29 end for

30

31 end for

32

33 end for

34

35 end for

return $p_{test}$

Algorithm 6 Test(G, L, U, $\epsilon$)

The essence of the FPTAS is to quantize and round down edge costs while the
travel time information is kept. We use dynamic programming to solve the
rounded problem exactly by enumerating the cost-bounded minimum-travel-time
path. The rounding procedure guarantees the optimal cost for the rounded
problem is polynomially bounded of input size, therefore guarantees a
polynomial time complexity. We modify the test procedure of the FPTAS in
Section 3.2 of [61], especially the traveling time coordination for each RSP.
Then we incorporate the rounding and scaling procedure of Algorithm 1 in [61]
to design our FPTAS. The test procedure of our FPTAS is elaborated in Alg 6.
$s_{i}$ and $d_{i}$ denote the source and destination nodes for $i$-th RSP
problem, where the sequence of the 5 RSP problems is the same as defined in
Section 2 Model and problem formulation.

Compared to Algorithm 1 in Section 3 of [61], the only difference is that we
need to coordinate the 5 RSP problems differently. The traveling time
coordination for the 5 RSP problems is presented in the loop of line 15 to
line 28 in Alg 6. The rounding and scaling procedure in Alg 6 guarantees a
polynomial time complexity. The proof is conceivable from Section III of [60]
and Section 3 of [61]. With the test procedure in Alg 6, we follow the same
search structure as in [60] and [61] to find the near-optimal solution for our
two-truck platooning problem. First, we need an initial lower bound LB where
$\textbf{LB}\leq OPT$. Obviously, 0 is a trivial lower bound. However, to
accelerate the binary search, we use the solution for the unconstrained two-
truck platooning problem as the lower bound LB, _i.e._ , the 2 trucks can
drive most efficiently on every edge. For the upper bound, we use the solution
that the 2 trucks drive most inefficiently on every edge. The binary search
procedure is presented in Alg 7. Since the proof for our FPTAS is almost the
same as previous work in Section 3 of [60] and [61], we omit the proof here.

1 Get a lower bound LB and upper bound UB for OPT.

2 $B_{L}\xleftarrow{}\textbf{LB}$

3 $B_{U}\xleftarrow{}\textbf{UB}$

4 while  _$B_{U}/B_{L} >2$_ do

5 $B\xleftarrow{}\sqrt{B_{L}\cdot B_{U}}$

6 if  _Test(G, B, B, $\epsilon$) = NULL_ then

7 $B_{L}\xleftarrow{}B$

8

9 else

10 $B_{U}\xleftarrow{}B$

11

12 end if

13

14 end while

FPTAS $\xleftarrow{}$ Test(G, $B_{L}$, $2B_{U}$, $\epsilon$)

Algorithm 7 An FPTAS

There are three loops in Algorithms 6. The first loop which starts from line 6
has a time complexity of $\mathcal{O}\left(M\hat{U}\right)$, and the second
loop starts from line 6 has a time complexity of
$\mathcal{O}\left(M\hat{U}^{2}\right)$. The time complexity for the third loop
starts from line 6 is $\mathcal{O}\left(\hat{U}^{4}\right)$. Since $\hat{U}$
is $\mathcal{O}\left(\frac{\textbf{UB}(N+1)}{\textbf{LB}\epsilon}\right)$, so
the time complexity for Algorithm 6 is the larger one between
$\mathcal{O}\left(M\frac{\textbf{UB}^{2}(N+1)^{2}}{\textbf{LB}^{2}\epsilon^{2}}\right)$
and
$\mathcal{O}\left(\frac{\textbf{UB}^{4}(N+1)^{4}}{\textbf{LB}^{4}\epsilon^{4}}\right)$.
Algorithm 7 has a time complexity of
$\mathcal{O}\left(\log(\frac{\textbf{UB}}{\textbf{LB}})\right)$. Note that
it’s easy to find a polynomial bounded upper bound UB for our two-truck
platooning problem, like we can simply use the single truck path and speed
planning solution in [60]. Therefore, Algorithm 6 and 7 are an FPTAS for our
two-truck platooning problem.

|  Wenjie Xu is currently a doctoral student at École polytechnique fédérale
de Lausanne (EPFL). He received his MPhil degree in Information Engineering
from The Chinese University of Hong Kong, and B.E. degree in Electronic
Engineering from Tsinghua University in 2018. His research interests lie in
the interface of optimization, control and machine learning, with applications
to building control and intelligent transportation.
---|---
|  Titing Cui is currently a doctoral student at University of Pittsburgh. He
received his M.S. degree in Applied and Computational Mathematics from KTH
Royal Institute of Technology in 2019, and B.S. degree in Mathematics and
Applied Mathematics from Zhejiang University in 2017. His research interests
include optimization and algorithm design in the fields of the intelligent
transportation system, integer programming, revenue management and pricing.
---|---
|  Minghua Chen (S’04 M’06 SM’ 13 F’22) received his B.Eng. and M.S. degrees
from the Department of Electronic Engineering at Tsinghua University. He
received his Ph.D. degree from the Department of Electrical Engineering and
Computer Sciences at University of California Berkeley. He is currently a
Professor of School of Data Science, City University of Hong Kong. Minghua
received the Eli Jury award from UC Berkeley in 2007 (presented to a graduate
student or recent alumnus for outstanding achievement in the area of Systems,
Communications, Control, or Signal Processing) and The Chinese University of
Hong Kong Young Researcher Award in 2013. He also received IEEE ICME Best
Paper Award in 2009, IEEE Transactions on Multimedia Prize Paper Award in
2009, ACM Multimedia Best Paper Award in 2012, and IEEE INFOCOM Best Poster
Award in 2021. He receives the ACM Recognition of Service Award in 2017 and
2020 for the service contribution to the research community. He is currently a
Senior Editor for IEEE Systems Journal, an Area Editor of ACM SIGEnergy Energy
Informatics Review, and an Award Chair of ACM SIGEnergy. Minghua’s recent
research interests include online optimization and algorithms, machine
learning in power systems, intelligent transportation systems, distributed
optimization, and delay-critical networked systems. He is an ACM Distinguished
Scientist and IEEE Fellow.
---|---