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

1、.不确定性条件下的最优路径问题摘要本文针对现实生活中的交通网络，综合各种影响因素，建立不确定条件下的最优路径选择模型。首先，本文改变传统路径最短算法的思路，以寻求行驶时间最短为目标，综合考虑不确定因素，通过线性回归分析，建立了基本的各路段行驶时间与路段平均行驶时间、行程时间标准差、行程紧急程度、动态交通变化量之间的模型。得出不确定条件下车辆从起点到终点最优路径的定义和数学表达式，并将此模型运用于第一问示例，得出结论。其次，在已知每条路径行驶时间均值与标准差的条件下，借助蚁群算法在实际交通网络中寻找最优路径。接着，考虑到道路拥挤情况，利用道路阻抗排队论的结论在原有模型基础上进行改进，建立新的模型

2、并应用于交通网络最优路径的搜索。最后，对现实网络的重新分析，综合其他不确定因素完善现有模型。关键词：回归分析 蚁群算法 排队论一、问题重述目前，交通拥挤和事故正越来越严重的困扰着城市交通。随着我国交通运输事业的迅速发展，交通“拥塞”已经成为很多城市的“痼疾”。在复杂的交通环境下，如何寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的，即：假设每条路段上的行驶时间是确定的。在这种情况下，最优路径就是行驶时间最短的路径，可以用经典的最短路径算法来搜索(例如Dijkstra 最短路径算法)。目前的车辆路径导航系统也大都是基于这

3、种理想的状况下的最优路径算法，寻找行驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。第一问：如图1所示的交通网络，起点：中国矿业大学，终点：徐州火车站。假设车辆的行驶时间是随机变量。如果走绕城快速路，平均33分钟到达，虽然路程远，但是很少发生堵车，所以行驶时间的波动很小，标准差只有1分钟；如果走市区道路，平均30分钟到达，虽然路程近，但是市区经常发生堵车，所以行驶时间的波动很大，标准差高达15分钟。如果用传统的最优路径算法，应该选市区道路，因为平均时间短。在现实中，为了准时到达目的地，驾驶员通常会选择

4、路程稍远的绕城快速路。起点终点市区道路均值30分钟，标准差15分钟中国矿业大学徐州火车站绕城快速路均值33分钟，标准差1分钟图1. 示例交通网络对于一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立数学模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式，将此模型应用到图1的例子中会选择哪条道路。提示：(1) 传统的最优路径可以看成是平均行驶时间最短的路径，本题中的最优路径不仅要考虑平均行驶时间，而且还要考虑不确定性条件下车辆准时到达终点的可靠性等因素; (2) 假设车辆在每条路段上的行驶时间是随机变量，这里的“路段”相当于网

5、络图中的“边”。第二问：根据第一问的定义，假设已知每条路段行驶时间的均值和标准差，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。第三问：在现实的交通网络中，某个路段发生了交通拥堵，对上游或者下游路段的交通状况有很大的影响，从而导致了交通路段之间的行驶时间有一定的相关性，这种相关性情况很复杂，其中一个典型的例子如下：下游路段发生交通拥堵使车辆减速或者排队，导致上游路段发生拥堵。请建立数学模型描述这种交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中，并设计算法解决考虑相关

6、性的最优路径搜索问题，给出算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。提示：这里的相关性，可以从空间和时间的两个方面考虑。空间相关性：同一个时间段(例如7:00-8:00之间)，路段a和路段b的相关性。时间相关性：对于路段a，不同时间段的相关性，例如7:00-8:00和8:00-9:00之间的相关性。当然，也可以两种相关性同时考虑。第四问：从不确定性条件下交通网络的实际情况出发，在合理假设下，进一步完善前三问的数学模型和相关算法。或者，提出一种或多种与前三问不同的最优路径的定义方法，建立相关的数学模型并设计算法，应用数值算例验证算法的有效性。如果可能的话，从理论

