基于多属性优先级的动态路径规划方法*

李 彤，李德敏，张光林，吴思畏（1.东华大学 信息科学技术学院，上海 201620；2.教育部 数字化纺织服装技术工程研究中心，上海 200000）

基于多属性优先级的动态路径规划方法*

李 彤1，2，李德敏1，2，张光林1，2，吴思畏1，2
（1.东华大学 信息科学技术学院，上海 201620；2.教育部 数字化纺织服装技术工程研究中心，上海 200000）

针对现存大多数动态路径规划算法目标单一问题进行研究，提出基于理想点的多属性决策方法解决该问题，属性的选取融合时间、路程及现代最为重视的安全因素，使得动态路径规划的结果更加均衡。同时在多属性决策过程中引入优先级这一概念，使得驾驶员可以根据自身的需求及驾驶技术对交通信息的重要度进行排序，得到匹配度最高的驾驶方案。仿真结果表明，基于多属性优先级的动态路径规划算法既能够起到多目标均衡的路径规划效果，同时又能够实现个性化驾驶。

动态路径规划；多属性决策；逼近理想点；优先级

0 引言

车辆的动态路径规划是指车辆在不同地理位置根据当前时刻的道路交通信息选择驾驶路线的方法。根据实时交通信息作出的动态路径规划可以有效地避免拥堵路段、事故路段，提高行驶效率，在城市车辆规划中有较大的应用［1］。

近年来，随着传感网络、通信技术等信息科技的发展，国内外学者已对车辆的动态路径规划进行了大量的研究，高峰、王明哲针对已有路径选择模型缺乏选择决策过程的问题，提出了一种基于决策场理论的车辆路径选择过程框架，建立一种面向过程的车辆动态路径选择模型［2］。宋久元等人充分利用启发式搜索具有方向性的启发信息，对A*算法进行了改进，采用双向的A*算法来避免过多的节点搜索和搜索过界的问题［3］。CHEN C L P、Zhou Jin和 Zhao Wei利用基于三角模糊集的多属性决策方法进行动态导航，避免了大型传感网络中传统的交通信息中心不能及时传递全球实时交通信息这一问题［4］。朱东杰、崔刚等人设计了基于动态路径规划的车载自组网的车辆移动模型，并提出了一种基于 Dijkstra的动态路径规划算法［5］。

然而上述研究中，仍存在一些问题：（1）现存动态路径规划算法大部分还是基于最短时间或者最短路径，不能达到较好的平衡效果；（2）路径规划算法对信息的处理方式较单一，驾驶员不能进行个性化设置。为了解决上述问题，本文将城市道路划分为交叉路口集合和路段集合，将从出发点到目的地的长距离路径规划问题拆分成车辆在各个交叉路口时的路段选择问题，简化了路径规划过程中对全局路网的信息计算。路段选择过程综合考虑车辆速度、安全系数、预期路程3种较为重要的交通信息，利用多属性决策法分析该问题，使得车辆的动态路径规划结果较为均衡。在多属性决策过程中引入信息优先级设置概念，按照个人偏好设置计算各交通信息的权重向量，以达到个性化驾驶的目的。

1 车辆移动模型

传统的动态路径规划算法基于最短距离算法或最短时间算法进行路径规划，当车辆每次到达一个交叉路口时，通过收集到的实时交通信息检测当前的路径规划是否为最优，若非最优路径，则重新规划车辆从当前位置到目的地的最优路径。该方法对当前位置到目的地的全局路网进行规划时产生较大计算量，当车辆移动速度较快时，很难起到良好的路径规划效果。

本文将城市路网看作交叉路口Pi与两个相邻交叉路口间连接路段Pi_j的集合，即G=｛P，R｝，其中R为有向路段，即同一路径的不同方向为不同路段。当车辆每次行驶到交叉路口Pi时，车辆向交叉路口通信设备发送路径规划请求，Pi处的路口设备接收到请求信息后，发送反馈信息，将与Pi毗邻路段的车辆速度、预期成本、安全系数等信息反馈给车载设备，车载设备根据道路属性信息进行多属性决策，将最佳下一行驶方向反馈给驾驶员，重复该过程，直到车辆到达目的位置。

2 道路信息分类

假设交叉路口节点都建设有可以进行无线通信、有线通信和信息存储的路旁设备，路网中的每辆车都安装通信设备、GPS和电子地图。为了实现车辆在交叉路口的路段选择，需要搜集3种道路交通信息：车辆速度、预期成本、安全系数。

