基于区域分层的车辆队列行驶路径优化算法*

冯鹏程 高社生 王 东

(西北工业大学自动化学院1) 西安 710072) (武警后勤学院军交运输系2) 天津 300309)

基于区域分层的车辆队列行驶路径优化算法*

冯鹏程1,2)高社生1)王 东2)

(西北工业大学自动化学院1)西安 710072) (武警后勤学院军交运输系2)天津 300309)

为了满足部队摩托化机动时车辆编组行驶组织指挥的需求，提出了车辆队列行驶时的编组类型、行驶速度、队列长径的具体概念.结合车辆队列行驶对道路等级和行车速度的影响，建立了区域交通网络路径决策模型；基于单车区域椭圆、矩形区域选择的算法不足，设计了基于车辆队列长径参数、方圆结合的区域划分方法和分层路径优化Dijkstra算法；并通过具体的道路交通网络，进行了仿真计算.结果表明，设计的算法稳定、可行，能够满足部队摩托化机动时快速决策、快速到位的需求实际.

路径优化； 队列行驶； 军事物流；公路运输

0 引 言

车辆行驶路径优化算法，对研究信息化条件下的公路运输网络路径优化问题的求解有重要意义.对于这类问题，目前的研究主要集中在单车[1]或多车配送问题[2]，用于解决现代物流运输车辆调度问题，没有考虑车辆队列行驶时对于道路的特殊需求.对于确定环境下有约束最短路径问题的研究，国内外的研究大致可以归纳为有时间约束的最短路径问题[3]、点边数有约束的最短路径问题[4]、多权最短路径问题[5]、边权有时间依赖性[6]的最短路径问题和网络中最关键点及最关键边问题[7].Dijkstra提出的网络最短算法，被认为是求解不含负边长一般网络的最有效算法之一[8].确定环境下无约束单权网络最短路径算法的各种改进算法，都是基于标号算法基础上的，所不同的在于数据结构的定义[9].由于Dijkstra是一种遍历NP-hard算法，当节点规模较大时，很难得到问题的精确解，因此，在单车配送算法中，通常采用椭圆模型和矩形模型[10],这2种区域划分算法虽然都能够达到减少了最短路径算法的搜索空间的目的，但没有考虑车辆队列行驶长径的特性.

部队在进行遂行多样化任务公路运输保障时，通常采用车辆编组行进，受到行军纵队长径、编组车辆性能和安全防卫等因素的影响，对路径的选择有不同的要求.针对部队车辆队列行驶路径决策的实际问题，考虑车辆队列长径、不同道路的运行速度，划分标号的选择方式和范围，定义合适的数据结构，减少计算工作量；并基于车辆队列通过需求，设计高等级道路优先选择算法，以期实现车辆队列快速、安全到位的目的.

1 车辆队列行驶定义

美国联邦公路局智能车辆高速公路系统项目中，将车辆队列行驶定义为多辆车排成一列，以一定的速度等速行驶，而且车辆之间保持较小的纵向间距[11].这是一个定性的定义，难以进行定量分析.因此，本文在分析近年来部队车辆队列行驶案例的基础上，给出车辆队列行驶定义如下.

定义1 小编组行车

在行驶中，车辆按照小编组、大间距的原则编组行进；是一种小规模车辆队列行驶方法，适用于执行倒短、接力运输任务；特点是灵活机动，工作时效性好，有利于提高行车速度.

定义2 大编组行车

在行驶中，车辆按照建制大编组、多梯次的原则编组行进；是一种大规模车辆队列行驶方法，适用于执行运量集中、运距较长的运输任务；特点是运量大，保持部队建制完整.

定义3 车辆队列长径

车辆队列长径是指队列头车至尾车的长度.

小编组行车队列长径=[车长(m)×车数+车辆间隔(m)×(车数-1)] ×1/1 000

大编组行车队列长径=[车长(m)×车数+车辆间隔(m)×(车数-1)+单位间隔(m)×(单位数-1)] ×1/1 000

其中，车长取值为实际车身长度的近似值；车辆间隔按照道路通行条件和行车速度有所不同，见表1；单位间隔是指为了保持单位建制和便于管理，大编组内各单位之间所保持的较大间隔，取1 000 m.

表1 车辆队列行驶速度和间隔距离

定义4 车辆队列行驶时间

车辆队列行驶时间的计算是确定车辆队列到达或者通过时间，保证按时限完成行进任务的重要参数.车辆队列行驶时间可分为总持续时间和通过节点时的时间.