7、上分析算法的收敛性、复杂性等性质。说明：本题中的所涉及的算例最好能采用真实的交通网络数据，也可以使用自己假设的数据，交通网络的规模越大越好。二、问题背景随着智能交通系统（ITS）的发展，对出行者路径选择行为的研究也成为各国学者关注的热点问题之一。路径选择主要解决的问题是：以智能交通系统实时提供的路况信息和驾驶者交通需求为输入，在一定优化目标下，为驾驶者提供最合理的出行路径。在传统路径选择方法中，一般是以Dijkstra 最短路径算法为典型，此类算法虽然降低了模型的复杂度，但是忽略了驾驶者的个性化需求，诱导系统为不同的人群提供相同的方案，这必然会在网络中产生集聚效应，产生拥挤漂移现象，使网络交通

8、流量处于失衡状态。所以，有必要在多不确定属性条件下，对路径选择综合分析。三、基本假设与符号说明3.1基本假设1.交通网络中的各路段行驶时间均值与标准差已知。2.本文收集的数据真实可靠。3. 忽略驾驶者主观导致行驶时间变化的因素。3.2符号说明四、问题分析与思路流程4.1问题分析首先对于综合评估不确定性因素的建模，我们不止考虑到时间最短以及时间的波动性（也就是标准差）这两个因素，还有另外一些不确定性因素，例如，安全性、舒适性、拥挤程度、车道数、道路质量等级、行人及非机动车数量、交通事故率、行程费用、沿途景观等。这些都将作为影响最终时间的主要因素，注意这些因素是不确定的。从驾驶人的角度考虑，理想最

9、优路径的确定过程应综合考虑各主要出行影响因素并充分体现驾驶人的主动性。所以综合面向驾驶者的个性化需求构建可行路径的属性集即路径综合评价指标体系。利用回归分析建立行程时间模型。其次，当我们面对一个具体的复杂网络时，解答：此次建模不止考虑到时间最短以及时间的波动性（也就是标准差）这两个因素，还有另外一些不确定性因素，例如，安全性 ，舒适性 ，拥挤程度 ，车道数 ，道路质量等级 ，行人及非机动车数量 ，交通事故率 ，行程费用 ，沿途景观等 。这些都将作为影响最终时间的主要因素，注意这些因素是不确定的。从驾驶人的角度考虑， 理想最优路径的确定过程应综合考虑各主要出行影响因素并充分体现驾驶人的主动性。

10、本文综合面向驾驶人的个性化需求，构建可行路径的属性集即路径综合评价指标体系如下： （1）式中为行程平均时间，注意此行程平均时间仅仅是在不考虑人的主观性所得出的平均值，以时间最短为主要目标; 为行程时间标准差，衡量在没有其他因素影响下的偏离行程平均时间的程度；为当前行程目标紧急程度评价项用以衡量驾驶人的紧急程度；为动态路段交通变化量用以衡量较理想平均路段交通的偏离程度，例如突然发生较大堵塞等状况。为行程距离; 为行程舒适度,是考虑可行路径各路段的拥挤程度 ,车道数，道路质量等级 ,行人及非机动车数量等因素而所得的综合评价值 ; 为安全度, 是考虑可行路径各路段交通事故率的综合评价值 ;为行程费用

11、 ，主要考虑路段收费和油耗。可见上述，皆是影响最终行程时间的相关因素，只是各因素在所占权重上会不一样。而另外的因素是影响驾驶员主观原则的因素。总之，以上因素皆是评价最短路径的主要因素。由以上说明可知，最终行程时间x=x(，),假设最终行程时间函数是关于四个主要变量的线性函数，另外根据以上分析我们知道在不考虑除以外的因素时，x=,如此我们利用基准值T=的增量形式来表达关于最终时间函数的表达式。要求x=x(，)的表达式，也就是x=T（1+ ），我们可以将叫做偏差量，相应的叫做相应比重。具体分析计算如下：对于，由于它是由标准差引起的，也就说与平均值之间的偏差，假设行程时间变量服从正态分布，那么我们理

