交巡警服务平台的设置与调.docx

摘要：本文有关节点分配给平台，也可认为对总数少于节点数的平台分配给哪个节点的问题，怎样分配调度是最优的方案，考虑工作量、出警时间、路程、发案率、人口、地区面积的要素，运用运筹学中0-1整数规划,给出最优方案,最短路程要素通过Matlab写的Dijstra算法算出是否能在3min到达的矩阵。
针对问题一：把节点分配给平台的优化度问题，考虑各种要素建立目标函数，函数对应的约束条件，通过Lingo求解得出结论。
针对问题二：在问题一的基础上，研究全市的优化度，并通过模型解出最合理的设置方案，若与原图出入较大，则调整某些个使合理度最低的点，再把模型调整采用某种方法解出时间最优解。
关键词：线性规划 0-1整数规划 优化 动态规划
一、 问题提出
（1）给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二、 模型假设和符号系统

1. 平台和事件设置、发生在节点处;
2. 事件发生的报警时间，平台的反应时间忽略不计;
3. 警车经过节点拐弯时间忽略不计;
4. 道路，平台，节点位置一切以图像为准;
5. 车辆的速率是稳定的60km/h;
6. 工作量不计在路上的时间;
7. 两个事件不会在同一平台管辖同时发生。

变量
表示的含义
i
第i个平台
j
第j个节点

最短路径矩阵

优化度

从i到j点间的最短路径长度(km)

发案率(次)
t
时间(min)

i与j标号路是否最短路径的路程在3公里以内，满足则为1，否则为0

第i平台需要的工作量
三、 问题分析
首先建立模型，从问题总体看出是优化度的模型，优化度要用到线性规划算法，线性规划主要解决对分配问题的优化度，建立最终的目标函数，由警车最短行走路程，发案率的约束条件限制。
算法，还有假设2条道路是否连同，连通则为1，否则为0，形成连通或断开矩阵，便于了解真实道路状况，来算出最短路径，0-1整数规划解决。
接下来的算法，是Dijkstra求权算法，求权算法是求出不同路径最短路径的长度。
那么如何解模，用Lingo语言来解决目标函数。
四、 模型的建立
用线性规划，建立A区优化度：
用第一题做例，目标函数：

约束条件：

策变量:
决用Lingo解出对应模型的:
五、 模型的求解

通过CAD画出所有平台3公里内的区域:

图一
3分钟到达的，由图可以直接排除29号，其余的还有28号等可以大致排除。
1）用Dijstra计算最短路径的长度，在matlab用Dijstra算法作为一个函数，代码见附件。
填入数据，统计excel参数B和y,见附件：
求出Dij的矩阵：

1
2
3
4
5
…
20
1
Inf
2

…

2
2
Inf

…

…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
92

…

表一
在matlab输入代码:
>> B=[175
1 78
2 44
…
…
91 92];
y=[

…
…
14.49];
gjdij(B,y)
得出不同路径最短路径，再化为0-1数据：
>> y<=3
得到：

1
2
3
4
5
…
20
1
0
1
0
0
0
…
0
2
1
0
1
0
0
…
0
3
0
1
0
0
0
…
0
4
0
0
0
0
0
…
0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
92
0
0
0
0
0
…
0
表二
红色标注最短距离在3公里以内的,1~20是平台，1~92是节点。同时，由图筛选出了6个所有平台3 min钟内无法到达的点分别为：
j=28,29,38,39,61,92分别对应:
i=15,15,16,2,7,20
方案一可以选择筛选找出大致的分配方案，并作最后答案的参考，以测验结果的合理性，结果如下：
平台
节点
1
1,67,68,69,71,73,74,75,76,78
2
2,40,43,44,70,72
3
3,54,55,65
4
4,57,60,62,63,64,66
5
5,49,50,51,52,53,56,58,59
6
6,47
7
7,30,32,48
8
8,33,46
9
9,31,34,35,45
10
10
11
11,26,27
12
12,25
13
13,21,22,23,24
14
14
15
15
16
16,36,37
17
17,41,42
18
18,80,81,82,83
19
19,77,79
20
20,84,85,86,87,88,89,90,91
表三
表三仅基于距离而言的最优方案。
方案二：由距离与发案率的乘积。
目标函数：

约束条件：

