The formulation is given in (<ref>) and the definition of notations used in the formulation is
provided in Table <ref>. Note that we assume the order of vehicles in a platoon
does not affect its fuel saving. In the continuous-time formulation, all vehicles are labeled with
positive integers and we only allow a vehicle with a greater index to follow a vehicle with a smaller
index as a convetion. (See the definition of the decision variable $f_{u,v,i,j}$ in Table <ref>.)

maximize         ∑_(i,j)∈∪_v_v (  ∑_v∈_i,j σ^l C_i,j ℓ_v,i,j + ∑_u,v∈_i,j u>v σ^f C_i,j f_u,v,i,j )

subject to:        t_v,O_v ≥T_v^O        ∀v∈,

t_v,D_v ≤T_v^D      ∀v∈,

t_v,j = t_v,i + T_i,j     ∀v∈,  ∀(i,j)∈_v,

t_u,i - t_v,i ≤M(1-f_u,v,i,j)     ∀(i,j)∈⋃_v∈ _v,   ∀u > v∈_i,j,

t_u,i - t_v,i ≥-M(1-f_u,v,i,j)      ∀(i,j)∈⋃_v∈ _v,   ∀u > v∈_i,j,

∑_w∈_i,j: w<v f_v,w,i,j ≤1-ℓ_v,i,j     ∀v∈,  (i,j)∈_v,

∑_u∈_i,j: u>v f_u,v,i,j ≤(λ-1)ℓ_v,i,j     ∀v∈,  (i,j)∈_v,

∑_u∈_i,j: u>v f_u,v,i,j≥ℓ_v,i,j      ∀v∈,  (i,j)∈_v,

f_u,v,i,j∈{0,1}     ∀u,v∈, u>v, ∀(i,j)∈_v,

ℓ_v,i,j∈{0,1}     ∀v∈, ∀(i,j)∈_v,

where the $M$ in constraints (<ref>) and (<ref>) is a big-M coefficient
satisfying $-M\le t_{u,i}-t_{v,i}\le M$ for all $(i,j)\in\cup_v\cR_v$, $u,v\in\cV_{i,j}$ with $u>v$
and any feasible values of $t_{u,i}$ and $t_{v,i}$.