车辆队列行驶总持续时间(h)=[总行程(km)+车辆队列长径(km)]/队列行驶速度(km/h)+休息时间(h)

休息时间可区分为小休息和大休息.小休息，通常是指每两小时组织一次，时间为0.5 h；大休息，是在日行程过半时，间隔4 h，时间为小1.5 h，通常含一次进餐时间；如果总持续时间超过1 d，则还要另行计算宿营时间.

车辆队列行驶通过节点时间(h，min)=队列头车到达出发点时间(h，min)+出发点至节点距离(km)/队列行驶速度(km/h)+休息时间(min)

定义5：队列行驶速度

车辆间隔按照道路通行条件有所不同，预设情况见表1[12].

2 区域交通网络路径模型建立

将有限区域内，含有n个节点，m条有向边的路网系统抽象成一个模型交通网络[13]，即G={V,E,C,L}.

式中：V为有限节点集合，V={v1,v2,…,vn}；E为有限弧集，E={e1,e2,…,em}；C为公路等级，C={c1,c2,…,cm}，ci为对每个弧(vi,vj)∈E对应的公路等级,ci=0,1,2,3，分别为高速、一、二、三级公路；L为对每个弧(vi,vj)∈E，对应的距离，km，L={l1,l2,…,lm}.

设P={xij|(vi,vj)∈E}表示从起点v1到终点vn的一条路径.

(1)

起点v1到终点vn的模型可以描述为

(2)

(3)

式中:T为优化目标;Tij为网络中从vi到vj的车辆队列通行时间，计算方法按照定义4进行.如果弧(vi,vj)∉E，则时间为+.

3 车辆队列行驶区域分层路径优化算法设计

3.1 节点区域划分

区域划分是针对道路网络的空间分布特征提出的，其目的是合理选择道路网络节点数目，提高算法效率.本文针对椭圆算法相对复杂、矩形算法精度较低的不足，本文提出利用车辆队列行驶在不同道路环境下速度不同的特点来构建方圆结合区域的方法，使得迂回距离的大小和因道路环境不同而能节省的时间相一致，并便于区域动态扩展.

步骤2 按照车辆队列编组类型，结合表1，分别计算在这一空间距离下，两种极限道路条件下(高速公路与三级公路)的车辆队列行驶的时间差Δtmax.

步骤3 用这一时间差乘以车辆队列行驶的最大速度，得到一个可迂回的距离ΔLmax.

步骤4 分别以S和E为圆心，以ΔLmax/2为半径做圆.

步骤5 做平行于SE的2个顶点圆的切线形成图1所示区域，选择这一区域中的道路网络节点，作为优化搜索区域.

步骤6 如果道路等级达不到预设条件，按比例增加划分区域圆的半径.

道路网络区域的划分见图1.

图1 车辆队列行驶道路网络区域的划分

3.2 道路分层算法设计

由于在区域划分时，考虑了最大迂回道路的时间延误问题，因此，在区域内的点，高等级道路优先的原则，等同于时间最短原则.为了尽可能选择高等级的路径，减少算法节点，提高运输效率，同时减少计算时间，本文提出了道路分层优化算法，算法流程见图2.

图2 分层路径优化算法流程

4 算 例

4.1 道路模型及节点区域划分

某部队执行应急运输保障任务，采用大编组队列行车，车辆队列长径约为5 km，所在地域的有向交通网络见图3，出发点为节点v1，目的地为节点v12.

按照区域划分算法，在此区域内，有效的交通网络模型可表示为

C={2,3,3,2,1,2,0,2,2,1,0,3,0,2,2,2,2,2,3,2,2,0}

L={50,80,40,40,60,70,50,80,40,125,110,100,70,70,40,50,60,80,60,50,120,120}

km.

节点v16，v17，v18，v19，v20及其他未标明节点在区域范围之外，不予考虑.

图3 道路交通网络模型及区域划分

4.2 路径分层选择优化计算

按照公路等级矩阵C分层，可以得到：E0={e7,e11,e14,e23}，为高速公路.

E1={e5,e10,e13}，为一级公路.

E2={e1,e4,e6,e8,e9,e15,e16,e17,e18,e19,e21,e22}，为二级公路.

E3={e2,e3,e12,e20}为三级公路.

按照定义4和定义5计算车辆队列通过各有向边的时间得到时间矩阵T，这里采用大编组白天行车参数.

