交警巡平台的最优安排问题.doc

2011高教社杯校内大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写） C
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 重庆文理学院
参赛队员 (打印并签名) ：1. 曾秀华
2. 王纯净
3. 黄若萍
指导教师或指导教师组负责人 (打印并签名)：

日期： 2011 年 7 月 25 日

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

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

编 号 专 用 页

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

赛区评阅记录（可供赛区评阅时使用）：

评
阅
人

评
分

备
注

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

全国评阅编号（由全国组委会评阅前进行编号）：

交警巡平台的最优安排问题

摘要

本文研究了在规定的出警时间内能到达各个区域以及存在一些多发事区域的情况下，如何合理安排交警巡平台下的问题。
对于问题1，本文利用Floyd算法求出了最短路距离矩阵，在此基础上，本文以每个路口到与各个区域相连的路口，求出每个路口到最远区域的最长距离，与在规定出警时间内出警的最长距离分析比较，建立模型一，找出不能在A路口和M路口设立交警巡平台。
对于问题二，本文利用了问题1中的最短路距离矩阵，求出H路口到O路口是另外的路口到路口最远距离中的最短距离，且H路口到O路口的距离为90米，结合图和最短路距离矩阵，求出每个路口到最远区域的最短距离，与90米相比较建立模型二，依据模型二求出C路口、H路口和I路口设为交巡警平台到最远区域可以使出警至最远地块时间达到最短。
对于问题三，本文以在规定出警时间能到达最远区域、到（4）、（16）区域的距离之和最短和到各个区域最短距离之和最短这3个原则建立模型三，依据模型三，求出在H路口设立交警巡平台最好。

关键词：Floyd算法，最短距离，最优解，MATLAB，Excel,图论法

一、问题重述

在重庆市某街区设立交巡警平台,在设立交巡警平台时，常常要考虑能否在规定的出警时间能达到最远区域，那些区域是多发事区域等等众多因素，从而建立 设立交巡警平台的最优方案。
下图是该街区草图，街区内部从上到下有平行的5条路，从左到右有平行的7条路。路口处都标有字母，这些道路街区分成17个地块（1）2），…，（17）。路的宽度忽略不计，每段的长度可以从图中得知。例如，DE=20，又AG=30，所以EI=10。图中标数与实际比例为1：25，单位是米。

根据以往到达事发地点的出警时间分析，规定巡警出动规定从接到报警到达出事地点不得超过5分钟。这里假定：不论案件发生在地块内什么位置，警员到达出事地块的边缘，就算到达了出事地点。按照实际操作，进一步规定：在路上行使时间为出警时间，出警时间不得超过3分钟，又警车的车速恒为60千米/小时。问
（1）、哪些路口不能设为交巡警平台？
（2）、哪个路口设为交巡警平台可以使出警至最远地块时间达到最短？说明理由。
（3）、若地块（4）（16）是事件多发区，交巡警平台设在哪里好呢？根据实际情况提出“好”的原则，并根据原则给出答案。

二、模型假设

1、假设题中所给出的数据真实可靠。
2、假设在该街区的15个路口的任何地方都可设立交巡警平台。
3、假设巡警在出警的路上无任何障碍。
4、假设巡警接到报警后，马上出动，无时间损失。
5、假设不论案件发生在地块内什么位置，警员到达出事地块的边缘，就算到达了出事地点。
6、假设在分析问题1、2时，假设地块（1），（2），…，（17）出事的概率是相同的。
7、假设警车的车速恒为60千米/小时。

三、符号定义说明
：路口到路口的连接矩阵
：记录插入点的信息的矩阵
:：最短距离矩阵
：最短距离矩阵的行指标
：最短距离矩阵的列指标
：第几的个区域
：设立的交警巡平台到各个区域的最短距离中的最长距离
：设立的交警巡平台
：可设交警巡平台的路口到（4）区域的距离矩阵
：可设交警巡平台的路口到（16）区域距离矩阵
：可设交警巡平台的路口（16）区域的最短距离矩阵
：可设立的交警巡平台的路口到（4）、（16）区域的最短距离之和
：中的最小值

四、问题分析

