带时间窗的卡车编队路径优化

张泽锡，钟文健，林柏梁

(北京交通大学，交通运输学院，北京 100044）

0 引言

卡车编队的概念最早出现在20世纪60年代，LEVINE 等[1]称这种组织方式为“一排移动的车辆(A String of Moving Vehicles)”。指将一组采用车联网技术而实现彼此相连的卡车以较短的车头间距共同行驶的组织模式。意味着，尽管没有物理连接，但多辆卡车却可以非常紧密的连接在一起共同行驶，跟随车(后车)根据引导车(前车)的行驶状态采取刹车、加减速和转向等操作，共同完成运输任务。这种新兴的组织形式可以带来效率提升、资源节省和安全保障等多个方面的优势，因此，受到了广泛关注。当前，斯堪尼亚和特斯拉等公司已经对这种组织方式展开研究。此外，YOU 等[2]也提到，未来该组织模式可以广泛应用在高速公路沿线的服务区或高速公路出入口附近的配送中心和仓库。

驾驶强度和能耗排放强度较大的大型货运车辆是环境污染的主要来源[3]，从节约燃油成本的角度，卡车编队行驶相比卡车单独行驶，具有更近的车头间距，引导车起到帮助跟随车“破风”的作用，形成气流真空带，降低跟随车辆的空气阻力，达到减少燃油消耗的目的。不同的车头间距、行驶速度以及编队规模会产生不同的燃油节省，ALAM 等[4]通过实验表明，当2辆卡车以行驶速度80 km·h-1和车头间距为25 m 行驶时，可以减少约30%的空气阻力，当变为由3 辆卡车组成的卡车编队时，可以减少40%的空气阻力，由于空气阻力的下降进而产生燃油节省。卡车编队行驶除节省燃油消耗外，也有助于降低碳排放水平，根据欧洲道路交通远程通信协调组织的研究报告显示，卡车在编队行驶状态下，引导车最多可以减少8%的CO2排放，跟随车辆最多可以减少16%的CO2排放。

由于卡车编队具有较短车头间距的特点，在降低燃油消耗的同时，占据更少的道路资源，显著提升道路通行能力。VANDER 等[5]估算出采用卡车编队的模式运行可使得每小时的道路通行能力增加1 倍。LIORIS 等[6]以城市道路系统中的交叉口为例，论证了编队通行的流动性优势，以16个交叉口73 个路段为背景，证明了编队行驶可以使得交叉口的通过能力增加为原来的2倍。

从保障安全的角度，道路安全全球现状报告指出，道路交通伤害已成为人类第八大死因，其中，90%以上的交通事故是人为原因造成的。通过采用跟随行驶将操作任务交给车辆自动完成，可以极大程度上减少驾驶员失误的概率，有效缓解驾驶疲劳，使得驾驶员的驾驶任务减免50%以上，在降低人力成本的同时提高道路行驶的安全性。

当前，针对这种颇具前景的组织方式，众多研究机构和研究人员在传感器控制、无线通信及雷达定位等技术领域进行研究，但在运营管理及调度技术上的研究则略显不足。然而，运营管理的优劣在很大程度上决定了这种组织方式的性能，因此，进行以提升运营管理水平为目标的卡车编队优化研究对进一步发挥卡车编队的优势大有裨益。当有意愿形成卡车编队的驾驶员数量充足时，不需要事先计划就能自发的形成卡车编队。但在该模式运用的初期，卡车编队的自发形成则可能遇到困难。因此，当前如何集中规划促使不同的卡车集中在一个卡车编队中共同行驶是需要解决的问题。

BHOOPALAM 等[7]首先对卡车编队这种组织方式中出现的各种新的交通规划问题进行分类；然后，调查了文献中这些问题的相关运筹学模型和解决方法；最后，确定了未来研究的方向。LARSSON等[8]构建了没有时间期限约束的可无限排队的卡车编队整数线性规划模型，以真实的大规模路网为背景，采用启发式算法求解出最优的燃油消耗。但忽视了卡车运行的时间窗口，这可能会导致卡车编队的集结等待时间过长，从而高估卡车编队的效果。此外，每辆卡车的路径事先是固定的，优化目标主要是通过组成卡车编队减少空气阻力，从而产生燃油成本节约，而本文中的路径则是不确定的，是需要解决的决策变量，优化目标要比仅仅通过卡车编队行驶，由于空气阻力减少所带来的燃油节省更为复杂。HOEF[9]设置集中协调者，收集完整的卡车信息用来生成卡车编队计划，即从行程确定的卡车中筛选出具有相同行驶路段的卡车，形成可无限排队的卡车编队，达到减少燃油消耗的目的。然而，以上文献均采用固定路径下无限编队模式，即卡车编队的规模不存在限制，只要具有重合路段的卡车不论数量多少均会被编入卡车编队中。然而，在实际情况中，卡车编队的规模会对道路安全以及基础设施产生不同程度的影响，因此，卡车编队的规模应该限制在合理的范围内。YOU 等[2]将集装箱运送问题拆解为运送重箱和取回空箱两个部分，将卡车编队作为一个整体，构建以系统总成本最小为目标的优化模型，利用启发式算法进行求解，证明增加卡车编队的长度并更好地协调客户之间的集装箱共享有助于降低运输成本。XUE 等[10]采用具有协作式巡航控制系统的编队模式，以燃油消耗和劳动力成本消耗最小为目标，构建了以解决集装箱运输为主要任务的卡车编队路径优化模型，并采用启发式算法进行求解，量化估算出卡车编队运行模式的优势。但该模型考虑的卡车编队为固定模式，即卡车编队一旦形成难以自由拆解，本文在这些文献的基础上，注重研究某一特定卡车在何时何地编入哪个卡车编队的问题，即卡车编队可以自由拆解和组合，凡具有重合时间窗和运行路径的卡车在满足卡车编队规模的条件下，均可以与不同的卡车形成不同的卡车编队。国内，谭二龙等[11]利用货车的轨迹数据，探索出卡车编队能够形成的最大编队长度，并研究路网中的货车数目对卡车编队的影响，估算出货车自发编队所产生的燃油节省。

与其他相关研究相比，本文从运营管理及调度技术的角度研究卡车编队，在保证货物运输时效性的基础上，最大限度地节约燃油。为使构建的模型更加符合道路运输实际情况，考虑了卡车编队形成全过程，以卡车成组运行可以使得空气阻力下降，进而产生可观的燃油节省为研究动力，综合考虑卡车编队形成过程中额外产生的等待集结时间，以及为了形成卡车编队合理绕行因而额外增加的燃油消耗，作为成本纳入目标函数中，使得优化结果更具参考价值。此外，与以往的研究相比，本文并未将卡车编队问题视为旅行商问题，固定卡车编队去访问每一个节点并最终回到起始节点，而是借鉴商品网络流理论构建优化模型，卡车可以自由的选择是否与其他卡车共同组成卡车编队成组运行，优化结果既能体现各个弧段上卡车编队的构成情况，又能反映每个运输任务具体的走行路径。并通过数值实验进行验证，证实了模型的合理性和准确性。

1 卡车编队的形成

卡车编队根据自动化水平可以被划分为人工驾驶模式(HVs)、全自动驾驶模式(AVs)和半自动驾驶模式这3 个不同的层级。人工驾驶模式指卡车编队均由人类驾驶员驾驶，跟随车驾驶员手动完成与前车的跟随任务。全自动驾驶模式是未来的发展方向，即引导车辆和跟随车辆均可以在任何时间、任何路径和任何环境条件下完成所有动态驾驶任务。在港口码头和仓库工厂等相对封闭的场所中，全自动驾驶的卡车更容易实现，但对于开放的路网和复杂的真实路况，以现在的技术发展水平难以做到真正的自动驾驶。因此，YOU 等[2]和BHOOPALAM 等[7]众多学者以配备了协作式巡航控制系统(Cooperative Adaptive Cruise Control,CACC)的半自动卡车为例，进行卡车编队的优化研究。李淑庆等[12]的研究也表明，配备了协作式巡航控制系统的车辆可有效抑制速度扰动的波动幅度，使车队行驶趋于稳定。车辆之间通过V2V(Vehicle to Vehicle)通信技术彼此交换无线信息，无需通过基站转发，采用更小的车头间距实现对前车的自动跟随。引导车虽然仍需要人类驾驶，但其后的1个或多个跟随车辆会根据前车的行驶状态，自动实现刹车，转向和加减速等基本的驾驶任务，跟随车辆仍配备驾驶员，但无需进行人工驾驶，驾驶员主要解决一些突发情况。本文以目前较为成熟的半自动驾驶模式为基础展开研究，各种不同驾驶模式下的卡车编队如图1所示。

图1 各类驾驶模式下的卡车编队Fig.1 Truck platooning in various driving modes

在卡车编队推广应用的初期，以配备了协作式巡航控制系统的半自动驾驶卡车为卡车编队形成的技术基础，只有充分掌握卡车的出发地、目的地、最早出发时间、最晚到达时间、行驶速度以及可行的行驶路径等运输信息，筛选出潜在的可形成卡车编队的卡车，才能保障卡车编队的形成。

假设有7 辆具有运输任务的卡车需要将货物从5 个不同的起始地运送到4 个不同的目的地，卡车编队如图2所示。

图2 卡车编队示意图Fig.2 Truck platooning diagram

图2中，不同的实线表示不同起讫点的卡车可能的行驶路径。如图2(a)所示，共包括走行HGKD路径、GKD路径、ABJK路径、BJKG路径和IKF路径的5 个不同运输任务的卡车。虚线则表示另外可行的行驶路径，为了同其他卡车组成1个卡车编队，某些卡车也可能调整固有的行驶路径，甚至会产生一些迂回。例如，在图2(a)中，实线ABJK路径和虚线AIK路径均可以将货物从起始点A运送到目的地K，但如何选择行驶路径则需要综合各方因素，才能最终确定。

重合的行驶路段是构成卡车编队的必要条件，但最终是否能够形成卡车编队还需要结合各个运输任务的起止时间。如图2(b)所示，在以地点的经纬度为横纵坐标的基础上，增加时间轴为竖坐标，构建三维图，将卡车的出发时间和到达时间通过竖坐标的数值加以表示。其中，假定从A地出发的卡车行驶到B地时，正好满足B地卡车的最早出发时间，则无需等待。ABJK路径和BJKG路径中相互重合部分(BJK路线)、HGKD路径和GKD路径中相互重合的部分(GKD路线)则表示形成的卡车编队。其中B地和G地分别为卡车编队形成的地点，而K地和D地则分别为卡车编队解散的地点。

在真实的情况下，单个卡车或小规模的卡车编队为了与其他卡车共同组成规模更大的卡车编队，很可能产生集结等待时间。因此，为了更加合理地制定卡车编队运行计划，需要全面了解不同卡车包括：出发地、目的地、最早出发时间，最晚到达时间以及起始地及目的地之间的可能路径等在内的行程信息。此外，由于道路设计通行能力及安全原因，需要限制每个卡车编队的最大允许长度，此举也可能会对卡车编队的形成过程产生影响。

卡车编队可以通过前车减速和后车加速或两者结合的方式来形成，但在实际情况下，由于高速公路的最高限速和最低限速的影响以及路况的不确定性，采用这种方式组成卡车编队，不仅会导致卡车编队的形成过程消耗较长的时间产生不必要延误，而且会影响到其他车辆的正常行驶产生拥堵。此外，以目前的技术条件，很难精准控制每辆可能形成卡车编队的卡车在每一时刻的速度，因此，本文选用等待的方式形成卡车编队，并引入卡车编队集结时间的概念，展现卡车编队的形成对于正常驾驶的影响，在保证货物运输时效性的基础上，最大限度地节约燃油。

综上所述，当配备了协作式巡航控制系统辅助驾驶技术的卡车只有在走行路段相重合且运行时间相似时才有可能形成卡车编队，因此，充分而准确地掌握这些运输信息是合理安排哪些卡车组成卡车编队和确定某一特定卡车在何时何地加入或脱离卡车编队的关键。在此基础上，本文将考虑卡车编队形成全过程，例如：为形成卡车编队而额外产生的等待时间和合理绕行而增加的燃油消耗等因素，以最大程度地促进卡车编队的形成，尽可能地节约能源。

2 卡车编队的模型构建

为反映卡车编队形成全过程，在保证货物运输时效性的基础上，最大限度地发挥卡车编队节约燃油的效果，本文的运营成本采用包括时间成本和燃油成本在内的广义成本。为使全部运输任务总的运营成本最小，在货物运输过程中需要充分考虑货物的出发地、目的地、最早出发时间以及最晚到达时间等一系列可能影响到货物运输的因素。卡车编队运营成本通常包含燃油成本、与旅行时间有关的时间成本以及当货物未能按时送达的惩罚成本。因此，运营总成本为

式中：C为运营总成本；C(time)为运输所消耗的时间成本；C(penalty)为货物未能按时送达的惩罚成本，其中，与时间有关的成本均依据美国交通部时间价值的取值规则进行换算；C(fuel)为运行所消耗的燃油成本；X为计算运营总成本所涉及到的一系列决策变量，例如出行时间和走行路段等。

2.1 运行时间及集结时间分析

通常情况下，途中的行驶时间与运行里程相关，在运行里程和速度确定时，途中的行驶时间便可以唯一确定。途中的行驶时间为

式中：节点集合为N={1,2,…,i,j}，其中，相邻两个节点所组成的弧段集合ε={(i,j):i,j∈N,i≠j} ；uij为相邻节点间从节点i到节点j，即弧段(i,j)花费的行驶时间；dij为弧段(i,j)的里程；vˉ为途中的平均行驶速度。

除途中的行驶时间外，还需要考虑卡车编队的集结时间，由于高速公路的速度限制与路况的不确定性，难以精准地构建每个卡车编队的集结时间。因此，本文引入卡车编队平均集结时间的概念，衡量每辆卡车在该环节形成卡车编队所花费的平均集结时间。卡车编队的平均集结时间为

式中：τij为在弧段(i,j)上，形成卡车编队过程中，平均每辆卡车所花费的集结时间；hij为弧段(i,j)上的车头时距；ω为卡车数量。因此，卡车编队的平均集结时间与卡车数量和车头时距呈正相关。例如，当2辆卡车组成1个卡车编队时，其第2辆车与前车的时间差恰为车头时距hij，因此，平均每辆卡车的集结时间为与此相似，当3 辆卡车组成1 个卡车编队时，第3 辆卡车与第2 辆卡车的时间差为车头时距hij，但第3辆卡车与第1辆卡车的时间差为2倍的车头时距2hij，因此，平均每辆卡车的集结时间为当车队为其他规模时，也可以通过式(3)得到。车头时距为

式中：Qij为弧段(i,j)上可形成卡车编队的卡车交通量，其中，每个弧段上具体的交通量根据每个运输任务所包含的运输信息综合测定。由式(4)可知，卡车编队的集结时间与可形成卡车编队的卡车交通量呈反比，可形成卡车编队的卡车交通量越大意味着卡车编队的集结时间越短。例如，某弧段(i,j)上可形成卡车编队的卡车交通量为10 车·h-1，则所形成卡车编队产生的最短集结时间约为6 min。

此外，相邻节点所构成的弧段消耗的运行总时间为

因此，某一弧段的运行时间成本为

式中：为弧段(i,j)所花费的时间成本，ct为时间成本的系数。由于卡车编队的形成并不会影响任意弧段上所花费的行驶时间，因而，在卡车编队路径优化模型中仅考虑卡车编队形成过程中额外产生的集结等待时间。

卡车编队的集结时间占整个行程时间的比值为

式中：γ为组成卡车编队的临界值。在实践中，为了促使形成卡车编队，卡车编队的集结时间τij所占整个行程所花费的总时间tij不应过大，本文采用βij衡量卡车编队集结时间的占比，当βij ＞γ时，则不会形成卡车编队。

2.2 延误时间分析

设卡车集合为K={1,2,…,n}，不同的卡车沿着给定的路径从起点向终点行驶，当这些卡车均沿着同一路段向同一方向行驶时，这些不同起终点的卡车便可以在途中组成一个卡车编队。然而，卡车并不能在任何时候离开起始点，而是需要约束在出发时间窗口内为卡车k从节点i出发的最早时间，为卡车k从节点i出发的最晚时间。由于卡车需要充足的准备时间，早于最早出发时间出发是难以实现的，若晚于最晚出发时间出发，到达目的地时则难以达到客户的要求。因此，每辆卡车需要根据自身特定的时间窗去自由的选择独自出发还是与其他卡车共同组成卡车编队。

根据货物的类型及客户的要求，当卡车编队难以按照时间窗运送货物时，便会产生因货物提早出发或延迟出发所产生的惩罚。假定实际的出发时间为，则当卡车k提前于最早出发时间出发时，所提前的时间为

当卡车k晚于最晚出发时间出发时，所延误的时间为

因此，考虑提前出发和延误出发的惩罚项为

式中：pa为出发时间早于卡车最早出发时间时的惩罚系数；pd为出发时间晚于卡车最晚出发时间的惩罚系数。

因此，货物未能按规定的时间窗运送时所产生的惩罚成本为

2.3 燃油节省分析

组成卡车编队行驶与卡车单独行驶最大的不同之处在于降低了跟随车辆的空气阻力，从而达到减少燃油消耗的目的。为进一步展现两者之间的差异，本文参照NORUZOLIAEE等[13]构建简化的燃油消耗公式。卡车编队的总燃油消耗由卡车编队形成前(持续时间为τij)和卡车编队形成后(持续时间为tij-τij)所产生的燃油消耗两个部分构成，卡车编队某一弧段的燃油消耗为

式中：Fij(ω)为该卡车编队在弧段(i,j)所产生的燃油费用，除额外表示卡车编队规模外与含义相同；ζ为燃油价格；φ为每百公里燃油消耗；α为卡车采用编队形式行驶时跟随卡车产生的燃油消耗所节省的比重。通常情况下，卡车编队的加减速也会造成燃油消耗额外增加，但根据LAMMERT等[14]的实验研究发现，这些额外增加的燃油消耗微不足道，因此，卡车编队速度的瞬时改变并不会影响总的燃油消耗。

由于卡车编队的形成减少了跟随卡车的空气阻力，因此，这种组织形式极大地节省了燃油消耗。但对于首辆卡车来说，不论是否形成卡车编队，所产生的空气阻力的减少都微乎其微。因此，本文采用了LARSSON 等[8]和HOEF 等[9]以往大多数研究所采用的简单而直观的原则，即卡车编队中跟随车辆均以相同的比例计算所产生的燃油节省，而卡车编队中引导车的少量燃油节省则被忽略不计入所产生的燃油节省中。

当只有单独的1辆卡车在弧段(i,j) 行驶时，所产生的燃油消耗为

与单独1 辆卡车行驶相比，卡车编队每增加1辆卡车平均每辆卡车可产生的燃油节省为

式(14)表明，卡车编队集结时间的占比βij越小，则平均每辆卡车所产生的燃油节省的成本越大。此外，燃油节省的比值α和卡车编队的规模ω越大，平均每辆卡车所产生的燃油节省越多。其中，燃油节省比值α的值取决于卡车编队规模和卡车编队之间的车头间距等多方面因素。当卡车单独出发时，本文仍然将其视为1 个卡车编队，该卡车编队的卡车数量为1 辆，即ω=1，因而，并不会产生相应的燃油节省。

2.4 卡车编队路径优化模型

假设道路网络G={N,ε}，其中，节点集合为N，连接这些节点的弧段集合为ε，每个节点对应1个城市，每个弧段对应1 条路段。此外，定义运输任务集合为K，每1个运输任务仅包括1辆卡车，因此，第k个运输任务与第k辆卡车的含义相同，均包括起讫点、出发时间及到达时间等运输信息。其中，不同运输任务的起讫点可能相同，运输时间也可能重合。

在节点集合中N={1,2,…,i,j}，由这些相邻两个节点所组成的弧段集合ε={(i,j):i,j∈N,i≠j}，dij=|ij|为每条弧段的里程，其中，i,j∈N,i≠j。当完成这些运输任务时，会经过众多不同的弧段，这些连贯的弧段组成了完成该运输任务的路径，即定义第k辆卡车的运输路径可以由起始地o(k)到目的地d(k)之间的一系列首尾相连的弧段表示。将这些弧段的里程相加便为整个路径的运输总里程。其中，当不同运输任务将在某一时刻经过相同路段时，则这些承担不同运输任务的卡车可以组成卡车编队。

定义为0-1决策变量，当卡车k通过弧段(i,j)时，其值为1；反之，为0。通过该变量的定义使得优化结果既能直观反映每辆卡车具体的走行路径，又方便分析各个弧段中卡车编队的构成情况。此外，还需构建决策变量判断卡车编队是否形成，为0-1 决策变量，若在弧段(i,j)上第m辆卡车跟随在第k辆卡车后面运输，则该变量取值为1；反之，取值为0。为决策变量，表示卡车k从节点i出发的最早时间。

以卡车编队形成全过程为切入点，考虑完成全部运输任务所花费的时间及燃油成本最小化为目标，确定卡车编队路径优化模型的目标函数包含两个部分：第1 部分为卡车编队的燃油成本，表示为完成全部的运输任务所产生的总的燃油消耗；第2部分为时间成本，表示为卡车编队形成时所额外产生的集结时间和运输任务未满足时间窗的要求时所产生的惩罚成本，即

在卡车编队内，称某辆卡车之前与之紧密追随距离最近的卡车为该辆卡车的紧前卡车，某辆卡车之后与之紧密跟随距离最近的卡车为该辆卡车的紧后卡车。对于1辆卡车来说，当形成卡车编队且不为引导车时，它有且仅有1 辆紧前卡车，该约束保证了卡车编队的形成，即

节点处的流量平衡约束是保证每一辆卡车都可以从起始地运送到目的地，即

假定每个卡车编队最多可容纳θ辆车，确保卡车编队的规模限制在合理的范围内。卡车编队规模约束为

保证卡车编队形成的其他逻辑约束为

为避免出现个别卡车为了与其他卡车形成卡车编队而出现过度绕行情况，需要设置一定的绕道率约束绕行成本。绕道约束为

式中：D(k)为卡车k从起始地到目的地所需的最短路径里程；ρ为可以接受的最大绕行程度，通常情况下ρ≥1。

当卡车k从节点i出发的实际时间未按规定的时间窗运送时所产生的惩罚成本为

到达运输任务终点的时间不小于运输任务出发的时间、途中运输时间和平均每辆卡车所花费的在卡车编队形成过程中的集结时间之和。途中到达任意节点的时间约束为

为确保形成卡车编队内的卡车在相同时间出发，卡车编队内各卡车的时间约束为

式中：M为极大值。

此外，决策变量的取值范围为

综上，构建了卡车编队路径优化模型，模型以完成全部运输任务的燃油消耗成本以及额外增加的时间成本最小为目标，将每个运输任务是否通过路网中的弧段设置为决策变量，在考虑卡车编队规模的基础上，引入绕道率约束，既保证了卡车编队尽可能多的形成，又实现了最大限度地燃油节省，使卡车编队路径优化结果更加符合道路运输的实际情况，为卡车编队的广泛应用提供参考。

3 算例求解与分析

本文对某地区进行了人工抽象，路网G包括15 个节点，存在的路段数量为23 个。在卡车编队行驶技术普及的初期，同一家货物运输公司更易配置统一的可供于卡车编队行驶的通信设备。此外，从效益的角度考虑，来自于同一家货物运输公司的卡车驾驶员无需解决由于卡车编队内顺序不同而导致的收益分配不公平的问题。因而，企业内部的卡车更乐意组成卡车编队共同行驶。因此，本案例以某货物运输公司的30 个运输任务为例进行研究，其中，任意一个运输任务均包括起始点∈N，终点∈N，从起始点出发的时间，到达终点的时间。此外，该算例仅为验证模型的准确性，因此，假定卡车编队是在封闭环境中形成，不需要考虑社会车辆对卡车编队形成的扰动，并假定每辆卡车在途中任意时刻的行驶速度均相等，且平均行驶速度均为vˉ。每条弧段上的权重代表每条路段的里程，权重的单位为km。路网如图3所示。

图3 路网Fig.3 Road network

根据运输任务的起讫点可以将各个路段组合构成完整的运输路径。例如，从O→D的运输路径存在ONFD(总里程为188 km)、OMGFD(总里程为210 km)和OLJHD(总里程为223 km)等，当不考虑卡车编队运行时，显然ONFD路径为最优路径，但考虑卡车编队运行时，则需要考虑途中各个节点之间是否存在运输任务，以及各个运输任务的时间窗是否满足形成卡车编队的要求。因此，合理准确地组织卡车编队的形成是十分困难的，需要全面了解各个运输任务的起讫点和时间窗，将各个运输任务组合优化，才能得到全局最优的结果。考虑时间窗的卡车编队形成如图4所示。

图4 考虑时间窗的卡车编队形成图Fig.4 Formation of truck platooning considering time windows

假定任意运输任务的运输路径确定后，仍需要结合各个运输任务的时间窗来判断这些承担运输任务的卡车是否可以形成卡车编队。根据最早出发时间、最晚到达时间、公里数以及平均车速确定某个运输任务的最早出发时刻和最晚出发时刻，如图4(a)所示。以里程为x轴，时间为y轴，构建坐标系，以运输任务O→D时间窗为[8:00,13:00]和运输任务N→F时间窗为[9:30,12:30]为例进行绘制。如图4(b)所示，实心的阴影区域表示运输任务O→D可行的运行时间段，竖线形成的阴影区域表示运输任务N→F可行的运行时间段，其中，两个相互重合的阴影区域，即为可以形成卡车编队的可行时间段。其斜率为卡车在某任意时间的瞬时速度。

在计算前，需要对模型中使用的参数进行假定。参照NORUZOLIAEE 等[13]和国内成品油的价格确定参数φ=35 L·(1 00 km)-1，ζ=7 元·L-1。此外，依据美国交通部时间价值(VOT)的取值规则，结合中国的实际情况，ct=30 元·h-1。在卡车编队行驶的初期，需综合考虑可形成卡车编队的卡车数量等外在因素，因此，假定平均每个卡车在任意节点的集结等待时间均为6 min，每个卡车编队的规模不超过3辆卡车。形成卡车编队后，跟随车所产生的燃油节省比值为α=20%，该取值根据ALAM等[4]在隔离测试环境中的实地研究得出。此外，具体的运输任务如表1所示。

通过计算将30个运输任务分配在19个卡车编队中，与卡车单独运行相比节省燃油消耗超1000元，节省燃油费用达到14% 以上。 与NOURMOHAMMADZADEH 等[15]计算得出的5%的燃油节省相比，将卡车路径作为决策变量参与计算可以显著提升卡车编队的运营效果。采用商业软件LINGO11.0求解卡车编队路径优化模型，利用商业软件中自带的分支定界算法，经过90 s获得全局最优解，将计算结果进行汇总处理后，得出具体的卡车编队形成情况如表2所示。

表2中，以每个路段为1 个计量单位，例如：路段O→N中包括(1)，(2)，(5)这3 个不同的运输任务，可以在理论出发时间窗内的任意时刻出发，卡车编队在该路段上所产生的燃油费用为388.57元，与3辆卡车单独运行相比，卡车编队行驶可以产生59.78元的燃油费用节省。

表2 卡车编队求解结果Table 2 Calculation results of truck platooning

与传统的路径优化模型中选择起讫点间的最短路不同，根据求解结果可得：从L到I运输任务(14)的运行路径为L→K→I，但从图3中可知，该运行路径并非运输任务(14)的最短路径L→J→I，由于卡车编队的形成可以获得更多的燃油节省，因此，运输任务(14)放弃了原最短路径，在满足合理绕行的条件下，与运输任务(6)和(7)共同组成了卡车编队。同样，运输任务(7)为了与运输任务(6)组成卡车编队达到整个系统燃油消耗最小的目的，也放弃了原最短路径。

选取从起始点O到目的地A的路径展示卡车编队形成的具体情况，如图5所示。图中，上方的弧线表示运输需求，包括O→A，O→D，O→N，N→F，F→A和D→A这6 个不同的运输任务。在卡车编队规模为3 辆卡车的情况下，共形成4 个不同的卡车编队，其中，下方实线为形成卡车编队的路段，下方点划线为在该运输任务中尚未完成的路段，下方虚线为在该运输任务中已经完成的路段。

图5 形成的卡车编队Fig.5 Formation of truck platooning

4 结论

本文以配置了协作式巡航控制系统的半自动卡车为技术基础，从运营管理及调度技术角度对卡车编队行驶进行优化研究，以卡车成组运行可以使得空气阻力下降进而产生可观的燃油节省为研究动力，与其他研究相比，本文的创新性主要体现在：

(1)将时间成本和燃油消耗成本同时纳入目标函数，并将每个运输任务是否通过路网中的弧段设置为决策变量，优化结果既能反映每个弧段上卡车编队的构成情况，又能体现每个运输任务具体的走行路径。模型的约束除了考虑卡车编队的规模外，还将卡车为了形成卡车编队从而产生的合理绕行路径纳入约束体系，构建反映卡车编队形成全过程的卡车编队路径优化模型。

(2)以人工抽象假设的30 个运输任务需求为例，采用商业软件求解所构建的卡车编队优化模型，得到卡车编队19 个，节省燃油费用达14%以上，验证了模型的准确性，优化结果也证实了从运营管理角度进行综合优化有助于卡车编队充分发挥自身优势。