自动化学报  2019, Vol. 45 Issue (1): 143-152   PDF    
交通信息物理系统中的车辆协同运行优化调度
原豪男1, 郭戈2,3     
1. 大连海事大学控制科学与工程学院 大连 116026;
2. 东北大学流程工业综合自动化国家重点实验室 沈阳 110004;
3. 东北大学秦皇岛分校控制工程学院 秦皇岛 066004
摘要: 运输成本及温室气体的排放是衡量智能交通系统的重要指标,有效的运输调度可以降低运输成本和环境损害.针对路网中集成环保型货车的运输问题,本文提出一种基于交通信息物理系统(Transportation cyber physical system,TCPS)的大规模车辆协同调度及合并方案,以最大限度地降低运输成本和碳排放量.首先,采用局部调度策略,结合领队车辆选择算法及聚类分析,构建可合并车辆集合;然后,通过数学规划方法,实现每个车队集合中车辆路径与速度的改进优化处理;最后,通过突发情况的简易处理说明本文调度策略的可扩展性.仿真实验表明,用本文方法将车辆编组合并成车队行驶,较固定路径合并策略可显著降低路网中货运车辆的整体油耗.
关键词: 货运车辆     调度方案     交通信息物理系统     能耗    
Vehicle Cooperative Optimization Scheduling in Transportation Cyber Physical Systems
YUAN Hao-Nan1, GUO Ge2,3     
1. School of Control Science and Engineering, Dalian Maritime University, Dalian 116026;
2. Laboratory of Synthetical Automation for Industrial Process, Northeastern University, Shenyang 110004;
3. School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004
Manuscript received : May 28, 2018, accepted: September 27, 2018.
Foundation Item: Supported by National Natural Science Foundation of China (61273107, 61573077)
Author brief: YUAN Hao-Nan Master student at the School of Control Science and Engineering, Dalian Maritime University. His main research interest is intelligent transportation system.
Corresponding author. GUO Ge Professor at Northeastern University. He received his Ph. D. degree from Northeastern University in 1998. His research interest covers intelligent transportation system, moving target detection and tracking with network. Corresponding author of this paper.
Recommended by Associate Editor CHEN De-Wang
Abstract: Transportation costs and greenhouse gas emissions are important indicators of intelligent transportation systems. Effective transport scheduling can reduce transportation cost and environmental damage. This paper proposes a large-scale vehicle coordinated scheduling and merging strategy for large-scale vehicles based on transportation cyber physical systems (TCPS) to minimize transportation costs and carbon emissions. Firstly, a local scheduling strategy is used in combination with the leader vehicle selection algorithm and cluster analysis to construct the vehicle merging set. Then, through the mathematical programming method, the improvement and optimization of vehicle path and speed in each platooning set are realized. Finally, the expandability of the scheduling strategy is proved by the simple processing of emergency situations. Numerical simulation has shown that the method presented in this paper to schedule vehicle can greatly reduce the overall fuel consumption of vehicle fleets in fact compared to the fixed path merging strategy.
Key words: Freight trucks     scheduling scheme     transportation cyber physical systems (TCPS)     energy consumption    

公路货物运输是原材料和产品有效运送和及时供应的关键供应链组成部分, 占地面货物运输的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 路网及运输任务描述

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

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

图 1 车辆换路合并示意图 Fig. 1 The schematic diagram of vehicle merging
1.2 油耗模型

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

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

$ \begin{align} f(v, \theta(p))=&\ \theta(p)(F_{1p}v+F_{0p})\, + \nonumber\\ &\ (1-\theta(p))(F_{1}v+F_{0}) \end{align} $ (1)

其中, $v$表示车辆速度, $F_{1}$, $F_{0}$, $F_{1p}$, $F_{0p}$为常数, $\theta(p)$为二值函数, $\theta(p)=0$表示车辆单独行驶或作为车队中的领队车辆, $\theta(p)=1$表示车队中的跟随车辆.

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

$ \begin{align} F_{i}(v, \theta(p))=\sum\limits_{n=1}^{N_{i}^{d}}\int_{0}^{L(e[n])}f(v_{i}[m], \theta(p)){{\rm{d}}}x \end{align} $ (2)

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

$ \begin{align} F_{\mathit{\boldsymbol{total}}}=\sum\limits_{i\in N_{c}}F_{i}(v, \theta(p)) \end{align} $ (3)
1.3 本文目标

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

定义1(运输方案). 车辆运输方案$P=(e, v, t)$, 包括路径$e$、速度序列$v$、时间序列$t$.路径$e$由路网中$N_{e}$条边的序列组成, $e=(e[1], e[2], \cdots, e[N_{e}])$, $e[k]\in E$, 速度序列$v=(v[1], v[2], \cdots, v[N_{v}])$.原则上车辆速度在任意时刻都可发生改变, 本文假设速度仅在交通调度或拥堵时发生改变, 其他情况均保持匀速行驶.所以$N_{v}\leq N_{e}$.根据速度变化定义时间序列$t=(t[1], t[2], \cdots, $ $t[N_{v}+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], 所以本文不针对路径选择问题进行过多阐述, 只需规划出满足条件$\sum_{n=1}^{N_{i}^{d}}L(e[n])/v_{i{\max}}$ $\leq$ $t_{i}^{d}$ $-$ $t_{i}^{s}$$N$条最短路径即可.

2.2 调度可行性

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

$ \begin{align} &t_{i}^{s}+\frac{\sum\limits_{n=1}^{N_{i}^{D_{i}}}L(e[n])}{v_{i{\max}}}<t_{i}^{d}\nonumber\\& t_{j}^{s}+\frac{\sum\limits_{n=1}^{N_{j}^{D_{j}}}L(e[n])}{v_{j{\max}}}<t_{j}^{d} \end{align} $ (4)
$ \begin{align} &\small{\left|\frac{\sum\limits_{n=1}^{N_{i}^{m}}L(e[n])}{(1\!-\gamma)v_{i{\max}}\!+\gamma v_{i{\min}}}-\frac{\sum\limits_{n=1}^{N_{j}^{m}}L(e[n])}{(1\!-\gamma)v_{j{\min}}\!+\gamma v_{j{\max}}}\right|<} \nonumber\\ &\qquad\quad |t_{i}^{s}-t_{j}^{s}|, e[N_{i}^{m}]\in(e[t_{m}], e[t_{sp}]) \end{align} $ (5)
$ \begin{align} J_{\rm{coordination}}^{*}+c_{th}<J_{\rm{nominal}} \end{align} $ (6)

其中, $N_{i}^{D_{i}}$$N_{j}^{D_{j}}$表示车辆$i$$j$从出发地到目的地的总路段数, 上标$D_{i}$$D_{j}$表示可选择路径集, $N_{i}^{m}$$N_{j}^{m}$表示车辆从出发地到相遇路段的路段数, $e[t_{m}]$$e[t_{sp}]$分别表示公共路段的起止路段, $\gamma$为二值函数, 当车辆$i$到公共路段的距离大于车辆$j$时, $\gamma=0$, 否则, $\gamma=1$$J_{\rm{coordination}}^{*}$$J_{\rm{nominal}}$分别表示车辆单独行驶与换路合并行驶的最佳能耗, $c_{th}$为合并阈值, 表示改变路径或速度后增加的其他成本.为简化设计, 本文考虑$c_{th}=0$.式(4)为合并路径可行性, 表示车辆在准时到达的前提下的可选择路径集; 式(5)为时间可行性, 表示车辆能够在公共路段处完成合并行驶; 式(6)为油耗可行性, 表示采用合并行驶方案较单独行驶能够节约油耗, 其中JnominalJcoordination*表示如下:

$ \begin{array}{l} {J_{{\bf{nominal}}}} = \left( {\sum\limits_{n = N_i^{{\rm{now}}}}^{N_i^{{d_{\min }}}} L (e[n]) - x_i^{{\rm{now}}}} \right) \times \\ \left( {{F_1}\frac{{\sum\limits_{n = N_i^{{\rm{now}}}}^{N_i^{{d_{\min }}}} L (e[n])}}{{t_i^d - t_i^s}} - \frac{{x_i^{{\rm{now}}}}}{{t_i^d - t_i^s}} + {F_0}} \right)\\ \end{array} $ (7)
$ \begin{array}{l} J_{{\bf{coordination}}}^* = {v_c}{t_c}({F_i}{v_c} + {F_0}){\mkern 1mu} + \\ \quad \left( {\sum\limits_{n = N_i^{{\rm{now}}}}^{N_i^{sp}} L (e[n]) - x_i^{{\rm{now}}} - {v_c}{t_c}} \right)({F_{1p}}{v_p} + {F_{0p}}){\mkern 1mu} + \quad \\ \left( {\sum\limits_{n = N_i^{sp} + 1}^{N_i^d} L (e[n])} \right)({F_1}{v_a} + {F_0}) \end{array} $ (8)

其中, $v_{p}={\sum\nolimits_{n=1}^{N_{j}^{\min}}L(e[n])}/({t_{j}^{d}-t_{j}^{s}})$表示车队行驶的速度. $t_{c}=(\sum\nolimits_{n=N_{j}^{}}^{N_{m}}L(e[n])-\sum\nolimits_{n=N_{i}^{}}^{N_{m}}L(e[n])$ $+$ $x_{i}^{\rm now}-x_{j}^{})/{(v_{c}-v_{p})}$表示后车经过$t_{c}$时间后追上前车组成车队行驶, $N_{i}^{\rm now}$, $N_{i}^{sp}$, $N_{i}^{d{\min}}$, $N_{i}^{dc}$分别为车辆当前时刻、分离时刻、最短路径及调度路径的路段数, $x_{i}^{\rm now}$表示当前时刻车辆$i$在路段$N_{i}^{}$上行驶的距离.车队分离后的速度$v_{a}$取决于追赶速度$v_{c}$, 其函数关系如下:

$ \begin{align} v_{a}=\frac{\sum\limits_{n=N_{i}^{sp}+1}^{N_{i}^{d_{c}}}L(e[n])v_{0}v_{p}}{ X- Y -Z} \end{align} $ (9)

其中,

$ \begin{align*}&X=v_{p}v_{0}(t_{i}^{d}-t_{i}^{s}-t_{c}) \\&Y=v_{0}\left(\sum\limits_{n=N_{i}^{\rm now}}^{N_{i}^{sp}}L(e[n])-x_{i}^{\rm now}-v_{c}t_{c}\right)\\& Z=v_{p}\left(\sum\limits_{n=1}^{N_{i}^{\rm now}-1}L(e[n]) +x_{i}^{\rm now}\right)\end{align*} $

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

$ \begin{align} v_{c}=\, &\mathop{\arg{\min}}_{v\in[v_{\min}, v_{\max}]}\Bigg[vt(F_{1}v+F_{0})\, + \nonumber\\&\Bigg(\!\sum\limits_{n=N_{i}^{\rm now}}^{N_{i}^{sp}}L(e[n])\!- vt\!-x_{i}^{\rm now}\!\Bigg)(F_{1p}v_{p}\!+F_{0p})\, + \nonumber\\&\left(\sum\limits_{n=N_{i}^{sp}+1}^{N_{i}^{dc}}L(e[n])\right) (F_{1}v_{a}+F_{0})\Bigg] \end{align} $ (10)

其中, 时间$t$表示后车追上前车的时间, 与上文中的$t_{c}$意义相同.

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

2.3 车辆的合并决策

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

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

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

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

$ \begin{align} k=1-\frac{J_{\rm{coordination}}^{*}}{J_{\rm{nominal}}} \end{align} $ (11)

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

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

图 3 车辆与车辆集合的关系示意图 Fig. 3 The schematic diagram of the relationship between vehicles and vehicle sets
$ \begin{align} P^{(i)}:=\mathop{\arg{\min}}_{n_{l}\in N_{l}}k_{in_{l}} \end{align} $ (12)

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

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

输入. finitely transport assignments $N_c$

输出. leading vehicle set $N_I$

$N_I\leftarrow \varnothing$, $i=1$, $j\subset N_c \backslash N_I$

While $i\leq N_c$

If

$k_{ij}>k_{ji}~~\&~~k_{ij}>k_{j(j+1)}~~\&~~k_{ij}>k_{(j+1)j}$~

Then

$N_I\leftarrow N_I\cup \{i\}$

Else if

$k_{ij}<0~~\&~~(k_{ij}>k_{j(j+1)}\|k_{ij}<k_{(j+1)j})~~\&$

$\left(\exists k_{(j+1)(j+2)}>\forall k_{j(j+1)}\right)$

Then

$N_I\leftarrow N_I\cup\{i\}$

End if

End if

$i\leftarrow i+1$

End While

2.4 车队集合的速度优化

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

考虑每个车辆集合中包含一辆领队车辆$n_{l}$及多辆跟随车辆$N_{f_{i}, n_{l}}=\{f_{1}, f_{2}, \cdots\}$, 需要规划出每辆车的速度序列$V_{i}=\{v_{i}^{s}, v_{i}^{m}, v_{i}^{p}, v_{i}^{sp}\}$及时间序列$T_{i}$$=\{t_{i}^{s}, t_{i}^{m}, t_{i}^{p}, t_{i}^{sp}\}$.

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

$ {\mathop {\min \quad }\limits_{e:{e_i} \in R} \sum\limits_{i \in v} {{d_i}} f({v_i},{\theta _p})} $ (13)
$ \begin{array}{l} \begin{array}{*{20}{l}} {}\\ {{\rm{s}}.{\rm{t}}.\quad \sum\limits_{N = N_i^{{\rm{now}}}}^{N_i^m} L (e[n]) \le v_i^c(t_i^p - t_i^c) + } \end{array}\\ x_i^{{\rm{now}}} \le \sum\limits_{n = n_i^{{\rm{now}}}}^{n_i^{sp}} L (e[n]) \end{array} $ (14)
$ {v_{\min }} \le \forall v \le {v_{\max }} $ (15)

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

$ {d_i} = \left\{ {\begin{array}{*{20}{l}} {\frac{{\sum\limits_{N = N_f^{{\rm{now}}}}^{{N^m}} L (e[n]) - \sum\limits_{N = N_l^{{\rm{now}}}}^{{N^m}} L (e[n])}}{{v_f^c - v_l^c}}v_i^c + }\\ {\qquad \qquad \frac{{x_l^{{\rm{now}}} - x_f^{{\rm{now}}}}}{{v_f^c - v_l^c}}v_i^c,\qquad t \in [t_i^m,t_i^p]}\\ {\frac{{\sum\limits_{N = N_l^{{\rm{now}}}}^{N_l^{sp}} - x_l^{{\rm{now}}} - v_l^c(t_l^p - t_l^c)}}{{v_l^p}},\;\;t \in (t_i^p,t_i^{sp})}\\ {\frac{{\sum\limits_{N = N_i^{sp}}^{N_i^d} L (e[n])}}{{v_i^{sp}}}v_i^{sp},\quad \qquad \qquad t \in [t_i^{sp},t_i^d]} \end{array}} \right. $

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

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

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

车辆及规划信息的传递在时间维度上可以看成一个时间序列$ S_{i}=(\langle y_{i1}, T_{1}\rangle, \cdots, \langle y_{in}, T_{n}\rangle)$, $y_{in}$$T_{n}$时刻物理(网络)平面接收的车辆规划信息(车辆信息), 当$y_{ik}$, $k\in[1, n]$时刻信息异常时, 需要对该时刻信息进行替换补偿.通常物理平面与网络平面的突发状况都表现为网络感知信息异常.异常信息的传输可能导致运输系统对车辆的运输计划进行重新规划, 反复的规划占用大量系统资源, 降低运输方案的可执行性.针对网络传输过程中的异常信息的问题, 本文提出了一种基于车辆集合中不同车辆时空相关性的异常值替换算法, 该算法的有效性在其他领域的应用已得到证明.

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

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

$ \begin{align} \hat{v}_{it}=w_s\hat{v}_{it}^{s}+w_Tv_{it}^{t} \end{align} $ (16)

其中, $\hat{v}_{it}^{s}$$\hat{v}_{it}^{t}$分别表示$t$时刻采用SM与TM算法对车辆$i$的速度的估计值, $w_{s}$$w_{T}$为权重系数, $0$ $<$ $w_{s}$, $w_{T}<1$, 表示为

$ \begin{array}{l} {w_s} = \frac{{\bar R_s^2}}{{\bar R_s^2 + \bar R_T^2}}\\ {w_T} = \frac{{\bar R_T^2}}{{\bar R_s^2 + \bar R_T^2}} \end{array} $ (17)
$ {\bar R^2} = 1 - \left( {1 - \frac{{\sum\limits_{n = 1}^h {{{({{\hat v}_{in}} - {{\bar v}_i})}^2}} }}{{\sum\limits_{n = 1}^h {{{({v_{in}} - {{\bar v}_i})}^2}} }}} \right)\frac{{h - 1}}{{h - k - 1}} $ (18)

其中, $\bar{v}_i$为车辆$i$接收速度信息的均值, $h$为估计样本容量, $k$为车队中其他车辆的个数.可以看出该权重系数主要取决于回归方程对样本的拟合程度.

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

$ \begin{align} \hat{v}_{it}^s=\hat{\beta}_0+\hat{\beta}_1v_{1t}\, +\hat{\beta}_2v_{2t}\, +\cdots+\hat{\beta}_mv_{mt} \end{align} $ (19)

其中, $\hat{v}_{it}^{s}$表示收到异常信息的车辆$i$$t$时刻的信息估计值, $v_{kt}$为车队中其他车辆在$t$时刻的速度信息, $k={1, \cdots, m}$.偏相关系数$\hat{\beta}_k$表示如下:

$ \begin{align} (\hat{\beta}_0, \hat{\beta}_1, \cdots, \hat{\beta}_m)^{{\rm{T}}}=(X^\mathit{{\rm{T}}}X)^{-1}(X^\mathit{\boldsymbol{T}}V) \end{align} $ (20)

其中, $V=(v_{i1}, \cdots, v_{ih})$表示车辆$i$$t$临近时刻的$h$组样本数据, 车队中$m$个其他车辆的数据组成$X$表示如下:

$ \begin{align} X= \begin{bmatrix} 1&v_{11}&\cdots &v_{m1}\\ 1&v_{12}&\cdots &v_{m2}\\ \vdots&\vdots&\ddots&\vdots \\ 1& v_{1h}& \cdots&v_{mh}\\ \end{bmatrix} \end{align} $ (21)

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

$ \begin{align} \hat{v}_{it}^{t}=&\ \hat{\beta}_0+\hat{\beta}_1v_{i\left(t-\frac{v}{2}\right)}\, +\cdots+\hat{\beta}_{\frac{v}{2}}v_{i(t-1)}\, + \nonumber\\ &\ \hat{\beta}_{\frac{v}{2}\, +1}\hat{v}_{i(t+1)}\, +\cdots+\hat{\beta}_v\hat{v}_{i\left(t+\frac{v}{2}\right)} \end{align} $ (22)

其中, $v_{ik}$为车辆$i$$t$时刻的前$v/2$时刻的实际观测速度轨迹, $\hat{v}_{ik}$$t$时刻后的理想速度轨迹预测值, $k$ $\in$ $\{1, \cdots, v/2\}$.

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

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

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

$ \begin{align} m=\frac{x_f(t)-x_i(t)}{x_f(t+1)-x_i(t+1)} \end{align} $ (23)

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

$ \begin{align} &v(\omega_i)=-\frac{v_0}{c_{\max}-c_i}(c_i\omega_i-c_{\max}), \nonumber\\&\qquad\qquad\qquad\qquad\qquad \omega_i\in\left[1, \frac{c_{\max}}{c_i}\right] \end{align} $ (24)

其中, $\omega_i=y_i/c_i$表示道路的饱和度, $y_{i}$为道路$i$的车辆数, $c_{i}$为道路的拥堵容限, $\omega_i\geq1$表示该路段发生拥堵, 但车辆仍可以以某一速度行驶, 当车辆数$y_{i}$达到该路段的最大拥堵容限$c_{\max}$时, 车辆速度为0.

根据拥堵路段位置$P_c=(e_c, x_c)$、车辆当前位置$P_i=(e_i(t), x_i(t))$及拥堵路段平均车辆数量$\bar{y}_i$估计车辆的拥堵时间$t_{ct}$, 将其作为合并阶段$(t_i^m, t_i^p)$的延迟时间加入上述优化过程, 重新计算车辆的运输方案.

$ \begin{align} t_{ct}=\frac{(x_c-x_i^t)(c_i-c_{\max})}{v_0(\bar{y}_i-c_{\max})} \end{align} $ (25)

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

4 仿真实例

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

4.1 仿真条件

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

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

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

$ \begin{align} f(v, \theta(p))=&\ \theta(p)(5.0495\times 10^{-6}v\, + \nonumber\\&\ 8.5426\times 10^{-5})\, + (1-\theta(p))\, \times\nonumber\\ &\ (8.41598\times 10^{-6}v+4.8021\times 10^{-5}) \end{align} $ (26)

根据该模型, 当车队以80km/h的速度行驶时, 跟随车辆的节油率约为15.9%.假设初始默认速度为80 km/h, 速度可选择区间在70~90 $\rm{km/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可以看出, 本文提出的策略在车辆较少时调度效果明显, 可显著节约能耗.随着车辆的增加, 两种策略的调度效果差距减少, 但本文的策略总是优于固定路径合并策略.由于改变路径可以增加车辆合并的机会, 使本文的合并策略在一定程度上包含了固定路径合并策略.

图 8 两种策略的模拟调度的油耗对比 Fig. 8 Comparison of the fuel consumption of the simulation of two strategies

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

图 9 拥堵对车辆合并的影响 Fig. 9 Congestion impact on vehicle merging
图 10 考虑交通状况的车辆调度结果 Fig. 10 Vehicle scheduling results considering actual traffic conditions
5 结论

为了进一步提高道路吞吐量, 降低运输成本, 本文提出了一种基于交通信息物理系统(TCPS)的分布式车辆调度方案.该方案将绿色路径的思想融入到车辆的合并调度中, 提出了一种领队车辆选择算法解决了方案中的候选车辆选择冲突问题, 并针对网络信息传输异常及其突发情况进行处理, 说明了本文调度方案的可扩展性.

但本文调度方案在设计过程中仅考虑了用户均衡原则而忽略了整个路网的系统最优原则, 即没有考虑车辆的调度对路网中其他车辆的影响; 此外, 本文的调度方案没有考虑路网中的细节问题, 例如交通环境、速度限制、交通信号灯、车型及司机休息时间等.所以, 建立更广泛的调度系统仍是一个值得关注的问题.

参考文献
1
OECD/International Transport Forum, International Transport Outlook 2013: Funding Transport. Paris, France: OECD Publishing/ITF, 2013.
2
Papageorgiou M. Overview of road traffic control strategies. Ifac Proceedings Volumes, 2004, 37(19): 29-40. DOI:10.1016/S1474-6670(17)30657-2
3
Crainic T G, Laporte G. Planning models for freight transportation. European Journal of Operational Research, 1997, 97(3): 409-438. DOI:10.1016/S0377-2217(96)00298-6
4
Demir E, Bekta T, Laporte G. A review of recent research on green road freight transportation. European Journal of Operational Research, 2014, 237(3): 775-793. DOI:10.1016/j.ejor.2013.12.033
5
Karagiannis G. Vehicular networking:a survey and tutorial on requirements, architectures, challenges, standards and solutions. IEEE Communications Surveys and Tutorials, 2011, 13(4): 584-616. DOI:10.1109/SURV.2011.061411.00019
6
Varaiya P. Control design of an automated highway system. Proceedings of the IEEE, 2000, 88(7): 913-925. DOI:10.1109/5.871301
7
Liang K Y, Martensson J, Johansson K H. Heavy-duty vehicle platoon formation for fuel efficiency. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(4): 10511061.
8
Larson J, Kammer C, Liang K Y. Coordinated route optimization for heavy-duty vehicle platoons. In: Proceedings of the 2013 IEEE Intelligent Transportation Systems. Hague, Netherlands: IEEE, 2013. 1196-1202
9
Van De Hoef S, Johansson K H, Dimarogonas D V. Fuel-optimal centralized coordination of truck platooning based on shortest paths. In: Proceedings of the 2015 American Control Conference. Chicago, America: IEEE, 2015. 37403745
10
Meisen P, Seidl T, Henning K. A data-mining technique for the planning and organization of truck platoons. In: Proceedings of the 2018 International Conference on Heavy Vehicles. Paris, France: John Wiley and Sons, Inc, 2008. 19-22
11
Van D H S, Johansson K H, Dimarogonas D V. Coordinating truck platooning by clustering pairwise fuel-optimal plans. In: Proceedings of the 2015 Intelligent Transportation Systems. Las Palmas de Gran Canaria, Spain: IEEE, 2015. 408-415
12
Boriboonsomsin K, Barth M J, Zhu W. Eco-routing navigation system based on multisource historical and real-time traffic information. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(4): 1694-1704. DOI:10.1109/TITS.2012.2204051
13
Kaufman L, Rousseeuw P J. Finding Groups in Data: An Introduction to Cluster Analysis[Ph. D. dissertation]. Hoboken, NJ, USA: Wiley, 2008.
14
Jain A K. Data clustering: 50 years beyond k-means. In: Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases. Antwerp, Belgium: Springer-Verlag, 2008. 3-4
15
Besselink B, Turri V, van de Hoef S H. Cyber-physical control of road freight transport. Proceedings of the IEEE, 2016, 104(5): 1128-1141. DOI:10.1109/JPROC.2015.2511446
16
Sanders P, Schultes D. Engineering fast route planning algorithms. In: Proceedings of the 2007 International Conference on Experimental Algorithms. Rome, Italy: Springer-Verlag, 2007. 23-36
17
Liang K Y, Martensson J, Johansson K H. Heavy-duty vehicle platoon formation for fuel efficiency. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(4): 10511061.