交通信息物理系统中的车辆协同运行优化调度

2019-02-15原豪男郭戈

自动化学报 2019年1期

原豪男郭戈

公路货物运输是原材料和产品有效运送和及时供应的关键供应链组成部分,占地面货物运输的60%[1],对社会经济发展至关重要.随着经济的持续发展,货运市场呈现多元化趋势,新市场不断涌现,客户群不断增长.同时,行业内的竞争日趋激烈,燃料价格及运输成本不断走高,温室气体排放限制更为严格,使得公路货运面临严峻的挑战.许多企业开始在保证运输业务高质量的同时,寻求降低运输成本的方法.例如,道路基础设施运营商探讨通过道路可变限速、匝道合并、可选路线推荐等措施来提高交通系统的安全与效率[2],而货物运输运营商则侧重研究运行优化方法、算法及规划软件[3],包括油耗建模及基于不同油耗模型的交通规划[4].

近年来,基于信息和通信技术的交通信息物理系统(Transportation cyber physical systems,TCPS)为解决上述问题提供了有效的方案.该系统集成的环保型车辆通常配备先进的信息处理和通讯设备,可实现车辆与车辆、车辆与设备通信[5].同时,云计算和服务框架为TCPS提供了强大的计算及存储能力,并可与第三方工具和服务无缝集成,使得车辆的实时协调和自动控制成为可能.利用TCPS的部分功能,即可实现车辆的小间距跟随行驶控制(称为车队技术或道路火车技术),在提高道路容量、降低燃料消耗、提高交通效率和安全性等[6]方面有巨大的潜力,受到研究人员、汽车制造业和交通运输部门的广泛关注.文献[7]研究了具有公共路段的车辆合并算法,并对实际车队行驶进行验证和评估.文献[8]提出一种基于本地控制器的快速车队合并启发式算法.文献[9]提出一种基于最短路径和燃油最优的集中式车辆协调调度和控制方法.文献[10]采用数据挖掘技术研究了不同车队的经济性.

TCPS的核心并不在于车辆的协同编队问题,而在于通过交通载运工具、交通参与者、基础设施等交通要素的信息感知,利用高效可靠的信息传输和计算处理能力,形成有效、完备的控制信息,实现对交通运输系统的实时高效优化控制.简而言之,TCPS的主要规划手段为大范围的交通优化调度.尽管目前对所有车辆进行调度尚不现实,但如果拥有庞大规模车辆的运输公司能大范围合理调度和优化车辆任务路径和速度,使尽可能多的车辆在公共路段组成小间距车队行驶,则可大大降低运行成本和油耗.研究人员已对该问题进行了研究,文献[9]提出了一种大规模车辆的协调方案,此方案首先确定车辆的最短路径,然后在最短路径的基础上确定车队的组成.文献[11]同样基于固定路径,通过实施追赶策略完成车辆的最优分配.但实际中,由于交通状况、道路特征等因素使得最短路径的能耗并非最优,即路径最短可能并非最佳行驶路径[12].受文献[12]以“绿色路径”的启发,本文从不同角度研究车辆的优化调度问题.考虑到路径的改变可能促成更多车辆的合并,对同一区域位置和路径相近的多辆货车,可微调部分或全部车辆的速度与路径,使其在某些公共路段组成车队行驶,从而节约燃料.这样调度车辆合并的过程中,车辆的加速、减速和改变路径意味着不同的油耗或成本,加速会因空气阻力增大而导致油耗增加,而减速与改变路线可能导致延误问题.因此,如果涉及的车辆数量较大,则计算每辆车的最优行驶计划将非常困难.

大规模车辆调度的关键问题是如何有效划分车队集合,即如何从大范围车辆中选择出领队车辆及相应的跟随车辆.受聚类算法的中心点划分思想启发[13],本文采用聚类算法将大范围车辆划分为车辆集合,大大降低了车辆调度优化问题的难度[14].具体思想是以车辆合并行驶的最大燃料节约率为量度依据,通过聚类分析将大范围的车辆划分为多个车队集合,并筛选出领队车辆.