1、 问题1的分析
问题1希望设计A、B、C、D、E、F、G、H、I、J、K、L、M、N、O这15个路口，那些路口不能设为交巡警平台的方案。属于图论模型问题。
根据图中给出的每段路的长度，求出各个路口间的距离，写出带权邻接矩阵，利用Floyd算法求出距离矩阵。
根据距离矩阵，求出A、B、C、D、E、F、G、H、I、J、K、L、M、N、O这15个路口中每个路口到其它路口距离的最长距离。
因为题中给出要求，在路上行使时间为出警时间，出警时间不得超过3分钟，又警车的车速恒为60千米/小时。所以很容易的计算出从交巡警平台到出警地点的距离不能超过3千米（），每个路口到其它路口的最长距离不能超过3千米，图中标数与实际比例为1：25（单位是米），所以根据图中的数据每个路口到其它路口的最长距离不能超过120米（）。
当求出哪些路口到其它路口的最长距离超过3千米，然后就知道这些路口可能不能设为交巡警平台，求出这些路口，然后结合图形和距离矩阵，看这些路口到图形中17个区域的最短距离中的最长距离是否超过3千米，若没有超过则可以设交巡警平台，若超过则不能设交巡警平台，从而就找出了哪些路口不能设交巡警平台，因此建立模型一。
2、 问题的2分析
问题2是希望找出可设立交警巡平台的路口到最远区域间的所花费的时间最短的路口，可转化为在问题1的基础上，让每个可设立交警巡平台的路口到最远区域的最短距离与问题1中最短距离矩阵中可设立交警巡平台的路口到达最远区域距离的最小值相比较，若大于它，这个路口不是所求解，若小于它，则求出该可设立交警巡平台的路口到最远区域的最短距离，最后比较小于这些最短距离，求得最优解。
3、问题3的分析
问题3是希望在知道（4）、（16）两个区域为多事区基础上，设计建立交警巡平台的最佳方案。
根据交警巡平台的设立原则，在规定的出警时间内能到达每个区域的基础上，交警巡平台应该离多事区最近。因此交警巡平台到达（4）、（16）这两个区域的距离之和最短，建立模型三。

五、模型的建立与求解

