1 Optimizing Two-Truck Platooning with Deadlines Wenjie Xu Titing Cui and Minghua Chen Fellow IEEE

2025-04-28 0 0 5.34MB 19 页 10玖币

侵权投诉

Optimizing Two-Truck Platooning with Deadlines

Wenjie Xu, Titing Cui, and Minghua Chen, Fellow, IEEE

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 consump-

tion by jointly optimizing path planning, speed planning, and

platooning conﬁguration. Such a two-truck platooning problem is

pervasive in practice yet challenging to solve due to hard deadline

constraints and enormous platooning conﬁgurations to consider.

We ﬁrst leverage a unique problem structure to signiﬁcantly

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 + )to the optimal (for any  > 0) with a time

complexity polynomial in the size of the transportation network

and 1/. 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 efﬁcient 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 efﬁciency, Timely truck transportation,

Path planning, Speed planning, Platooning, Algorithm, Optimiza-

tion

I. INTRODUCTION

Heavy-duty trucks, transporting freights across national

highways, play a critical role in society’s economic devel-

opment. 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 frac-

tion 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

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 ´

Ecole Polytechnique F´

ed´

erale 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 ﬁrst 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).

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 efﬁciency 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]–[7]. Similar to what racing cy-

clists exploit, trucks traveling in a platoon experience a reduc-

tion in air drag, which translates into lower fuel consumption.

Many studies, e.g., [8]–[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 trafﬁc throughput [13] and even safety. To

date, platooning has received signiﬁcant attention from private

ﬂeets and commercial carriers [14].

However, it is algorithmically non-trivial to capitalize the

platooning potential to minimize the convoy’s total fuel con-

sumption. First, it requires exploring three distinct design

spaces: path planning, speed planning, and platooning conﬁg-

uration. Path planning and speed planning are well-recognized

mechanisms for saving fuels by optimizing the driving paths

and the speed proﬁles 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 conﬁgurations deﬁne the road segments for pla-

tooning 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 oper-

ation; 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 conﬁguration, 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 P=NP [20], [21].

Existing studies. Previous researches on truck platooning

arXiv:2210.01889v1 [eess.SY] 4 Oct 2022

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]–[24] 7X7XConvex optimization 7

[25] 7X X X Distributed method 7

[26] X7X7Hub heuristic 7

[20] X7X X Integer programming (IP) 7

[27] X X X X K-set clustering + IP 7

[28] 7 7 X X Mixed integer programming X

[29] X7X X Iterative heuristic 7

This work X X X X 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.

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-speciﬁed paths, the

authors of [21], [22], [24] obtain the optimal speed proﬁles

for each truck by solving a series of convex optimization

problems. The authors in [23] and [30] use a similar technique

to solve a ﬁxed-path platooning problem. When the traveling

speed on each road segment is ﬁxed, the path planning in

the platooning problem is often formulated as an integer

linear programming (ILP) problem [20], [27], [31]–[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 [29], [35]–[38]. [35] formu-

lates 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 conﬁguration 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

trafﬁc 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 pro-

cedure 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 conﬁguration, 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]–[44]. Two-truck platooning is not only the

mainstream of current platooning practice [42], but it also

incurs minimum safety concern for the surrounding trafﬁc

sharing the roads [40] [43] [41].

To our best knowledge, this is the ﬁrst work in the literature

to minimize total fuel consumption for truck transportation

by simultaneously optimizing path planning, speed planning,

and platooning conﬁguration, 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 efﬁcient platoon later. We make the

following contributions.

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 conﬁguration. Our formulation is built upon

an elegant problem structure that signiﬁcantly simpliﬁes 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 + )

times the minimum for any  > 0, with a time complexity

polynomial in the size of the transportation network and

1/. 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.

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 efﬁcient 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 satisﬁed.

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

A. System Model

We model a national highway network as a directed graph

G,(V, E). Each edge e∈Erepresents a road segment with

homogeneous grade, surface type, and environmental condi-

tions. Each node v∈Vdenotes an intersection or connecting

point of adjacent road segments. We deﬁne N,|V|as the

number of nodes and M,|E|as the number of edges. For

each e∈E, we use De>0to denote its length and rl

e>0

(resp. ru

e) to denote the minimum (resp. maximum) driving

speed.

There are mainly three types of truck fuel consumption

models [45]: (i) ﬁrst-principle white-box models, e.g., the

kinematics model based on the Newton’s second law [23],

[24], [46]–[50]; (ii) black-box models based on ﬁtting a

mathematical function to real-world data, e.g., [51]–[58]; (iii)

grey-box models that lie between the two models, e.g., [59].

White-box models are developed by using domain knowl-

edge 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

efﬁciency. 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 sufﬁce, 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 deﬁne function fe(re) : [rl

e, ru

e]→R+

as the (instantaneous) fuel consumption rate for the truck

traveling over eat speed re1. It is well understood that

fe(re)can be modeled as a strictly convex function over the

speed range [rl

e, ru

e]; see e.g., [60], [61] with justiﬁcations.

Many existing works [62]–[69] also use polynomial functions

to model the fuel consumption rate fe(·). Following the

practice, in this paper, we assume that fe(·)is a strictly

1This 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.

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

sufﬁces 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 segments2. For ease of discussion, we further deﬁne

the fuel consumption function for a truck to traverse eas

