基于变结构离散动态BN的最优交通路径规划

(西安工程大学 电子信息学院,西安 710048)

0 引言

随着近年来我国的国民经济飞速发展，城市机动车的数量不断增加，交通需求量也急剧增加，交通拥堵成为我国乃至全世界共同面临的问题。但是，仅仅靠改善交通设施，成本大且效果不好。面对这一系列问题，路径规划算法的研究已经变得非常重要。

车辆路径规划算法有两种类型分别为静态路径规划算法和动态路径算法[1]。静态路径规划就是依据某些优化准则(如路径距离最短，所用时间最短等)结合实际地理信息，找到一条从起始状态到目标状态的最优路径。近年来，有许多学者对静态路径规划算法进行了改进，但是静态的路径规划算法相对比较简单，应用于实际的交通状况意义不大。动态路径规划[2]是在静态路径规划中加入实时的交通信息，得到符合要求的路径。一些研究者基于传统的路径规划算法对动态路径规划算法[3-6]进行了优化改进，但大都解决的都是最短路径问题。为了使驾驶者有更好的驾驶体验，未来对路径规划或路径寻优方法的研究应更加关注驾驶者的驾驶偏好。文献[7]提出了一种具有在线组件和离线组件的系统，以利用轨迹解决最小的路上时间问题。在线查询应答组件利用路线上的停车设施来避免预测的交通拥堵并最终减少驾驶员的路上时间，而离线组件解决如何根据历史轨迹生成道路网络的速度曲线。文献[8]提出了一种基于遗传算法的协同优化方法,以及一种自适应实时优化策略,能够为驾驶员提供燃料经济路线，同时使用交通数据和车辆特性来优化车辆路线，以改善给定的预期行程时间的燃料经济性。这些文献都只考虑了单一因素，没有对影响交通路径规划的其他方面进行更多研究。

BN是一种类似人类思维过程的建模工具，可以对复杂系统的不确定性进行推理和分析。现实生活中，实际的路网是复杂多变的，对交通进行路径规划的问题就是解决不确定性问题。动态BN作为一个与时间序列结合的复杂因果关系网，在处理交通路径规划中的时序数据以及表达驾驶员偏好方面具有独特的优势。因此，本文采用动态BN理论[9-10]，通过驾驶员偏好分析、模型结构建立、模型参数确定等一系列工作，建立基于变结构离散动态BN[11]的最优交通路径规划模型，能够考虑驾驶员的驾驶偏好[12]。研究结果可在动态路径规划的应用方面提供参考，规划出满足驾驶员偏好的最优路径。

1 变结构动态BN

BN是基于概率推理的数学模型，可以通过有向无环图(DAG)和条件概率表(CPTs)直观的表达变量间的依赖关系。BN能够通过一些变量的信息，推理得出其他变量的概率信息，可以解决不定性问题，被广泛应用在多个领域。

动态BN是静态BN结合时序发展而来的。通常由初始网络和转移网络两部分组成。一个完整的动态BN包含有限个时间片，每个时间片由一个有向无环图和条件概率表组成。从一个时间片到另一个时间片的跨越反映了时变作用。

传统的动态BN实际上是一个特殊的变结构动态BN，变结构动态BN可以是每个时间片上的网络结构不同，也可以是参数不相同。完全确定一个变结构动态BN需要知道：先验概率P(X)、状态转移条件概率P(Xt|Xt-1)、观测值P(Y)。

在动态BN中，根据变量是否离散或连续，可以分为连续动态BN和离散动态BN。本文主要采用隐变量和观测变量均离散的变结构离散动态BN模型。

2 最优路径规划方法基本思想

本文为解决交通拥堵，提高道路使用率，同时兼顾驾驶者的驾驶体验，提出基于变结构离散动态BN的交通最优路径规划方法。具体地，首先分析影响交通路径规划的主要因素，鉴于驾驶员的个人偏好，本文选择行驶时间、路况、行驶距离、出行费用4个因素作为最优出行路径评价指标；然后建立变结构离散动态BN模型；接着对模型进行参数学习；最后采集数据获得证据信息，采用基于时间窗的动态BN近似推理算法中固定窗口宽度方法[13]进行在线推理，根据实时采集到的交通信息得出最优的交通路径。图1给出了本文提出方法的最优路径规划方法的流程图。

图1 最优路径规划方法的简单流程

