服务平台的设置与调度7Word文档格式.docx
《服务平台的设置与调度7Word文档格式.docx》由会员分享，可在线阅读，更多相关《服务平台的设置与调度7Word文档格式.docx（37页珍藏版）》请在冰点文库上搜索。
本文将问题转化为：
从20个服务平台中选出13个对13条交通要道进行封锁，且这13个平台所用的时间要最小的规划问题。
本文引入0-1变量表示一个巡警服务台是否封锁一条交通要道，从而建立这个问题的0-1规划模型，并借助数学软件LINGO进行求解。
（3）根据问题一
（1）的分配方案可知：
当标号为39、61、28、29、38、92的路口有案件发生时，标号为2、7、15、16、20的巡警服务台的出警时间将超过3min，即出警时间过长。
此时每个巡警服务台的工作量分别为：
按问题一
（1）的分配方案20个巡警服务台的工作量
平台标号
1
2
3
4
5
6
7
8
9
10
工作量
10.3
8.3
5.6
6.6
9.7
2.5
8.2
1.6
11
12
13
14
15
16
17
18
19
20
4.6
8.5
2.1
.3.8
5.3
6.1
3.4
10.7
此时巡警服务台的工作量不均衡度为8.4314。
由1），2）可知现有巡警服务台的工作量极其不均衡且有些地方出警时间过长。
针上述问题题目要求再增加2—5个巡警服务台来解决上述问题。
本文首先建立集合覆盖的0-1规划模型，然后利用MATLAB对模型进行求解，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加巡警服务台的数目与位置。
问题二：
（1）本文定义了两个评价原则：
原则一：
巡警能在3min之内到达案发路口
根据以上两个原则对该城区现有巡警服务台的设置方案的合理性进行评价。
若现有巡警服务台的设置不合理，本文则提出方案对全城的巡警服务台设置进行优化：
方案：
保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；
（2）当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发
3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台
警力围堵嫌疑犯。
因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌
疑犯逃跑方向，所以此问题可转化为以下模型：
对于任意时间，嫌疑犯驾车逃跑的最大范围为：
在时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，
记为，将的边界点集记为。
所谓最快围堵方案，即寻找一个最短时间，
适当的调配巡警警力，使其在时间内能够到达边界点，这样嫌疑犯就被控制
在区域中，此时嫌疑犯将无法逃脱。
三符号说明
Cij：
巡警平台i与路口j之间的最短距离
Cj：
j号巡警平台的工作量，其中j=1…24
tij=
I：
C类路口的集合
：
平均工作量
工作量不均衡度
i路口的发案次数，其中i=1,2…92
Q：
需要增加巡警服务台的路口的候选集
Y：
嫌疑人最大逃跑范围的边缘节点的集合
X：
所有巡警平台的集合
E：
X中一点到Y中一点的最短路径的集合
t：
接到报案后时间的增量
四模型假设
1.每个巡警服务平台的服务能力相同。
2.每个路口只由一个巡警平台负责。
3.每个巡警平台至少负责一个路口。
4.巡警按最短路劲前往案发路口。
5.案件都发生在路口。
6每个巡警平台辖区内所有路口案发率之和为该平台一天的工作量。
7.逃犯的逃跑速度与警车速度相同。
8.以所有巡警平台工作量的方差，作为工作量不均衡度。
五模型建立和求解
问题一
问题1.1
问题1.1中，要将92个路口纳入20个交巡警平台的管辖范围。
必须保证，每个路口都在一个交巡警平台的管辖范围内。
同时，每个路口所属的交巡警平台，要是所有20个平台中到该路口距离最短的。
如果一路口，在其3km路程内，仅有一个巡警平台，称其为A类路口。
如果一路口，在其3km路程内，有多个巡警平台，称其为B类路口，将它分到最近的平台。
如果一路口，在其3km路程内，没有巡警平台，称其为C类路口，将它分到最近的平台。
根据以上要求，分别为92个路口找到距离最短的交巡警平台，这是典型的最短路问题。
最短路是图论研究中的一个经典算法问题。
最短路问题,一般来说就是从给定的网络中找出任意两点之间距离最短的一条路径。
求最短路有的一种主要方法是求图上任意两点之间最短距离的Floyd-Warshall算法。
根据Floyd-Warshall算法及其在C语言程序上的运用【1】，编写C语言程序（见附录1），进行求解，得出分配方案如下表（表1）：
交巡警服务平台管辖范围表
服务平台
管辖路口
1，67，68，69，71，73，74，75，76，78
11，26，27
2，39，40，43，44，70，72
12，25
3，54，55，65，66
13，21，22，23，24
4，52，56，57，60，62，63，64
5，49，50，51，53
15，28，29
6，58，59
16，36，37，38
7，30，32，47，48，61
17，41，42
8，33，46
18，80，81，82，83
9，31，34，35，45
19，77，79
20，84，85，86，87，88，89，90，91，92
表1
问题1.2
问题1.2中，要对20个巡警平台进行调度，封锁13个路口。
要使得实现全封锁的时间最短。
这是图论中的指派问题【2】。
指派问题可以看做是0-1规划问题。
记20个巡警平台分别为i=1,2…20；
记13个需要封锁的路口按标号从小到大的顺序，分别为j=1…13.，记巡警平台i与路口j之间的最短距离为Cij。
引入0-1变量xij，如果平台i对路口j进行封锁，记xij=1，否则记xij=0。
目标函数：
其中i=1…20，j=1…13。
约束条件：
每个路口都要有一个平台对其封锁，即：
，j=1…13
每个平台最多封锁一个路口，即：
，i=1…20
综上所述，此问题的优化模型为：
利用C语言程序和Lingo进行编程求解，程序见附录2，过程如下：
1．根据Floyd-Warshall算法，编写C程序对Cij求解，得到20个巡警平台到13个路口的最短距离Cij。
2.将上一步中得到的数据导入Lingo中，根据已知的目标函数和约束条件，用Lingo求的最优解。
Lingo解得的结果表明，实现全封锁的最短用时为8.0155分钟，具体的平台调度方案如下表（表2）：
调度方案表
路口标号
21
22
23
24
用时（min）
3.7914
6.7417
6.0256
3.2650
7.7079
0.500
3.5916
28
29
30
38
48
62
4.7518
8.0155
3.2135
5.8809
2.4758
6.4489
表2
问题1.3
1、初步分配方案的确定
同样运用问题一中的方法可以得到：
距离C类各个路口小于3km的路口集合，如下表（表3）：
距离C类各个路口小于3km的路口集合表
C类路口标号
39
92
集合
{28,29}
{38,39,40}
{48,61}
{87,88,89,90,91,92}
表3
对上表中的6个集合求并，得到需要增加巡警服务台的路口的候选集Q={28,29,38,39,40,48,61,87,88,89,90}。
本文将要在候选集Q中选择2-5个路口设置巡警服务台，使需求集I=[28,29,38,39,61,92]中的所有路口在案发生时均有巡警在3min之内能赶到。
集合覆盖模型的建立
首先，建立覆盖矩阵T6×
13，其元素：
i=1,2…6,j=1,2…13。
其次，建立集合覆盖模型：
满足：
.
其中：
最后，利用MATLAB运用搜索法得到：
至少从候选集Q中选出4个路口来设置巡警服务台，才能解决出警时间过长的问题。
此时共有48种可能的分配方案。
分别如下表（表4）所示：
48种分配方案表
28,38,48,87
28,38,61,87
28,39,48,87
28,39,61,87
29,38,48,87
29,38,61,87
29,39,48,87
29,39,61,87
28,38,48,88
28,38,61,88
28,39,48,88
28,39,61,88
29,38,48,88
29,38,61,88
29,39,48,88
29,39,61,88
28,38,48,89
28,38,61,89
28,39,48,89
28,39,61,89
29,38,48,89
29,38,61,89
29,39,48,89
29,39,61,89
28,38,48,90
28,38,61,90
28,39,48,90
28,39,61,90
29,38,48,90
29,38,61,90
29,39,48,90
29,39,61,90
28,38,48,91
28,38,61,91
28,39,48,91
28,39,61,91
29,38,48,91
29,38,61,91
29,39,48,91
29,39,61,91
28,38,48,92
28,38,61,92
28,39,48,92
28,39,61，92
29,38,48,92
29,38,61，92
29,39,48,92
29,39,61，92
表4
2、最终分配方案的确定
1）为每种方案中的24个巡警服务台分配管辖范围。
步骤一：
同样按照问题一
（1）中的求解过程1和2可得到有24个巡警服务台的集合覆盖矩阵K92×
24。
步骤二：
此时由上述集合覆盖矩阵可将城区A的92个路口分为A、B两类：
A类：
已只由一个巡警服务台进行管辖；
B类：
可被多个巡警服务台进行管辖；
将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。
对于B类的路口，在综合距离最近与工作量平均的情况下来进行分配。
首先选择距离路口i最近的巡警服务台j（j=1,2…24），然后利用公式
计算巡警服务台j的工作量
，若
则将路口i分配给巡警服务台j管辖，否则选择次短距离的巡警服务台进行同样考虑。
最后得到每种分配方案中24个巡警服务台的管辖范围。
步骤三：
根据平局工作量公式
与工作量不均衡度公式
，利用MATLAB分别对48中分配方案中巡警服务台的工作量不均衡度进行计算。
得到下表（表5）：
48中分配方案对应的工作量不均衡度表
3.4890
4.7194
3.0742
4.3046
4.6490
4.2498
3.4916
4.6672
3.0768
4.2524
表5
由表中数据可得：
最小不均衡度为3.0742，有8种分配方案。
如下表（表6）所示：
满足题目一（3）要求的4个巡警服务台的路口标号表
表6
本文仅给出其中方案一（在路口标号为28、39、48、87处增加巡警服务台）对应的城区A的24个巡警服务台的管辖范围（表7）与每个巡警服务台对应的工作量，如下表（表8）：
方案一中24个巡警服务台的管辖范围表
服务台
管辖范围
1,67,68,69,71
13,21,22,23,24
2,43,44,70,72
54,55,3,65，
15,
4,57,60,62,63
16,36,37
53,5,49,50,51
41,17,42
6,52,56,58,59
18,74,80,81,82
7,30,32
19,75,76,77,78
8,33,45,46，
20,85,86,90,91
9,31,34,35
28,29
38,39,40
11,26,27
61,67,48
12,25
87
92,83,83,87,88
表7
方案一中每个巡警服务台对应的平均工作量表
6.5
6.4
6.8
5.1875
不均衡度
3.8
6.3
2.7
4.3
3.6
表8
问题二
问题2.1
根据题目中提到的信息，我们从两个方面对现有设置方案进行评价：
巡警服务台的工作量均衡度尽量小
依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。
讨论现有设置方案是否满足原则一：
全城六区A，B，C，D，E，F现有个80巡警服务台、582个路口，运用问题一
（1）中的算法，得到全城C类路口的数目与位置，如下表（表9）：
C类路口的位置标号
61
122
123
124
151
152
153
183
199
200
201
202
203
205
206
207
208
209
210
215
238
239
240
247
248
251
252
253
257
259
261
262
263
264
268
269
285
286
287
288
299
300
301
302
303
304
312
313
314
315
316
317
318
319
329
330
331
332
336
337
339
344
362
369
370
371
387
388
389
390
391
392
393
395
407
408
409
411
412
413
417
418
419
420
438
439
443
445
446
451
452
455
458
459
464
469
471
474
486
487
505
506
507
508
509
510
512
513
514
515
516
517
518
519
522
523
524
525
526
527
529
533
540
541
559
560
561
566
569
574
575
578
582
表9
计算结果表明：
582个路口中共有138个C类路口，即在案发时巡警不能在
3min到达此路口，约占全城总路口数的1/4。
讨论现有设置方案是否满足原则二：
运用问题一（3）中的方法，为每个巡警服务台分配管辖范围，并计算工作
量及巡警服务台的工作不均衡度。
结果如下（表10）：
现有配置下每个巡警服务台的工作量
巡警服务台
93
178
4.5
378
2.6
94
11.3
179
379
7.4
95
9.5
180
380
17.1
96
11.5
181
6.2
381
97
182
12.2
382
98
12.1
320
8.7
383
40.4
99
321
834
100
322
4.4
385
9.1
166
323
4.2
386
167
324
7.9
475
13.1
168
4.7
325
2.2
476
169
326
5.1
477
39.6
170
12.69
327
7.6
478
7.2
171
12.4
328
6.7
479
12.9
172
372
5.2
480
28.4
173
373
4.1
481
174
10.1
374
5.5
482
6.
升级会员 