2015年五一数学建模A题不确定性下的最短路径问题--CUMT赖增强

2015年暑期数学建模培训第一次模拟承诺书我们仔细阅读了数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其它公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们授权数学建模联赛赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号为（从A/B/C中选择一项填写）：我们的参赛报名号为：参赛组别（研究生或本科或专科）：本科所属学校（请填写完整的全名）中国矿业大学南湖校区参赛队员(打印并签名)：1.赖增强2.兰卫旗3.李康杰日期：2015年8月11日获奖证书邮寄地址：中国矿业大学南湖校区桃4B5032邮政编码：221116收件人姓名：赖增强联系电话：183612308562015年暑期数学建模培训第一次模拟编号专用页竞赛评阅编号（由竞赛评委会评阅前进行编号）：评阅记录评阅人评分备注裁剪线裁剪线裁剪线竞赛评阅编号（由竞赛评委会评阅前进行编号）：参赛队伍的参赛号码：1（请各参赛队提前填写好）：1不确定条件下的最优路径问题摘要本文针对如何在复杂的交通环境下寻找一条可靠、快速、安全的最优路径的问题，考虑到交通堵塞、恶劣天气、路途成本等不确定因素对司机路径选择的影响，建立多个不确定条件下的最优路径模型。对于问题一，我们在各个路段所用时间服从正态分布N(μ，δ2)的基础上,建立了在不确定条件下求最短路的NP模型，给每个路段设定一个预留到达的时间t，为了尽可能准确的到达目的地，选取95%的概率，满足P{T≤t}≫95%,那么最优路径的定义就是预留时间最小的那个路径，将其转换为标准的正态分布，通过标准的正态分布得到了在不确定性条件下车辆从起点到终点预留时间的数学表达式：t=μ+Φ−1δ。计算得对应的t（绕城）=34.645min，t（市区）=54.675min，那么最优路径为绕城快速路。对于问题二，在第一问定义的基础上进一步引入Bool系数β(a,k),在搜集得到的具体的交通网络中，建立了一个从起点到终点路径为∑β(a,k)na=1Talink的正态分布，通过求最小预留时间t(min)=E[Tkpath]+Φ−1√Var[Tkpath],得出最优路径的算法。其中E[TKpath]=∑β(a,k)na=1E[Talink]，Var[Tkpath]=∑β(a,k)na=1Var[Talink]，但Var[Tkpath]的根式不具有线性可加性。不能用经典的dijkstra算法求解。对此采用基于双目标规划的思路，利用第K短路径算法，分别对E[Tkpath]，Var[Tkpath],运用matlab编程，找出各自前十条最短路径。之后在其并集中找出最优路径：V1→V3→V4→V8。由此建立了求最短路的NPK模型。最后从时间的渐进性态上分析模型的复杂性和收敛性。对于问题三，我们只考虑各路段空间上的相关性，并用概率论中的协方差来表示这种耦合关系，建立了NPK模型。得出可靠时间的数学表达式t=E[TKpath]+Φ−1(ρ)√∑δ(a,k)Var[Talink+∑cov(a−1,a)na=2na=1；求解得最优路径：V1-V3-V5-V8。关键词：NPK模型，K-短路，预留时间，正态分布，渐进性态。2一.问题重述目前，交通拥挤和事故正越来越严重的困扰着城市交通,如何在复杂的交通环境寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。传统的最优路径就是行驶时间最短的路径，这是基于理想交通情况下分析的，而事实上，在现实生活中，受到很多不确定性因素的影响，例如：交通工具、恶劣天气、突发事件，导致车辆的行驶时间均存在不确定性。为了减少交通阻塞所耽误的时间，尽可能快的到达目的地，解决不确定性性条件下的最优路径问题，现依次提出以下问题：（一）针对一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立相关的数学模型，定量地分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式。并将此模型应用到图1的例子中会选择哪条道路。（二）根据第一问的定义，假设已知每条路段行驶时间的均值和标准差，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。从理论上分析算法的收敛性、复杂性等性质。（三）建立数学模型，描述下游路段发生交通拥堵使车辆减速或者排队，导致上游路段发生拥堵的交通路段之间驾驶时间的相关性，并将此相关性应用到第一问和第二问的最优路径搜索问题中，并设计算法解决考虑相关性的最优路径搜索问题，给出算例验证算法的有效性。从理论上分析算法的收敛性、复杂性等问题。二.基本假设符号说明3.1基本假设3.1.1各个路段所用时间服从正态分布。3.1.2假设仅相邻两条路段之间具有相关性。3.1.3假设任意两条相邻路段组成的协方差矩阵为一个随机的正半定矩阵。3.2符号说明3.2.1Tnlink两相邻节点之间的路段3.2.2Tmpath从起点到终点的路径起点终点市区道路均值30分钟，标准差15分钟图.1中国矿业大学徐州火车站绕城快速路均值33分钟，标准差1分钟33.2.3β(a,k)Bool系数。当路径a通过此路段k时为13.2.4Var[T]对随机变量T求方差运算3.2.5Φ−1（ρ）标准正太分布累计概率函数的逆函数3.2.6cov(t1,t2)随机向量t1,t2协方差四.模型的建立与求解4.1问题一4.1.1问题分析本问题是对于题设的交通网络，已知每条路段行驶时间的均值μ和标准差δ条件下。定量分析车辆行驶时间的不确定性，以及给出在不确定性条件下最优路径的定义和数学表达式。假设各个路段所用时间服从正态分布N(μ，δ2)模型，利用MATLAB模拟（附录一）两条路径的正态分布图[1]：（图4.1.1.1）图4.1.1.1给每个路段设定一个预留到达的时间t，为了尽可能准确的到达目的地，选取95%的概率，满足P{T≤t}≥95%。那么最优路径的定义就是预留时间最小的那个路径。4.1.2模型建立与求解已知到达目的地所用时间和预留时间满足：P{T≤t}≥95%，将其转换为标准的正态分布：P{T＜t}≥95%，得到Φ0（t）≥95%，t≥Φ0-1（ρ），（其中ρ为95%）即可解得每条路段的t≥μ+1.645δ，取t=μ+1.645δ。我们将上诉模型称之为不确定条件下的NP模型。应用已知的数学表达式，将图1所给的数据：μ1=33，δ1=1；μ2=30，δ2=15；带入公式计算出：t（绕城）=34.645min，t（市区）=54.675min，最优路径为绕城快速路。4.2问题二4.2.1问题分析4根据第一问中的最优路径定义和相关数学表达式，对于一般交通网络，可以结合K短路径算法建立NPK模型，最后从时间的渐进性态上分析其复杂性和收敛性。4.2.2模型建立与求解对于一般交通网络，为了方便设计算法找到最优路径，搜集了八个城市之间路段的时间均值和时间标准差，列表如下(表4.2.2.1)：表4.2.2.1我们可以将其转化为图论问题。将八个城市看做节点构成一个节点集：V={V1,V2,V3,V4,V5,V6,V7,V8}各个城市之间的道路看做边集：E={V1→V2，V1→V3，V1→4，V1→V5，V1→V6，V1→V7，V2→V3，V1→V4，V2→V7，V3→V4，V3→V5，V4→V5，V4→V8，V5→V6，V4→V8，V6→V7，V6→V8，V7→V8}则可将八个城市之间的交通网络图看做一个无向赋权图G（图.4.2.2.2）每条路为图中的边。八个城市之间交通网络数据图V7V2V3V4V6V8V1V5(70,15)(20,8)(80,5)(70,6)(20,5)(30,5)(20,10)(10,7)(30,12)(60,10)(30,15)(40,5)(40,2)(60,10)(10,2)(40,15)(50,2)图.4.2.2.2在第一问定义的基础上，针对每条路段引入Bool系数β(a,k),当该路段被选择时为1，否则为0。那么从起点到终点的路径可表示为∑β(a,k)na=1Τkpath，可知其服从正态分布。通过求该路径的最小预留时间V1→V2V1→V3V1→V5V1→V6V1→V7V2→V3V2→V4V2→V7V3→V4（10，2）（20，5）（70，6）（40，15）（80，5）（20，10）（30，5）（70，15）（10，7）V3→V5V4→V5V4→V8V5→V6V5→V8V6→V7V6→V8V7→V8（50，2）（30，12）（60，10）（30，15）（40，2）（20，8）（60，10）（40，5）两个城市之间的时间差，标准差路段名称（μ，δ）路段名称（μ，δ）5t(min)=E[Tkpath]+Φ−1（ρ）√Var[Tkpath],得出最优路径。[2]对于t（min）=E[Tkpath]+Φ−1（ρ）√Var[Tkpath]，其中：E[Tkpath]=∑β(a,k)na=1E[Talink]Var[Tkpath]=∑β(a,k)na=1Var[Talink]由于Var[Tkpath]的根式不具有线性可加性。不能用经典的dijkstra算法求解。对此我们基于双目标规划的思路[3]，分别将E[Tkpath]，Var[Tkpath]作为边权，运用matlab编程（附录二），求出前十条最短路径。表4.2.3.1表4.2.3.2根据上述两表数据，运用公式:t（min）=E[Tkpath]+Φ−1（ρ）√Var[Tkpath]求出并集中的前16条最优路径的预留时间（表4.2.3.3）表4.2.3.3节点期望节点期望V1→V6→V7→V8V1→V3→V5→V8V1→V2→V4→V5→V8V1→V2→V3→V4→V5→V8V1→V6→V5→V8第6条路第7条路第8条路第9条路第10条路100110110110110100100100V1→V3→V4→V8V1→V2→V4→V8V1→V3→V4→V5→V8V1→V6→V8V1→V2→V3→V4→V8时间期望值最小的前10条路第1条路第2条路第3条路第4条路第5条路90100节点方差节点方差129174177189189V1→V2→V4→V8V1→V3→V4→V8V1→V2→V4→V5→V8V1→V5→V3→V4→V8V1→V7→V6→V8第6条路第7条路第8条路第9条路第10条路33405086112V1→V3→V5→V8V1→V5→V8V1→V7→V8V1→V2→V4→V3→V5→V8V1→V2→V3→V5→V8时间方差值最小的前10条路第1条路第2条路第3条路第4条路第5条路节点预留时间节点预留时间节点预留时间节点预留时间148.5787155.2551182.615212.615预留时间最小的前16条路第9条路第10条路第11条路第12条路V1→V7→V8V1→V2→V4→V5→V8V1→V2→V3→V5→V8V1→V2→V3→V4→V5→V8124.5099126.1653129.1495129.6557131.6319131.8853137.409138.5397第13条路第14条路第15条路第16条路V1→V3→V5→V8V1→V2→V3→V4→V8V1→V6→V7→V8V1→V6→V8第5条路第6条路第7条路第8条路V1→V6→V5→V8V1→V2→V4→V3→V5→V8V1→V7→V6→V8V1→V5→V3→V4→V8V1→V5→V8111.699118.6836119.4498V1→V3→V4→V8V1→V2→V4→V8V1→V3→V5→V8第1条路第2条路第3条路第4条路120.40396为了直观进