本文的贡献在于基于TCPS提供的车辆及交通信息,考虑车辆速度与油耗的关系、车队行驶节约燃油以及速度与路径选择对到达时间的影响,提出一种基于油耗优化的大规模运输车辆调度方法.1)在保证不延误的前提下协同规划新的行驶路径,使最初没有公共路段的车辆拥有部分共同路段,以油耗优化为依据,调度它们到指定的共同路段合并列队行驶;2)同时改变车辆路径和速度,使车辆尽快合并列队行驶;3)采用全局优化合并策略,调度所有车辆同时合并列队行驶,避免成对合并时节油率相近车辆需等待合并的问题.

本文结构如下:第1节为问题描述;第2节从速度、时间、位置等角度分析车辆的合并可行性,通过本文算法及聚类分析规划出车队集合,并针对每个集合中的车辆调度方案实现进一步的优化;第3节为信息传输异常及突发交通状况等问题的解决方案;第4节为仿真分析;第5节为结论和展望.

1 问题描述

1.1 路网及运输任务描述

设目标路网中存在一个有限运输任务的集合Nc,每个运输任务绑定一辆重型货车.车辆i的运输任务,包括车辆的起点、终点、出发时间、到达时间,车辆当前位置Pi=(ei(t),xi(t)),ei(t)表示车辆所处道路段,xi(t)为车辆在该路段行驶的距离.函数L(ei)表示路网模型与实际道路长度的映射关系.用R=(N,E)描述路网,N为所有节点的集合,E为所有边的集合,分别表示道路交叉口和连接两交叉口的路段.

实际路网中几乎所有的车辆都是单独行驶,缺少车辆间的协作,本文以车队行驶能有效减少跟随车辆的油耗为基础,通过改变车辆的路径与速度使原本单独行驶的车辆有机会合并成车队,且较单独行驶能够节约能耗.车辆的换路合并如图1.车辆在合并过程中包含单独行驶、合并、车队行驶和分离行驶四个阶段,每个阶段的对应速度如图1所示.值得注意的是,并非所有合并车辆都包含四个运输阶段.例如,部分车辆从出发地就与其他车辆组成车队行驶,不存在单独行驶与合并阶段;也并不是所有车辆的合并都需要改变路径,图1仅是对本文调度策略的一个说明.

1.2 油耗模型

车队行驶时,忽略车队中的车间距及车辆的物理尺寸,认为车队中所有车辆都有相同的位置和速度,每个车队包括一辆领队车及一辆或多辆跟随车,且只有跟随车辆能够节约能耗.

以速度的一阶多项式对车辆单位距离的油耗进行建模,并认为此种建模方式在速度区间[vmin,vmax]内与实际油耗相近,满足本文的研究需求.根据文献[15],可将油耗模型描述为

图1 车辆换路合并示意图Fig.1 The schematic diagram of vehicle merging

其中,v表示车辆速度,F1,F0,F1p,F0p为常数,θ(p)为二值函数,θ(p)=0表示车辆单独行驶或作为车队中的领队车辆,θ(p)=1表示车队中的跟随车辆.

所以车辆i从起点到终点的总油耗为

其中,vi[m]表示车辆i的速度序列且每辆车的m值不同,表示车辆i从起点到终点的路段数.所有车辆完成合并后的总油耗为

1.3 本文目标

本文的目标是在保证所有车辆准时到达终点的前提下,规划出最省油的运输方案.每辆车的运输方案主要包括车辆从起点到终点的路径及速度.

定义1(运输方案).车辆运输方案P=(e,v,t),包括路径e、速度序列v、时间序列t.路径e由路网中Ne条边的序列组成,e=(e[1],e[2],···,e[Ne]),e[k]∈E,速度序列v=(v[1],v[2],···,v[Nv]). 原则上车辆速度在任意时刻都可发生改变,本文假设速度仅在交通调度或拥堵时发生改变,其他情况均保持匀速行驶.所以Nv≤Ne.根据速度变化定义时间序列t=(t[1],t[2],···,t[Nv+1]),即速度v[k]在(t[k],t[k+1])保持不变.