ce(te),te·fe(De/te),∀te∈[tl

e, tu

e],(1)

where teis the travel time of the truck and tl

e,De/ru

eand

e,De/rl

eare the minimum and maximum travel duration,

respectively. We note that ce(·)is strictly convex over [tl

e, tu

as its second-order derivative c00(te) = f00 (De/te)D2

e/t3

eis

positive. The function has taken into account the inﬂuence of

road grade, surface type, truck weight, and environment con-

ditions. We deﬁne the platooning fuel consumption function

when the two trucks platoon on road segment eas

e(te) =2(1 −η)ce(te),(2)

where η∈(0,1) is the average fuel-saving ratio and it

usually takes value around 0.1 [20], [25], [26]. Thus when

the two trucks platoon at the same speed, they jointly save a

2η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 [20], [26], 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 veriﬁed 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

(si, di, αi

s, βi

s, αi

d, βi

d),i= 1,2. Here siand diare origin

and destination for truck i, respectively. The pickup window

[αi

s, βi

s]deﬁnes the time period for pickup at si, and the deliv-

ery window [αi

d, βi

d]represents the time period for delivery at

di. We deﬁne the traveling time window of truck i(i= 1,2)

as Ti

s, T i

d, where Ti

s,αi

sand Ti

d,βi

dare the earliest

departure time and the latest arrival time, respectively.

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 ﬁrst compute

the optimized total fuel consumption of two trucks driving

separately, by applying the single-truck algorithm [60] to

2The 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.

Start

Two-truck

platooning

instance

Get the solution

without platooning Stop

Two truck

platooning

feasible?

Yes Get the solution

with platooning

Return the solution

without platooning

Return the solution

with less fuel cost

from the two solutions

Fig. 1: The ﬂow chart of our overall solution.

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

decomposition.

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 ﬁrst step. Otherwise, we

solve the feasible two-truck platooning problem with our pro-

posed 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.

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-

hard3and admits no FPTAS4. Interestingly, the following

lemma reveals an elegant structure of the feasible two-truck

platooning problem, which allows us to signiﬁcantly 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.

Lemma 1 covers the observation in [26] as a special case

without deadline constraints and speed planning. It implies

3A problem is APX-hard if it is NP-hard and cannot be approximated within

an arbitrary constant factor (≥1) in polynomial time unless P=NP.

4In 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 [19], [71].

that without loss of optimality, we can focus on solutions in

which the two trucks form a platoon only once. This structure

signiﬁcantly reduces the number of platooning conﬁgurations

to consider, leading to a new formulation that admits efﬁcient

algorithms. In particular, applying Lemma 1, we divide the

two-truck platooning problem into merging and splitting points

selection problem and the following ﬁve sub-problems:

1) pre-platooning path and speed planning for truck 1;

2) pre-platooning path and speed planning for truck 2;

3) in-platooning path and speed planning for truck 1 and

4) post-platooning path and speed planning for truck 1;

5) post-platooning path and speed planning for truck 2.

We denote the ﬁve decomposed paths by sub-path 1/2/3/4/5,

respectively; see Fig. 2 for an illustration. For ease of presen-

tation, we denote the set {1, ..., k}as Nk. We introduce binary

variables xi

e, e ∈E, i ∈N5for path planning, where

e=1,if edge eis selected by the sub-path i;

0,otherwise.

We also introduce non-negative variables ti

eto denote the

travel time of the (corresponding) trucks over edge eon the

sub-path i. Furthermore, we use binary variables yvand zvto

indicate whether the two trucks start and ﬁnish platooning at

node v∈V, respectively.

D. Problem Formulation

For simplicity of presentation, we deﬁne ~x ,(xi

e, i ∈

N5)e∈E,~y ,(yv)v∈V,~z ,(zv)v∈V,~

t,(ti

e, i ∈N5)e∈E,

and T,~

t:tl

e≤ti

e≤tu

e,∀e∈E, i ∈N5. We deﬁne Pas

the feasible set of (~x, ~y, ~z)as follows:

P,n(~x, ~y, ~z)xi

e, yv, zv∈ {0,1},∀e∈E, i ∈N5, v ∈V,

e∈Out(v)

e−X

e∈In(v)

e=1v=s1−yv,∀v∈V,

e∈Out(v)

e−X

e∈In(v)

e=1v=s2−yv,∀v∈V,

e∈Out(v)

e−X

e∈In(v)

e=yv−zv,∀v∈V,

e∈Out(v)

e−X

e∈In(v)

e=zv−1v=d1,∀v∈V,

e∈Out(v)

e−X

e∈In(v)

e=zv−1v=d2,∀v∈V,

v∈V

yv= 1,X

v∈V

zv= 1o,(3)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1OptimizingTwo-TruckPlatooningwithDeadlinesWenjieXu,TitingCui,andMinghuaChen,Fellow,IEEEAbstractWestudyatransportationproblemwheretwoheavy-dutytruckstravelacrossthenationalhighwayfromseparateoriginstodestinations,subjecttoindividualdeadlineconstraints.Ourobjectiveistominimizetheirtotalfuelconsump-t...

展开>> 收起<<

1 Optimizing Two-Truck Platooning with Deadlines Wenjie Xu Titing Cui and Minghua Chen Fellow IEEE.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Optimizing Two-Truck Platooning with Deadlines Wenjie Xu Titing Cui and Minghua Chen Fellow IEEE

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: