基于双层规划的自动卡车运输专用网络设计优化

　　摘 要: 为保障交通系统安全性和卡车货运自动化的发展, 有必要对自动卡车货物运输专用网络进行科学规划与布局. 考虑自动卡车专用道会减少普通车辆的路权, 对普通车辆的出行路径选择行为造成影响. 首先, 从路网整体出发, 以系统出行时间最小为目标, 充分考虑路网普通车辆的出行路径选择行为, 构建了一种新的自动卡车专用运输网络设计的双层规划模型. 其次, 提出了一种基于实数编码的改进差分进化算法求解建立的双层规划模型, 不仅保证解的可行性，还避免了复杂的不可行解修复过程. 最后, 通过 Sioux Falls 基准网络实例和大量随机算例对比测试结果验证了模型和算法的有效性.

　　关键词: 自动卡车;专用道网络;路径规划;双层规划;自适应差分进化算法

　　引 言

　　近年来,5G 技术和人工智能的迅速发展加快了智能化社会的进程.5G 技术和人工智能的普及应用将很大程度推进车联网的快速构建和自动驾驶的实现与成熟, 在智能交通领域体现得尤为明显[1]. 自动驾驶发展的重要组成部分之一是自动卡车. 在旺盛的物流需求背景下, 自动卡车货物运输具有相对固定的运输路线与需求刚性的特点, 相对于自动驾驶承运车具有更加容易落地与商业化的优势, 如图森未来公司已在美国实现了自动驾驶货运服务[2,3]. 另一方面, 在完全实现自动驾驶之前, 人工驾驶车辆与自动驾驶车辆混行的过渡阶段将长期存在, 如何在该阶段安全、高效地管理混合交通流成为保障高质量交通发展的重要现实问题[4].

　　因此, 在未来复杂的混行道路环境中, 首先为自动卡车货运规划专用运输网络是保障道路安全、运输效率并促进自动驾驶技术发展的有效举措, 具有重要的现实意义.专用道策略是一种提供与其他车辆分离道路的经济、有效的方法, 具体是指在现有城市交通网络中选择部分路段的车道设置成为仅供特定车辆使用的专用车道, 为其提供相对安全畅通的道路条件提高运输效率. 然而, 在城市化进程不断加快的时代,为自动卡车设置专用车道会使普通车辆可使用的道路空间减小, 很可能使原本的交通状况更加糟糕, 对整个系统的普通车辆造成负面影响. 如何科学合理规划自动卡车运输专用道网络, 有效分配路网资源,保障自动卡车运输任务效率与专用车道造成的负面影响之间的权衡至关重要. 因此, 本文将在 5G、人工智能不断推进自动驾驶发展的背景下, 重点研究未来自动卡车运输专用网络的设计优化问题.

　　目前, 专用道设置规划问题 (Lane ReservationProblem, LRP) 得到了国内外研究学者的广泛关注. 研究应用场景主要可分为特殊事件的临时专用道设置规划、危险品运输的专用道设置规划、自动卡车专用道设置规划以及公交专用道的设置规划等方面. 绝大多数研究集中于公交专用道优化. 如,Zhao 等[5] 提出一种动态公交专用道设置策略,以交叉口平均延误最小化为目标建立混合整数非线性规划. Han 等[6] 针对部分路段旅行时间信息, 研究随机公交车专用道优化问题, 提出面向服务的分布式鲁棒优化模型. 少部分研究了特殊事件的临时专用道和危险品专用道设置规划.

　　如,Li 等[7] 研究运输任务合并下的大型运动会专用道设置问题, 建立整数线性规划. Wu 等[8] 同时考虑剩余容量和预算限制建立双目标整数规划模型, 并提出新的松弛优化求解算法. 张圣忠等[9] 以总体出行成本最小、专用道影响最小、专用道利用率最大建立双层规划模型,并采用 NSGA-Ⅱ 算法求解. 自动卡车运输专用道优化问题研究很少, 然而在 5G、人工智能技术背景下自动驾驶的成熟实现势不可挡, 很有必要提前为自动卡车规划专用运输网络, 为未来混行交通状态提供理论和实践参考.

　　在微观层面,Xun 等[10] 为精确评估大规模路网引入自动货车车道引起的交通流变化提出一种微观 -中观交通仿真器, 结果表明为自动货车提供专用道会导致广泛的道路网络交通流变化. 在宏观层面,Fang 等[11] 首次将专用道策略引入自动卡车货物运输研究中, 优化专用道路段选择并为自动卡车运输任务规划专用道路径, 提出整数线性规划模型并验证了问题的 NP 难特性. 随后,Wu 等[12]在文献[11] 的基础上提出有效不等式建立了新的整数线性规划并提出求解大规模问题的两阶段精确算法.上述成果一定程度上丰富了专用道设置规划研究, 但还存在以下不足：

　　1) 现有文献对于路段上存在车道被设置为专用道后, 将原本在该车道上行驶的普通车辆直接移至该路段上剩余的普通车道上,而不考虑部分车辆可能的重新路径选择, 不能很好的反映自动卡车专用道规划后对系统的影响. 2) 现有文献考虑普通车辆路径选择行为后, 大多用于求解小规模算例, 如何开发适合中大规模算例的求解算法值得进一步思考. 因此, 本文将针对上述研究问题与挑战, 进一步分析自动卡车专用车道和普通车辆之间的动态相互影响关系, 建立一类新的关于自动卡车专用运输网络优化的双层规划模型, 同时针对自动卡车专用运输网络规划的问题特性开发了基于实数编码改进差分进化算法 (Improved DifferentialEvolutionary Algorithm, IDEA), 利用不同规模的案例验证算法与模型的有效性.

　　1 问题描述及符号定义

　　1.1 问题描述

　　本文采用有向图 G(N, A) 表示城市交通网络;其中 N 代表网络节点的集合, 每个节点表示实际交通网络的交叉路口;A 表示城市交通网络的弧集合,每条弧表示实际道路路段. K 表示自动卡车运输任务集合,O、D 分别表示任务的起点集合与终点集合,每个运输任务都有对应的起讫点 (OD) 以及严格的时间限制. 为保障运输任务的准时完成, 需要将部分车道转化为仅供自动卡车运输任务行驶的专用车道,以提高自动卡车运输任务的效率和安全性. 此外, 为促进自动驾驶的不断成熟以及安全性, 要求自动卡车运输任务所经过的路径均设置专用道.

　　但是, 一旦某些路段上设置了专用道, 将会对该路段上的普通车辆产生负面影响, 使该路段上普通车辆可使用的道路容量降低, 造成道路拥挤, 行驶时间增大. 与此同时, 城市网络的交通状态也将改变, 专用道路段上原本的普通车辆可能重新进行路径规划, 导致网络中的普通车辆流量重新分配. 而普通车辆的路径规划结果反过来又将直接决定路网整体行驶时间, 影响了专用道布局方案. 因此, 本文从系统的角度出发,充分考虑专用道与普通车辆之间的相互影响, 以专用道负面影响最小为目标, 确定能够保证运输任务都能准时完成的专用道优化设置方案.

　　1.2 假设条件

　　1)每条路段至少 2 车道, 确保设置专用道后普通车辆还可以在当前路段行驶. 2) 每条路段至多有 1个车道为专用道. 3) 每个任务从其起点到讫点之间存在可行路径.

　　2 模型建立

　　上层规划模型描述从整个系统角度如何确定自动卡车专用运输网络方案, 使得在保证所有任务能够准时完成的情况下对普通车辆影响最小.下层规划模型采用 Beckmann 等价模型描述在对应专用道方案下, 普通车辆的路径选择行为. 所有普通车辆都以力图最小化各自最短出行成本为目的,最终将达到一种用户均衡状态. 在用户均衡状态下,连接每个出行 OD 对的所有被使用的路径有相同的旅行时间, 且小于等于任何未被使用过的路径旅行时间[13].

　　3 算法设计

　　双层规划模型是 NP 难问题[15]. 由于本文建立的双层规划模型是非线性模型并且很难将问题转化为线性模型, 不具备良好的问题特性, 本文选用差分进化算法 (Differential Evolutionary Algorithm, DEA)内嵌 FrankWolfe 算法[16] 对双层规划模型进行求解.传统求解专用道优化问题, 通常用 0-1 编码来表示专用道的设置与否. 一旦道路网络规模增大, 该编码方式将造成过度冗长的个体, 搜索空间极度增大. 此外, 自动卡车专用道设置问题要求每个任务路径的专用道是连续的, 对解的要求严苛, 不易生成可行解, 通常需要伴随复杂的解修复过程. 为此, 本文提出一种基于实数编码的 IDEA 解决考虑普通车辆路径选择的自动卡车专用运输网络优化问题.

　　3.1 预处理令交通网络中所有路段都有一条车道作为自动卡车专用道, 可得一个完全专用道网络, 并将其命名为 G′. 在 G′ 中可以为每个任务规划运输路径, 计算任务路径旅行时间. 在 G′ 中每个任务满足其时间限制的路径数量是有限的, 是可以枚举的. 可以发现,只要从每个任务满足时间限制的可行路径集合中随机选择一条路径进行组合而得到的路段集合就是一个可行的专用道方案. 此外,Yen 的 K 最短路径算法[17] 是用于枚举任意起讫点间所有无环路径的有效方法. 所以, 本文将该方法应用于所有满足任务时间限制的无环路径以及对应完成时间的枚举.

　　4 案例分析

　　为了验证本文构建的模型和改进算法的有效性,以 Sioux Falls 为案例, 与不同场景下求解的专用道方案进行效果对比分析, 对应的场景描述见表 2. 此外,为验证 IDEA 中预处理与实数编码结合的有效性, 随机生成仿真算例进行测试, 与传统 0-1 编码的差分进化算法 (BDEA) 进行对比.

　　4.1 参数敏感性分析

　　DEA 的控制参数主要包括 NP、F、CR, 选取合适的控制参数对于算法的性能至关重要. 由于算法不同阶段对控制参数的要求不尽相同, 固定的控制参数存在一定的缺陷, 本文对 F、CR 采用自适应形式, 在不同进化阶段动态的调整, 以改善算法性能. 由于 CR 的自适应规则需要选定 CRmin 以及CRmax, 不易以参数敏感性分析的方法来确定, 则以通常的经验规则令 CRmin=0.2,CRmax=0.9. 而对于NP、M axIter、F 以敏感性分析来确定相对合适的参数值, 以保证算法相对优良的求解质量和效率.

　　4.2 实例分析

　　本文考虑了普通车辆的路径选择, 并采用用户均衡原则描述了交通网络中普通车辆路径选择的流量分布情况. 在有出行需求的交通网络中, 无论是否设置专用车道出行者都会进行路径选择, 为了检验本文提出的双层规划模型的效果, 以 Sioux Falls 网络为实例, 在表 2 中所描述的网络场景中, 分别考虑普通车辆的路径选择行为进行用户均衡交通分配,比较这三种场景下的系统总时间.

　　5 结论

　　(1) 本文在未来自动驾驶与人工驾驶混行背景下, 基于自动卡车专用道对普通车辆出行路径选择的影响分析, 构建了一个新的双层规划模型以表示自动卡车专用网络布局方案和普通车辆出行路径选择结果之间的动态相互影响关系, 对自动卡车专用运输网络优化设计问题进行研究.(2) 针对自动卡车专用运输网络设计问题的特征，设计了一个基于实数编码的 IDEA 对模型进行求解，具体包括考虑问题特性的预处理策略、高效的实数编码规则以及自适应交叉算子和缩放因子,不仅保证了解的可行性, 同时还避免了复杂的不可行解修复过程以及算法的早熟收敛.

　　(3) 以 Sioux Falls 基准算例, 分别在文中三种场景的交通网络状态进行优化结果对比. 结果表明, 建立的双层规划模型能够得到较优的自动卡车专用网络布局方案, 有效减小自动卡车专用道对交通系统的影响, 改善系统运行效率. 而且专用道设置并不会绝对增加系统影响, 在某些关键路段设置自动卡车专用道还能够改善交通网络效率, 达到较好的效果.

　　(4) 通过对不同规模的随机算例测试发现, 随着自动卡车任务的增加 IDEA 显著优于 BDEA, 随着普通车辆出行需求的增加,IDEA 与 BDEA 差距相对较小. 表明 IDEA 对能够更好的解决运输任务较多的自动卡车专用道设计问题, 为大规模网络的专用道设计问题提供一定的理论参考.(5) 本文对于普通车辆出行路径选择行为的描述是基于静态交通分配原理. 在未来的研究中可以进一步以动态的方式描述普通车辆的出行路径选择,以便更加准确的衡量专用道的影响以及设置效果.

　　参考文献 (References)

　　[1] 郭戈, 许阳光, 徐涛, 等. 网联共享车路协同智能交通系统综述 [J]. 控制与决策, 2019, 34(11): 2375-2389.(Guo G, Xu Y G, Xu T, et al. A survey ofconnected shared vehicle-road cooperative intelligenttransportation systems[J]. Control and Decision, 2019,34(11): 2375-2389.)

　　[2] 田野. 干线物流: 进击的高速自动驾驶卡车 [J]. 智能网联汽车, 2021, (05): 29-31.(Tian Y. Trunk logistics: aggressive high-speedautonomous trucks[J]. Intelligent Connected Vehicles,2021, (05): 29-31.)

　　[3] Roldan S, Jallais C, Hoedemaeker M, et al. Preparingfor Safe and Successful Truck Platooning on PublicRoads: Collaboration between the United States andthe European Union[J]. Institute of TransportationEngineers. 2021, 91(11): 35-40.

　　[4] 姚志洪, 顾秋凡, 徐桃让, 等. 考虑时延的智能网联汽车混合交通流稳定性分析 [J/OL]. 控制与决策:1-8[2022-04-09].(Yao Z H, Gu Q F, Xu T R, et al. Stability ofMixed Traffic Flow with Intelligent Connected VehiclesConsidering Time Delay[J/OL]. Control and Decision:1-8[2022-04-09].)

　　作者：吴 鹏†, 颜宝卿

转载请注明来自发表学术论文网：http://www.fbxslw.com/jjlw/30214.html