决策变量:
用Lingo解出最优的,代码部分见附件。
得到目标函数的最优方案:
1
19，70，74
2
3，39，40，69，73，75
3
2，44，54，55，67，75
4
4，57，60，62，63，64，65，66
5
49，53
6
6，50，51，52，56，58，59
7
5，30，33，48，61
8
8，34，35，36，47
9
7，32，46
10
10
11
11、26、27
12
12、25
13
13、21、22、23、24
14
14
15
15、28、29、31
16
9、16、37、38、45
17
17、41、42、43
18
20、71、80、82、88、89、90
19
1、18、76、77、78、79、83
20
81、84、85、86、87、91、92
表四
方案三：仅由发案率讨论。
目标函数：

约束条件：

决策变量:
用Lingo解出模型，代码见附件。
得到的最优方案如下：
1
1、67、68、69、71、73、74、75、76、78
2
2、39、40、43、44、70、72
3
3、54、55、65、66
4
57、60、62、63、64
5
49、50、51、52、53、56、58、59
6
6
7
7、30、32、47、48、61
8
8、33、46
9
9、31、34、35、45
10
10
11
11、26、27
12
12、25
13
13、21、22、23、24
14
14
15
15、28、29
16
16、36、37、38
17
17、41、42
18
18、80、81、82、83
19
19、77、79
20
20、84、85、86、87、88、89、90、91、92
表四
2）建立第二问的模型，目标函数:

约束条件：

同理用Lingo解出最优的,输入代码，代码在附件。
得到运算结果，如下:
节点
12
14
16
21
22
23
24
28
29
30
38
48
62
总路程
平台
12
16
3
14
10
13
11
15
7
8
17
9
1

路程
0
6.7

3.3
7.7
0.5
3.8
4.8
8.0
3.1
4.8
4.2
4.9
57.8
表五

综上，平均要min到达13个路口,分配如上。
3） 第三问的求解:
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，需要增加2至5个平台。
由第一问可知有6个路口出警时间超过3min，等同于平台到路口
3km：信息如下表：
交通路口序号
28
29
38
39
61
92
出警路程（km）

表六
再列出A区内92个路口中，能够分别满足28、29、38、39、61、92这6个路口点在3min内的警车车程赶到的所有点，如下表：
交通路口序号
3min内车程的交通路口序号
28
28、29
29
28、29
38
38、39、40
39
38、39、40
61
48、60、61
92
87、88、89、90、91、92
表七
用说理方式解决方案:
首先由此可知，28，29两点任选其一作为一平台；38，39，40三选一作为一平台，而60路口并不在需要缓解的路口范围之内，而48在，所以选48作为一个平台；87，88，89，90，91中选一个作为平台。因此，为满足出警时间条件，至少新增4个平台。
其次再逐个细分，28，29中，29的发案率高于28，所以选29作为交巡警平台，29管辖28；38，40由于距离限制都不能缓解其他平台的压力，而39被高工作量的2平台管辖，所以选39作为交巡警平台，能缓解2平台的压力；87，88，89，90，91路口中只有89能在3min内到达高工作量的20平台，所以选89作为一交巡警平台，能缓解20平台的工作压力。
综上所述，得到最终优化的增设方案是：在29、39、48、89四个路口处设为交巡警服务平台。

通过CAD画出全市所有平台3km内的区域：

图三
在问题一的基础上我们把A区扩展到全市，题中已给出全市交巡警服务平台的位置，问题在于如何判断题中交巡警服务平台的位置是否合理。
1) 要建立全市的模型：
目标函数：

决策变量：
约束条件：

通过Lingo软件解出该模型，从而分配全市各平台所管辖的各个节点。再根据上图找出该市交巡警服务平台在3min内不能到达的节点。
区域
3min之内不可到达的节点
不合理节点附近的点
C区
200，201，202
174
D区
362
362
E区
387，388，389，390
407
表八
由Lingo可知，看出180，477，这2个平台的工作量太大，并且有一个平台的工作量相对于其他平台太小。明显可见现有的交巡警分布是不合理的。
解决方案：在180，477周围增设平台，根据平台管辖的各个节点，考虑案发率的情况，在174，407处设为新增交巡警服务平台，362路口很孤立，所以单独设为新增平台，综上，在174，362，407三处增设交巡警服务平台，使其工作量大大减少。
2) 问题二可以分析得到：
3min后接警，在第一问基础上，警车能在3min到达所有的节点，由图画出罪犯可能到达的最大范围:

