研究生数学建模竞赛优秀论文选《行车时间估计和最做路线选择A》24页.docx
《研究生数学建模竞赛优秀论文选《行车时间估计和最做路线选择A》24页.docx》由会员分享，可在线阅读，更多相关《研究生数学建模竞赛优秀论文选《行车时间估计和最做路线选择A》24页.docx（37页珍藏版）》请在冰点文库上搜索。
研究生数学建模竞赛优秀论文选《行车时间估计和最做路线选择A》24页
全国第二届部分高校研究生数模竞赛
题目行车时间估计和最优路线选择（A）
摘要：
本题是解决公路车辆行驶时间预测和最优路线选择的问题。
首先，通过对SanAntonio某段公路一段监测数据进行分析，结合实际情况，提出了两种行车时间估计模型：
模型一仅采用各测点的行车速度信息，在单位观测时间内，所有通过测段车辆速度为相邻两测点速度的平均值，车辆行驶时间为测段长度与均值速度的比值，为研究各个测段行驶时间的相互影响，计算了各测段行驶时间向量的相关系数矩阵；模型二综合考虑了观测速度和流量，车辆通过测段的时间由自由通过时间和滞留时间两部分组成。
分别采用两种模型对该观测段行车时间进行估测，两种模型计算结果基本吻合，并给出了基于概率的行车时间估计区间；对两种模型进行评价，提出了两种模型各自的适用条件及影响因素。
然后，由于各个路段行驶时间的不确定性，现有的交通系统不能准确的估计行驶时间并选择最优路线。
为考虑各种路况特征（单个路段平均行驶时间，路段长度和行驶时间方差）对总行车时间的影响，引入广义行车费用，给定各个路况特征对行车时间的影响权重值，进而计算出各个路段的广义行车费用，最优路线即为广义行车总费用最少的路线。
特别的，当路段长度的权重值为1（仅考虑距离影响）时，采用Dijkstra算法编制了VB程序，可以获得任意两点间的最优路线。
另外，结合现有系统提供的信息，根据行车时间估计模型一，可以得到各个路段行驶时间向量的协方差矩阵，进而求出任一行驶路线的平均行驶时间及其方差；比较所有行驶路线的平均行驶时间，得出最优路线，因此，考虑各个路段行驶时间相互影响时，该方法适用于节点较少的最优路线选择问题。
参赛密码
（由组委会填写）
关键词：
行车时间滞留量Dijkstra算法广义费用相关性最优路线
参赛队号1356
I：
行车时间估计模型
一、问题描述：
公路行车时间估计对于现代交通运输起着重要的作用。
为了进行行车时间估计，在美国SanAntonio的公路上，安装探测装置以测定车流量和车速。
探测器每天24小时进行数据采集，每2分钟采样一次，每次采样时间为20秒，每一次采样可以得出当前的车流量和车速，根据某一天下午3：
40至傍晚6：
58的测量数据，对以下问题分析研究：
1、分析公路的交通特征，即车行通畅情况和交通拥堵情况。
2、给出车辆行驶时间的预测模型。
二、问题分析：
636m417m522m475m
traveldirection
Detector1Detector2Detector3Detector4Detector5
图1测点布置图
根据直观了解，如果所有车辆在某一测段内行驶速度变化不大，则相邻两个探测器的测得的速度差值也不会大，因而可以认为探测器所测得的速度值，就是该区间内每辆车的行驶速度，那么行车时间应为该段距离与此速度的商，据此，我们提出第一种车辆行驶时间估计模型，此模型仅与探测器所测得的速度有关。
另外，对于某个测段，如果进入该区间的车辆多于驶出该区间的车辆，其结果就是造成该测段内车辆拥堵，影响正常行驶，则部分车辆将在区间内“耽搁”一些时间，根据这一个实际情况，我们建立了第二种车辆行驶时间估计模型，此模型中考虑了交通流量的影响。
三、模型假设、建立与求解
（一）第一种行车时间估计模型
1、假设
（1）在各路段中车辆单向行驶。
（2）测点在20秒内的行车状况可以代表2分钟内的行车状况。
（3）每辆车在两测点间的行驶速度为进入点速度和驶出点处速度的平均值，即：
v=1（v
2i
+
vj）
（1）
其中下标i表示车辆进入处测点位置，j表示车辆离开处测点位置。
（4）车辆在时刻tn通过各个测段的行驶时间T（Xi,j,tn）服从正态分布。
2、模型建立
（1）基本单元模型
车辆通过lij的时间为：
图2基本单元模型
T=lij
Vv
=2lij
vi+vj
（2）
式中lij表示两测点之间的距离，vi，vj分别表示驶入测点i和驶出测点j处的行车速度。
（2）实用计算模型
根据基本单元模型，可得出tn时刻Xi,j测段的行车时间为：
T（X,t）=
2l（Xi,j）
（3）（3）
Vi,jn
v（Xi
tn）+v（X
j,tn）
式中i,j——分别表示车辆进入点和车辆驶出点；
Xi,j——表示相邻两探测器间的测量段；
l（Xi,j）——表示Xi,j测段的长度；
v（Xi,tn）——表示tn时刻，车辆进入Xi,j测段时的速度；
v（Xj,tn）——表示tn时刻，车辆驶出Xi,j测段时的速度。
则车辆通过Xi,j测段的平均时间为：
TV（X
i,j）=
N
∑TV（Xi,j,tn）
n=1
N
（4）（4）
式中N表示该测段测量数据个数。
3、模型求解
表1各测点行车速度（单位：
mile/h）
tn
v（X1,tn）
v（X2,tn）
v（X3,tn）
v（X4,tn）
v（X5,tn）
03:
40:
07PM
57
54
62
20
58
03:
42:
07PM
62
68
63
21
59
……
……
……
……
……
……
06:
58:
07PM
64
68
57
36
64
表2测段间距（单位：
m）
l（X1,2）
l（X2,3）
l（X3,4）
l（X4,5）
全程
636
417
522
475
2050
把表1和表2中的数据代入（3）、（4）式，得到各测段行车时间和全程行车时间，结果如下表：
表3行车时间及标准差
X1,2
X2,3
X3,4
X4,5
全程
TV（Xi,j）（sec）
26.93
26.71
61.55
52.8
167.95
标准差S（sec）
8.92
40.52
106.84
61.02
165.5
对于不同时刻各测段行车时间和全程（包括四个测段）行车时间，计算结果如图4、图5所示：
650
600
550
500
450
400
350
300
250
200
150
100
50
0
-50
t
04:
18:
07PM04:
58:
07PM05:
44:
07PM06:
24:
07PM--
n
图4不同时刻各测段的行车时间
1000
800
600
400
200
0
t
04:
18:
07PM04:
58:
07PM05:
44:
07PM06:
24:
07PM--
n
图5不同时刻全程的行车时间
4、结果分析及评价
（1）相关性分析
考虑各个测段行驶时间存在相互影响，用软件Matlab求出四个测段行车时间向量
[TV
（Xi,j
t1）
TV（X
i,j
t2
）TV
（Xi,j
tN
）]T的协方差，协方差矩阵为：
⎡0.0080
4⎢
⎢0.0310
C=10⨯
⎢0.0734
⎣
⎢0.0036
0.0310
0.1642
0.3551
0.044
0.0734
0.3551
1.1420
0.0583
0.0036⎤
⎥
0.0044⎥
0.0583⎥
⎥
0.3723⎦
用函数CORRCOEF（X）函数求得四个测段行车时间的相关系数，其相关系数矩阵
为：
⎡1.0000
⎢
⎢0.8589
CF=
⎢0.7703
⎢0.0662
0.8589
1.0000
0.8203
0.0177
0.7703
0.8203
1.0000
0.0895
0.0662⎤
⎥
0.0177⎥
0.0895⎥
1.0000⎥
矩阵CF中的元素CF，其中CF=
Cij。
ijij
由相关函数矩阵可以看出，TV（X1,2）与TV（X2,3）、TV（X3,4）的相关系数分别为0.8589
和0.7703，说明TV（X1,2）与TV（X2,3）、TV（X3,4）之间相互影响程度较大；而TV（X4,5）与
TV（X1,2）、TV（X2,3）、TV（X3,4）的相关系数则分别为0.0662、0.0177、0.0859，其值均较小，这说明TV（X4,5）对TV（X1,2）、TV（X2,3）、TV（X3,4）的影响较小。
四个测段的行车时间
中，最大相关系数0.8589出现在TV（X1,2）与TV（X2,3）之间，说明该两测段行车时间的相关程度最大，在进行行车时间评估时应对此重点进行考虑。
（3）模型评价及建议
从图4、图5可以看出，在特定交通时段内，其行车时间明显高于其它时段的行车时间；另一方面，由表3计算结果也看出，如果对整个观测时段得到的全部数据一起进行统计分析，其均值标准差S过大。
故结合实际情况，建议将交通时段分成两部分，交通高峰期和非交通高峰期。
对图4、图5进行观测分析，把05:
15PM~06:
25PM定为交通高峰期，其余时间定为非交通高峰期。
200
150
100
50
0
-50
650
600
550
500
450
400
350
300
250
200
150
100
50
0
-50
-100
-150
-200
03:
58:
07P04M:
18:
07P04M:
38:
07P04M:
58:
07P06M:
28:
07P06M:
48:
07PM--
t
n
图5非高峰期各测段的行车时间
t
05:
24:
07P0M5:
40:
07P0M5:
50:
07P0M6:
00:
07P0M6:
10:
07P0M6:
20:
07PM--
n
图6非高峰期各测段的行车时间
表4高峰期和非高峰期各测段行车时间和全程行车时间
X1,2
X2,3
X3,4
X4,5
全程
非高峰期
TV（Xi,j）（sec）
23.5
14.8
24.1
27.2
89.5
标准差S（sec）
1.0
0.7
5.9
11.2
17.0
高峰期
TV（Xi,j）（sec）
32.5
44.2
108.0
108.4
293.0
标准差S（sec）
12.0
60.0
115.1
84.6
222.1
在非高峰期交通时段，行车时间按（μ-2σ,μ+2σ）进行估计，其中μ为均值，σ为
方差，则从第1测点到第5测点间的行车时间的估计区间（55.5秒，129.5秒），保证概率为95.44%。
在高峰期交通时段，第1测点到第5测点间行车时间数据离散性较大，给出行车时间的预测区间意义不大，故只给出平均行车时间：
293秒。
（二）第二种时间估计模型
1、模型假设
（1）在各路段中车辆单向行驶。
（2）测点在20秒内的行车状况可以代表2分钟内的行车状况。
Q（Xi,tn）=6⨯q（Xi,tn）
，Q（Xj,tn）=6⨯q（Xj,tn）
（5）
式中q（Xi,tn）——20秒内进入测段Xi,j的车辆数；
q（Xj,tn）——20秒内驶出测段Xi,j的车辆数；
Q（Xi,tn）——120秒内进入测段Xi,j的车辆数；
Q（Xj,tn）——120秒内驶出测段Xi,j的车辆数。
（3）车辆在测段间的行驶时间为自由通过时间TF和滞留时间TC的代数和，且TF和TC不相关，即：
TT=TF+TC
（6）
（4）车辆自由通过某测段的速度vf（Xi,j）为两测点间所测得的平均行车速度最大值，即：
vf（X
i,j
）=Max{v（Xi,tn）+v（Xj,tn）,∀n=1,2,N}
2
（7）
（5）车辆在某测段内的滞留时间TC只与该测段内的滞留量有关。
（6）滞留量不能为负，当进入车辆数小于驶出数量时，认为没有滞留车辆，滞留量为零。
2、模型建立
（1）自由通过时间计算模型
根据假设（4），车辆在Xi,j测段的自由通过时间为：
T（X
）=l（Xi,j）
（8）
Fi,j
vf（X
i,j）
（2）滞留时间模型
1）滞留时间基本模型
车流方向
ij
图7测段内车辆滞留量图
Qi表示2分钟内进入测点i的车辆数，Qj表示2分钟内驶出测点j的车辆数，则Ki,j
表示该2分钟内滞留在Xi,j段内的车辆数，根据假设（6），车辆滞留量不能为负，所以
对Ki,j定义如下：
⎧Qi-Qj
Qi-Qj>0
Ki,j=⎨
⎩0
Qi-Qj≤0
（9）
从统计意义上来讲，滞留在Xi,j测段内的车辆都被“耽搁”2分钟，则在Xi,j内，
C
由于交通拥堵“耽搁”的总时间量为T'
=∆t⨯K
i,j
，其中∆t为2分钟，即120秒。
对于
“通过”该测段的每辆车来说，在该测段因为滞留而被“耽搁”的平均时间为：
2）滞留时间实用计算模型
'
T
TC=C
Qj
=∆t⨯Ki,j
Qj
（10）
基本模型中Ki,j没有考虑tn-1时刻滞留的车辆在tn时刻影响，如果用tn-1时刻滞留量与tn时刻车辆滞留量两者的平均值作为在Xi,j测段内在tn时刻的车辆滞留量，更为合理。
故将Ki,j修正为Ki',j：
K'（X
i,j
tn
）=K（Xi,j,tn-1）+K（Xi,j,tn）
2
⎧Q（Xi,tn）-Q（Xj,tn）
Q（Xi,tn）-Q（Xj,tn）>0
（11）
K（Xi,j,tn）=⎨
⎩0
Q（Xi
tn
）-Q（X
j,tn
）≤0
（12）
由（10）、（11）式可以得出在测段Xi,j内的滞留时间：
T（X
t）=∆t⋅K'（Xi,j,tn）=K（Xi,j,tn-1）+K（Xi,j,tn）⋅∆t
（13）
Ci,jn
Q（X
j,tn）
2Q（X
j,tn）
式中TC（Xi,j,tn）——在tn时间段内每辆通过车辆在测段Xi,j上的滞留时间；
∆t——两次测量的时间间隔，为120秒。
则车辆通过Xi,j段的平均滞留时间为：
TC（X
i,j）=
N
∑TC（Xi,j,tn）
n=1
N
（14）
式中N表示该测段测量数据个数。
3、模型求解
表6各测点行车速度和车流量
Detector1
Detector2
Detector3
Detector4
Detector5
tn
Speed
（mile/h）
Flow
Speed
（mile/h）
Flow
Speed
（mile/h）
Flow
speed
（mile/h）
Flow
Speed
（mile/h）
Flow
03:
40:
07PM
57
10
54
9.7
62
8.9
20
10.7
58
5.9
03:
42:
07PM
62
9.5
68
11.4
63
13.6
21
10
59
12.2
……
……
……
……
……
……
……
……
……
……
……
06:
58:
07PM
64
4.2
68
3.9
57
4.5
36
4.4
64
4.1
Speed：
v（Xi,tn）Flow：
q（Xi,tn）
把表6数据代入（5）、（12）、（13）、（14）式，计算滞留时间TC（Xi,j）；代入（7）、
（8）式计算自由通过时间TF（Xi,j）；把TC（Xi,j），TF（Xi,j）的计算值代入（6）式得到行
车总时间TT（Xi,j）。
TT（Xi,j）计算结果如表7所示，按照该模型计算，走完全程需要的平均时间估计值为166.95秒。
表7探测器所测各测点行车速度和车流量
X1,2
X2,3
X3,4
X4,5
全程
l（Xi,j）（m）
636
417
522
475
2050
vf（Xi,j）（m/s）
30.62
31.51
29.95
29.27
—
TF（Xi,j）（s）
20.77
13.23
17.43
16.23
67.66
TC（Xi,j）（s）
31.63
20.61
35.99
11.06
99.29
TT（Xi,j）（s）
52.40
33.84
53.42
27.29
166.95
四、两种行车时间估计模型评价与改进
第一种时间估计模型和第二时间估计模型都假设了20秒内的行车状况能代表2分
钟内的行车状况，在第一模型中，只考虑了行车速度影响因素，而此行车速度为20秒内的行车速度，显然，如果增加观测时间，这个模型的精度将提高。
对于第二模型，考虑了行车速度和流量的影响，在这一假设条件下，降低了流量的测量精度。
表8两种模型行车时间计算结果比较
T（X1,2）
T（X2,3）
T（X3,4）
T（X4,5）
全程时间
第一种模型
26.93
26.71
61.55
52.8
167.95
第二种模型
52.40
33.84
53.42
27.29
166.95
第一种时间估计模型计算的全程行车时间为167.95秒，第二种时间估计模型计算的全程时间预计值为166.95秒，两者计算值基本相同；但是，由表8可以看出，对于各个测量段，所计算出的行车时间估计值有一定差别。
从全程2.050公里来看，可以认为流量对行车时间估计没有影响，但是对于单个测段，流量对行车时间的估计值有一定影响。
第一种模型仅考虑了测点的行车速度，适用于距离较短、交通状况良好的情况下的行车时间估计，第二种模型综合考虑了最大行车速度和流量对行车时间的影响，当各测段内流量发生变化时，认为交通状况变化（例如：
交通拥堵）产生车辆滞留，适用于测段距离较长的路段行车时间估计。
但该模型为一种简化模型，它的第（6）个假设认为滞留量不能为负，这一假设有一定的局限性，实际情况应考虑观测区间长度和观测时间间隔长度的影响，当测段长度比较大，或者观测时间间隔比较小时，滞留量可以为负，对于这类情况该模型有待改进。
II&III：
最优路线的选择和行驶时间评估模型
一、问题描述
由于各个路段行驶时间的不确定性，SanAntonio现有的交通系统在提供最优路线和可靠的行驶时间估计时存在缺陷。
现有的交通系统中的路况信息包括：
路段正常行驶，路段拥堵，路段严重拥堵，路段在施工（但车辆运行情况不明），实时信息牌（某些信息牌在某些时刻没有路况信息显示）在各个路段的分布情况。
这些路况信息每隔5分钟更新一次，用鼠标点击某一路段，还可以获得该路段的运行速度信息。
由于各个路段行驶时间的不确定性，现有的系统不能准确的给出最优路线和可靠的时间估计值。
因此，需要给出各路段行驶时间不确定性的衡量指标，并在此基础上建立合理的时间评估模型和最优路线选择模型。
二、问题分析
通常，在每条可供选择的路线的特征确定之后，最优路线的选择还要根据司机的行驶习惯来确定。
也就是说，最优路线的确定要满足多目标的约束（比如行驶时间、路程、是否堵车等各个方面的因素），还要满足司机在选择路线时的个人习惯。
这样，建立每一种类型的司机行驶时间（司机从出发地到达目的地的时间消耗）的数学达式是比较困难的，而对这样一个多因素影响下的行驶时间函数，其最优解的确定变成了求解NP问题，这也是相当困难的。
根据以上分析，最优路线选择时需要考虑的问题包括：
1、考虑各种因素的影响，直接计算出发地到目的地之间的时间（NP问题）计算耗时很长，不适合大规模交通系统使用。
2、个别路段不能提供相关路况信息或信息不准确。
4、不同司机选择最优路线的决策方法不同。
三、模型假设、建立与求解
（一）不考虑各个路段行驶时间的相关性
1、假设
（1）各个路段的行驶时间T都服从正态分布。
（2）假定利用现有系统可以获得的各个路段的路况，采用问题I中提出的方法，可以得到在时刻t通过各个路段的平均时间T（t），以及行驶时间的均方差σT（t）。
（3）各个路段的平均行驶时间T（t），各个路段行驶时间的方差σT（t）都是相互独立的随机变量。
（4）司机对各种路况特征的使用偏好为已知。
（5）以各个路段的平均行驶时间T（t），行驶时间的方差σT（t）和路段的长度作为表示路段特征的指标。
（6）在司机通过任意到达目的地路线的时间∆t内，各个路段的路况特征指标不变。
（7）在各路段中车辆单向行驶。
2、建立模型
根据以上假设和分析，可以建立第i个路段上广义行驶费用的线性方程：
3
Yi=∑wjZij（t）=w1Zi1（t）+w2Zi2（t）+w3Zi3（t）
j=1
式中：
wj表示路段第j个特征指标在广义行驶费用中占的权重；
（15）
Zij（t）表示t时刻第i个路段上第j个特征指标的标准化值（即第i个路段第j个特征值与所有路段第j个特征值最大值的比值），根据假设（6），Zij（t）=Zij（t+∆t）；
Zi1（t）表示t时刻第i
升级会员 