T={1.43,2.67,1.33,1.14,1,2,0.83,2.29,1.14,2.78,1.83,3.33,1.17,2,1.14,1.43,1.71,2.29,2,1.67,3.43,2}h.

由分层算法得到新起点S0与新终点E0，对应路径e11，通过时间为1.83h，连通后进入第三层得到S至S0的最小通过时间路径e1，通过时间为1.43h，E0至E的最小通过时间路径e17，通过时间是1.71 h.

已知车辆队列长径为5km，e1为二级公路，依据表1，白天大编组行车速度为35km/h，则车辆队列通过时间为0.14h；按节点和目标函数分析，应安排1次小休息，1次大休息，共计2h；则车辆队列行驶总持续时间为7.11h，也就是7h7min.

5 结 束 语

车辆队列行驶路径优化方法是信息化条件下部队机动决策的重要依据, 限制搜索区域算法，是提高最短路径搜索效率的一种常用的有损算法.本文给出了车辆队列行驶的基本定义，提出了一种区域分层优化的算法，并通过算例进行验证，结果表明算法可靠、高效，符合部队摩托化机动编组行车的路径优化决策需求.值得说明的是，本文在层次算法中套用的确定环境下的Dijkstra路径选择算法，适用于区域较小，节点较少的情况；如果区域过大，节点过多时应采用启发式算法，以提高计算效率；如果路网密度过小，区域内线路不足，则应扩大区域划分半径.

[1]CHERKASSKYBV,GOLDBE-RGAV,RADZIKT.Shortestpath′salgorithms:theoryandexperimentalevaluation[J].MathematicalProgramming,1996,73:129-174.

[2]LIWenquan,WANGWei.Capacityofmultivehicletypesmixedtrafficflow[J].JournalofSystemsScienceandSystemsEngineering,2001(1):122.

[3]丁秋雷,胡祥培,李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实践, 2007(10):98-104.

[4]何方国,齐 欢,范 琼.有约束的随机最短路问题模型及算法[J].武汉理工大学学报,2008,32(6):1125-1128.

[5]肖晓伟,肖 迪,林锦国,等.多目标优化问题的研究概述[J].计算机应用研究,2011,28(3):805-808.

[6]王江晴,康 立.动态车辆路径问题仿真器的设计与实现[J].核电子学与探测技术,2007,27(5):991-994.

[7]夏 珩,郑四发,李 兵,等.干线运输优化的两阶段局部搜索启发式算法[J].系统仿真学报,2008,20(15):4141-4145.

[8]PAOLOT,DANIELEV.Thevehicleroutingproblem[M].北京：清华大学出版社,2011.

[9]YANGH，BELLMGH.Modelsandalgorithmsforroadnetworkdesign:areviewandsomenewdevelopments[J].TransportReview, 1998,18:257-278.

[10]王海梅,周献中.一种限制搜索区域的最短路径改进算法[J].南京理工大学学报：自然科学版,2009,33(5):638-642.

[11]MICHAEL Z,STEFANO F,BROWAND F K.Drag measurements on 2,3 and 4 car platoons[C].SAE Paper, 940421.

[12]FENG Pengcheng,GAO Shesheng，SONG Feibiao.Area-layered paths optimizing algorithms of platoon vehicle[C]∥International Conference on Industrial Control & Electronics Engineering,2011:2780-2788.

[13]STIG N,BENGT R.Computer cartography shortest route program[M].Sweden:The Royal University of Lund,1969.

Paths Optimizing Algorithms for Platoon Vehicle Based on Area-layered

FENG Pengcheng1,2)GAO Shesheng1)WANG Dong2)

(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi’an710072，China)1)(MilitaryTransportationDepartment,CAPFLogisticsUniversity,Tianjin300309，China)2)

According to the organizing and command demand for the vehicle platoon in military transportation, the attribute of the vehicle platoon were defined firstly,including type, speed and length. Secondly,combined with the influence of road grad and vehicle platoon speed, the model of paths optimizing area traffic net was built.Finally,based on the deficiency of the single vehicle ellipse and rectangle area partition,an area-layered paths optimizing algorithms for platoon vehicle was designed in consideration of the vehicle platoon length.The testing results showed that the algorithm described herein was stable and feasible, and should be useful to military transportation based on the quick and safety demands.

path optimizing； platoon vehicle； military logistics； road conveyance

2015-02-08

*武警总部后勤部课题资助

U492.7

10.3963/j.issn.2095-3844.2015.03.007

冯鹏程(1974- )：男，博士生，副教授，主要研究领域为物流技术与装备