（一） 问题1模型的建立与求解
1、 Floyd算法简介[1]
Floyd算法是弗洛伊德（floyd）提出的一种解决每对节点之间最短路径问题的的算法。
算法的基本思想：直接在图的带权邻接矩阵中，用插入顶点的方法依次构造出v个矩阵D(1)、D(2)、…、D(v),使最后得到的矩阵D(v)为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
1.在邻接矩阵T中表示第i个区域到第j个区域之间的距离；
2.用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，，如果的距离变小，则=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，中包含了最短路径的信息。
关于本文具体问题的算法（算法程序见程序1）如下：
1.先根据题目所给的各个路口之间距离的数据为初始矩阵赋值，其中没有相连的路口距离赋给无穷大，且P(i,j)=0(i=j)。
2.进行迭代计算。对任意两点，若存在，使，则更新。
3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵S(i,j)。
2、模型一的建立
在上述最短路距离矩阵S(i,j)的基础上，分析这15个路口设为交巡警平台情况，建立模型一：
首先，在15个路口中任意选取一个路口设为交巡警平台
其次，交巡警平台到最远区域在规定时间里不能到达，则该路口不能设为交巡警平台，从而引入变量，表示交巡警平台到第个k区域最长距离
（k=1,2,…17）
最后，比较与120米的大小。
3、模型一的求解
依据模型一，并根据图中所给的数据，写出图中各路口距离表（距离表见附录中表1），并根据Floyd算法写出带权邻接矩阵（矩阵见附录中的矩阵1），利用MATLAB软件(程序见附录中程序2)求得最短路距离矩阵：
从最短路距离矩阵S中很容易看出A、D、F、L、M、O这6这路口可能不能设为交警巡平台。
在S矩阵中可以看出A路口到L路口的最短距离为130米（大于120米），从图中可以看出L路口与（10）、（14）、（15）这3个区域相连，并且9）区域与路口E相连，（14）区域与路口J相连，而（15）区域只与路口L相连，所以若在A路口设交警巡平台，在规定的出警时间内不能到达（15）
区域，因此A路口不能设交警巡平台。
在S矩阵中可以看出D路和F路口到每个路口最短距离的最长距离都是到M路口，最短距离为125米（大于120米），从图中可以看出与M路口与（11）、（12）、（16）这3个区域相连，并且（11）、（12）、（16）这3个区域分别与G路口、H路口、N路口相连，D路口和F路口到这3个路口的距离都小于120米，根据S矩阵和图可知，若在D路口或F路口设立交警巡平台，都能在规定的出警时间内到达每个区域，所以D路口和F路口都可以设为交警巡平台。
在S矩阵中可以看出L路口到A路口和M路口的最短距离分别为130米（大于120米）和125米（大于120米），从图中可以看出A路口与（1）、（5）、（6）区域相连，并且（1）、（5）、（6）这3个区域分别与B路口、G路口、H路口相连，L路口到这3个路口的距离都小于120米，而上面分析可以知L路口到与M路口相连的区域距离都小于120米，根据S矩阵和图可知，若在L路口设立交警巡平台，能在规定的出警时间内到达每个区域，所以L路口可以设为交警巡平台。
在S矩阵中可以看出M路口到D路口、F路口、M路口的最短距离都是125米，从图中可以看出D路口与（3）、（4）、（5）、（8）这4个区域相连，并且（4）
区域只与D路口相连，所以若在L路口设立交警巡平台，在规定出警时间内，不能到达（4）区域，即M路口不能设立交警巡平台。
在S矩阵中可以看出O路口到A路口的距离135米（大于120米），而到其他路口的距离都不大于120米，由上面分析可知，O路口到与A路口相连的区域都不大于120米。所以O路口可以设立交警巡平台。
综上所诉，在A路口和M路口不能设立交警巡平台。
（二）问题2模型的建立与求解
由第1题的分析得知A路口、L路口不能设为交巡警平台，只需考虑剩下的13个路口。由问题1的最短距离矩阵可知，可设交警巡平台的每个路口到所对应最远区域的的最短距离为90米。
若B路口南设置为交巡警平台，结合图和最短距离矩阵S可知，B路口到（14）区域的最短距离为95米（大于90米），所以B路口不可能成为最优解。
若C路口设置为交巡警平台，结合图和最短距离矩阵S可知，C路口到最远区域的最短距离是85米（小于90米），所以C路口有可能成为最优解。
若D路口设置为交巡警平台，结合图和最短距离矩阵S可知，D路口到（16）区域的最短距离为110米（大于90米），所以D路口不可能成为最优解。
若E路口设置为交巡警平台，结合图和最短距离矩阵S可知，E路口到最远区域的最短距离为90米（等于90米），所以E路口有可能成为最优解。
若F路口设置为交巡警平台，结合图和最短距离矩阵S可知，F路口到（1）区域的最短距离为95米（大于90米），所以F路口不可能成为最优解。
若G路口设置为交巡警平台，结合图和最短距离矩阵S可知，G路口到（4）区域的最短距离为100米（大于90米），所以G路口不可能成为最优解。
若H路口设置为交巡警平台，结合图和最短距离矩阵S可知，H路口到最远区域的最短距离为85米（小于90米），所以H路口有可能成为最优解。
若I路口设置为交巡警平台，结合图和最短距离矩阵S可知,I路口到最远区域的最短距离为85米（小于90米），所以I路口有可能成为最优解。
若J路口设置为交巡警平台，结合图和最短距离矩阵S可知，J路口到（1）区域的最远距离为95米（大于90米），所以J路口有可能成为最优解。
若K路口设置为交巡警平台，结合图和最短距离矩阵S可知，K路口到（1）区域的最短距离为105米（大于90米），所以K路口不可能成为最优解。
若L路口设置为交巡警平台，结合图和最短距离矩阵S可知，L路口到（1）区域的最短距离为115米（大于90米），所以L路口不可能成为最优解。
若N路口设置为交巡警平台，结合图和最短距离矩阵S可知，N路口到（4）区域的最短距离为110米（大于90米），所以N路口不可能成为最优解。
若O路口设置为交巡警平台，结合图和最短距离矩阵S可知，O路口到（1）区域的最短距离为120米（大于90米），所以O路口不可能成为最优解。
综上所述，C路口、E路口、H路口、I路口都有可能成为最优解。C路口、H路口、I路口到达最远区域的最短距离都为85米，而E路口到最远区域的最短距离为90米，所以最优解是C路口、H路口、I路口。
即C路口、H路口、I路口路口设为交巡警平台可以使出警至最远地块时间达到最短。
（三）问题3模型的建立与求解
1、模型三的建立
首先在第一题最短路距离矩阵S(i,j)的基础上，除了不能设立交警巡平台的A路口、M路口外，可以写出每个路口与（4）、（16）区域相连路口的最短距离矩阵。
其次，由于每个可设立交警巡平台的路口到（4）、（16）区域距离和最短，引入变（1，2，3....13 ）。
然后求出可设立交警巡平台的路口到（4）、（16）区域最短距离