2.1 车辆速度

车辆速度v表示路段上正在行驶的全部车辆的速度，由于路段上同时行驶的车辆速度不同，因此可以用区间数来表示该路段的车辆速度，即v=［vL，vU］。车辆速度越快，表明道路越畅通，因此该信息为效益型信息。

2.2 预期路程

预期路程s表示车辆从当前位置到达目的地的预期路程，实际问题中该信息在一定范围内取值，因此用区间数表示s=「sL，sU」。车辆行驶到交叉路口时，由于可能选择不同路段导致不同预期路程，显然预期路程越大，车辆行驶的开销越大，因此该信息为成本型信息。

2.3 道路安全系数

道路安全系数b表示路段交通环境的安全程度，不同的路段宽度、路段坡度、路面行驶质量、路面视认性会对其数值产生较大影响［6］。路段的道路安全系数越高，发生交通事故的可能性就越小，因此该信息为效益型信息。

3 多属性优先级路径决策

车辆行驶过程中与前方交叉路口设备建立通信，获取到了其连接的不同路段的3种道路交通信息，但是其在决策中所占的权重并不清楚，因此本文采用逼近理想点法来解决权重模糊的多属性决策问题。与传统算法不同的是，本文所提出的算法中加入了优先级的概念，即驾驶员可以根据个人驾驶需求、习惯等对道路交通信息设置不同的优先级，选择不同的决策模型进行路径规划，从而达到个性化的动态路径规划目的。具体计算步骤如下：

（1）确定备选道路的信息集A=［aij］n×m。其中i表示前方路口所连接的道路编号，1≤n≤4；j表示同一路段不同道路信息，1≤m≤3。

（2）标准化信息集R=［rij］n×m。

为了消除不同物理量纲对路径选择的影响，将已知的信息数据标准化，标准化公式如下［7］：

（3）设置路段交通信息优先级。

依据驾驶员的个人偏好确定3种交通信息重要度的优先级，其中1为最高级，3为最低级，根据信息的优先级将集合R中的数据重新排列为R′。

（4）确定正理想点r+和负理想点r-［8］。

（5）计算不同优先级的交通信息与正负理想点偏差。

若交通信息优先级为1，偏差计算公式为：

若交通信息优先级为2，偏差计算公式为：

若交通信息优先级为3，偏差计算公式为：

（6）计算属性信息的权重向量。

为了使所有路径选择方案在所有路段交通信息作用下与正理想点偏差最小与负理想点偏差最大，ω需满足［8］：

d（rij，rj-）、d（rij，rj+）均为已知量，易根据式（8）计算得出精确的权重向量ω=［ω1，ω2，ω3］。

（7）代入权重向量ω=［ω1，ω2，ω3］计算每个方案与区间型理想点的相对贴近度 di，di值越大表示相应的方案越优。

4 仿真比较

为了证明本文提出算法的适用性及有效性，构建一个7×9的路网对其进行仿真，将本文提出的基于多属性优先级路径规划算法与最短距离路径规划法［9］、最短时间路径规划法［10］进行对比。

仿真过程中，车辆从位置0出发，行驶目的地为位置9，假设0～9路段车辆速度较慢，10～19、20～29、30～39路段车辆速度中等，50～59路段车辆速度非常快，其他路段车辆速度较快；0～9路段安全级别为较差，10～19、50～59路段安全级别为一般，30～39、40～49路段安全级别为非常好，其他路段安全级别为较好，详细参数设置如表1所示。

表1 仿真参数设置

按照上述设置对最短距离算法、最短时间算法、非个性化多属性决策算法进行仿真，得到3种算法的路径规划如图1所示。根据路径图，可以通过加权平均的方式计算出不同路径规划算法下车辆的行驶路程、平均速度、行驶时间、平均安全系数等参数，如表2所示。

从表2可以看到，多属性决策算法规划的动态路径各项指标比较均衡，兼顾了多重交通信息，能够使驾驶员得到更良好的驾驶体验。

依据驾驶员的需求和驾驶技术，可以选择多属性优先级的方法进行路径规划，本文以下述3种优先级方案为例仿真，得到路径规划结果如图2所示。

图1 不同路径规划算法的仿真路径图