2 车辆协同编组与运行优化调度

2.1 系统描述

目前,信息和通信技术被广泛应用于交通运输系统中,将传感器、控制单元和自动化技术与微芯片相结合,使它们能够通过无线技术相互通信.因此,现代交通运输系统的特点是运输物理空间(车辆动力学)和运输网络空间(传感器网络和通信网络)之间的紧密耦合.本文考虑如图2所示的调度系统,该系统由物理和网络两个平面组成.物理平面描述了交通环境约束下的车辆移动性,而网络平面描述交通物理系统和通信网络的信息.车辆通过先进的传感及通讯技术实时共享车辆的运输信息,然后通过中央处理器计算出每辆车的运输计划并发送回车辆.当有信息更新时(例如车辆偏离计划运输方案,运输任务的结束或新任务的产生),重复上述规划过程.

图2 车辆调度系统Fig.2 Vehicle scheduling system

交通信息物理系统是最复杂的控制系统之一,为车辆调度及合并问题提供有效的理论方法和解决方案.为了分析的易处理性,本文仅考虑在这个贡献中没有时间延迟的确定性情况(因网络传输延时对远距离车辆调度影响忽略不计),且控制决定可以立即执行.车辆在网络平面的运输方案的规划分为以下几个阶段:

1)收集每辆车可选择的前N条最短路径;

2)对所有目标车辆的合并可行性进行分析;

3)初步规划出车辆的运输方案,并筛选出领队车辆;

4)加入速度优化,规划出车辆的运输方案P.

由于阶段1的路径规划问题已经有了相当成熟的算法[16],所以本文不针对路径选择问题进行过多阐述,只需规划出满足条件的N条最短路径即可.

2.2 调度可行性

车队的形成对于实现车辆调度至关重要,如何有效地将分散在道路中的车辆组成车队是本文研究的关键问题,在调度前需要比较各路预测旅行时间及能耗的差异,当变更路径后效用增值超过一定阈值时,改变预选路径(最短路径)及速度.为此,需要判断车辆i和j是否满足换路合并的条件,即从时间、空间、能耗的角度分析车辆调度后能否满足运输任务的需求.

其中,

所以能耗最优的追赶速度vc表示如下:

其中,时间t表示后车追上前车的时间,与上文中的tc意义相同.

注1.本文计划通过调度所有车辆的路径与速度来完成编队行驶,而前文的描述仅考虑调度部分车辆完成车队行驶的问题.由于直接改变所有车辆的路径与速度可能会产生一个领队车辆存在多个候选车辆且不能完成与所有候选车辆的合并问题,所以本文首先通过局部调度方法实现车辆的初步优化,然后在局部调度的基础上实现改进优化.

2.3 车辆的合并决策

本节将车辆的默认运输方案与调度方案结合,从大范围车辆中规划出可合并的车辆集合.每个车辆集合包含一个领队车辆与多个最优跟随车辆,最优跟随车辆表示该车辆与其所在的车辆集合中的领队车辆合并成车队行驶能够最大限度的节约能耗.其中,领队车辆保持其默认运输方案,跟随车辆实施调度方案.

定义2(默认运输方案).车辆按照出发时选定的路径及速度行驶,在到达目的地之前,路径及速度不发生改变.

定义3(调度方案).车辆通过改变路径与速度在公共路段完成与其他车辆的合并,组成车队行驶.

根据式(7)和式(8)的计算结果,定义两辆车合并行驶的燃料节约率k,循环计算每辆车实施默认运输方案、其他车辆实施调度方案所有车辆间的k值,并将所有的k值作为车辆协调图的权重.通常情况下的两辆车,分别采用调度方案时,只有一辆车能满足到达时间的限制,所以,本文认为任意两节点间的边只有一条,权重值只有一个.不存在A车可以作为B车的候选合并车辆、B车也可以作为A车的候选合并车辆的情况.

