题目要求:
试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问题:
(1)附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图,相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。
对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。
文件来源:
可以到数学建模官网区找往期试题,里面可以下载到完整的题目和数据文件。全国大学生数学建模竞赛 (mcm.edu.cn)
思路:
1.利用现有的数据计算出每个节点之间的直达路径,然后再通过弗洛伊德算法,求解任意两个节点之间的最短距离。
2.先计算出距离交通平台3km之内的交通节点,然后将重复的节点,找到它们最近的交通平台并分配,将任意平台都不能3分钟到达的节点,找到最近的交通平台,最后得到交巡警服务平台的管辖范围。
3.找到距离平台最近的路口节点,或者找到距离路口节点最近的平台节点,一个路口节点只能匹配一个平台节点,一个平台节点也只能匹配一个路口节点。
源代码:
弗洛伊德算法
floyd.m
function [Dist]=floyd(DISTANCE)
Dist = DISTANCE;
n = size(DISTANCE,1);
for k=1:n
for i=1:n
for j=1:n
if (Dist(i,k)+Dist(k,j)<Dist(i,j))
Dist(i,j)=Dist(i,k)+Dist(k,j);
end
end
end
end
%保存到文件
fid=fopen('Dist.txt','wt');
[m,n]=size(Dist);
for i=1:m
for j=1:n
if j==n
fprintf(fid,'%g\n',Dist(i,j));
else
fprintf(fid,'%g\t',Dist(i,j));
end
end
end
主程序
clear;clc;
%读取数据
file = 'cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls';
%节点数据
JIEDIAN = xlsread(file,1,'B2:C93');
%disp(Apoint);
%整数化
[row1,column1] = size(JIEDIAN);
for i = 1 : row1
for j = 1 : column1
JIEDIAN(i,j) = round(JIEDIAN(i,j));
end
end
%disp(JIEDIAN);
%巡警平台数据
PINGTAI = [20,2];
for i = 1 : 20
for j = 1 : column1
PINGTAI(i,j) =JIEDIAN(i,j);
end
end
%disp(PINGTAI);
%路线数据
ROAD = xlsread(file,2,'A2:B144');
[row2,column2] = size(ROAD);
for i = 1 : row2
for j = 1 : column2
if(ROAD(i,j) > 92)
ROAD(i,1) = 0;
ROAD(i,2) = 0;
end
end
end
%disp(ROAD);
%求节点之间的直接距离
DISTANCE = zeros(92);
for i = 1 : 92
for j = 1 : 92
DISTANCE(i,j) = inf;
if(i == j)
DISTANCE(i,j) = 0;
end
end
end
%disp(DISTANCE);
for i = 1 : row2
for j = 1 : column2
x1 = ROAD(i,1);
x2 = ROAD(i,2);
if ((x1 == 0)&&(x2 == 0))
continue;
else
dis=sqrt((JIEDIAN(x1,1)-JIEDIAN(x2,1))^2+(JIEDIAN(x1,2)-JIEDIAN(x2,2))^2);
DISTANCE(x1,x2) = dis;
DISTANCE(x2,x1) = dis;
end
end
end
%disp(DISTANCE);
%FLOYD算法并写入文件dist中
Dist = floyd(DISTANCE);
%找出每个平台距离不大于30(换算后距离)的节点以及无法到达的节点
PT_y_JD = [];
PT_n_JD = 21:92;
for i = 1 : 20
k = 1;
PT_y_JD(i,k) = i;
for j =21 : 92
if(Dist(i,j)<=30)
k = k + 1;
PT_y_JD(i,k) = j;
PT_n_JD(PT_n_JD == j) = [];
end
end
end
%读取出入A区的节点
GATE = xlsread(file,4,'C2:C14');
%分别以到出入节点的距离和到平台的距离形成两个矩阵
%距离出入口节点最近的平台
PT_y1_GT = [];
%距离平台最近的出入口节点
PT_y2_GT = [];
column3 = length(GATE);
for j = 1 : 20
k = 1;
dis_to_GT2 = [];
for i = 1 : column3
PT_y2_GT(i,1) = GATE(i);
dis_to_GT1 = Dist(GATE(i),1:20);
dis_to_GT2(end+1) = Dist(j,GATE(i));
mindis = min(dis_to_GT1);
if(Dist(GATE(i),j) == mindis)
PT_y1_GT(j,k) = GATE(i);
k = k + 1;
end
end
k = 2;
mindis = min(dis_to_GT2);
for i = 1 : column3
if(Dist(j,GATE(i)) == mindis)
PT_y2_GT(j,k) = j;
k = k + 1;
end
end
end
%到平台的距离不用修改即可使用
PT_yy_GT = [];
for i = 1 : column3
for j = 1 : 20
if (j == PT_y2_GT(i,2))
PT_yy_GT(j,1) = j;
PT_yy_GT(j,2) = PT_y2_GT(i,1);
end
end
end
%把每个平台辖区的平台节点删去,优化范围辖区
%前面已优化
%求出优化范围辖区
%找出重复出现的节点
REPEATED_JD = [];
[row4,column4] = size(PT_y_JD);
UN_REPEATED_JD = [];
%定义计数变量
for k = 21 : 92
count = 0;
for i = 1 : row4
for j = 1 : column4
if(PT_y_JD(i,j)==k)
count = count + 1;
end
if((count > 1)&&(i == row4)&&(j == column4))
REPEATED_JD(end+1) = k;
else if((count==1)&&(i == row4)&&(j == column4))
UN_REPEATED_JD(end+1) = k;
end
end
end
end
end
%找出重复节点最近的交通平台,并记录在优化的巡警范围数组里面
PT_yy_JD = [];
dis_to_PT = [];
row5 = length(REPEATED_JD);
for j = 1 : 20
k = 1;
PT_yy_JD(j,k) = j;
for i = 1 : row5
dis_to_PT = Dist(REPEATED_JD(i),1:20);
mindis = min(dis_to_PT);
if(Dist(REPEATED_JD(i),j) == mindis)
k = k + 1;
PT_yy_JD(j,k) = REPEATED_JD(i);
end
end
end
%把不重复的节点记录进去,得到最优范围覆盖节点
column5 = length(UN_REPEATED_JD);
for i = 1 : column5
[row , column] = find(PT_y_JD == UN_REPEATED_JD(i));
countZeros = length(find(PT_yy_JD(row,:)>0));
k = countZeros + 1;
PT_yy_JD(row,k)=UN_REPEATED_JD(i);
end
%把无法及时抵达的点也记录进去,得到最优覆盖
for j = 1 : 20
k = 1;
for i = 1 : length(PT_n_JD)
dis_to_PT = Dist(PT_n_JD(i),1:20);
mindis = min(dis_to_PT);
if(Dist(PT_n_JD(i),j) == mindis)
countZeros = length(find(PT_yy_JD(j,:)>0));
k = countZeros + 1;
PT_yy_JD(j,k)=PT_n_JD(i);
end
end
end
fprintf('优化后的交通平台管辖范围\n');
disp(PT_yy_JD);
fprintf('交通平台及其负责的A区出入点\n');
disp(PT_yy_GT);
运行结果:
优化后的交通平台管辖范围
1 67 68 69 71 73 74 75 76 78
2 40 43 44 70 72 39 0 0 0
3 65 66 54 55 0 0 0 0 0
4 57 63 64 60 62 0 0 0 0
5 50 51 52 56 58 59 49 53 0
6 0 0 0 0 0 0 0 0 0
7 32 47 48 30 61 0 0 0 0
8 33 46 0 0 0 0 0 0 0
9 31 34 35 45 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
11 26 27 0 0 0 0 0 0 0
12 25 0 0 0 0 0 0 0 0
13 21 22 23 24 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0
15 28 29 0 0 0 0 0 0 0
16 36 37 38 0 0 0 0 0 0
17 42 41 0 0 0 0 0 0 0
18 80 81 82 83 0 0 0 0 0
19 77 79 0 0 0 0 0 0 0
20 84 85 87 88 89 90 91 86 92
交通平台及其负责的A区出入点
1 12
2 14
3 16
4 21
5 22
6 23
7 24
8 28
9 29
10 30
11 38
12 48
13 62
tips:
1.一开始导入excel文件时,matlab会提示该文件没有添加到路径,直接添加就好。
2.在分配路口节点到平台的过程中,我同时进行了将路口节点分配到距离它们最近的平台节点和将平台节点分配到距离它们最近的路口节点两个操作。结果发现将路口节点分配到距离它们最近的平台节点所得结果一个平台会包含多个路口节点,不太合理。将平台节点分配到距离它们最近的路口节点,可以得到合适的结果。
3.本次floyd算法仅仅需要得到最短距离的矩阵,没有要求路径,所以代码里面没有实现路径部分。
后面的两问,以后学会了再写,我们一起进步。各位看官,瑞斯拜~~
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)