最后，根据设立交警巡平台的原则，确立最优解。

2、模型三的求解
从图中可知，（4）区域只与D路口相连，（16）区域与M路口和N路口相连。
由S矩阵可以求出可设交警巡平台的路口到（4）区域的距离矩阵，到（16）区域距离矩阵
利用MATLAB（见程序2）可以算出（16）区域的最短距离矩阵

即=[110 110 110 110 150 125 110 110 130 150 170 110 130]
因为
所以Y=100米，即B路口、C路口、D路口、E路口、H路口、I路口、N路口到（4）、（16）这两个区域的距离这和最短为110米。
由2题可知C路口、H路口、I路口设为交巡警平台可以使出警至最远地块时间达到最短，因此按这个原则，C路口、H路口、I路口为优解。
根据设立交警巡平台到达每个区域距离之和最短这一原则，可最终确立最佳设立点。利用C路口、H路口、I路口到各个区域的最短距离表（见附录中的表2），用Excel可以算出这3个路口到达每个区域最短距离之和分别为770米、630米、635米。因为按照这个原则，最优解在H路口。

六、模型的评价与推广

1、模型的优点
（1） 模型结构简单，而且便于计算，当数据量很大时，此优势更加突出。
（2）本模型利用数学工具简化问题，简单易懂且较直观。
（3）结合权威资料，合理的分析处理数据，增加了模型的准确性。

2、模型的缺点
模型的影响因素过于单一化，使得结果与实际情况有些误差。比如说没有考虑每个区域的路况（街道是否经常堵车，街道的平坦度等等）。

3、改进方向
本文模型适合于区域较少的情况，当区域量十分庞大的时候，模型的误差变大，所以我们考虑到，对于区域量很大的情况，以区域密集度为决策量，选出密集度高的区域或多发事区域作为设立交警巡平台，在对交警巡平台被选点利用本文模型进行求解，这样使得问题变得简单化。
七、参考文献
【1】陈汝栋，于延荣编著. 数学模型与数学建模. 北京市：国防工业出版社, 2009.05.
【2】刘振鹏，罗文劼，石强编著. 数据结构. 北京市：中国铁道出版社, 2010.06第182页
【3】史荣昌，魏丰编著. 矩阵分析. 北京市：北京理工大学出版社, 2010.06第29页
【4】王海英，黄强，李传涛，褚宝增编著. 图论算法及其MATLAB实现. 北京市：北京航空航天大学出版社, 2010.01第14页

【5】刘广臣,宋美,董珍. 大学生数学建模竞赛策略的研究[J]. 高等数学研究, 2007, (03) .
【6】林华珍,周根贵. 求解最短路问题的一种优化矩阵算法[J]长江大学学报(自科版)理工卷, 2007,(04)
【7】聂桂根. MATLAB在测量数据处理中的应用[J]测绘通报, 2001,(02)

八、附录

表1 图中各路口距离表
区域号
区域号
距离(m)
A
B
15
A
C
45
A
D
70
A
G
30
A
M
55
B
C
30
B
D
55
B
H
30
B
N
55
C
D
25
D
E
20
D
I
30
E
F
20
E
I
10
F
K
10
G
H
15
G
I
70
G
J
80
G
K
90
G
L
100
G
M
25
H
I
55
H
J
65
H
K
75
H
L
85
H
N
25
I
J
10
I
K
20
I
L
30
J
K
10
J
L
20
J
O
25
K
L
10
M
N
15
M
O
80
N
O
65

表2、C路口、H路口、I路口到各个区域最短距离
路
口
区
域

C
H
I
(1)
30
30
85
(2)
0
30
55
(3)
0
60
30
(4)
25
85
30
(5)
45
15
70
(6)
30
0
55
(7)
0
0
0
(8)
25
65
10
(9)
45
55
0
(10)
65
75
20
(11)
75
15
70
(12)
60
0
55
(13)
55
0
0
(14)
65
65
10
(15)
85
85
30
(16)
85
25
80
(17)
85
25
25
总和
775
630
625

问题一的带权邻接矩阵

程序1
unction D=floyd(T)
n=size(T,1);
D=T;
for i=1:n
for j=1:n
R(i,j)=j;
end
end
for k=1:n
for i=1:n
for j=1:n
if (D(i,k)+D(k,j))