2015年五一杯数学建模A题不确定性条件下的最优路径问题解题全过程文档及程序

2015年五一杯数学建模

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

原题再现

  目前，交通拥挤和事故正越来越严重的困扰着城市交通。随着我国交通运输事业的迅速发展，交通“拥塞”已经成为很多城市的“痼疾”。在复杂的交通环境下，如何寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。
  传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的，即：假设每条路段上的行驶时间是确定的。在这种情况下，最优路径就是行驶时间最短的路径，可以用经典的最短路径算法来搜索(例如 Dijkstra 最短路径算法)。目前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法，寻找行驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。
  第一问：如图 1 所示的交通网络，起点：中国矿业大学，终点：徐州火车站。假设车辆的行驶时间是随机变量。如果走绕城快速路，平均 33 分钟到达，虽然路程远，但是很少发生堵车，所以行驶时间的波动很小，标准差只有 1 分钟；如果走市区道路，平均 30 分钟到达，虽然路程近，但是市区经常发生堵车，所以行驶时间的波动很大，标准差高达 15 分钟。如果用传统的最优路径算法，应该选市区道路，因为平均时间短。在现实中，为了准时到达目的地，驾驶员通常会选择路程稍远的绕城快速路。

  对于一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立数学模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式，将此模型应用到图 1 的例子中会选择哪条道路。提示：(1) 传统的最优路径可以看成是平均行驶时间最短的路径，本题中的最优路径不仅要考虑平均行驶时间，而且还要考虑不确定性条件下车辆准时到达终点的可靠性等因素; (2) 假设车辆在每条路段上的行驶时间是随机变量，这里的“路段”相当于网络图中的“边”。
  第二问：根据第一问的定义，假设已知每条路段行驶时间的均值和标准差，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。
  第三问：在现实的交通网络中，某个路段发生了交通拥堵，对上游或者下游路段的交通状况有很大的影响，从而导致了交通路段之间的行驶时间有一定的相关性，这种相关性情况很复杂，其中一个典型的例子如下：下游路段发生交通拥堵使车辆减速或者排队，导致上游路段发生拥堵。请建立数学模型描述这种交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中，并设计算法解决考虑相关性的最优路径搜索问题，给出算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。提示：这里的相关性，可以从空间和时间的两个方面考虑。空间相关性：同一个时间段(例如 7:00-8:00 之间)，路段 a 和路段 b 的相关性。时间相关性：对于路段 a，不同时间段的相关性，例如 7:00-8:00 和 8:00-9:00 之间的相关性。当然，也可以两种相关性同时考虑。
  第四问：从不确定性条件下交通网络的实际情况出发，在合理假设下，进一步完善前三问的数学模型和相关算法。或者，提出一种或多种与前三问不同的最优路径的定义方法，建立相关的数学模型并设计算法，应用数值算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。

整体求解过程概述(摘要)

  本文以一般交通网络图为研究对象，在每条路径中每个路段的行驶时间的均值和方差已知的基础上，构造最优路径可靠性模型，保证相同高的概率到达时行驶总时间最短，然后把时间相关性和空间相关性融入建立的模型中，层层求解。最后根据所建立的模型分析算法，得出最优路径。
  针对问题一，考虑到在现实中从起点到中间的路径错综复杂，且每条路径的路段数量不确定，我们绘制了一般交通网络图。在已知各路段行驶时间的均值与标准差的前提下，给出最优路径的定义。基于各路段的行驶时间服从正态分布的假设下利用卷积公式，针对每条路径给出以行驶总时间为变量的正态密度函数。最后对所得函数变形处理，得到判断最优路径的数学模型，并根据模型求出示例一的最优路径。
  针对问题二，首先利用卷积公式和0 -1规划，给出最优路径定义的条件下和给出最优路径的搜索算法，运用 Matlab 和 excel 从所有路径中，搜索最优路径；并将其最优路 径 搜 索 算 法 运 用 到 实 际 问 题 中 ， 简 化 图 如 图 2 ， 搜 索 最 优 路 径 为p - v2 - v1 - v4 - Q ，该路径的均值为 17.77，标准差为 3.66。
  针对问题三，在时间相关性方面构造 Copula 函数和最大似然估计函数，利用 excel软件，得到从 v1 - v5 ，在7 : 00 ~ 8 : 00 堵塞时8 : 00 ~ 9 : 00 对其他路段的均值和标准差的影响。在空间相关性方面，构造 Moren 模型和空间自相关分析，得到在一定时间下，某个路段出现交通事故，对其他相关路段的影响。结论为第 8 路段的均值为 12，标准差为 3.6。
  针对问题四，赋予路段均值和方差的等权重，作为该路段的行驶参考时间，最终转化为 Dijkstra 算法，求得最优路径为 P - v1 - v4 - Q ，最优行驶时间为 13.65。本文逻辑严谨，切入点独到，综合运用多种模型及软件，结果可靠且多样化。

模型假设：

  1．假设每条路段行驶时间服从正态分布；
  2．假设每条路段行驶时间的均值和标准差；
  3．已知假设所有不确定因素对行驶时间的影响都可以用均值和标准差体现；

问题分析：

  对问题一的分析
  相比于传统最优路径，改良后的最优路径需要把现实中的不确定因素纳入考虑范围，对此我们将各路段行驶时间变量化，引入正态分布，首先将现实中的交通网络简化为一般网络，基于各路段的行驶时间服从正态分布的假设，利用正态分布可加性把每条路径上的多个路段整合为一个路段。然后利用卷积公式，给出每条路径的的正态密度函数，变形得出可靠性模型，并将相同概率下及时到达的路径中用时最短的路径定义为最优路径。

  对问题二的分析
  由于从起始点到终点道路的复杂性。由上我们已经给出不同路径给出最优路径的最优方法。故本题所要考虑的主要问题即为给出已知各路段的情况下，给出求出所有路径的一般算法，然后根据第一问结论，得出最优路径。

  对问题三的分析
对于路段的不确定性，由上第一问与第二问我们探讨知，我们给出了在只考虑一般道路状况下（此处道路交通状况不包括对行驶时间造成较大影响的情况）给出了一般最优路径的求解一般算法。对于问题三，我们主要将交通事故、恶劣天气、突发事件等考虑在内，并从时间相关性和空间相关性两个方面。并利用控制变量法，即在考虑该路段时间相关性时，不考虑空间相关性对其造成的影响。分析空间相关性时，不对时间相关性加以考虑。

  对问题四的分析
  由于从起点到终点每个路段都是随机的，从实际来看从起点到终点所需时间越短越好，但是有时不得不考虑图中的随机因素，既要考虑途中所耽搁的时间，如果我们将均值和方差去权重即反映了个人的行程偏好不同。

模型的建立与求解整体论文缩略图

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码：(代码和文档not free)

Clcf
Clear all;
Syms n1,n2 ,n3 ,n4,n5
A=load(‘data,txt’);
B=rref(A);
C=null(A)
b=B*[n1,n2,n3,n4,n5]+null(A);
put(‘b)’

X=load(‘data1,txt’); %各个导入不同的数据
X=x(:);
[mu,sigma]=normfit（x）;
hist(x);
figure;
histfit(X);

p=[0 0.07 0.13 0.18 0.26 0.31 0.39 0.46 0.53 0.60 0.68 0.76 0.85 0.93 1.04 1.2 1.29 1.44 1.55 1.65]
n=length(up)
x=1:n
for i=1:n
t1(i)=33+up(i)*1
t2(i)=30+up(i)*15
end
plot(x,t1,'*')
hold on
plot(x,t2,'b+')
xlabel('p 分位数')
ylabel('条件保证所需时间')
title('不同路径的时间')
legend('快速路','城区路','Location','best')

全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可