条件相关毕业论文模板范文 与不确定性条件下最优路径有关电大毕业论文范文

这是一篇与条件论文范文相关的免费优秀学术论文范文资料,为你的论文写作提供参考。

不确定性条件下最优路径

不确定性条件下最优路径的研究

顾爱华,郭青慧

(盐城师范学院信息工程学院,江苏 盐城 224002)

摘 要:城市交通情况复杂多变,交通事故、突发事件等更增加了车辆行驶时间的不确定性.本文是在此基础上进行的最优路径的研究,旨在不确定条件下,找到可靠、快速、安全的最优路径.首先,不确定条件下分析不同车辆经过每条路径的时间均值和标准差,给出每条路径的时间代价,所有路径中花费时间代价最小的即为最优路径.而最优路径模型就是在合理的假设下利用迪杰斯特拉算法得到最小的时间代价,并实际应用到市区交通网络,得到绕过拥挤路段的最优路径.本文主要叙述不确定条件下两点交通的最优路径以及交通网络的最优路径研究.

关键词:最优路径;时间代价;迪杰斯特拉算法;两点交通;交通网络

中图分类号:TP311

文献标识码:A

1 引言(Introduction)

目前,交通拥挤和事故正越来越严重的困扰着城市交通.随着我国交通运输事业的迅速发展,交通“拥塞”已经成为很多城市的“痼疾”.在复杂的交通环境下,如何寻找一条可靠、快速、安全的最优路径,已经成为所有驾驶员的共识.图结构被应用描述数据之间的复杂结构,对海量图数据的分析和挖掘越来越重要[1,2].在现实世界中还有边对应的权值不是一个而是多个,并且源节点到某一个节点的最短路径是有限制条件的,这就成为多约束最优路径问题[3].传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的,即:假设每条路段上的行驶时间是确定的.在这种情况下,最优路径就是行驶时间最短的路径.目前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法,寻找行驶时间最短的路径.事实上,由于在现实生活中,会受到很多不确定性因素的影响,例如:交通事故、突发事件等,车辆的行驶时间存在着不确定性.所以,城市智能交通系统中,如何设计一款可靠、快速和安全的最优路径,成为驾驶员的共识.

针对这些问题,进行“不确定条件下最优路径的研究”.首先,在不确定条件下分析不同车辆经过路径的时间均值和标准差,给出每条路径的时间代价;在此基础上,在合理假设下利用迪杰斯特拉算法得到起点和终点之间的最小时间代价,即为最优路径.本文按照此思路,将设计的最优路径应用到两点网络和交通网络中,得到相应的结果,验证了最优路径的合理性.

2 两点交通(Two-point traffic)

2.1 两点交通的最优路径模型

在不确定性条件下,以经典的最短路径算法来搜索的车辆路径导航系统是有缺陷的.例如,为了准时到达目的地,驾驶员通常宁愿避免拥挤的市区道路,而选择路程稍远的绕城快速路.经典的最短路径算法是假定每条路段上的行驶时间为确定值,而不同数量的车辆实际经过同一条路段的时间不可能为确定值.其中有诸多的因素对我们的驾驶状况有影响,如道路的维护,早中晚的时间段,道路周围的设施和建筑,道路本身的状况等等.这些都是导致不确定性的原因,从而使道路的流量变化.我们以某一个城市中某一区域,私家车经过同一条路段的不同行驶时间和影响道路的状况的事物(如,红绿灯的数量、红绿灯等待时间)为参数,计算该路段的平均时间和时间的标准方差,建立车辆从起点到终点的最优路径的定义和数学表达式.

本文研究的目的是找出起点到终点之间花费时间最短的车辆行驶路径.但传统最优路径算法只考虑了车辆在路段上的行驶时间,因此无法搜索到符合实际情形的最优,所以在这里我们增加一些衡量最优路径的指标.具体的指标有时间的均值、时间的标准差,以及影响两者的权重指标.根据实际的情况出发,在驾驶的过程中由于道路不稳定的状况,而导致时间的波动较大,所以我们给标准差赋以较大的权值.在最优路径算法中应加入每个路段的行驶时间的方差,方差的数值越大说明该路段拥挤概率越大,反之越小.定义某段道路的行驶时间的均值和该段道路行驶时间的标准差分别为

2.2 模型的具体应用

以图1为示例,将我们的模型应用到图1的例子,其中大学为起始点,火车站为终点,并且取.

虽然经过市区道路时间的均值为30分钟,而绕城快速路需要的时间均值为33分钟,其时间代价为19.5.但是由于市区道路拥挤,其标准差为15分钟,而绕城快速路的标准差只要1分钟,时间代价为10.6.通过本模型的应用,选择绕城快速路的时间代价要小于选择市区道路的时间代价.

3 交通网络(Traffic network)

3.1 交通网络的最优路径模型

在两点道路的最优路径模型中,提出的基于均值和方差的最优路径模型只是针对简单的两个点计算道路的时间代价.因此在实际的交通网络中,我们建立城市道路网络模型,G表示城市道路网络模型.该模型由集合共同描述,即抽象为“{节点集合}+{弧段集合}+{路权集合}的带权复杂交通网络来描述,其中为城市道路网络的节点(公交站台)集合;为城市道路网络的路段(公交站台之间的路段)集合.为城市道路网络的路段权值(时间代价)集合,实际上两个道路节点之间的行驶代价不仅和路段的长度有关,还与道路拥挤程度有关.