12、所当然的认为服从标准正态分布，所以可以将当做一个区间数，由概率论的相关知识，我们可以只考虑偏差概率大的部分，即；对于，由于它是由即当前行程目标紧急程度评价项用以衡量驾驶人的紧急程度所决定，我们可以用离散值来标定相应紧急程度，当然程度越急，相应时间也就会减得越少。如此我们可以用：，其中驾驶员很急，则对应，驾驶员一点都不急对应，在这之间对应0。为了简便分析，我们只分这三种等级，很明显的可以看出这种取值是符合实际的。对于，为动态路段交通变化量用以衡量较理想平均路段交通的偏离程度，我们仿照来规定取值，其中对应较我们所建立的理想时间时的路段交通堵塞状况要轻得多，则对应较之重的情形了，在这之间是0，也就是

13、相差不多的情况。对于，则依实际而定。如此最终行程时间函数模型建立。之后是关于最短路径的评价标准，兼顾x, 等因素来做相应的综合评价。在不确定性条件下车辆从起点到终点的最优路径的定义如下，关于综合评价的最小值所对应的路径即为最优路径。以下是关于综合评价的模型：建模所需要的理论模型是不确定型多属性决策方法模型：多属性决策是决策理论研究的重要内容 ,现已被广泛应用于项目评估、方案优选 、效益综合评价等诸多领域。对于智能交通系统研究中的路径选择问题 ，交通路网信息本身就存在较大的动态性和随机性 ，诸多路径评价指标只能通过测算 、建模来给出当前交通状态下的估计值， 与真实值相比存在误差，简单将其忽略有可

14、能导致路径选择结果的不合理性， 同时驾驶人作为单一个体， 由于其性格、 爱好、 驾驶熟练程度的不同 ，对路径选择具有一定的偏好性 。而且这种偏好本身具有模糊性 ，难以量化， 因此 本文基于不确定型多属性决策方法研究动态路径选择问题 ，具有较强的实际应用背景。对于不确定型多属性决策问题 ，设可行方案集为，属性集为,各属性对应的权重向量为，属性权重满足，且对于任意的，有。设为可行方案关于属性的取值区间，则决策矩阵为： A= (2)考虑到属性类型有效益型(属性值越大越好型)和成本型（属性值越小越好型），为了消除不同物理量纲对决策结果的影响，需要将决策矩阵A化为规范化矩阵。根据区间数的运算法则，对于效

15、益型和成本型，转换公式分别为式（3），（4）： （3） （4）由于多属性决策的本质是对各方案综合属性值的排序比较，针对规范化决策矩阵，假定各属性的权重向量W已确定，则方案的综合属性值为： （5）由于仍是区间数，为了能对方案进行排序，需定义区间数之间两两比较的可能度概念。以下是相关可能度概念的定义：当a和b之间至少有一个是区间数时，设，记，则称为的可能度，且 （6）基于各方案之间的可能度，令,建立各方案的可能度互补矩阵P,对于互补判断矩阵，相关文献里给出了互补判断矩阵的排序向量的一个计算公式： (7)按其分量大小对方案进行排序即可得到最优方案。以上是关于我们建立综合评价体系所要用到的理论模型，之

16、后将它与我们所要解决的实际问题结合起来。回到解答刚开始的地方，我们建立了8个主要因素，其中前4个主要因素导出了行程时间这个主要因素，所以最终我们建立了5个主要因素。按照理论模型中对应的说法是我们建立了5个属性，即：令，如此我们就建立了相应的属性集。需要说明的是，为综合评价的方便，需将不同物理意义的各种评价指标转换为0,1区间的量纲为1 的满意度评价指标，本文同意将其转化为成本型（设计指标越小越好型）；同时，由于在实际中客观交通路况的动态变化和主观个性票号的改变，路径评价指标值具有一定的随机性，可以表示为区间数形式，即：以下是关于一开始所说的指标权重的确定：在一般情况下 ，出行者会根据个人经验喜

17、好或习惯去选择路径 ，对指标权重的确定反映了驾驶人的个性化需求 ，但个性化偏好往往具有复杂性和模糊性 ，用模糊数表示判断的结果能够更好反映事物的客观本质。 因此， 本文将驾驶人的个性化需求引入指标权重确定过程 ，基于模糊数学理论进行指标权重的个性化确定， 相比一般方法 ，模糊分析法简化了驾驶人判断路径评价指标相对重要性的复杂程度， 解决了可行路径优化排序过程中的一致性问题。模糊分析法的基本过程是以矩阵形式表达各路径评价指标对驾驶人的相对重要性 ，从而建立相应的模糊矩阵。 （8）评价指标比相对重要评价指标比同样重要 （9）评价指标比相对重要对模糊矩阵F进行一致化处理，构成模糊一致矩阵R，即其中：

18、 （10）然后基于模糊一致矩阵进行指标权重的确定，即得： （11）按下式进行归一化： （12）从而可得到路径指标权重向量W。至此最优路径模型建立完毕。第二问：根据第一问的定义，假设已知每条路段行驶时间的均值和标准差，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。答：我们针对现实生活中的路网信息不确定性，利用多属性的决策方法对所有可行路径进行综合评估排序，以求得最优路径。我们根据第一问的结论，现在将一个复杂的交通网络分为若干段，基于蚁群算法进行动态路径选择。1 蚁群算法原理生物世界中的蚂蚁在觅食时可以在没

19、有任何可见提示的情况下找出蚁穴到食物源最短路径，并且随环境变化及时搜索新的最短路径。研究发现，这是因为蚂蚁能够在其走过的路径上分泌一种称作信息素的挥发性化学物质，通过这种方式形成信息素轨迹。蚂蚁在寻径时能感知信息素的存在及其强度，并以此直到自己的运动方向。信息素的强度越高，蚂蚁选择该方向的概率越大。假设存在A、B两条路径，在不考虑信息素挥发的情况下，当m只蚂蚁经过两条路后，第m+1只蚂蚁选择A路径概率为，选择B路径的概率为。式中:Am和Bm分别为经过A、B路径的蚂蚁数, ;h和k为匹配参数,根据Goss等人的双桥实验,h 2,k20。对于一条路径来说,选择它的蚂蚁越多,则该路径上的信息素强度就

20、越大,从而吸引更多的蚂蚁,形成一种正反馈。蚂蚁正是通过这种正反馈最终发现最短路径的。受蚂蚁集体觅食行为的启发,意大利学者Dorigo于1991年首次提出了蚁群算法。目前该算法已经广泛应用于各个领域,并取得了较好的效果。本文将着重探讨蚁群算法在动态诱导方面的具体应用。2 基于蚂蚁寻径原理的路网模型将经济圈公路网中的公路交汇处和枢纽抽象为节点,公路(包括高速公路、国道、省道等等)抽象为路径,公路网中的车辆驾驶员对应成一只只蚂蚁,就可以将经济圈公路网中的动态路径选择问题和蚂蚁寻径问题联系起来。那么驾驶员k在节点i选择相邻节点j的转移概率为 (1)式中: 为路段的“信息素”; 为与节点i相邻的所有节点

21、的集合; , 为路段的路权,可以取作路段长度,也可取作行驶费用成本,还可取作行驶时间; 为路段上的车辆平均速度,反映了路段的饱和度,即已有交通量和设计交通量的比值,路段饱和度越高,车辆的平均速度就越小。可见,路段的路权大小、饱和度与驾驶员选择该路段的概率成反比。、和为启发式因子,分别反应信息素、路段权重和路段饱和度在路径选择时的相对重要程度,可根据具体情况确定。另外需要为每个驾驶员设计一个禁忌表,记录驾驶员k已走过的节点,不允许驾驶员在单次行程中重复经过这些节点。信息素的刷新规则有局部刷新规则和全局刷新规-则两种。局部刷新规则是指每一个驾驶员每经过一个路段便及时更新该路段的信息素强度。当驾驶员

22、k经过路段后,该路段的信息素强度刷新公式为 (2)式中:为信息素挥发度,在(0,1)范围内取值;为可调参数,根据取值路段的交通状况特征,如高峰时间和非高峰时间、公路的等级而有所不同。在公式中, 为路段的行程时间。当行程时间时,路段的信息素则完全处于挥发状态,此时信息素不再增加,而是随的增加而减小。全局刷新规则是指驾驶员到达目的节点时,再更新公路网中所有路段的信息素强度。设驾驶员k从源节点到目的节点经过的路径为s,则可将所有路段的信息素强度公式刷新为 (3)式中: ,为路径s上的瓶颈路段平均车速,即路径s上所有路段平均车速的最小值, ,;为路径s的全长;为可调参数,取决于路段的交通状况特征;为瓶

23、颈路段车速对信息素强度的影响程度。全局刷新公式中引入了瓶颈路段平均车速作为参考指标,这样可以为瓶颈车流速大的路径分配较强的信息素,从而诱导驾驶员在通畅的路径上通行。另外模拟信息素的挥发也使得选择次数多的路径要比较少选择的路径信息素要强。两种刷新规则的不同在于反馈信息类型的不同,全局刷新规则使用的是全局信息,刷新时迭加的信息素大小取决于生成解的优劣程度,驾驶员选择的路径越短、瓶颈路段平均速度越快,那么这条路径上所贡献的信息素量就越多。而局部刷新规则使用的是局部信息,在搜索过程中不受解的优劣度影响,其启发信息只是的增强,而在全局刷新规则中代表了一个与完全不同的信息类型。由此可见全局刷新规则明显优于

24、局部刷新规则,不仅可以更精确地寻求最优路径,更能大大减少迭代次数。3参数取值 蚁群算法与其它模拟进化算法一样,存在着收敛速度慢、易陷入局部最优等缺陷。而模型中各参数的取值更直接关系到算法的收敛速度和全局搜索能力。信息素挥发度是算法最关键的参数之一,若过大,在处理较大的交通网络问题时,一些未被选择的路径信息素含量可能很快就会降低到趋近于0,而有被选择的路径则被选择的可能性会增大很多,因而降低了算法的全局搜索能力;若过小,虽然算法的全局搜索能力提高了,但是算法的收敛速度将会降低,算法的迭代次数会大大增加。通过计算机的仿真实验分析ant-cycle system模型,将启发式因子和路段信息素初始值均

25、取为1,运算停止条件为相邻的两次循环搜索中最优解的差别小于0.001。由实验结果可知值在0.3 0.5范围内时,算法的搜索效率和收敛速度会比较好。针对动态路径选择问题的实际要求,应该首先考虑算法的稳定性和最优解的全局性,其次才是其收敛速度,因此,取0.3为宜。启发式因子反映了驾驶员在运动过程中残留信息量在路径选择中的相对重要程度,a的大小反映了路径选择时随机性因素作用的强度,其值越大,驾驶员选择曾经走过的路径的可能性也就越大,搜索的随机性减弱,可见值过大容易使路径搜索过早限于局部最优。启发式因子反映了路段的权重(距离、费用、行驶时间等)在路径选择中的相对重要程度,的大小反映了路径选择时确定性因

26、素作用的强度,其值越大,驾驶员在某个局部点上选择局部最短路径的可能性越大,尽管搜索的收敛速度加快,但随机性减弱,也很容易陷入局部最优解。启发式因子反映了路段实时饱和度在路径选择中相对重要程度,的大小反映了实时性因素作用的强度,其值越大,驾驶员选择服务水平高的路段的可能性就越大,搜索的实时变动性加大,增加了全局最优解的不确定性,可见值过大会使算法的收敛性能大大降低。3个启发式因子既相关又矛盾,对算法性能的影响很大。通过对上述路网模型的仿真实验,当取= 0.3时,实验结果表明的最优值在1左右,而和在2 5之间最优。4 动态路径选择的步骤描述假设经济圈公路网中的每个节点都安设有一台专门的交通信息服务器,并