不确定性条件下的最优路径问题

不确定性条件下的最优路径问题

摘要

本文研究了某城市两地点间在不确定性条件下选择最优路径的问题，主要根据交通网络数据，建立数学模型，确定了不确定性条件下的最优路径，并且对模型的优缺点进行了分析，提出了改进方法，以更好地研究城市不确定性条件下的最优路径选择问题。 在问题一的求解中，为了定量的分析车辆行驶时间的不确定性，选择出在不确定性条件下车辆从起点到终点的最优路径。

关键字：正态分布函数，加权平均法，最优路径，概率，函数积分，数学期望

1

不确定性条件下的最优路径问题

目录

摘要 .............................................................................................................................. 2 一.问题的提出 ......................................................................................................... 4 二.问题的分析 ......................................................................................................... 4 三.建模过程 .............................................................................................................. 6 1.模型假设 ....................................................................................................................... 6 2.定义符号说明 ............................................................................................................ 6 3.问题一求解 .................................................................................................................. 7

3.1问题一模型建立 .......................................................................................................... 7 3.2模型求解 ...................................................................................................................... 8 3.3模型检验 ...................................................................................................................... 8 3.4模型评价 ...................................................................................................................... 8

4.问题二求解 .................................................................................................................. 8

3.1具体交通网络问题的提出 .......................................................................................... 9 3.2问题二模型建立 ........................................................................................................ 10 3.3模型求解 .................................................................................................................... 11 3.4模型检验 .................................................................................................................... 11 3.5模型评价 .................................................................................................................... 11

5.问题三求解 ................................................................................................................ 11 6.问题四求解 ................................................................................................................ 13 四.模型的结论及见解 ......................................................................................... 20 五.参考文献 ............................................................................................................ 21 六．附录 ................................................................................................................... 22

2

一．问题的提出

目前，交通拥挤和事故频发严重的妨碍城市交通。随着我国交通运输事业的迅速发展，交通“拥塞”成为了很多城市的“顽疾”。在复杂的交通环境下，寻找一条可靠、快速、安全的最优路径，已成为驾驶员的共识。 通过对道路状况的查证，大量交通网络数据的收集，以及通过运用相关数据建立相应数学模型进行有效的分析，进而选择最优路径，日益成为人们关注的焦点。本论文通过查找道路交通数据，运用正态分布函数、加权平均法、matlab算法的方法去解决出行路径的选择问题。通过利用得到的数据，采用数学建模的方法完成以下任务： (1) 定量的分析车辆行驶时间的不确定性，给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式，同时给出最优路径。

(2) 通过设计算法搜索最优路径，并将算法应用到具体的交通网络中，用计算结果验证算法的有效性。

(3) 建立数学模型描述交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中，设计算法解决相关性的最优路径搜索问题，给出算例验证算法的有效性。

(4)提出一种或多种与前三问不同的最优路径的定义方法，建立相关的数学模型并设计算法，应用数值算例验证算法的有效性。

二．问题的分析

通常，在每条可供选择的路线的特征确定之后，最优路线的选择问题就可以转化为类似经过可供选择路段时所需要的时间最少的问题。行驶时间的长短受到不确定因素的影响，例如：驾驶员特征的影响，车辆交通特性，道路基本特征，这些不确定因素会影响到行驶时间的均值和标准差，进而影响了行驶时间。对这样一个多因素影响下的行驶时间，其最优解的确定就用正态分布方程和积分方程来求解。

根据以上分析，最优路线选择时需要考虑的问题包括：

1、考虑各种因素的影响，均值和标准值的计算较麻烦，不适用于路段状况较复杂的情况；

2、每条路段不能提供相关路况信息或信息不准确； 3、不同驾驶员选择最优路线的决策方法不同； 4、相关不确定性因素分析 （1）驾驶员的交通特性

在交通要素中，驾驶员具有特别重要的作用。在驾驶员烦人行驶过程中，起控制作用的是驾驶员的驾驶技术以及驾驶特征，如激进型的驾驶员与保守型的驾

3

不确定性条件下的最优路径问题

驶员对同一种驾驶环境的反应是有很大差别的；在驾驶员的反应操作过程中，起控制作用的是驾驶员的生理、心理素质和反应特性，而不同驾驶员之间的基本生理素质千差万别。同时，对每一个驾驶员来说，他在下一时刻面临的选择也是不确定的，其前车的运行状态将直接影响到他的驾驶情况。驾驶员作为影响交通流的最主要的主观因素之一，存在着许多不可预测与不确定性。