定义4(车辆协调图).车辆协调图为有向加权图G=(Nc,εc,Wc),Nc为节点的集合,每个节点表示一辆运输车辆,εc为连接两个节点的边的集合,Wc=k为每个边的非负权重.如果车辆之间不能合并成车队行驶或合并后不能节省油耗,那么这两个节点间不存在边.

根据上述定义,首先通过领队车辆选择算法筛选出领队车辆,简化协调图中的部分边,然后通过聚类算法规划出车辆的合并集合.算法中j表示协调图中直接与i相连的车辆集合,kij为车辆i和j合并行驶的燃料节约率,其中i为领队车辆,j为跟随车辆,∃k(j+1)(j+2)＞∃kj(j+1)表示存在一种车辆组合j+1,j+2的燃料节约率大于所有的车辆j,j+1的组合.车辆i与车辆集合j,j+1,j+2的关系如图3所示.领队车辆集合筛选完成后,需要确定每个集合中的跟随车辆,由于领队车辆的确定简化了协调图中部分车辆间的边的关系,使得候选车辆的选择问题类似于数学中的聚类分析问题,且已知聚类中心的个数,所以通过k中心点算法来获得每个车队集合中的跟随车辆,计算车辆i应该属于的车队.

其中,P(i)表示将车辆i分配给Nl个车队中节油率最高的车队,通过比较候选跟随车辆与不同领队车辆间的最大燃料节约率k值,将跟随车辆划入k值最大的领队车量集合中,以此初步确定车辆的合并方案.

算法1.领队车辆选择算法

输入.finitely transport assignmentsNc

输出.leading vehicle setNI

图3 车辆与车辆集合的关系示意图Fig.3 The schematic diagram of the relationship between vehicles and vehicle sets

2.4 车队集合的速度优化

本节考虑通过第2.3节规划出的车队集合P中的车辆的速度优化问题.根据文献[17]可知,当两辆车合并成车队时,同时调节两辆车的速度相对于单一追赶策略能够更大限度地节省能耗.而前文中的调度方案是在领队车辆采用默认运输方案、跟随车辆采用调度方案的基础上确定的.而本文是在保证车辆集合中所有车辆能够完成合并的前提下做出进一步速度优化,该优化可以改变车队集合中所有车辆的速度与路径,即每个车队集合中所有车辆均可执行调度方案.其中,车队集合中所有车辆的公共路段集合用R={e1,e2,···,en}表示,n为最大公共路段数.

考虑每个车辆集合中包含一辆领队车辆nl及多辆跟随车辆Nfi,nl={f1,f2,···},需要规划出每辆车的速度序列及时间序列.

车队集合中的车辆速度优化问题描述如下:

目标函数(13)与式(3)意义相同,表示每个车辆集合中所有车辆从出发位置到目的地的油耗和.两个限制条件(14)和(15)分别表示对合并位置与速度的限制,即所有车辆的合并必须发生在公共路段处且车辆的速度始终保持在道路交通所允许的速度范围内,其中vi表示车辆i各个阶段的速度序列,di表示各阶段行驶的距离,表示如下:

上述优化问题可借助计算机利用数学规划方法得到各阶段与各个车辆的最优驾驶速度,将结果带入式(16)可得到相应的合并点及分离点的时刻与位置.

3 调度系统的可扩展性研究

对于本文的运输系统而言,网络的引入虽然为分散行驶的车辆调度与规划带来了方便,但无线传感网络的查询处理过程中的感知信息缺失问题不可避免,将给调度系统带来不利影响,甚至造成不稳定.另外,实际交通状况也可能造成车辆的误调度.将上述存在的问题视为干扰项,并提出相应的解决框架.由于网络延时对大范围车辆调度影响较小,所以针对网络信息传输异常数据及其突发情况造成的部分路段的车辆延误问题,提出了解决方案,同时也说明了本文运输系统的可扩展性.

定义5(异常信息).车辆在执行运输计划的过程中,未收到计划信息(通常指速度信息)或收到的计划信息发生突变而同一车队集合中的其他车辆运输计划信息保持不变,则认为该车辆发送或接收的信息异常(忽略速度调度时的信息异常).

