  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.