研究的目的是找出起点到终点之间花费时间最短的车辆行驶路径.但传统最优路径算法只考虑了车辆在路段上的行驶时间,忽略了路段中存在的拥挤程度,因此无法搜索到符合实际情形的最优路径.所以必须在最优路径算法中应加入每个路段的行驶时间的方差,方差越大说明该路段拥挤概率越大,反之越小.

以某一个城市中不同的公交车经过同一条路段(,为该路段的二个公交站台)的不同行驶时间为参数,计算该路段的平均时间和时间的标准方差,建立车辆从起点到终点的最优路径的定义和数学表达式.

每段道路行驶时间的均值矩阵和标准差矩阵分别为

在连通网络中,找出任意节点到节点的一条路径,使得时间代价最小.在Dijkstra最短路径算法中[4],该算法是基于贪心策略,按路径长度递增的次序产生最短路径的经典算法,主要思想是以起始点为中心向外层层扩展,直到扩展到目标点为止,即以道路的长度为权重.类似于Dijkstra最短路径算法思想,我们把每个路段的时间代价定义为权重,目标为求解.具体算法如下:

(1)用邻接矩阵来表示为时间代价赋权的图,集合T等于T-S用于存放当前还未找到最小时间代价的节点.那么从v1到图中其余节点的最小时间代价的初值为

(4)重复(2)(3)共n-1次.由此求得从到图中其余各节点的最小时间代价路径.

类似于Dijkstra最短路径算法,我们提出的算法用最简单的实现方法就是在每次循环中,再用一个循环距离最短的点,然后用任意的方法更新与其相邻的边,时间复杂度显然为.对于空间复杂度:如果只要求出距离,只要n的附加空间保存距离就可以了(距离小于当前距离的是已访问的节点,对于距离相等的情况可以比较编号或是特殊处理下).如果要求出路径则需要另外V的空间保存前一个节点,总共需要2n的空间.

基于均值矩阵和方差矩阵的最优路径算法的最小时间代价的最优子结构性质,该性质描述为:如果是从顶点i到j的最小时间代价路径,k和s是这条路径上的一个中间顶点,那么必定是从k到s的最小时间代价路径.下面证明该性质的正确性.

假设是从顶点i到j的最小时间代价路径,则有.而不是从k到s的最小时间代价路径,那么必定存在另一条从k到s的最小时间代价路径,那么.则与是从i到j的最小时间代价路径相矛盾.因此该性质得证.

3.2

模型的具体应用

对盐城市区的交通网进行模拟,其中图2为盐城市区图,途中用粗线标出的线路是我们此次建模比赛中所要研究的线路,用红色标志球所标识的是路线中的各个结点,共计20个.为了使图示简洁明了,将20个结点以数字代替,同时为了使线路表示的更加的清晰明了,我们以图2为模型,绘制了如图3所示的盐城市区示例交通网络.

注:3-5-10-13-16-19:解放路,5-4:建军路,10-9-8-20:青年路,13-12-11:东进路,16-15-14:世纪大道,19-18-17:新都路,其中在现实生活中解放路和建军路交通较为阻塞.

图2中对应的盐城市中心公交站点,对应数字含义如下:

根据真实路况的数据,设定车辆经过各个路段不同时间(图4),求得各个路段行驶时间的均值矩阵为(inf表示无穷大,代表两个地点之间没有直接可以到达的道路).

根据模型,在MATLAB上面依据道路权值矩阵采用迪杰斯特拉算法编写程序并运行,我们寻找从节点3到节点19(人民公园到农业发展银行)的最短路径,运行结果如下:

3

2

4

7

8

11

14

17

18

19

所经道路权值总和为660,根据实际情况,此路径绕过了路程短却拥挤的解放路和建军路,而选择了路径较长却不太拥挤的其他道路,在不确定的条件下,会花费更少的时间代价,通过一条可靠、快速、安全的道路准时到达目的地.

4 结论(Conclusion)

本文提出的城市道路中搜索最优路径的算法,与以往算法不同的是,本算法不仅仅考虑路径的距离长短,更加入了车辆通过路径的平均时间与时间的标准差,以及通过平均时间和标准差得到的一个相对确切的时间代价,在不确定条件下(如道路拥挤)给出最优的路径,使得驾驶员能够可靠、快速、安全到达目的地.并且在大学到火车站两点之间以及盐城市区交通网络进行了具体的应用中,使得驾驶员能够选择更合理的路线,绕过拥挤的路段,花费尽可能少的时间到达目的地,运行结果令人满意,因此本文中提出的算法具有实际应用价值.

参考文献(References)

[1] 张素智,张琳,曲旭凯.基于最短路径的加权属性图聚类算法研究[J].计算机应用与软件,2016(11):212-214.

[2] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008(1):48-61.

[3] 邹永贵,魏来.带多约束条件的最优路径选择算法研究[J].计算机应用,2008(05):1101-1103.

[4] Cormen,H.Thomas,Leiserson,E.Charles,Rivest,L.Ronald,Stein,Clifford (2001)."Section 24.3:Dijkstra´s algorithm".Introduction to Algorithms (Second ed.).MIT Press and McGraw Hill:595-601.

作者简介:

顾爱华(1978-),男,硕士,实验师.研究领域:软件工程与复杂网络.

郭青慧(1995-),女,本科生.研究领域:网络系统集成,物联网技术.

条件论文范文结:

关于本文可作为条件方面的大学硕士与本科毕业论文条件论文开题报告范文和职称论文论文写作参考文献下载。

1、晋升副高职称论文条件