由于车队集合中不同车辆的空间相关性,当某辆车或网络平面收到的速度信息异常时,可以利用STM算法通过车队集合中的其他车辆的信息对其进行估计.为不失一般性,设同一时刻仅存在一辆车速度异常.由于路径信息的不可跳变性,所以只针对车辆的速度异常信息进行估计,采用STM算法模型刻画目标车辆与车队其他车辆的速度相关性,车辆i对任意时刻t的估计信息如下:

基于空间相关性的SM算法对车辆i在t时刻的估计信息如下:

其中,V=(vi1,···,vih)表示车辆i在t临近时刻的h组样本数据,车队中m个其他车辆的数据组成X表示如下:

同理,可将基于时间相关性的TM算法的估计值表示如下:

其中,vik为车辆i在t时刻的前v/2时刻的实际观测速度轨迹,为t时刻后的理想速度轨迹预测值,k∈{1,···,v/2}.

虽然基于STM算法的信息估计可有效补偿丢失信息,但实际交通的突发状况也可能导致运输计划不可执行.车辆间信息传输机制如图4所示.

假设网络平面在t时刻收到的目标车辆状态信息Pi=(ei(t),xi(t),vi(t))与计划运输信息速度绝对误差超过一定阈值(10%),且多个采样周期的状态信息持续异常时,则需进一步判断.比较其前车t时刻与t-1时刻的状态信息,如果速度波动较大,则认为该路段可能出现突发状况,采集t+1,t+2,···多个时刻目标车辆与其前车的状态信息,如果速度恢复正常(目标车辆可按计划速度行驶),则运输系统持续进行监测状态;否则计算目标车辆与前车的车间距的变化率m,如果m持续降低到某一值时,则认为该路段发生车辆拥堵(不考虑路段车辆数达到路段最大容限及自身车辆事故等情况),需要重新规划车辆的运输计划.

由于突发状况不可提前预测,所以对车辆重新规划时需要预测车辆的拥堵时间,车辆恢复自由驾驶时,实施规划后的运输方案.拥堵时车辆行驶速度取决于道路的拥堵程度,且较难确定.因此以路段畅通ωi∈[0,1],车辆速度为任意值v0(以最佳车速为例)与路段车辆数达到最大容限ωi=cmax/ci,车辆速度为0作为端点值,用线性函数逼近ωi∈[1,cmax/ci]时车辆拥堵程度与车速的关系.

图4 信息传输机制Fig.4 Information transmission mechanism

其中,ωi=yi/ci表示道路的饱和度,yi为道路i的车辆数,ci为道路的拥堵容限,ωi≥1表示该路段发生拥堵,但车辆仍可以以某一速度行驶,当车辆数yi达到该路段的最大拥堵容限cmax时,车辆速度为0.

根据拥堵路段位置Pc=(ec,xc)、车辆当前位置Pi=(ei(t),xi(t))及拥堵路段平均车辆数量估计车辆的拥堵时间tct,将其作为合并阶段的延迟时间加入上述优化过程,重新计算车辆的运输方案.

对于物理平面车辆收到异常信息的情况可以通过发送多个数据包进行检验.

4 仿真实例

本节通过TCPS模拟实际高速公路路网,对本文提出的车辆调度方法进行研究.通过仿真分析验证本文的换路合并策略的有效性及相对于最短路径调度策略的优越性和可扩展性.

4.1 仿真条件

图5 车辆运输任务Fig.5 Vehicle transportation tasks

首先在TCPS的框架下,模拟构建华北及其周边地区的部分路网,其次在华北地区某时刻500km2的区域随机产生40个运输任务,如图5所示.在其周边约500～1000km2的区域产生A,B,C,D,E5个目的地,正方形表示车辆(每辆车当前时刻的位置),其中,在路线上的正方形的车辆表示正在执行运输任务的车辆,其他正方形表示待出发的车辆;六角星为车辆的目的地,且每辆车的当前状态信息及其目的地已通过TCPS获得.设在不发生调度的情况下,每辆车均以最短路径匀速单独行驶,未考虑路况及其他因素干扰.