The objective (<ref>) consists of two terms corresponding to
fuel saving of lead and trailing vehicles on each edge, respectively.
Note that maximizing the total fuel saving is equivalent to minimizing the total fuel cost.
Constraints (<ref>)–(<ref>) ensure that vehicle travel times are consistent.
Constraints (<ref>)–(<ref>) ensure that if vehicle $u$
follows vehicle $v$ in a platoon on edge $(i,j)$, they must traverse the edge simultaneously.
Constraint (<ref>) ensures that if vehicle $v$ is a lead vehicle
on an edge, it cannot follow any other vehicles.
If $v$ is not a lead vehicle,
it can follow no more than one vehicle (the lead vehicle) on an edge.
(Note that our formulation does not allow any trailing vehicle to lead another
Constraint (<ref>) enforces that
a vehicle can lead at most $\lambda-1$ other vehicles.
Constraint (<ref>) states that if $v$ is a lead vehicle
on an edge, the number of vehicles following $v$ on that edge must be at least one.

Sets, parameters, and variables for the continuous-time formulation.

Set     Definition

$\cR_v$     route of vehicle $v\in\cV$ (an ordered subset of edges in the route)

$\cN_v$     set of nodes on $\cR_v$, $v\in\cV$

$\cV_{i,j}$     set of vehicles taking the edge $(i,j) \in \cup_{v\in\cV}\cR_v$

Parameter     Definition

$T_v^O,T_v^D,T_{i,j}$     defined in Table <ref>

$\lambda$     maximum number of vehicles permitted in a platoon

$M_{u,v,i,j}$			    a vehicle-pair and edge dependent big-M coefficient

Variable     Definition

$t_{v,O_v}$     departure time of vehicle $v$ from node $O_v$

$t_{v,i}$     arrival time of vehicle $v$ at an intermediate node $i$ along its route $\cR_v$

$f_{u,v,i,j}$     1 if vehicle $u$ follows vehicle $v$ at edge $(i,j)\in\cR_u\cap\cR_v$, 0 otherwise. (We require $u>v$ by the convention of ordering.)

$\ell_{v,i,j}$     1 if vehicle $v$ leads a platoon at edge $(i,j)\in\cR_v$, 0 otherwise

Supplemental Material

§ PROOFS

Necessarity: Suppose that by coordinating the starting time,
all vehicles in $\cV^{\prime}$ can form a
platoon when driving along the path $P$.
Then the arrival time at the node $s$ for vehicles in $\cV^\prime$ must be the same.
Let $t_0$ be the arrival time at the node $s$ of these vehicles.
Since for any $v\in\cV^{\prime}$, the arrival time
of $v$ at the node $s$ must be within the time window $[\ul{t}_{v,s},\ol{t}_{v,s}]$,
it implies that $t_0\in[\ul{t}_{v,s},\ol{t}_{v,s}]\;\;\forall v\in\cV^{\prime}$.
Therefore, the intersection of any two
vehicles' time windows at $s$ must contain $t_0$, and hence non-empty.

Sufficiency: Suppose $|\cV^{\prime}|=n$. We label vehicles using indices $1,2,\ldots,n$ in the proof.
The time window for the vehicle $k$ at $s$ is denoted as $[\ul{t}_{k,s},\ol{t}_{k,s}]$.
It amounts to show the following claim: If any two vehicles'
have non-empty time window intersection at $s$, then the intersection of
all vehicles' time windows at $s$ is non-empty.
If the above claim holds, then any element in $\cap^n_{k=1}[\ul{t}_{k,s},\ol{t}_{k,s}]$ can be chosen
as the simultaneous arrival time at node $s$ for all vehicles in $\cV^{\prime}$,
and the departure time of each vehicle can be determined accordingly.
We prove the claim by induction on $n$. The claim obviously holds for the case $n=2$.
Suppose the claim holds for $n$, we now show that it holds for $n+1$.
By the induction hypothesis, the set $\cap^n_{k=1}[\ul{t}_{k,s},\ol{t}_{k,s}]$ is non-empty.
Since the intersection of finitely many closed interval is also a closed interval,
the set $\cap^n_{k=1}[\ul{t}_{k,s},\ol{t}_{k,s}]$ must be a closed interval and we
denote this interval as $[\hat{t}^1,\hat{t}^2]$.
If $[\ul{t}_{n+1,s},\ol{t}_{n+1,s}]\cap[\hat{t}^1,\hat{t}^2]$
is non-empty, then the claim holds.
Suppose $[\ul{t}_{n+1,s},\ol{t}_{n+1,s}]\cap[\hat{t}^1,\hat{t}^2]$
is empty. Then it follows that either $\ol{t}_{n+1,s}<\hat{t}^1$ or $\ul{t}_{n+1,s}>\hat{t}^2$.
Without loss of generality, we assume that $\ol{t}_{n+1,s}<\hat{t}^1$.
Since $[\hat{t}^1,\hat{t}^2]=\cap^n_{k=1}[\ul{t}_{k,s},\ol{t}_{k,s}]$,
there exists a vehicle $m$ ($1\le m\le n$)
such that $\ul{t}_{m,s}=\hat{t}^1$.
It implies that $\ol{t}_{n+1,s}<\ul{t}_{m,s}$, and hence
$[\ul{t}_{n+1,s},\ol{t}_{n+1,s}]\cap [\ul{t}_{m,s},\ol{t}_{m,s}]=\emptyset$, which leads to a contradiction.

The proof is straightforward. For (a) if there exists a vehicle $u$ which does not
share any edges with any other vehicles, then the shared tree $T$ is decomposable.
For (b), obviously $\cR_u\cap\cR_v$ cannot contain any loops since $\cT$ is a tree.
Suppose $\cR_u\cap\cR_v$ is non-empty and it is not a path. Then it must consist
of multiple disjointed paths. Let us denote these paths as $s_1\to s_2$, $s_3\to s_4$,
..., $s_{2k-1}\to s_{2k}$, where $s_1,s_2,\ldots,s_{2k}$ are in the order of being visited by the
two vehicles. Consider the two disjointed paths $s_1\to s_2$ and $s_3\to s_4$.
We conclude that the path $\cR_u(s_2,s_3)$ is disjointed with $\cR_v(s_2,s_3)$,
and these two paths form a loop in the undirected graph,
which contradicts to the tree structure.

(a) Let $s$ be the first visited node on the directed path $\cR_u\cap\cR_v$.
A necessary and sufficient condition for $u$ and $v$
to form a platoon is that the arrival times of $u$ and $v$
at the node $s$ must be equal.
Let $\cR_u(O_u,s)$ be the
directed path from $O_u$ to $s$, and let $\cR_v(O_v,s)$ be the directed path from
$O_v$ to $s$. We must have $\cR_u(O_u,s)\cap\cR_v(O_v,s)=\emptyset$.
Let $P_0$ be the generalized path from $s$ to the root $r$.
The simultaneous arrival condition for $u$ and $v$ at node $s$ is written as:

\begin{equation}\label{eqn:t+a=t+a}
\end{equation}

By definition, the relative times of $O_u$ and $O_v$ with respective to $r$ are

\begin{equation}\label{eqn:T=T}
\begin{aligned}
&\rT_{O_u,r}=\sum_{(i,j)\in\cR_u(O_u,s)}T_{i,j}+\sum_{(i,j)\in P_{s,r}}T_{i,j}-\sum_{(i,j)\in P_{r,s}}T_{i,j}, \\
&\rT_{O_v,r}=\sum_{(i,j)\in\cR_v(O_v,s)}T_{i,j}+\sum_{(i,j)\in P_{s,r}}T_{i,j}-\sum_{(i,j)\in P_{r,s}}T_{i,j},
\end{aligned}
\end{equation}

where $P_{s,r}$ (resp. $P_{r,s}$) is the subset of edges in $P_0$ that are
pointing from $s$ to $r$ (resp. from $r$ to $s$).
Using (<ref>), we find that the equation (<ref>) is equivalent to

(b) Proof of the necessity:
Suppose vehicles in $\cV(\cT)$ are pseudo-platoonable on $\cT$.
Consider a departure-time coordination $\Set*{t_{v,O_v}}{v\in\cV(\cT)}$ that ensures
the pseudo-platoonability of vehicles in $\cV(\cT)$.
Based on the result of Part (a), we define the relative departure time $\rt_v$
for every vehicle $v\in\cV(T)$ as $\rt_v=t_{v,O_v}+\rT_{O_v,r}$.
We construct an auxiliary undirected graph $\cG^0$. The graph $\cG^0$
consists of $|\cV(\cT)|$ vertices, and each represents a vehicle.
An edge is created between $u$ and $v$ if and only if
$\cR_u\cap\cR_v$ is non-empty. Since $\cT$ is non-decomposable,
the graph $\cG^0$ must be connected.
According to the result in Part (a), if $\cG^0$ has an edge between $u$ and $v$,
then $\rt_u=\rt_v$. It follows that all vehicles in $\cV(\cT)$ must have a same relative
departure time denoted as $\rt$, and hence $\rt$ is in the intersection of
the relative time windows of all vehicles in $\cV(\cT)$.

Proof of the sufficiency:
Suppose the intersection of the relative time windows of
all vehicles in $\cV(\cT)$ is non-empty. We can pick any time $\rt$ in
the intersection and set the departure time of vehicle $v$ as $\rt_v=\rt-\rT_{O_v,r}$
for all $v\in\cV(\cT)$. Using the result of Part (a), it implies that any two vehicles
from $\cV(\cT)$ that have non-empty shared path can be platooned.
By definition it means the vehicles in $\cV(\cT)$ are pseudo-platoonable.

Lemma <ref>(b) indicates that if $\cV^0$
are pseudo-platoonable, then the subgraph of $\pG(\cT)$
induced by $\cV^0$ is a clique. Conversely, we can use a
similar argument as in Proposition <ref>
to show that if the RTW's of any two vehicles in $\cV^0$ have non-empty
intersection (i.e., the subgraph of $\pG(\cT)$ induced by $\cV^0$ is a clique),
then intersection set $\cap_{v\in\cV^0}\textrm{RTW}_v$ is non-empty,
where $\textrm{RTW}_v$ is the RTW of $v$, indicating that
the vehicles in $\cV^0$ are pseudo-platoonable by Lemma <ref>(b).

Without loss of generality, we assume that the RTWs of all vehicles in $\cV$ are distinct,
and hence $|\cC|=|\cV|$, otherwise let $\cC$ be the set of distinct RTWs. We prove the proposition
by induction on $N=|\cC|$. We first prove the claim that at every iteration of the algorithm,
the set $\cS$ is a collection of sorted time buckets. We prove this claim by induction on $N$.
Suppose it holds for $N=n$ and consider the case of $N=n+1$. By induction hypothesis,
$\cS$ is a collection of sorted buckets at the end of the $n^{\textrm{th}}$ iteration.
It then suffices to show that after calling the procedure $\Call{Refine}{\cS,[\tau^{n+1}_1,\tau^{n+1}_2]}$,
the $\cS$ remains to be a collection of sorted time buckets. First, at any iteration
of the loop at Line <ref>, if the condition at Line <ref> holds a time
bucket in $\cS$ is split into two which maintains the property. Second, notice that at any iteration
of the loop at Line <ref>, the $[q_k,p_{k+1}]$ is the gap between two consecutive time
buckets $[p_k,q_k]$ and $[p_{k+1},q_{k+1}]$ in the original $\cS$. Therefore, the intersection
interval $[q_k,p_{k+1}]\cap[\tau^{n+1}_1,\tau^{n+1}_2]$ is still between the original
$[p_k,q_k]$ and $[p_{k+1},q_{k+1}]$, and hence the property is maintained.
It is clear that the incorporation of $[-\infty,p_1]\cap[\tau^{n+1}_1,\tau^{n+1}_2]$
at Line <ref> and $[-\infty,q_{m}]\cap[\tau^{n+1}_1,\tau^{n+1}_2]$
at Line <ref> will also maintain this property since the added intervals
appear at two ends of $\cS$. Therefore, $\cS$ is a collection of sorted time buckets
in the case of $N=n+1$, concluding the proof of the claim.

We focus on proving the bounds. The proof for the lower bound is straightforward,
since every time a new interval (distinct from all previous intervals) is added to update $\cS$,
the cardinality of $\cS$ increases by at least one.
To prove the upper bound, denote $\cS^{(n)}$ as the collection of sorted time buckets
at the end of iteration $n$ of the main algorithm. We notice that $\cS^{(n)}$
can be partitioned into $r$ (for some $r\ge 1$) subsets
denoted as $\cS^{(n)}_1$, …, $\cS^{(n)}_r$, such that the union of all time buckets
in any subset $\cS^{(n)}_k$ is a single interval and
$(\cup_{I\in\cS^{(n)}_i}I)\cap(\cup_{J\in\cS^{(n)}_j}J)=\emptyset$ for all $i,j\in[r],\;i\neq j$,
where $[r]:=\{1,\ldots,r\}$.
Every subset $\cS_i$ can then be represented as
$\cS^{(n)}_i=\{[p_k,q_k]\}^{\beta(i)}_{k=\alpha(i)}$ with the indices and parameters satisfying
the following conditions:
β(i)≥α(i)      for  i∈[r],

α(i+1)=β(i)+1      for  i∈[r-1],

q_k=p_k+1      for  k∈{α(i),…,β(i)-1},  i∈[r].
Furthermore, for each $i\in[r]$ there exist indices $\sigma(i)$ and $\lambda(i)$
such that
^(n)_i=ATD{[τ^k_1,τ^k_2]}^λ(i)_k=σ(i)       for i∈[r],

λ(i)≥σ(i)      for i∈[r],

σ(i+1)=λ(i)+1      for i∈[r-1],

where $\Call{ATD}{\{[\tau^k_1,\tau^k_2]\}^{\lambda(i)}_{k=\sigma(i)}}$ denotes the set of sorted
time buckets generated by applying the adaptive time discretization on the set
$\{[\tau^k_1,\tau^k_2]\}^{\lambda(i)}_{k=\sigma(i)}$ of intervals.
Then the induction hypothesis implies that $|\cS^{(n)}_i|\le 2(\lambda(i)-\sigma(i)+1)-1$ for $i\in[r]$.
Consider the procedure $\Call{Refine}{\cS^{(n)},[\tau^{n+1}_1,\tau^{n+1}_2]}$.
The operations within the loop at Line <ref> will add at most $r-1$ new intervals, and all the other
operations together will increase the cardinality of $\cS$ by at most 2. Therefore, we have
|^(n+1)|≤|^(n)|+r+1≤∑^r_i=1[2(λ(i)-σ(i))+1] + r+1

which concludes the proof for the upper bound. Note that the lower and upper bounds
can be achieved. The lower bound is achieved when all intervals in $\cC$ are disjointed.
The upper bound is achieved by taking the following set of intervals:

(a) We first prove for the upper bound.
It is clear that the count is invariant under rescaling of the coordinate.
To simplify the presentation, we rescale the coordinate
in the way that $H\to 1$, $h\to h/H=r$.
We first sort the sequence $\Set*{T^k_1}{k\in[N]}$ in ascending order,
and let $(k)$ be the vehicle index of the $k^\textrm{th}$ element in the
sorted sequence. Then the RTW of vehicle $(k)$ is denoted as $[\T{k}_1,\T{k}_2]$.
Consider the process of calling Refine$\cS$,$[\T{k}_1,\T{k}_2]$
for $k=1,\ldots,N$ in Algorithm <ref>.
Excluding a certain zero-measured set of events, it can be seen that when
a new RTW $[\T{k}_1,\T{k}_2]$ is incorporated to refine the collection $\cS$
of sorted time buckets, $|\cS|$ increases by either one or two, and the increment
is two if and only if at least one RTW from $\Set*{[\T{i}_1,\T{i}_2]}{i\in[k-1]}$
has a proper intersection with $[\T{k}_1,\T{k}_2]$.
This observation leads to the following representation
of $|\cS|$ when Algorithm <ref> terminates:
where $I_k$ is the indicator of the event
$\bigvee^k_{i=2}\big\{[\T{k}_1,\T{k}_2]\cap[\T{i}_1,\T{i}_2]\textrm{ is proper}\big\}$.
It follows that

=N+∑^N_k=2(∪^k-1_i=1{k_1∈[i_1,i_2]} )

= N+∑^N_k=2∑^k-1_i=1(k_1-i_1≤ri )
where in the third equality we use the assumption that the first end points $\{T^{(i)}_1\}^n_{i=1}$
are sorted in ascending order, indicating that the event
$\big\{\T{k}_1\in[\T{i}_1,\T{i}_2]\text{ or }\T{k}_2\in[\T{i}_1,\T{i}_2]\big\}$ is equivalent
to $\big\{\T{k}_1\in[\T{i}_1,\T{i}_2]\big\}$, and in the last equality the uniformly distributed
random variable $\U{i}\sim\cU(0,1)$ is independent of other random parameters.
So it amounts to derive an upper bound for $\bP\big(\T{k}_1-\T{i}_1\le r\U{i} \big)$. It is well known that
the ascending sequence $\{\T{k}_1\}^N_{k=1}$ follows the order statistics
From <cit.>,
the random parameters $(\T{i}_1,\T{k}_1)$ have the following joint density function
and hence the probability density function of the gap $\T{k}_1-\T{i}_1$
can be derived:

g_i,k(t) = ∫^1-t_0 f_i,k(u,u+t)du

=N!/(i-1)!(N-k)!(k-i-1)!·t^k-i-1 ∫^1-t_0 u^i-1(1-u-t)^N-k du

=N!/(i-1)!(N-k)!(k-i-1)!·(i-1)!(N-k)!/(N-k+i)!t^k-i-1(1-t)^N-k+i   (integrate by parts)

Therefore, we find out that
(k_1-i_1≤s)=∫^s_0 g_i,k(t)dt=∫^s_0 N!/(N-k+i)!(k-i-1)!t^k-i-1(1-t)^N-k+i dt

≤∫^s_0 N!/(N-k+i)!(k-i-1)!t^k-i-1 = N!/(N-k+i)!(k-i)!·s^k-i=Nk-is^k-i.
It then follows that
(k_1-i_1≤rU_i)=∫^1_0(k_1-i_1≤rs)ds≤Nk-i∫^1_0 (rs)^k-ids

The probability $\bP(I_k=1)$ can then be upper bounded as

=q(1-q^k-1)e/2(1-q)     for q≠1,
where we define $q:=e(N+1)r/2$ and we use the upper bound
$\binom{n}{k}\le\left(\frac{en}{k}\right)^k$ for the binomial coefficient
to get the last inequality. An upper bound for $\E[|\cS|]$ follows as

which concludes the proof for the upper bound.

(b) Now we prove for the lower bound. Let $I^\prime_k$ be the indicator of the event
$\big\{[\T{k}_1,\T{k}_2]\cap[\T{k-1}_1,\T{k-1}_2]\textrm{ is proper}\big\}$
for $k\in\{2,\ldots,N\}$. Clearly, we have $I_k\ge I^\prime_k$ almost surely, which
leads to the following lower bound of $\E[|\cS|]$:
From the joint probability density (<ref>), we can compute the probability

$$\bP\big(\T{k}_1-\T{k-1}_1\le s\big)=\int^s_0g_{k-1,k}(t)=1-(1-s)^N.$$

It then follows that

=N+N-1/(N+1)r[N+12r^2-N+13r^3 ]

which concludes the proof.

For any feasible time-bucket assignment $\chi=\Set*{\chi_v}{v\in\cV}$, $\chi_v$ indexes a feasible
time bucket of vehicle $v$. Let $\pi_v$ be the middle point of the time bucket $\chi_v$. It is clear that the
schedule $\pi=\Set*{\pi_v}{v\in\cV}$ is feasible to the FRCVP problem and $\varphi(\pi)=\chi$,
which shows that the mapping $\varphi$ is surjective. Consider a feasible schedule
$\pi$. By Lemma <ref>, any two vehicles $u$ and $v$ are
pseudo-platoonable if and only if $\pi_u=\pi_v$. Since $\pi_u=\pi_v$ implies that
$\varphi_u(\pi)=\varphi_v(\pi)$. This means that the feasible platooning configurations
are preserved under the mapping $\varphi$, and hence
To prove the last assertion, let $\chi^*$ be an optimal time-bucket assignment to (<ref>)
and $\pi^*\in\varphi^{-1}(\chi^*)$ be any schedule that is mapped to $\chi^*$ under $\varphi$
satisfying $\pi^*_u=\pi^*_v$ if $\chi^*_u=\chi^*_v$.
Suppose $\pi^*$ is not an optimal schedule to the FRCVP and let $\pi^\prime$
be an optimal schedule. The non-optimality of $\pi^*$ indicates that
Since we have proved that $\text{Obj}^{\text{FRCVP}}(\pi^*)=\text{Obj}^{\text{VA}}\circ\varphi(\pi^*)$
and $\text{Obj}^{\text{FRCVP}}(\pi^\prime)=\text{Obj}^{\text{VA}}\circ\varphi(\pi^\prime)$,
we conclude that $\text{Obj}^{\text{VA}}\circ\varphi(\pi^*)<\text{Obj}^{\text{VA}}\circ\varphi(\pi^\prime)$.
Therefore, the time-bucket assignment $\varphi(\pi^\prime)$ must be different from $\chi^*=\varphi(\pi^*)$,
and it achieves a better objective value for (<ref>), contradicting to the optimality of $\chi^*$.

We prove the theorem by reducing the scheduling problem of unit execution time tasks with unbounded
number of machines (Sched-UET-$\infty$) to the tree-based FRCVP problem. The Sched-UET-$\infty$ problem
is known to be NP-complete
and it states as follows:
Given $n$ tasks, each has a time window for execution and the two end coordinates
of every time window are non-negative integers.
Every task can be completed in one unit of time on a machine, and there are unlimited amount of machines
at every time instant. This means if a time unit is feasible for multiple tasks, these tasks can be assigned
to the corresponding number of machines and get all completed in one unit of time. The goal is to find
the minimum number of machine operations to complete all tasks. Note that if multiple machines are working
in parallel, it counts as a single operation. Note that the Sched-UET-$\infty$ is equivalent to the minimal
clique partition of an interval graph.

For any instance of the Sched-UET-$\infty$ problem,
we can construct an instance of the tree-based FRCVP problem such that solving the
tree-based FRCVP instance can give a solution to the Sched-UET-$\infty$ instance.
The construction is as follows: The $n$ tasks are mapped to $n$ vehicles. We can construct
the route of each vehicle such that they only share exactly the same edge $e$ along their routes.
Picking the origin node of an arbitrary vehicle as the root.
For every vehicle, we can make up the starting and destination time as well as
the length of other edges along its route such that the RTW
of the vehicle is the same as the time window of the corresponding task.
We have the following claim hold.Claim. If $\sigma^l=0$ and $\sigma^f>0$, solving the tree-based FRCVP instance
constructed above can induce an optimal solution to the Sched-UET-$\infty$ instance. Proof.
When the tree-based FRCVP instance has been solved to optimality, the solution can give $m$
different time units (time buckets) such that the set of vehicles can be divided into $m$ groups,
and vehicles within a same group form a platoon on the shared edge $e$. The total amount of
fuel saving is equal to $(n-m)\sigma^fC_e$ since a lead vehicle cannot save fuel by the parameter
setting. Therefore, maximizing the total fuel saving is equivalent to minimizing the number of
partitions of the set of vehicles. Based on the construction, the number of partitions in the FRCVP
instance is equal to the number of machine operations in the Sched-UET-$\infty$ instance.
This concludes the proof.

Let $\cV^*_t$ be the subset of vehicles assigned to $t$ in an optimal solution. Since
$\sum_{t\in[T]}H(\cV^*_t)=\opt$ by the definition of optimal solution and
$H(\cV^*_t)\le H(\cV_t)\le\frac{1}{T}\opt$ by assumption,
it follows that $H(\cV^*_t)=H(\cV_t)=\frac{1}{T}\opt$ for all $t\in[T]$.
Notice that $\cV^*_t$ is a subset of $\cV_t$ for all $t$. The above equalities
indicate that assigning vehicles from the set $\cV_t\setminus\cV^*_t$ to $t$
does not increase any fuel saving as compared to $\cV^*_t$. It further implies
that for any three distinct vehicles $u\in\cV_t\setminus\cV^*_t$, $v\in\cV_t\setminus\cV^*_t$
and $w\in\cV^*_t$, any mutual intersection of the three sets $\cR_u$, $\cR_v$ and $\cR_w$ is
is an empty set. For every $t$, we define the following two subsets
$\cU_t:=\{u:\;\exists v\in\cV_t,\;v\neq u,\;\text{s.t. }\cR_u\cap\cR_v\neq\emptyset\}$
and $\cW_t:=\{w:\;\forall v\in\cV_t,\;v\neq w,\;\cR_w\cap\cR_v=\emptyset\}$.
It is straightforward to check that $\cU_t$ and $\cW_t$ are two disjoint classes
and $\cV_t=\cU_t\cup\cW_t$ for all $t$. By definition, we have
$H(\cU_t)=H(\cU_t\cup A)=\frac{1}{T}\opt$ for any subset $A\subseteq\cV_t\setminus\cU_t$
and for all $t$. Furthermore, the subsets $\{\cU_t:\;t\in[T]\}$ are disjoint. Indeed, if
there exists a $v\in\cU_t\cap\cU_{t^\prime}$ for two time buckets $t$ and $t^\prime$,
consider where $v$ has been assigned in the optimal solution $\{\cV^*_t:\;t\in[T]\}$.
Clearly, at least one of $\cV^*_t$ and $\cV^*_{t^\prime}$ does not contain $v$.
Without loss of generality, assume $v\notin\cV^*_t$. Then we conclude that
H(^*_t) = H(^*_t∩_t) ≤H(_t∖{v}) < 1/T,
which leads to a contradiction.
Note that each $\cU_t$ can be constructed with computational complexity
$\mathcal{O}(|\cV||\cE|)$ and the overall computational complexity is $\mathcal{O}(|\cV||\cE||\cT|)$
for constructing $\cU_t$ for all $t\in[T]$. For every $v\in\cV\setminus(\cup^T_{t=1}\cU_t)$,
it can be assigned to an arbitrary feasible time bucket without changing the objective value.

Let $\cE_1=\cE_0\cap(\cup_{v\in\cU_1}\cR_v)$ and $\cE_2=\cE_0\cap(\cup_{v\in\cU_2}\cR_v)$.
Notice that $\cE_0=\cE_1\cup\cE_2$. For any $e\in\cE_1\setminus\cE_2$,
we should have $n_e(\cU_1)\ge 2$, since $n_e(\cU_1\cup\cU_2)\ge 2$ but
$e\notin\cup_{v\in\cU_2}\cR_v$. The difference on the left side of (<ref>)
can be evaluated as follows

H(_1∪_1,_0) + H(_2∪_2,_0) - H(_1,_0) - H(_2,_0)

- ϕ∘n_e(_1) + ϕ∘n_e(_2∪_2)
- ϕ∘n_e(_2)]