3 变结构动态BN最优交通路径规划模型建立与分析

3.1 影响最优路径选择的因素

在交通系统中驾驶员是重要参与者，驾驶员在行驶中要对路径进行选择，对于具体的道路状况，不同的驾驶员有不同的偏好。实际的驾驶中会有许多外界因素的干扰，使得驾驶员对于最优路径有多样的选择。综合考虑影响驾驶员路径选择因素，主要有行驶距离、行驶费用、行驶时间、道路拥挤程度(路上车辆数、排队长度)、路况(车辆行驶速度)和身体状况等，各个因素有各自的特征与属性。驾驶员对路径进行选择时会依据自身偏好，对于不同路径选择影响因素有不同的心理接受范围和标准。鉴于驾驶员的个人偏好，本文选择行驶时间、行驶距离、路况、出行费用4个因素作为最优出行路径评价指标。

3.2 变结构离散动态BN模型建立

将最优交通路径评估指标中的各个影响路径规划的因素设定为单片离散动态BN中的观测节点，同时赋予节点离散值域，建立单片离散动态BN的有向无环图，如图2所示。

图2 单片离散动态BN

3.3 模型参数确定

3.3.1 参数学习

单时间片内离散节点的初始状态分布参数可通过统计方法得到，主要的是状态转移概率和单时间片内的条件分布参数的确定。本文采用最大似然估计产生状态转移概率，自适应产生算法[14]得出条件概率。

变结构离散动态BN可以是每一个时间片的观测变量和隐变量个数不同，也可以是不同时间片的变量之间的条件概率不同，而参数的自适应产生算法就是模型变化时，能按照某种原则自动产生条件概率表的一种算法。

按照BN的理论，条件概率表表示的是子节点在已知父节点的状态时的概率分布。假定存在一个节点D，有n个状态(d1,d2,…,dn)，其子节点设为C，且有m个状态，则条件概率表计算P(cj|di)，i=1,2,…,n，j=1,2,…,m。

隐节点的各个状态，总是在其子节点集合中，需要找出其相关节点和不相关节点。已知隐节点的某一状态，可以找出其相关节点的最偏好状态和最不偏好状态，将相关节点的状态按从大到小顺序排列，条件概率表可采用负1次、负2次或者负高次幂的形式构成。即：

图3 离散动态BN结构模型

或：

(1)

按照该观测节点的重要性从小到大排列，条件概率表可以用正高次幂的形式构成。例如：

(2)

而对于隐节点状态的不相关节点，也存在一定的偏好。一般采用一次幂的形式形成条件概率表，即:

(3)

(4)

3.3.2 变结构动态BN推理

在一个动态BN的结构和参数都已知的情况下，获得证据信息后，就可以对网络进行在线推理。本文采取的是基于时间窗的动态BN近似推理算法中固定窗口宽度方法[来进行在线推理，根据实时采集到的交通信息得出最佳的交通路径。

推理需要两个过程，分别为滤波操作Filtering(tn+1)和平滑操作Smoothing(tm)。其中，tn+1和tm分别为第n+1个时间片和第m个时间片。滤波是在所有给定的证据条件下，计算当前状态的后验概率分布P(Xt|y1:t)。平滑是在所有给定的证据条件下，计算过去某一状态的后验概率，即对某个满足1≤k

假设存在一个已知的时间边界tT,设到目前为止观测序列的长度为n。算法从n=1开始，并不断地从动态环境中得到观测值。假设第tn个时间片进入了时间窗，则执行以下操作：1)若n

图4 新证据被添加时的时间窗操作方法

4 仿真实验

本文的仿真用C++语言编程实现，在CPU频率为1.90 GHz，内存为4.00 GB的计算机上运行得到结果。

4.1 实例分析

收集西安某地区的交通信息，将实际交通路网转化成有向图来模拟交通路径图，如图5所示，驾驶员偏好选择路径距离较短且路况较好。

图5 西安某地交通路径示意图

根据图5所示的交通路径信息，驾驶者从起始点S到目标节点D，把驾驶的道路按时序分为6个时间片，节点1到节点2为一个时间片，2到3分为一个时间片，依次划分。前三个时间片中，每个时间片隐节点都有三个状态，即有上路径、中路径和下路径可选择，后三个时间片每个时间片有上路径和下路径可选择。