根据一个驾驶员到目的地的目的、年龄、性别等特性进行预测的模型 T1??19131?(t?16)?2?e?(?）tdt ??22???其中：

?i是xj的线性函数

xj代表驾驶员到目的地的目的、年龄、性别等。 q代表流量 k代表密度 （2）车辆交通特性

不同车辆在外观和性能方面有很大差别，而影响交通流的主要因素是超车加速时间、最高车速等性能，驾驶员会根据自己或乘客的乘车目的随时随意改变车辆速度，而车辆的性能无疑对驾驶员的驾驶造成很多影响。 （3）道路基本特性

道路是汽车交通的基础、支撑物。衡量路网的指标主要有路网密度，道路结构，道路线性，道路网布局，没有两个路网的结构是完全相同的，而乘客在面临道路选择时，天气、个人喜好等都是影响其决定的因素，哪条路段会被选中是无法预测的。 ①非拥挤状态

当车辆与车辆之间的相互作用不是很明显，每个驾驶员都自由地驾驶时，可以更加精确地估计出每类驾驶员的自由流速度，下面公式揭示出这个关系：

Ft,非拥挤?qt,非拥挤（x,t)?Viimax,iik(x,t)??i(x,t)k??i(x,t)

q总，非拥挤（x,t)??qi??V

max,iiq总，非拥挤??Vimax,ipik总??i(x,t)Vmax,i?i类驾驶员的自由流密度ki?单位长度的公路上车辆的密度F?流量 ②拥挤状态

在拥挤状态下，假设一类驾驶员的速度是所有车辆速度的线性函数，由此得

4

出流—密度关系

si?ai?biVdi?ki?pik?所以V?(pi??piai)/(?pisi)kiiiVV?pi(ai?biV)a?bVpi?spi??pisii?ipipi(ai?biV)pi?i类驾驶员所占比例VVq总，拥挤?Vk???S?pisii?i所以q总，拥挤?（pi1??piai)/(?pibi??pi)kikiiii?(1?k?piai)/(?piai)i

三.建模过程

1.模型假设

（1）在每条路段中车辆单向行驶；

（2）每条路段的行驶时间T都服从正态分布；

（3）在驾驶员通过任意到达目的地路线的时间?t内，每条路段的路况特征指标不变；

（4）已知每条路段行驶时间的均值和标准差； （5）车辆在每条路段上的行驶时间都是随机变量；

（6）每条路段的平均行驶时间T(t)，每条路段行驶时间的标准差都是相互独立的随机变量；

（7）驾驶员对各种路况特征的使用偏好为已知；

（8）以每条路段的平均行驶时间和行驶时间的标准差作为表示路段特征的指标； （9）在阻塞情况下，驾驶员不改变行驶路段。 （10）不考虑各个路段行驶时间的相关性

2．定义符号说明

5

不确定性条件下的最优路径问题

?i:第i条路的行驶时间均值；?i:第i条路行驶时间的标准差；

Pi:第i条路行驶所用时间的概率； Ti：第i条路行驶时间的期望值； Tmin:最优路径行驶时间的期望值；

3．问题一求解

3.1问题一模型建立

3.1.1车辆从起点到终点的最优路径的定义

在从起点到终点的所需要的时间概率服从正态分布的条件下，时间概率与时间的乘积的面积就是从起点到终点所需的时间，其面积使用积分来求解，其上限为??3?，其下限为?-3?，根据所需时间来确定最优路径。

根据以上假设和分析，可以建立第i条路段上广义行驶时间的正态分布程：

Ti???i?3?i?i?3?ip(ti)tidt(i?1,2,3?)

式中：Ti?经过路段i所需要的时间 p(ti)?1(ti??)?2e?(?)

2??22?? P(ti)表示路段i行驶时间的概率

??-3?，?-3??0?-3??? ?0，?-3??0??均值

??标准差?Mi?nT1,T2?? Tmin根据时间的数学期望最小，来确定最优路径的选择 3.1.2图一案例的求解

6

T1??363012?(t?33)?2??e?(?)?tdt ?2??T2??7501?(t?30)?2?e?(?)?tdt ?2?2252?15??MATLAB编写算法如下

clc,clear

a=1/(2*pi)^0.5 syms t

T1=a*int(exp(-0.5*((t-33)^2))*t,t,30,36) b=1/(((2*pi)^0.5)*15) syms t

T2=b*int(exp(-1/250*(t-30)^2)*t,t,0,75) T3 =T1; T4 =T2; if T3

'方案一为最佳方案' else

'方案二为最佳方案' end

3.2模型求解

matlab求解的到结果为：方案一为最佳方案。

3.3模型检验

matlab求解的到结果为：方案一为最佳方案。故而走均值为33分钟，标准差

为1分钟的绕城快速路，而不是走市区道路，结果符合现实情况，可知所建模型正确。

3.4模型评价

通过验证，通过所建数学模型求出的结果符合实际情况，该模型不是通过单

单的路段行驶时间的均值来选择最优路线，而是在时间均值的基础上加上由不确定因素所产生的时间标准差，两者共同影响着最优路线的选择，最终通过模型中的T（路段时间期望）来选择最优路线，哪条路的时间期望越小，哪条路就是最优路径。

4．问题二求解

