An improved decomposition-based heuristic for truck platooning Boshuai Zhao1and Roel Leus2

2025-04-24 0 0 822.69KB 44 页 10玖币

侵权投诉

An improved decomposition-based heuristic for

truck platooning

Boshuai Zhao1and Roel Leus2

1ORSTAT, KU Leuven, Leuven, Belgium, boshuai.zhao@kuleuven.be

2ORSTAT, KU Leuven, Leuven, Belgium, roel.leus@kuleuven.be

Abstract: Truck platooning is a promising transportation mode in which several

trucks drive together and thus save fuel consumption by suﬀering less air resistance.

In this paper, we consider a truck platooning system for which we jointly optimize the

truck routes and schedules from the perspective of a central platform. We improve

an existing decomposition-based heuristic by Luo & Larson (2022), which iteratively

solves a routing and a scheduling problem, with a cost modiﬁcation step after each

scheduling run. We propose diﬀerent formulations for the routing and the scheduling

problem and embed these into Luo and Larson’s framework, and we examine ways to

improve their iterative process. In addition, we propose another scheduling heuristic

to deal with large instances. The computational results show that our procedure

achieves better performance than the existing one under certain realistic settings.

Keywords: truck platooning, decomposition, routing, scheduling

1 Introduction

Truck platooning is a transport mode in which several trucks drive together at

close distances. Due to the aerodynamics, trucks undergo less air resistance and thus

save in fuel consumption. Previous research (Bonnet & Fritz, 2000) indicates that

energy can be saved by at most 20% for the trailing trucks (so not for the ﬁrst one; we

arXiv:2210.05562v3 [econ.TH] 19 Feb 2023

subsequently refer to these trucks as the “following” trucks) of a truck platoon. This

transportation mode used to be diﬃcult to achieve because it requires close distances

between trucks. With the advances in autonomous driving technology, however, the

synergistic operation (e.g. acceleration, braking, and steering) of multiple trucks can

be guaranteed, and truck collisions avoided.

Various associations and academic institutes have recently paid attention to truck

platooning. In 2015, the Netherlands organization for applied scientiﬁc research

(TNO) gave a full report about the beneﬁts and risks of this freight mode, involving

diﬀerent supply chain stakeholders (Janssen et al., 2015). Later, the European Au-

tomobile Manufacturers’ Association (2017) provided a roadmap describing how to

achieve multi-brand platooning before 2025. In this roadmap, there are three stages

of autonomy: in the ﬁrst stage, drivers have to stay alert while driving; in the second

stage, drivers in the following trucks of a truck platoon can rest during the trip; and

the third stage is fully autonomous driving. Moreover, in 2017, the Transport De-

partment of Singapore cooperated with Scania and Toyota Tsusho to design a truck

platooning system for their country (Ministry of Transport - Singapore, 2017). In

2017, the Volpe center of the U.S. Transportation Department tested car platooning

in Maryland and believed this mode to be beneﬁcial for saving both time and fuel

consumption (Tiernan et al., 2017).

Creating a truck platoon is often diﬃcult for trucks because they usually follow

diﬀerent routes and delivery schedules. In most cases, before joining a platoon,

drivers have to wait in a station, hub, or highway entrance, and even change original

routes to meet other trucks, which unavoidably leads to additional delivery costs and

waiting time. Therefore, there is not only a trade-oﬀ between the beneﬁts and costs

of the platooning mode but also an adjustment for the truck’s time schedule.

We present a small problem instance to illustrate the general delivery process and

the functioning of the platooning mode. In this instance, three trucks are required

to deliver (travel) from their origin to their destination within a given time window;

see Table 1 for the details. Each truck can choose its own path. If a truck follows

another one in a platoon then it can save 10% fuel costs. For simplicity, we assume

that each truck maintains the same constant speed; the corresponding travel time

(expressed in minutes) and delivery cost on each arc are proportional, and equated

Table 1: Truck details for the example instance

Truck origin destination time window

A1 2 2:00 pm to 3:00 pm

B1 3 7:00 pm to 8:00 pm

C1 6 7:00 pm to 12:00 pm

3 4

1 1

0.99

1.5

Figure 1: Road network for the example instance (the numbers indicate the arc

lengths)

with the arc length; see Fig. 1 for the road network.

Two solutions are shown to illustrate how platooning inﬂuences distribution plan-

ning. Fig. 2 depicts a feasible solution in which each truck chooses its shortest path:

truck Afollows path 1 −2, truck Bon path 1 −3, and truck Con path 1 −2−5−6.

Since trucks Aand Bhave non-overlapping delivery intervals, they cannot meet on

arc (1,2) to form a platoon. Therefore, the total delivery cost can be computed as 1

(truck A) + 1 (truck B) + (1 + 1 + 0.99) (truck C) = 4.99. An optimal solution is

given in Fig. 3, where truck Astill follows path 1 −2 and Bpath 1 −3, but truck C

now takes path 1 −3−4−6. In this way, trucks Band Ccan form a platoon on