依据驾驶员偏好，选择路径距离和路况两个因素作为评价指标，构建的基于变结构离散动态BN的最优路径决策模型，如图6所示。隐变量X状态为该时刻可选路径的条数，前三个时间片的有三条路径可以选择，后三个时间片有两条路径可以选择。

在构建的模型中，先验概率是对初始时刻隐节点状态的分布估计。本文采用最大似然估计进行参数学习，得到路径选择类型的先验概率为P(x1,x2,x3)=(0.3,0.4,0.3),x1,x2,x3分别代表隐藏节点的三个状态，即上、中、下路径。采用变结构动态BN的参数的自适应产生算法，自动生成各个时间片的条件概率，如表1，表2所示。

状态转移概率时间片之间的条件概率，可以根据统计学规律得出，如表3所示。P(Xt+1|Xt)表示第t个时间片到第t+1个时间片的状态转移概率，t={1,2,…,6}。

在同一天时间内，每条路径的交通流量都是在不断变化的，并且区别很大。而在短时间内，每条路径上的变化一般不会太大，故本文仅选择某一个时间段进行研究。取K1和K2时刻，观测6个时间片的路径距离(km)和路段平均速度(km/h)，如表4所示。

离散化处理表4中的观测数据，采用基于时间窗的近似推理算法进行推理，得到K1、K2时刻最优交通路径决策结果如分别为表5、表6所示。

图6 变结构离散动态BN的最优路径决策模型

tP(Y11|X)P(Y41|X)P(Y12|X)P(Y42|X)P(Y13|X)P(Y43|X)N M FC H YN M FC H YN M FC H Y10.55,0.27,0.180.75,0.22,0.030.17,0.33,0.500.18,0.27,0.550.17,0.33,0.500.18,0.27,0.5520.17,0.33,0.500.18,0.27,0.550.74,0.18,0.080.75,0.22,0.030.17,0.33,0.500.18,0.27,0.5530.17,0.33,0.500.18,0.27,0.550.17,0.33,0.500.18,0.27,0.550.85,0.12,0.030.75,0.22,0.03

表2 后三个时间片条件概率表

表3 状态转移概率表

表4 观测数据表

表5 K1时刻最佳交通路径决策结果

表6 K2时刻最佳交通路径决策结果

在表5中，前三个时间片每一列数据依次为选择上、中、下路径的概率值，取这3个概率值中的最大值所对应的路径作为该时间片上决策出的路径。后三个时间片每一列数据依次为选择上、下路径的概率值，取这2个概率值中的最大值所对应的路径作为该时间片上决策出的路径。通过分析仿真结果，可以看出路径选择是(中、上、下、下、下、下)，记为S1。根据表6，可以得知在不同时刻对同一路段要求距离最短且路况好的路径选择是(上、下、下、下、下、下) ，记为S2。表5和表6决策的路径不一致，由此说明路径的选择与距离和路况有关，路况信息在不断变化，决策出的路径也在变化。

4.2 本文提出方法与Dijkstra算法仿真结果比较

根据表4的观测数据，采用Dijkstra算法决策出的路径为(中、中、上、上、下、上)，记为S3。

将本文提出方法在K1时刻和K2时刻与Dijkstra算法分别进行比较，如表7所示。

表7 仿真结果比较

从表7可以得出，如果在K2时刻采用K1时刻的路径S1，行驶时间比K2时刻的路径S2所用时间更长。表明本文所提方法可以根据实时路况信息决策出更短的路径。

由表7可知，Dijkstra算法在K1和K2时刻决策出的路径相同，尽管决策的路径距离最短，但不能考虑路况的变化。而本文提出的基于变结构离散动态BN交通最优路径规划方法结合了实时的路况信息，所以决策出的路径不同，不一定最短。在K1和K2时刻，本文方法规划的路径的行驶时间都比Dijkstra算法更短。因此，本文所提的最优路径规划算法能够快速有效的根据实时信息对路径进行在线最优规划。

5 结束语

本文提出了基于变结构离散动态BN的交通最优路径规划方法，建立适合于实际路网的变结构离散动态BN模型，结合实例，成功地将动态BN应用到交通路径规划中。计算结果不但验证了变结构离散动态BN具有良好的交通路径规划能力，也验证了变结构离散动态BN基于实时信息的强大更新能力。在现实生活中，实际的路网是非常复杂的，本文提出的算法更适合稀疏的网络，进一步的研究工作将面向稠密复杂路网探讨最优路径规划。