目前交通最优路径的选择备受关注，但现有阶段车辆路径导航系统也大都是基于理想状况下的最优路径算法从而来选择行驶时间最短的路径。但实际情况

7

不确定性条件下的最优路径问题

是，现实生活中交通路径的选择会受到很多不确定性因素的影响，例如：恶劣天气、交通拥堵、交通事故、突发事件等等，因此车辆行驶路径及时间方面存在着不确定性。

根据第一问的定义，在已知每条路段行驶时间的均值和标准差，设计算法搜索最优路径，并将该算法应用到济南市具体的交通网络中，计算结果验证建立算法的有效性。

4.1具体交通网络问题的提出

我们选定起始点为济南市交校路5号，终点为济南火车站，可知共有三条路

线可供选择如图5.1，每一条线路均有其行驶不确定性存在，方案一路段行驶时间的均值和标准差分别为（16）、（1），方案二路段行驶时间的均值和标准差分别为（17）、（5），方案三路段行驶时间的均值和标准差分别为（15）、（4）。对问题一中所建立起的（名称）模型进行相应的改进并将其运用到此具体的题目中，求解出三条线路的时间，来确定最优路径，进而验证建立算法的正确性及有效性。

方案 1 2 3 行驶时间 16分钟 17分钟 15分钟 行驶距离 5.0公里 5.7公里 6.0公里 时间均值 16 17 15 时间 标准差 1 5 4 途中红绿灯个数 14个 14个 10个

8

图4.1交通路线图

（1）针对问题带入模型求解

（2）对第1步进行分析说明

（3）通过前两步得出上述具体问题的答案，并说明算结果验证建立算法的有效性（回扣原问题）

4.2模型建立

T1??191312?(t?16)?2??e?(?）tdt ??2??T2??3221?(t?17)?2?e?(?)?tdt ?502?5??1?(t?15)?2?e?(?)?tdt

322?4???T3??273matlab编写算法如下

clc,clear

a1=1/((2*pi)^0.5*1) syms t

T1= a1*int(exp(-1/2*(t-16)^2)*t,t,13,19) a2=1/((2*pi)^0.5*5) syms t

T2= a2*int(exp(-1/(2*5^2)*(t-17)^2)*t,t,2,32) a3=1/((2*pi)^0.5*4)

9

不确定性条件下的最优路径问题

syms t

T3= a3*int(exp(-1/(2*4^2)*(t-15)^2)*t,t,3,27) T4= T1; T5 = T2; if T4

'方案一比方案二好' else

'方案二比方案一好' end T4= T1; T6 = T3; if T4

'方案一比方案三好' else

'方案三比方案一好' end T5 =T2; T6=T3; if T5

'方案二比方案三好' else

'方案三比方案二好' end

4.3模型求解

matlab求解的到结果为：方案一比方案二好，方案一比方案三好，方案三比

方案二号。故而可知最终选择方案一（即走百度地图所推荐的线路）。

4.4模型检验

matlab求解的到结果为：方案一比方案二好，方案一比方案三好，方案三比

方案二号。故而可知最终选择方案一（即走百度地图所推荐的线路），结果符合现实情况，可知所建模型正确。

4.5模型评价

通过验证，通过所建数学模型求出的结果符合实际情况，该模型不是通过单单的路段行驶时间的均值来选择最优路线，而是在时间均值的基础上加上由不确定因素所产生的时间标准差，两者共同影响着最优路线的选择，最终通过模型中的T（路段时间期望）来选择最优路线，哪条路的时间期望越小，哪条路就是最优路径。

10

附 录

1.问题一中中国矿业大学至徐州火车站路径最优问题mablab程序的编写

clc,clear

a=1/(2*pi)^0.5 syms t

T1=a*int(exp(-0.5*((t-33)^2))*t,t,30,36) b=1/(((2*pi)^0.5)*15) syms t

T2=b*int(exp(-1/250*(t-30)^2)*t,t,0,75) T3 =T1; T4 =T2

>> if T3

'方案一为最佳方案' else

'方案二为最佳方案'

end

问题二中交校路5号至济南火车站路径最优问题mablab程序的编写

clc,clear

a1=1/((2*pi)^0.5*1) syms t

T1= a1*int(exp(-1/2*(t-16)^2)*t,t,13,19) a2=1/((2*pi)^0.5*5) syms t

T2= a2*int(exp(-1/(2*5^2)*(t-17)^2)*t,t,2,32) a3=1/((2*pi)^0.5*4) syms t

T3= a3*int(exp(-1/(2*4^2)*(t-15)^2)*t,t,3,27) T4= T1; T5 = T2; if T4

'方案一比方案二好' else

'方案二比方案一好' end T4= T1; T6 = T3; if T4

'方案一比方案三好' else

11

不确定性条件下的最优路径问题

'方案三比方案一好' end T5 =T2; T6=T3; if T5

'方案二比方案三好' else

'方案三比方案二好' end

12

本文来源：https://www.bwwdw.com/article/zlmo.html