arc (1,3), thus saving 1 ∗10% = 0.1 due to the 10% cost savings for one of the two

trucks. The total delivery cost is then as follows: 1 (truck A) + 1 (truck B) + (1 +

1 + 1) (truck C)−0.1 (fuel saving) = 4.9.

Our work is inspired by the popular “sharing economy” concept. The popular-

ity of collaborative shipping is increasing, with as main goal to share the available

truck capacity (Creemers et al., 2017) and individual logistics capabilities (Dahle

et al., 2019). Truck platooning aims to share freight routes to reduce air resistance,

and can thus be regarded as a new type of collaborative shipping. The threshold for

3 4

AA C

Figure 2: A feasible solution

3 4

B C

Figure 3: An optimal solution

this type of collaboration is lower because diﬀerent sources do not need to be in the

same truck. Its potential users could be all trucks involved in the freight market,

similar to all private cars in the shared travel market.

In this paper, we focus on the operational planning issues of truck platooning

from the perspective of a central platform. Our goal is to explore which beneﬁts can

be gained by an integrated truck ﬂeet system, and how to design an algorithm for

the system to handle the dispatching of a large number of trucks. From a practical

perspective, our work can help the freight industry to eﬃciently integrate freight

resources and contributes to the reduction of air pollution. From an academic per-

spective, this research provides a better method for handling the large-scale joint

routing and scheduling problem.

Our contributions are threefold. First, we compare two diﬀerent mixed-integer

programming (MIP) formulations for making truck platooning decisions. Second, we

improve a heuristic based on a decomposition framework of Luo & Larson (2022).

Speciﬁcally, we propose diﬀerent formulations for the two subproblems of the frame-

work (the routing and the scheduling problem) and improve the iterative process.

Third, we provide a heuristic for the scheduling subproblem to handle large instances.

The remainder of this article is organized as follows: in Section 2, we present a

literature review. Subsequently, in Section 3, we deﬁne the truck platooning prob-

lem and examine two types of existing formulations, one in continuous time and one

in discrete time. Next, a decomposition-based heuristic based on Luo & Larson’s

framework is described in Section 4 and a heuristic for large scheduling instances is

developed in Section 5. Then, in Section 6 we analyze our computational experi-

ments. Finally, we conclude the article in Section 7.

2 Literature review

Below we survey earlier related work on truck platooning. We ﬁrst consider the

routing problem, then the scheduling problem, and then joint routing and scheduling.

2.1 Routing problem for truck platooning

The routing problem for truck platooning is to optimize the vehicle routes to

facilitate the formation of truck platoons. Larsson et al. (2015) study the truck

platooning problem by ignoring the constraints of delivery deadlines. They prove

that their problem is NP-hard and propose two constructive heuristics and a local

search algorithm. The ﬁrst one, called the best pair heuristic, with the same logic

as Larson et al. (2013), chooses the best pairwise platoons based on the platooning

savings. The second one, called the hub-based heuristic, divides the trucks into

several subsets and selects a hub for each truck subset. Here, the hub is selected from

certain nodes traversed by platoons. This method restructures the entire problem

into multiple sub-problems, where each sub-problem optimizes the routes for a subset

of trucks from the origin to the hub and then from the hub to the destination.

2.2 Scheduling problem for truck platooning

The scheduling problem is to adjust the freight schedule of trucks with ﬁxed

routes so as to enable them to form platoons. Boysen et al. (2018) consider the

identical-path platooning problem, in which all trucks have the same path but diﬀer-

ent delivery time windows. They propose three diﬀerent functions for the platooning

costs (linear, concave, and general) and analyze the computational complexity un-

der diﬀerent settings. Moreover, they explore the impact of various factors and ﬁnd

that few platooning partners, limited platoon size, and tight delivery time windows

can decrease the potential platooning beneﬁts. Van de Hoef (2016) studies a sim-

ilar problem but assumes that trucks can drive at diﬀerent speeds. He ﬁrst builds

a number of truck pairs and then constructs multi-truck platoons based on these

pairs. He proves that the problem is NP-hard and proposes a local improvement

heuristic for large instances. Zhang et al. (2017) consider platooning with uncer-

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

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

10 玖币 0人已下载

立即下载

摘要：

Animproveddecomposition-basedheuristicfortruckplatooningBoshuaiZhao1andRoelLeus21ORSTAT,KULeuven,Leuven,Belgium,boshuai.zhao@kuleuven.be2ORSTAT,KULeuven,Leuven,Belgium,roel.leus@kuleuven.beAbstract:Truckplatooningisapromisingtransportationmodeinwhichseveraltrucksdrivetogetherandthussavefuelconsumpti...

展开>> 收起<<

An improved decomposition-based heuristic for truck platooning Boshuai Zhao1and Roel Leus2.pdf

共44页,预览5页

还剩页未读，继续阅读

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

An improved decomposition-based heuristic for truck platooning Boshuai Zhao1and Roel Leus2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: