数学建模最优路径设计

2015高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名

参赛队员(打印并签名) ：1

2

指导教师或指导教师组负责人(打印并签名)：

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）

日期：2015年7 月27 日赛区评阅编号（由赛区组委会评阅前进行编号）：

2015高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

从工业学院到西南交通大学最优路径设计

摘要

本文对现在生活中行车时间的不确定性进行了分析，并给出了最优路径的定义，即：行车所需期望时间最短且该路段行车时间的标准差最小。在将时间期望值和时间标准差值两个决策变量合成为一个决策变量时，为消除不同指标带来的不可公度性，我们对这两个指标进行了无量纲化。

对于问题一，建立双目标优化模型，给出最优路径的定义和数学表达式。将这两个目标相加合成单目标。利用MATLAB编程求解，将所建模型应用到例子中，得出的结论是：选择道路A。

对于问题二，在问题一定义的最优路径的基础上，建立图论模型，应用Dijkstra算法，利用MATLAB编程，得出最优路径选择结果为：工业学院→C→K →G→西南交通大学。

对与问题三，结合时间和空间上的相关性，采集足够多的时刻的车流速度，用神经网络算法可以拟合出该条路时刻关于车流速度的函数，建立图论模型分析时间和空间上的相关性。

关键词：多目标优化图论模型Dijkstra算法

1、问题重述

随着我国交通运输事业的迅速发展，交通拥挤和事故正越来越严重的困扰着城市交通。在复杂的交通环境下，寻找一条可靠、快速、安全的最优路径，已成为所有驾驶员的共识。

传统最优路径问题的研究大多是基于“理想”交通状况下分析的，景点的最优路径算法都是假设每段路的行驶时间是确定的。但是由于在现实生活中，行车会受到很多不确定性因素的影响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。基于这种不确定性，讨论以下问题：

1.建立数学模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式。并将此模型运用到图1例子中会选哪条路。

2.根据第一问的定义，设计算法搜索最优路径，并将该算法应用到具体交通网络中，验证算法的有效性。

3.交通路段之间的行驶时间的相关性分析。时间上的相关性，对于相同路段不同时间段的相关性；空间上的相关性，相同时间段不同路段的相关性。或者将时间和空间上的相关性综合起来考虑。

2、模型假设

1.假设题目所给数据是在大量实验统计后得到的，数据真实可靠；

2.假设题目给出数据所用的样本容量大小相同；

3.假设从起点到到终点时间消耗不超过1小时；

4.假设同一路段上下行的期望时间和标准差时间相同；

5.假设各不同路段的期望时间和标准差时间相对独立。

3、变量说明

T：表示从起点（工业学院）到终点（西南交通大学）期望时间；

σ：表示从起点（工业学院）到终点（西南交通大学）标准差时间；

i x ：x 类指标中的第i 个指标；

x ：x 类指标的平均值； i x '：i x 无量纲化后的指标；

λ：指标权重，改变期望时间和标准差时间重要性的系数；

't ：t 无量纲化后的指标；

σ'：σ无量纲化后的指标；

w ：期望时间和标准差时间两个指标合成的指标；

V ：顶点集，即题图给出的A~K 的点； E ：无向弧集；

T ：无向弧上的期望时间； S ：无向弧上的标准差时间； ok t :表示从起点到终点期望时间；

ij x :表示0，1变量，ij x 取1时，表示所选路径经过了节点i 到节点j 的路段；

ij x 取0时，表示所选路径没有经过节点i 到节点j 的路段。

σok ：从起点到终点标准差时间，其中0表示起点位置标号，k 表示终点位置标号； ij

y ：

是第i 种指标的第j 个量无量纲化后的量;

ij x ：第i 种指标的第j 个量;

i x 表示第i 种指标的平均数; ij t :从第i 个节点到第j 个节点的期望时间;

σij :从第i 个节点到第j 个节点的标准差时间;

ij

t ':ij t 无量纲化后的量;

σ'ij

:σij 无量纲化后的量; t :所有的路段的期望时间平均值; σ:所有的路段的标准差时间平均值; ij w :由期望时间和标准差时间两个指标合成的指标。

()ij u d ：

第i 个节点到第j 个节点的那段街的关于d 时刻的函数值，即速度。

ok T ：表示起点0到j 点的最短消耗时间。

4、模型准备

4.1对最优路径的理解

影响实际问题的因素很多，要解决实际问题就要建立适当的数学模型，即要把建模对象所涉及的次要因素忽略掉，否则所得模型会因为结构太复杂而失去可解性同时又不能把与实质相关的因素忽略掉，而造成所得模型因为不能足够正确反映实际情况而失去可靠性。因此需要对实际问题进行抽象、简化、确定变量和参数，并应用某些“规律”建立起变量、参数间确定的数学模型。

影响路线选择的因素很多，譬如瞬时车流量、是否有交通事故、车辆状况等，而实际要解决的是从工业学院到西南交通大学的时间最省路径，因此车流量和路径长度成为影响解决本问题的主要因素，而是否有交通事故发生和车辆状况等次要因素均可忽略掉。

所以最优路径可定义为：实际行车路径所需期望时间最短且该路径行车时间的总标准差最小。

5、模型的建立与求解

5.1问题1模型的建立与求解

5.1.1建模思路

问题1要求给出在不确定条件下车辆从起点到终点最优路径的定义和数学表达式并将此模型应用于例子中，说明选择哪条路。建立双目标优化模型，再建立优化模型，将两个目标综合起来考虑，使之变为一个目标。对于问题一和问题二我们在不考虑时间相关性和空间相关性的情况下，我们假设各路段行车的标准差时间相互独立，由概率的基础知识可以得知，多个随机变量相互独立，多个随机变量和的标准差就等于各自标准差的和。所以在解决问题一和问题二的时候，在假设标准差时间是相互独立的情况下，我们将各标准差时间相加作为和的标准差是合理的处理方式。

5.1.2模型建立

最优路径的定义：行车所需期望时间最短且该路段行车时间的标准差最小，考虑建立双目标决策：

目标—：总的期望时间最短，即：

min T(1) t表示从起点到终点期望时间。

目标二：时间波动要小，即要求这个路径的总标准差要小。

minσ(2) σ表示从起点到终点标准差时间。

5.1.3模型求解

对于多目标，这里用相加合成为单目标，在这之前要进行无量纲化，这里用

均值法无量纲化法，公式如下1????

：

'=

i

i x x x

(3)

i x 是x 类指标中的第i 个指标。x 是x 类指标的平均值，i x '是i x 无量纲化后的指标。

经过无量纲后，就可以转换成单目标。

()1λσλ''=+-w t

(4)

这里λ是指标权重，改变期望时间和标准差时间重要性的系数，对于不同的人看重的不同，所以这里λ分别取0.2,0.5和0.8。σ'是σ无量纲化后的指标，

't 是t 无量纲化后的指标，w 是由期望时间和标准差时间两个指标合成的指标。

合成的单目标就为：

min w (5)

λ取0.2时，结果：选择道路A. λ取0.5时，结果：选择道路A. λ取0.8时，结果：选择道路B.

5.2问题2模型的建立与求解

5.2.1建模建立

为了可以尽可能快速到达目的地，所以要求这条路径总期望时间t 要短，又考虑到不确定因素的影响，所以要求时间的波动最小，即这条路径标准差σ要小。 目标—：总的期望时间最短，即：

min ;ok t

(6)

ok t 表示从起点到终点期望时间，o 表示起点位置标号，k 表示终点位置标

号。

=∑∑N N

ok ij ij i

j

t t x

(7)

ij t 表示节点i 到节点j 的路段期望时间，ij x 表示0，1变量，ij x 取1时，表示所选路径经过了节点i 到节点j 的路段；ij x 取0时，表示所选路径没有经过节点i 到节点j 的路段。

目标二：时间波动要小，即要求这个路径的标准差要小。

min ;σok

(8)

σok 表示从起点到终点标准差时间，其中o 表示起点位置标号，k 表示终点

位置标号。

σσ=∑∑N N

ok ij ij i

j

x

(9)

这里σij 表示节点i 到节点j 的路段标准差时间，ij x 表示0，1变量，ij x 取1时，表示所选路径经过了节点i 到节点j 的路段；ij x 取0时，表示所选路径没有经过节点i 到节点j 的路段。

约束一：每个节点最多可以进入一次且最多只可以出去一次。

1N

ij

i

x

≤∑ (10)

1N

ij

j

x

≤∑ (11)

约束二：由于这里的路径不必要形成一个圈，所以起点只能出去一次，即进入零次，终点只

能进入一次，即出去零次。

0N

io

i

x

=∑ (12)

0N

kj

j

x

=∑ (13)

这里o 表示起点位置标号，k 表示终点位置标号，io x 表示从第i 个节点是否到

起点o 的0,1变量，io x 取0时表示第i 个节点不到起点o ，io x 取1时表示第i 个节点要到起点o ，kj x 表示从终点k 是否到第j 个节点的0,1变量，kj x 取0时表示从终点k 不到第j 个节点，kj x 取1时表示从终点k 要到第j 个节点。

综上： min ;ok t

(14) =∑∑N N

ok ij ij i

j

t t x

(15) min ;σok

(16)

σσ=∑∑N N

ok ij ij i

j

x

(17)

11..0

0N

ij i N

ij j

N

io

i N

kj j x x s t x x ?≤???≤????=???=??

∑∑∑∑ (18)

5.2.2模型优化

对于多目标问题难以求解，通过一定关系把多目标合成一单目标，在这之前，先对这两个指标进行无量纲化，采用均值法[]

1来无量纲化。即：

=

ij ij i

x y x (19)

ij y 是第i 种指标的第j 个量无量纲化后的量，ij x 表示第i 种指标的第j 个

量，i x 表示第i 种指标的平均数。经过以上无量化公式可对t ，s 无量纲化，即：

'=ij ij

t t t

(20)

σσσ

'=ij ij

(21)

ij t 是表示从第i 个节点到第j 个节点的期望时间，σij 是表示从第i 个节点到

第j 个节点的标准差时间，ij

t '是ij t 无量纲化后的量，σ'ij 是σij 无量纲化后的量，t 是所有的路段的期望时间平均值，σ是所有的路段的标准差时间平均值。

经过无量纲化后，就可把双目标合成单目标，即： ()1λσλ''=+-ij ij

ij w t (22)

这里λ是指标权重，改变期望时间和标准差时间重要性的系数，可根据不同

人的需求，λ取不同的值。ij w 是由期望时间和标准差时间两个指标合成的指标。 合成的单目标即为：

min ;ok w

(23)

这里的ok w ，其中o 表示起点位置标号，k 表示终点位置标号，ok w 表示从起点到终点合成指标指数，要求最小。

=∑∑N N

ok ij ij i

j

w w x

(24)

这里ok w 表示从起点o 到节点k 的最短标准差时间，ij w 表示从第i 个节点到第

j 个节点的路段时间的标准差。

综上：

min ;ok w

(25)

=∑∑N N

ok ij ij i

j

w w x

(26)

5.2.3模型求解

这里是从工业学院到西南交通大学，为了方便描述我们对地图上的节点标序号（见图1）

图1 路线地图简图

根据图1所示，即求0k w 最小权，节点o （工业学院）到节点k （西南交通大学）的最小权。

我们用图论模型求0k w 最小值，即：给定一个非空的简单无向网络图

G (,,)=V E W ，其中：V 为顶点集，()12

,n V v v v =；E 为有向弧集，

()()()

{

}1223,,,,

,,=i j E v v v v v v ，W 为有向弧上的权值，即合成最优指标

1111ij W w ???=??，这里就可以用Dijkstr 算法求W 的最小权值。

下面计算权1111ij W w ???=??的邻接矩阵，标准差1111ij σσ???=??和期望时间

1111ij T t ???=??的邻接矩阵。经过公式无量纲化得σ'ij

和'ij t 则可由下面公式（27）计算出1111ij W w ???=??的邻接矩阵。

()1λσλ''=+-ij ij

ij w t (27)

这里λ是权重，表示决策者在标准差σ'ij

和期望时间'ij t 更看重那一方面。对

于不同的人看重的不同，所以这里λ分别取0.2,0.5和0.8。

即为最优路线。

用matlab 程序（见附件1）计算出结果：

λ为0.5时，结果：工业学院→C →K →G →西南交通大学。

5.3问题3模型的建立与求解 5.3.1建模思路

根据题的要求，结合时间和空间上的相关性考虑。采集每条路的车流速度。对于每一条路，采集足够多的时刻的车流速度，用神经网络算法可以拟合出该条路时刻关于车流速度的函数。同理，拟合出每条路的时刻—车流速度函数图，可记着()ij u d ，表示第i 个节点到第j 个节点的那段路的关于时刻d 速度函数图。这样，根据拟合结果，就可以算出某条街某个时刻的车流速度。这样就可以根据车流速度计算实时最省时间路线。 5.3.2建模建立

根据历史数据，时间上，根据对确定的一条路，对每一天的车流速度每十分钟统计一次的数据用神经网络算法可以拟合出时刻关于车流速度的函图，

()=ij u f d

(28)

()ij u d 是第i 个节点到第j 个节点的那段街的关于d 时刻的函数值，即速度。

d 是出发时刻距00:00时刻的分钟数。对于空间上，统计了每条路的时间关于车流速度的函数图。那么可以算出第i 个节点到第j 个节点的消耗时间。

()

''=ij ij

ij s t u d (29)

ij

t ''是第i 个节点到第j 个节点的时间，ij s 是第i 个节点到第j 个节点的路程。

根据每段路的时间

N

N

ok ij

ij i

j T t x ''=∑∑ (30)

min ok T 表示示起点0到终点k 的最短消耗时间。ij t 表示从第i 个节点到第j 个节点

的路段时间。

min ok T

(31)

min ok T 表示示起点0到终点k 的最短消耗时间。

综上：

min ok T

(32)

N N

ok ij

ij i

j

T t x ''=∑∑ (33) ()

''=ij ij

ij s t u d

(34)

()=ij u f d

(35)

6、模型的分析、推广与改进

路线选择问题是一个多目标规划问题，其中最主要的目标是路线长度最短和道路的畅通概率最大。Dijkstra 算法是比较成熟的求非负权网络最短路问题的算法。

目前该模型还存在一些可以改进的方面。第一，不同路段的交通高峰到来的时间不一样，可以统计出不同路段在不同时刻交通畅通的概率，可以把时间为该模型的一个函数；第二，这个系统与当地交警支队的交通指挥系统相连接，可以为某些特种车辆服务，在某路段遇到交通堵塞，可以通过交通管理系统控制信号灯等方式，完成交通调度，以最短的时间保证比如执行紧急任务的特种车通过该路段。

7、参考文献

[1] 叶宗裕，关于多指标综合评价中指标正向化和无量纲化方法的选

择，https://www.sodocs.net/doc/3b2789907.html,/KCMS/detail/detail.aspx?QueryID=1&CurRec=1&recid=&filename=ZJTJ20030

4008&dbname=CJFD2003&dbcode=CJFQ&pr=&urlid=&yx=&v=MDAyODhZT1JuRnl2aFc3L 01QeWZmWkxHNEh0TE1xNDlGYklSOGVYMUx1eFlTN0RoMVQzcVRyV00xRnJDVVJMK2Y=

8、附录

附件1；

t=[0 0.826 inf inf inf inf 1.37 inf inf inf inf;0.826 0 1.661 inf inf inf inf inf inf inf inf;inf 1.661 0 1.242 inf 1.476 inf inf inf inf inf;inf inf 1.242 0 1.104 inf inf inf inf inf inf;inf inf inf 1.104 0 1.288 inf inf inf inf 2.44;inf inf 1.476 inf 1.288 0 1.586 inf 2.824 inf inf;1.37 inf inf inf inf 1.586 0 1.984 inf inf inf;inf inf inf inf inf inf 1.984 0 1.802 inf inf;inf inf inf inf inf 2.824 inf 1.802 0 0.94 inf;inf inf inf inf inf inf inf inf 0.94 0 0.55;inf inf inf inf 2.44 inf inf inf inf 0.55 0];

s=[0 0.5 inf inf inf inf 0.4 inf inf inf inf;0.5 0 1 inf inf inf inf inf inf inf inf;inf 1 0 0.5 inf 0.8 inf inf inf inf inf;inf inf 0.5 0 0.6 inf inf inf inf inf inf;inf inf inf 0.6 0 0.5 inf inf inf inf 0.7;inf inf 0.8 inf 0.5 0 0.6 inf 0.7 inf inf;0.4 inf inf inf inf 0.6 0 0.7 inf inf inf;inf inf inf inf inf inf 0.7 0 0.3 inf inf;inf inf inf inf inf 0.7 inf 0.3 0 0.3 inf;inf inf inf inf inf inf inf inf 0.3 0 0.16;inf inf inf inf 0.7 inf inf inf inf 0.16 0];

w=0.2*t+0.8*s;

[min,path]=dijkstra(w,1,10)

function [min,path]=dijkstra(w,start,terminal)

n=size(w,1); label(start)=0; f(start)=start;

for i=1:n

if i~=start

label(i)=inf;

end, end

s(1)=start; u=start;

while length(s)

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end, end

if ins==0

v=i;

if label(v)>(label(u)+w(u,v))

label(v)=(label(u)+w(u,v)); f(v)=u;

end

end

end

v1=0;

k=inf;

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end, end

if ins==0

v=i;

if k>label(v)

k=label(v); v1=v;

end, end, end

s(length(s)+1)=v1;

u=v1;

end

min=label(terminal); path(1)=terminal; i=1;

while path(i)~=start

path(i+1)=f(path(i));

i=i+1 ;

end

path(i)=start;

L=length(path);

path=path(L:-1:1);