图三
警车行走3min封锁住出口，罪犯在3min大致最多走到中圆，由图知在大圆和中圆之间的环状区域可最快封锁所有可能逃脱的节点出口，只要筛选出大中圆中所有节点，找出标号，调用全市警车到达这些节点。可用第一题第二问的同种方式解决，这里不再列出求解过程。
六、 模型的评价
问题一模型采用Lingo解出数据的统计的直白与清楚，再结合图二测试结果。如图二，直接给出3分钟出警所能到达的点。并且建立的时候，省去一些不必要考虑的因素，比如警察平台工作量是统计件数，只需要发案率，而不必将出警时间也纳入工作量，从而使模型理想化，便于量化与建模解模。
问题二模型是问题一的扩展，分析现有的全市警务平台的设置是否合理，接着对犯罪嫌疑人有可能逃往的路径进行分析，确立出嫌疑犯有可能逃窜经过的节点离服务平台的最短距离，并制定出调度全市交巡警服务平台警力资源的最佳围堵方案。
本模型仍存在不足之处，将工作量对发案率和距离的依赖简单的看成一种线性关系，这虽然给我们的计算带来了方便，但与实际情况还存在较大的差距。
七、 参考文献

附件
1.Dijstra算法程序matlab语言:
function dd=gjdij(sw,swjuli)%附录一 Dijkstra算法求解最短路径程序
A=sw;
y=swjuli;
B=inf*ones(92);
for i=1:size(A,1)
B(A(i,1),A(i,2))=y(i);
B(A(i,2),A(i,1))=y(i);
end
for h=1:20
s=zeros(92,1);
D=zeros(92,1);
for v=1:92
D(v)=B(h,v);
end
s(h)=1;
for v=1:91
j=1;
while j<=92&&s(j)==1
j=j+1;
end
for i=j+1:92
if s(i)==0&&D(i)<D(j)
j=i;
end
end
s(j)=1;
for k=1:92
if s(k)==0&&D(j)+B(j,k)<D(k)
D(k)=D(j)+B(j,k);
end
end
end
yy{h}=D;
end
dd=[yy{1} yy{2} yy{3} yy{4} yy{5} yy{6} yy{7} yy{8} yy{9} yy{10} yy{11} yy{12} yy{13} yy{14} yy{15} yy{16} yy{17} yy{18} yy{19} yy{20}];
2.（1）问题一(1)方案二的Lingo程序：(发案率)
model:
sets:
ii/1..20/;
jj/1..92/;
perhaps/1..92/:v;
links(pingtai,jiedian):w,x;
endsets
min=@max(ii(I):@sum(jj(J):x(I,J)*v(J));)-@min(ii(I):@sum(jj(J):x(I,J)*v(J)););
@for(jj(J):@sum(ii(I):w(I,J)*x(I,J))=1;);
@for(links:@BIN(x););
data:
w=
v=@ole('F:/shumoruanjian/3.xls',data1);
enddata
end
2.（2）问题一(1)方案三的Lingo程序：(发案率*距离)
model:
sets:
num_i/1..20/:q;
num_j/1..92/:v;
link(num_i,num_j):x,w;
endsets
data:
v=@ole('F:/shumoruanjian/3.xls',data1);
w=@ole('F:/shumoruanjian/4.xls',data2);
enddata
[OBJ]min=@max(num_i(i):@sum(num_j(j):v(j)*x(i,j);););
@for(link:x<=w;);
@for(num_j(j):@sum(num_i(i):x(i,j)*w(i,j))=1;);
@for(link:@BIN(x););
END
3.问题一(2)的Lingo程序：
model:
sets:
department/1..20/;
type/1..13/;
a/1..20/:c;
benefit(department,type):d,x;
endsets
min=@max(benefit(i,j):d(i,j)*x(i,j));
@for(benefit:@bin(x));
@for(department(i):
@sum(type(j):x(i,j))<1);
@for(type(j):
@sum(department(i):x(i,j))>1);
data:
d=@ole('F:/shumoruanjian/2.xls',data1);
enddata
end