表2 不同路径规划算法的仿真结果

图2 不同优先级设置的多属性决策方案路径图

方案1①安全②路程③时间。

方案2①时间②安全③路程。

方案3①路程②时间③安全。

根据图2路径图，同样可以计算得出车辆在多属性决策算法的不同个性化设置下，车辆的行驶路程、平均速度、行驶时间、平均安全系数等参数，如表3所示。

表3 不同优先级设置的多属性决策方案对比结果

仿真结果表明，使用多属性优先级的动态路径规划方法既综合考虑各项交通信息对驾驶的影响，同时又能够让驾驶需求、驾驶技术不同的驾驶员有个性化的驾驶体验。

5 结论

本文提出了一种基于多属性优先级的车辆动态路径规划方法，该算法改善了最短路径算法、最短时间算法追求单一指标最优化的情况，得到均衡了时间、路程及道路安全状况等因素的路径规划结果。同时在多属性决策进行路径规划的过程中，引入了优先级设置方法，能够区分不同交通信息的重要程度，方便驾驶员根据其需求设置，完成个性化驾驶的目的。

［1］邓向林.基于动态规划算法的出租车合乘模式研究［J］.微型机与应用，2013，32（8）：79-81，84.

［2］高峰，王明哲.面向决策过程的动态路径选择模型［J］.交通运输系统工程与信息，2009，9（5）：96-102.

［3］宋久元，滕国库，胡丽霞.路径规划算法的改进及在车载导航中的应用［J］.计算机与数字工程，2010，35（8）：95-98.

［4］CHEN C L P，Zhou Jin，Zhao Wei.A real-time vehicle navigation algorithm in sensornetwork environments［J］.IEEE Transaction on IntelligentTransportation Systems，2012，13（4）：1657-1666.

［5］朱东杰，崔刚，傅忠传.基于动态路径规划的VANET车辆移动模型研究［J］.高技术通讯，2014，24（6）：573-580.

［6］魏朗，高丽敏，余强，等.驾驶员道路安全感受模糊评判模型［J］.交通运输工程学报，2004，4（1）：102-105.

［7］达庆利，徐泽水.不确定多属性决策的单目标最优化模型［J］.系统工程学报，2002，17（1）：50-55.

［8］和媛媛，周德群.区间数多属性决策问题的逼近理想点方法［J］.统计与决策，2009（24）：9-11.

［9］乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现［J］.武汉测绘科技大学学报，1999，24（3）：209-212.

［10］CHABINI I，LAN S.Adaptations of the A*algorithm for the computation of fastest paths in deterministic discretetime dynamic networks［J］.IEEE Transaction on Intelligent Transportation Systems，2002，5（3）：60-74.

Dynamic route planning method based on multi-attribute and priority

Li Tong1，2，Li Demin1，2，Zhang Guanglin1，2，Wu Siwei1，2
（1.College of Information Science and Technology，Donghua University，Shanghai 201620，China；2.Engineering Research Center of Digitized Textile ＆ Fashion Technology，Ministry of Education，Shanghai 200000，China）

Most dynamic route planning methods now existed only have a single target.In view of this circumstance，a method called MADM based on the ideal point is proposed to solve this problem.The attributes merge time，distance and safety together to make a balance routing result.It also introduces an idea of priority to sort the traffic information according to their requirement and road sense，and finally the traveler could get the best route navigation.The result of simulation shows the dynamic route planning method based on multi-attribute and priority can make multi-objective of route planning equilibrium，as well as can realize a personalized driven.

dynamic route planning；multi-attribute decision making；gain on ideal point；priority

TP391

A

1674-7720（2015）18-0082-03

李彤，李德敏，张光林，等.基于多属性优先级的动态路径规划方法［J］.微型机与应用，2015，34（18）：82-84，88.

2015-05-18）

李彤（1990-），女，硕士研究生，主要研究方向：车辆自组织网络与应用。

李德敏（1963-），男，博士，教授，博士生导师，主要研究方向：移动计算网络与应用、自组织网络与应用。

张光林（1981-），通信作者，男，博士，副教授，主要研究方向：无线网络、车辆自组网。E-mail：glzhang@dhu.edu.cn。

国家自然科学基金（ 71171045 ， 61301118 ） ；上海市教科委创新项目（ 14YZ130 ） ；中央高校基本科研业务费专项基金资助和东华大学“励志计划”基金