采用的燃料模型为大约80km/h的仿射近似模型[15],以单位距离的油耗量表示车辆的油耗率.

根据该模型,当车队以80km/h的速度行驶时,跟随车辆的节油率约为15.9%.假设初始默认速度为80km/h,速度可选择区间在70～90km/h.

4.2 仿真分析

首先验证本文调度方案的有效性,设定每辆车的初始速度均为80km/h.将本文算法应用在模拟路网中,通过调整部分车辆的路径与速度使得部分车辆合并成车队行驶,对上述车辆的模拟调度结果如图6所示.其中,颜色相同的临近车辆表示可以通过路径与速度的调整(或只改变路径或速度中的某一项),使其在公共路段的某处组成车队行驶,且相对于单独行驶能够节省油耗.从图6可以看出,通过本文的调度方法,能够使较多车辆有机会合并成车队行驶,达到节能减排的目的.

图6 本文策略调度策略的仿真结果Fig.6 The simulation results of scheduling strategy in this paper

其次,验证变路径合并策略较固定路径合并策略[11]的优越性.文献[11]指出,当车辆相互靠近时,可以改变部分车辆的速度,使后车追上前车合并成车队行驶.将其思想应用在上述模拟路网,结果如图7.对比图6发现,可组成车队的车辆数明显减少,与之对应的节油能力也随之降低.原因如下:由于路网的复杂度较高,每辆车的最短路径不尽相同,固有公共路段较少且长度有限,到达公共路段的时间不一,所以合并成车队行驶的机会较少.假设存在出发地临近的两辆车,目的地相同,如果不改变路径,两辆车无公共路段.采用文献[11]中的固定路径策略,将无法节省能耗,如果采用本文的调度方法,通过路径与速度的微调,可以使车辆合并成车队行驶,从而降低能耗.从逻辑与仿真分析的角度验证本文的调度方案具有优越性.但本文的调度方案较大限度利用车辆的速度,使得本文策略在发生突发情况下的应变能力相对较差.

图7 固定路径合并策略的仿真结果Fig.7 The simulation results of fixed path merging strategy

最后,本文的策略也可以扩展到更多车辆,当某一地区参与运输的车辆数量增多时,车辆的合并机会也随之增大.基于本文换路合并策略与文献[11]中固定路径合并策略的大量车辆的仿真对比结果如图8.从图8可以看出,本文提出的策略在车辆较少时调度效果明显,可显著节约能耗.随着车辆的增加,两种策略的调度效果差距减少,但本文的策略总是优于固定路径合并策略.由于改变路径可以增加车辆合并的机会,使本文的合并策略在一定程度上包含了固定路径合并策略.

在实际路网中,许多因素会对车辆调度产生影响,特别是交通拥堵.所以,本文通过在不同位置设置不同的延时时间来模拟实际交通状况对具有公共路段的车辆合并的影响.仿真条件如下:具有公共路段的前后两辆车之间的车间距为2km,前车距离目的地100km,初始速度均为80km/h,车型一致,在不发生拥堵的前提下,两车合并行驶的最大节油率为13%.假设车辆经过拥堵路段后可自由行驶,且道路各个位置的拥堵消散速度一致.当不同位置出现交通拥堵时(设置不同的延时时间),两车的最大节油率如图9所示,可以看出,短时间的拥堵会对车辆的合并造成很大影响.本文的目的在于调度策略的研究,而交通流的预测可以通过TCPS预测得到,本文的调度策略可考虑更多实际情况.假设各个路段的拥堵状态已经预测得到(本文设置3处延时表示拥堵时间),其调度结果如图10.对比图10的圈出区域与图6的调度策略可以发现,交通拥堵状况的出现(随机在部分车队集合中设置的短时延时)可能使原本的车队集合分离,也可能使单独行驶的车辆与其他车辆合并,对调度结果影响很大,说明了实际交通状况对调度的重要性,同时也说明了本文调度方案的可扩展性.