=∑_e∈_1∖_2C_e[ϕ∘n_e(_1∪_1) - ϕ∘n_e(_1)]
+ ∑_e∈_2∖_1C_e[ϕ∘n_e(_2∪_2) - ϕ∘n_e(_2)]

+ ∑_e∈_1∩_2C_e[ϕ∘n_e(_1∪_1)
- ϕ∘n_e(_1) + ϕ∘n_e(_2∪_2)
- ϕ∘n_e(_2)],
where the last equality is due to the fact that for any $e\in\cE_1\setminus\cE_2$,
$n_e(\cU_2)=0$ and hence $n_e(\cV_2\cup\cU_2)-n_e(\cV_2)=0$.
To evaluate the first term in (<ref>) for a $e\in\cE_1$,
there are only three cases on $n_e(\cV_1)$ and $n_e(\cU_1)$:
(1) $n_e(\cV_1)\le 1$, $n_e(\cV_1)+n_e(\cU_1)\ge 2$; (2) $n_e(\cV_1)\ge 2$, $n_e(\cV_1)+n_e(\cU_1)\ge 2$.
For each case, we have
ϕ∘n_e(_1∪_1) - ϕ∘n_e(_1)=
{=3pt 1.4

σ^l+σ^f[n_e(_1)+n_e(_1)-1]     Case (1),

σ^fn_e(_1)     Case (2).

Notice that since $e\in\cE_1\setminus\cE_2$, we have $n_e(\cU_1)=n_e(\cV_3)$,
and hence the quantity $\sigma^l+\sigma^f[n_e(\cV_1)+n_e(\cU_1)-1]$ in Case (1)
is upper bounded by $\sigma^l+\sigma^f[n_e(\cV_3)-1]=\phi\circ n_e(\cV_3)$.
Then the following inequality holds for the two cases

ϕ∘n_e(_1∪_1) - ϕ∘n_e(_1) ≤2σ^f/σ^l+σ^f ϕ∘n_e(_3),
where the equality holds at Case (2) when $n_e(\cV_1)\ge2$ and $n_e(\cU_1)=n_e(\cV_3)=2$.
Evaluation of the second term in (<ref>) leads to a similar inequality
as (<ref>). The third term in (<ref>) can be evaluated
in the same manner for different cases of the
$[n_e(\cV_1), n_e(\cU_1), n_e(\cV_2), n_e(\cU_2)]$-combination.
One can show that the following inequality holds for all cases

- ϕ∘n_e(_1) + ϕ∘n_e(_2∪_2)
- ϕ∘n_e(_2) ≤2ϕ∘n_e(_3),
where the equality holds at $n_e(\cV_1)=n_e(\cU_1)=n_e(\cV_2)=n_e(\cU_2)=1$.
Notice that since $H(\cV_3,\cE_0)=\sum_{e\in\cE_0}\phi\circ n_e(\cV_3)$,
combining the inequalities (<ref>) and (<ref>)
concludes the proof.

Let $\cE^c_0$ be the complement set of $\cE_0$ with respect
to the set $\cE$ of all edges. The value $H^*$ can be decomposed as

H^*   =H(_1∪^*_1)+H(_2∪^*_2)

+H(_2∪^*_2,_0) + H(_2∪^*_2,^c_0).
Let $\cU_1$ and $\cU_2$ be the two subsets constructed in the function Assignment($t_1,t_2$).
The value $H_0$ can then be decomposed in a similar way:

H_0   =H(_1∪_1)+H(_2∪_2)

+H(_2∪_2,_0) + H(_2∪_2,^c_0)
Due to the definition of $\cE_0$, for any $v\in\cV_3$ there is no other vehicles
from $\cV_3$ that travel on any edge of $\cE_v:=\cR_v\setminus\cE_0$
(defined in Assignment). Therefore, for any subset $\cU$ of $\cV_3$
the following additive property holds on the edge set $\cE^c_0$:

H(_1∪,^c_0)-H(_1,^c_0)=∑_v∈[H(_1∪{v},^c_0) - H(_1,^c_0)]=∑_v∈[H(_1∪{v},_v) - H(_1,_v)],

H(_2∪,^c_0)-H(_2,^c_0)=∑_v∈[H(_2∪{v},^c_0) - H(_2,^c_0)]=∑_v∈[H(_2∪{v},_v) - H(_2,_v)].
With the help of (<ref>), the greedy policy of assigning vehicles
to $t_1$ and $t_2$ used in the function Assignment($t_1,t_2$)
guarantees that

Substituting (<ref>) into (<ref>) and (<ref>)

Using Lemma <ref>, we have

H(_1∪^*_1,_0) + H(_2∪^*_2,_0) ≤H(_1,_0) + H(_2,_0) + 2H(_3,_0).
On the other side, the following lower bound on
$H(\cV_1\cup\cU^*_1,\cE_0) + H(\cV_2\cup\cU^*_2,\cE_0)$
obviously holds

H(_1∪_1,_0) + H(_2∪_2,_0)
≥H(_1,_0) + H(_2,_0).
Substituting (<ref>) and (<ref>)
into (<ref>) leads to

It then suffices to bound $H(\cV_3,\cE_0)$ with the term on the
right side of (<ref>). We observe that

≥σ^f/σ^l+σ^f [H(_3,_0)-H(^*_1,_0)],

≥σ^f/σ^l+σ^f [H(_3,_0)-H(^*_2,_0)].
The validness of above two inequalities can be seen from the following extremal case:
Suppose for an edge $e\in\cE_0$, it is shared by three vehicles $v\in\cV_1$,
$u_1\in\cU^*_1$ and $u_2\in\cV_3\setminus\cU^*_1$.
If only considering the two vehicles $u_1$ and $u_2$, adding $u_2$ to follow $u_1$ in a platoon
leads to the amount of fuel saving increased from 0 to $(\sigma^l+\sigma^f)C_e$.
On the other side, if $v$ is included in the consideration such that $\{v, u_1\}$ is a platoon,
adding $u_2$ to the platoon leads to the amount of fuel saving increased from
$(\sigma^l+\sigma^f)C_e$ to $(\sigma^l+2\sigma^f)C_e$. The increment of fuel saving
in the two cases is $(\sigma^l+\sigma^f)C_e$ versus $\sigma^fC_e$, which gives the
factor $\sigma^f/(\sigma^l+\sigma^f)$ in the above inequalities.
Adding the two inequalities in (<ref>) gives

which concludes the proof.

Let $\cW_t$ be the subset of vehicles for which $t$ is a feasible time bucket.
Let $H_{ub}=\max_{t\in[T]}H(\cW_t)$. Let $\cW^*_t$ for $t\in[T]$ be the subset
of vehicles assigned to $t$ in an optimal solution of the FRCVP instance.
Clearly, $\cW^*_t$ is a subset of $\cW_t$, and $\textproc{Opt}=\sum^T_{t=1}H(\cW^*_t)$
by definition. Let $t_1$ and $t_2$ be two time buckets such that
$H(\cW^*_{t_1})\ge H(\cW^*_{t_2})\ge H(\cW^*_s)$ for all $s\in[T]\setminus\{t_1,t_2\}$.
For simplicity of notation, let $H_1:=H(\cW^*_{t_1})$ and $H_2:=H(\cW^*_{t_2})$.
The choice of $t_1$ and $t_2$ implies that $H_1\ge\frac{1}{T}\textproc{Opt}$
and $H_2\ge\frac{1}{T-1}(\textproc{Opt}-H_1)$.

Let $\cV_1$, $\cV_2$, $\cV_3$ and $\cE_0$ be defined the same as in Lemma <ref>
for $t_1$ and $t_2$. Let $H^*=\max_{\cU\subseteq\cV_3}H(\cV_1\cup\cU)+H(\cV_2\cup\cV_3\setminus\cU)$
with $\cU^*_1\subseteq\cV_3$ and $\cU^*_2=\cV_3\setminus\cU^*_1$ being an optimal solution of the problem.
Applying Lemma <ref> gives the following inequality

\begin{equation}\label{eqn:H*-H0_interm}
\ba
H^*-H_0&\le 2\left(1+\frac{\sigma^l}{\sigma^f}\right)
[H(\cV_1\cup\cV_3,\cE_0)+H(\cV_2\cup\cV_3,\cE_0)-H(\cV_1\cup\cU^*_1,\cE_0)-H(\cV_2\cup\cU^*_2,\cE_0)] \\
&= 2\left(1+\frac{\sigma^l}{\sigma^f}\right)
[H(\cV_1\cup\cV_3)+H(\cV_2\cup\cV_3)-H(\cV_1\cup\cU^*_1)-H(\cV_2\cup\cU^*_2)] \\
&\quad - 2\left(1+\frac{\sigma^l}{\sigma^f}\right)
[H(\cV_1\cup\cV_3,\cE^c_0)+H(\cV_2\cup\cV_3,,\cE^c_0)-H(\cV_1\cup\cU^*_1,,\cE^c_0)-H(\cV_2\cup\cU^*_2,,\cE^c_0)] \\
&= 2\left(1+\frac{\sigma^l}{\sigma^f}\right)
[H(\cV_1\cup\cV_3)+H(\cV_2\cup\cV_3)-H(\cV_1\cup\cU^*_1)-H(\cV_2\cup\cU^*_2)] \\
&\le 2\left(1+\frac{\sigma^l}{\sigma^f}\right)[2H_{ub}-H_1-H_2],
\ea
\end{equation}

where the first inequality is directly from (<ref>) in Lemma <ref>,
the second equality uses the additive property given in (<ref>),
and the second inequality uses the property
$\max\{H(\cV_1\cup\cV_3), H(\cV_2\cup\cV_3)\}\le H_{ub}$ by the definition of $H_{ub}$
and the definition of $\cU^*_1$ and $\cU^*_2$.
On the other side, we have $H^*\ge H_1+H_2$. Substituting this lower bound of $H^*$ into
(<ref>) leads to the following inequality
which further implies that

H_0   ≥[1+2(1+σ^l/σ^f)](H_1+H_2)

≥[1+2(1+σ^l/σ^f)]1/T-1+ [1+2(1+σ^l/σ^f)]T-2/T-1H_1

:= f(H_1,H_ub),
where $H_2\ge\frac{1}{T-1}(\opt-H_1)$ is used to get the second inequality,
and $f(H_1,H_{ub})$ represents the term on the right side of the second inequality in (<ref>)
which is a function of $H_1$ and $H_{ub}$. From Line <ref> of
Algorithm <ref> and (<ref>), the value $H_0$
has the following lower bound $H_0\ge\max\{H_{ub},\;f(H_1,H_{ub})\}$.
It amounts to find appropriate $H_1$ and $H_{ub}$ that can minimize the lower bound.
The lower bound minimization problem can be formulated as
H_1,H_ubmin max {H_ub, f(H_1,H_ub)}  s.t.  1/T≤H_1≤H_ub.
It can be verified that the optimal objective of the above problem is obtained by setting
$H_{ub}=f(H_1,H_{ub})$ and $H_1=\frac{1}{T}\opt$, which gives the minimum lower bound
This concludes the proof.

Clearly, under any schedule, the objective value achieved at the edge $e$ should be
upper bounded by $[(N-1)\sigma^f+\sigma^l]C_e$, which is corresponding to the amount
of fuel saving if the $N$ vehicles form a single platoon. For the schedule $\pi$, suppose
it leads to $k$ single-vehicle platoons and $r$ non-trivial platoons of size $n_1$, …, $n_r$,
on the edge $e$, respectively. The objective at $e$ in this case is equal to
(π,e)=rσ^lC_e + ∑^r_i=1(n_i-1)σ^fC_e

=∑^r_i=1n_iσ^fC_e - r(σ^f-σ^l)C_e

=(N-k)σ^fC_e- r(σ^f-σ^l)C_e,
where we use the equality $N=k+\sum^r_{i=1}n_i$.
Since there are at most $T$ time buckets, it implies that
$k+r\le T$. Therefore, we get that
(π,e)   =Nσ^fC_e-(k+r)σ^fC_e+rσ^lC_e

≥Nσ^fC_e - Tσ^fC_e.
Consequently, the ratio of interest can be bounded as
(π,e)/(π^*,e)≥Nσ^fC_e - Tσ^fC_e/[(N-1)σ^f+σ^l]C_e
which concludes the proof.

If there exists a vehicle $u$ such that for every vehicle $v\in\cU\setminus\{u\}$
either $\cR_u\cap\cR_v=\emptyset$ or $\cS_u\cap\cS_v=\emptyset$,
then the instance is separable with $\cU_1=\{u\}$ and $\cU_2=\cU\setminus\{u\}$.

Apply the following procedure to the instance $(\cT,\cU,\cS)$: (1) Let $\cE^\prime\gets\emptyset$,
$\cU^\prime\gets\emptyset$ and $\cW\gets\emptyset$.
(2) Repeat the following step until it cannot be executed: Find two distinct vehicles $v_1,v_2\in\cU\setminus\cU^\prime$
such that the sets $(\cR_{v_1}\cup\cR_{v_2})\setminus\cE^\prime$, $\cR_{v_1}\cap\cR_{v_2}$
and $\cS_{v_1}\cap\cS_{v_2}$ are all non-empty.
Set $\cU^\prime\gets\cU^\prime \cup\{v_1,v_2\}$ and $\cE^\prime\gets\cE^\prime\cup\cR_{v_1}\cup\cR_{v_2}$.
(3) Repeat the following step until it cannot be executed:
Find two vehicles $u\in\cU\setminus(\cU^\prime\cup\cW)$ and $v\in\cU^\prime$ such that
the sets $\cR_u\setminus\cE^\prime$, $\cR_u\cap\cR_v$ and $\cS_u\cap\cS_v$ are all non-empty.
Set $\cW\gets\cW\cup\{u\}$ and $\cE^\prime\gets\cE^\prime\cup\cR_u\cup\cR_v$.

We first show that when Step (2) cannot be executed, the following property holds:
For any edge $e\in\cE(\cT)\setminus\cE^\prime$ and any vehicle $u\in\cV_e\setminus\cU^\prime$
there exists a vehicle $v\in\cU^\prime$ such that
the sets $\cR_u\cap\cR_v$ and $\cS_u\cap\cS_v$ are all non-empty.
We prove this claim by contradiction. Suppose there exist an edge $e\in\cE(\cT)\setminus\cE^\prime$
and a vehicle $u\in\cV_e\setminus\cU^\prime$ which violate the statement.
Since the instance is inseparable, there must exist a vehicle $v\in\cU\setminus\{u\}$ such that
the sets $\cR_u\cap\cR_v$ and $\cS_u\cap\cS_v$ are all non-empty.
If $v$ is not in $\cU^\prime$, the vehicle pair $(u,v)$ satisfies the executable condition
at Step (2) by noting that $e\in (\cR_u\cup\cR_v)\setminus\cE^\prime$. This indicates
that Step (2) can be further executed, leading to a contradiction. Therefore, we have
$v\in\cU^\prime$. This proves the claim.

Next we show that when Step (3) cannot be executed, it holds that $\cE^\prime=\cE(\cT)$.
We prove the claim by contradiction. Suppose there exists an edge $e\in\cE(\cT)\setminus\cE^\prime$.
Since the instance is inseparable, there exist a vehicle $u\in\cV_e$ and a vehicle $v\in\cU\setminus\{u\}$
such that the sets $\cR_u\cap\cR_v$ and $S_u\cap S_v$ are both non-empty. If $v\notin\cU^\prime$,
vehicles $u$ and $v$ form a pair satisfying the conditions in Step (2), and hence that step can
be further executed, which leads to a contradiction. Otherwise if $v\in\cU^\prime$, the two vehicles
form a pair satisfying the conditions in Step (3), which makes that step further executable, leading
to a contradiction. Therefore, we have $\cE^\prime=\cE(\cT)$ when the procedure terminates.

Notice that vehicles are added into the set $\cU^\prime$ in pairs, and the two vehicles in a pair
can be platooned on their shared edges. This indicates the following lower bound

Let $k=|\cU^\prime|$ and $\cU^\prime=\{v_1,\ldots,v_k\}$.
When the procedure terminates, vehicles in $\cW$ can be partitioned into $k$
subsets denoted as $\cW_i$ for $i\in[k]$ such that every vehicle in $\cW_i$ can be (independently) platooned
with $v_i$ on an edge from $\cR_{v_i}$. Since $|\cR_{v_i}|\le L$ and every edge in $\cR_{v_i}$
is shared by at most $N_0$ vehicles. It follows that
and hence

||≤N_0|()| = N_0|^'|=N_0 |∪_u∈^'∪_u|

Combining (<ref>) and (<ref>) gives the bound
which concludes the proof.

When the condition $|\cE(\cT^\prime)|\ge N$ at Line <ref> is satisfied,
the edge $e$ at Line <ref> satisfies either one of the two conditions:
(a) $e$ is the first edge of the current path $P$; and (b) $e$ is not the first edge of $P$.
We first prove for the case (a) by contradiction. Suppose $|\cE(\cT^\prime)|\ge 3dN$
In this case, and suppose the node $s_1$ has $k$ (in and out) edges
that are not on $P$. Denote these edges as $e_1,\ldots,e_k$.
By the regularity assumption, we should have
$k\le 2d$. The tree $\cT^\prime$ in this case can be partitioned as
$\cT^\prime=\cup^{k}_{i=1}\cT_i$, where $\cT_i$ is the sub-tree of $\cT^\prime$
containing $e_i$. Since $|\cE(\cT^\prime)|=\sum^k_{i=1}|\cE(\cT_i)|$
and $|\cE(\cT^\prime)|\ge 3dN$, there exists a $\cT_i$ satisfying $|\cE(\cT_i)|\ge N+1$.
Let $P_i$ be a maximal path of $\cT_i$ that contains $e_i$. Let $e^\prime_i$ is the last
edge of $P_i$ ($e^\prime_i=e_i$ if $e$ is an in-edge of $s$). Notice that the algorithm
has called $\Call{Decomposition}{P_i,\cT_i,N}$ in Line <ref>.
In $\Call{Decomposition}{P_i,\cT_i,N}$, when the algorithm reached $e^\prime_i$
as the last edge of $P_i$, the condition at Line <ref> should satisfy since
$|\cE(\cT^\prime_i)|\ge N$, where $\cT^\prime_i$ is the sub-tree of $\cT_i$ that
includes the starting node but excludes the end node of $e_i$. This indicates that
the sub-tree $\cT^\prime_i$ should have been cut from $\cT_i$, leading to a contradiction
to the status of $\cT^\prime$.

We now consider the case (b). Since $e$ is not the first edge of $P$, it implies that
the condition of Line <ref> does not hold at any edge of $P$ that comes before $e$.
Let $e^\prime$ be the edge right before $e$, and suppose $e^\prime=(s_0,s_1)$ and $e=(s_1,s_2)$.
Let $\cT^{\prime\prime}$ be the maximal tree that includes the node $s_0$ but excludes the
edge $e^\prime$. Since the condition of Line <ref> does not hold at $e^\prime$, we should have
$|\cE(\cT^{\prime\prime})|\le N-1$. For a similar argument on the sub-trees induced by edges
of $s_1$ as in the case (a), we have
This concludes the proof.

Let $\Tctr$ be the tree after running the HeavyTrafficEdgeContraction
function on $\cT$. Let $\cT_1,\ldots,\cT_K$ be the list of sub-trees returned by the
Decomposition function. Since these sub-trees form a partition of $\cT$ in
edges, there exist exact $K-1$ pairs of sub-trees such that the two subtrees in the same
pair should be adjacent (i.e., sharing a node) in $\Tctr$.
Let $\obj^*(\cT_k)$ be the objective value at the subtree $\cT_k$
achieved by a global optimal solution of the FRCVP instance,
$\objloc(\cT_k)$ be the optimal objective value of the instance $(\cT_k,\cV_k,\{\cS_v:\;v\in\cV_k\})$,
where $\cV_k$ is the subset of vehicles of which the route intersects with $\cT_k$.

Let $\obj(\cdot)$ be the
objective value achieved by Algorithm <ref> at a given component.
Note that for a given pair of adjacent sub-trees, there are at most $N_0$
vehicles with the route intersecting with both sub-trees in the pair, and these
vehicles will lead to at most $2LN_0\sigma^f\Cmax$ fuel saving lost if
removed from the vehicle system. We refer these vehicles as the
sub-tree-crossing vehicles. It follows that

≤∑^K_k=1(_k) + N_0/N_0-T∑_e∈∖(e)

≤∑^K_k=1(_k)  + 2(K-1)LN_0σ^f+ N_0/N_0-T∑_e∈∖(e)
where Lemma <ref> is used to get the first inequality,
and the term $2(K-1)LN_0\sigma^f\Cmax$ is added in the second inequality
to upper bound the total fuel saving made by sub-tree-crossing vehicles.
Notice that since $|\cE(\cT_k)|\ge N_1$ for all $k\in[K-1]$ by the design
of the algorithm, and $\cT_K$ is the last (left-over) sub-tree added to the $treeList$
with $|\cE(\cT_K)|<N_1$. We also note that
for an inseparable sub-tree $\cT_k$, the number of vehicles sharing $\cT_k$
is correlated with the number of edges in $\cT_k$ in the sense that the following
inequality holds: $|\cV(\cT_k)|\ge|\cE(\cT_k)|/L$.
Combining this lower bound with the results from Lemma <ref>
leads to the following lower bound on $\obj(\cT_k)$ for $k\in[K-1]$:
The above inequality further implies that

Substituting (<ref>) into (<ref>) gives
Opt≤∑^K_k=1(1+ 5L^4N^3_0ρ/N_1)(_k)
The conditions on $N_0$ and $N_1$ ensure that $N_0/(N_0-T)\le 1+\epsilon$
and $5L^4N^3_0\rho/N_1\le\epsilon$, which leads to the inequality $\textproc{Opt}\le(1+\epsilon)\obj$
and hence $\obj\ge(1-\epsilon)\textproc{Opt}$.

We analyze the computational complexity of the algorithm. First, the number of sub-trees in the
$treeList$ is at most $|\cE|/N_1$ (up to rounding), where $\cE$ is the set of edges in $\cT$.
Each sub-tree has at most $3dN_1$ edges (Lemma <ref>),
and the number of vehicles involved in each sub-tree is at most $3dN_1N_0$.
The complexity of enumerating all feasible solution for each sub-tree is upper bounded
by $T^{3dN_1N_0}$. Notice that the conditions satisfied by $N_0$ and $N_1$
imply that $N_1\ge 5\rho L^4 T^3 (1+1/\epsilon)^3/\epsilon$.
Therefore, the complexity of the algorithm is estimated as

||/N_1·T^3dN_1N_0   ≤ϵ||/5ρL^4T^3(1+1/ϵ)^3·[exp(15ρdL^4T^41/ϵ(1+1/ϵ )^4)]^logT

which concludes the proof.

Let $[x^*,y^*,y^{\prime*},w^*]$ be an optimal solution of (<ref>). The optimal objective of the linear program
is expressed as

Since $\E[\obj(x^*)]\le\textproc{Opt}\le\widehat{\textproc{Opt}}$, it suffices to show that
$\frac{\E[\emph{obj}(x^*)]}{\widehat{\textproc{Opt}}}\to 1$ as $\frac{|\cV|}{|\cR|}\to\infty$.
The randomized algorithm returns a schedule in which vehicles that are assigned to a same
time bucket can form a single platoon on edges that they share.
Let $Y^\prime_{e,t}$ be the indicator random variable of the event that at least two vehicles
sharing the edge $e$ are assigned to the time bucket $t$. Let $W_{e,t}$ be the random variable
representing the quantity $(Q_{e,t}-1)^+$, where $Q_{e,t}$ is the number of vehicles
sharing $e$ that are assigned to $t$ by the randomized algorithm, and $(\cdot)^+:=\max\{0,\cdot\}$.
The expectation of $\obj(x^*)$ is written as
[(x^*)] =  ∑_e∈∑_t∈(σ^lC_e[Y^'_e,t]+σ^fC_e[W_e,t]).
We can get a lower bound for $\E[Y^\prime_{e,t}]$ as follows:
[Y^'_e,t]=(Y^'_e,t=1)≥max_(u,v)∈_e,t x^*_u,tx^*_v,t

≥max_(u,v)∈_e,t [ x^*_u,tx^*_v,t-(1-x^*_u,t)(1-x^*_v,t) ]

= max_(u,v)∈_e,t (x^*_u,t+x^*_v,t-1).
From the constraint (<ref>) if $\max_{(u,v)\in\cV_{e,t}} (x^*_{u,t}+x^*_{v,t}-1)\ge 0$, we have
$y^{\prime*}_{e,t}=\max_{(u,v)\in\cV_{e,t}} (x^*_{u,t}+x^*_{v,t}-1)$, otherwise $y^*_{e,t}=0$.
For both cases, we have shown that $\E[Y^\prime_{e,t}]\ge y^{\prime*}_{e,t}$.

We also have the following lower bound for $\E[W_{e,t}]$ by definition:
Let $\cC$ be the following subset of $(e,t)$ pairs

={(e,t): ∑_u∈_e,tx^*_u,t≥1},

and $\cC^\prime$ be the complement of $\cC$. Notice that the following property holds
where the constraint (<ref>) has been used to get the third equality above.
The term $\sum_{e\in\cR}\sum_{t\in\cS}\sigma^fC_ew^*_{e,t}$ in the objective of (<ref>)
can be split into two parts: $\sum_{(e,t)\in\cC}\sigma^fC_ew^*_{e,t}$ and $\sum_{(e,t)\in\cC^\prime}\sigma^fC_ew^*_{e,t}$,
which will be bounded separately using the constraint (<ref>). For the first part, we have

∑_(e,t)∈σ^fC_ew^*_e,t≤∑_(e,t)∈∑_u∈_e,tσ^fC_e x^*_u,t,
and for the second part we can use the definition of $\cC^\prime$ to obtain the following bound

On the other side, we get a lower bound of $\E[\obj(x^*)]$ using the following

[(x^*)]   ≥∑_(e,t)∈∪^'σ^lC_e[Y^'_e,t]+∑_(e,t)∈σ^fC_e[W_e,t]

+∑_(e,t)∈σ^fC_e(∑_u∈_e,tx^*_u,t-1 )

≥∑_(e,t)∈∪^'σ^lC_ey^'*_e,t+∑_(e,t)∈∑_u∈_e,tσ^fC_e x^*_u,t
Using the lower bound (<ref>) for $\E[\obj(x^*)]$,
and substituting (<ref>) and (<ref>)
into (<ref>) to get an upper bound for $\optLP$,
we deduce the following lower bound on the ratio

+∑_(e,t)∈∑_u∈_e,tσ^fC_e x^*_u,t
+∑_(e,t)∈∑_u∈_e,tσ^fC_e x^*_u,t+σ^fC_max|^'|.
Notice that the term $\sum_{(e,t)\in\cC}\sum_{u\in\cV_{e,t}}\sigma^fC_e x^*_{u,t}$
presented in both the numerator and the denominator has the following lower bound

∑_(e,t)∈∑_u∈_e,tσ^fC_e x^*_u,t

where the constraint (<ref>) has been used to get the last equality.
Since $|\cC|+|\cC^\prime|\le |\cR|T$, and $\frac{|\cV|}{|\cR|}\to\infty$,
combining (<ref>) and (<ref>) shows that
$\frac{\E[\obj(x^*)]}{\optLP}\to 1$, which concludes the proof.

Suppose $p$ is a break point generated on a vehicle $u\in\Vext$ at iteration $n$ in the while loop (Line <ref>)
of Algorithm <ref>. In the iteration $n+1$, the point $p$ will either be projected in the vertical
or the shifting mode to other vehicles. If the projection is in the vertical mode, the coordinate of the newly generated break
points by $p$ should have the same coordinate as $p$. If the projection is in the shifting mode, consider the case of projecting $p$ on a vehicle $u^\prime$ which is another virtual copy satisfying $u,u^\prime\in\cM(v)$ for some $v\in\Vvt$.
Then the projected point on $\rtw_{u^\prime}$ should have the coordinate equal to $a_{u^\prime}+p-a_u$, where $p$ in this expression represents
the coordinate of the point $p$. By the definition of the group $G$, it is easy to see that if $p\in G$, then the projected points
of $p$ in the next iteration should also in $G$ under the two projection modes. Since at the beginning of the while loop
in the algorithm, all break points are simply the end points of each vehicle, and hence in $G$, all break points generated
from the initial set in later iterations form a subset of $G$.

Given that $G$ is isomorphic to a one dimensional lattice group, it can then be represented as
$G=\{kc\;|\;k\in\mathbb{Z}\}$ for some constant $c\in\mathbb{R}$. Also notice that all the break points
should be generated within the bounded region $\Lambda = [\min_u a_u,\;\max_u b_u]$ by the algorithm.
Since there can only a finite number of elements from $G$ that are in $\Lambda$
(i.e., upper bounded by $\ceil{\Lambda/c}+1$),
the set of all break points generated by the algorithm must be finite,
which implies that the algorithm should terminate in a finite number of iterations.
The time buckets generated by the algorithm lead to a valid vehicle-to-time-bucket assignment
formulation (<ref>).