2011年数学建模全国赛论文

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

摘   要

    本文研究交巡警服务平台的设置与调度问题。

    针对问题一，本文以出警时间最短及各交巡警服务台工作量均衡为目标函数建立多目标规划模型，解决了各平台的管辖范围的分配问题。以出警时间最短为目标函数建立了整数规划模型，确定了发生重大突发事件时区交巡警服务平台警力合理的调度方案。以出警时间最短，各交巡警服务台工作量均衡，新增平台最少无目标建立多目标规划模型，确定需要增加平台的具体个数和位置。为满足各交巡警服务平台到所管辖范围内的事件突发地点所用的时间尽量在3分钟以内及工作量尽量均衡引进偏差变量，为确定各服务台管辖的范围、出入口由哪个服务台进行风俗及新增服务平台的位置分别引入0—1变量，运用目标规划发，并通过MATLAB对以上模型求最优解。

针对问题二，本文以各主城区交巡警服务平台的出警时间偏差最大值、工作量的偏差最大值，人口密度，平台个数为主要影响因子建立模糊综合评判模型对该市现有交巡警服务平台设置方案的合理性进行了评价。

以所分所得路口尽量多为目标函数建立了目标规划模型，解决了最佳围堵方案的确定，为确定围堵方案本文引入0—1变量，并通过LINGO对规划模型进行求解。

关键词：综合模糊评判；多目标规划；整数规划；0—1变量 

一、问题重述

“有困难找”，是家喻户晓的一句流行语。肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：

（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。

如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、符号说明

：时间正偏差

：时间负偏差

：工作量正偏差 

：工作量负偏差

：第个交巡警服务平台到第个路口所用的时间

：第个路口的事故的发生率

：第个路口对时间的权重

：第个交巡警服务平台到第个路口的距离

三、模型假设

1．正常情况下都能顺利到达事发地点。

2．在对嫌疑犯追捕过程中，嫌疑犯不会往回跑。

四、问题分析

问题一

问题一需要确定：（1）为各交巡警服务平台分配管辖范围使交巡警尽量能在3分钟内到达事发地；（2）确定重大事件发生时对13个交通要道实现快速全封锁的交巡警服务平台警力合理的调度方案；（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况确定需要增加平台的具体个数和位置。针对上述问题本文主要考虑各交巡警服务平台到所管辖范围内的事件突发地点所用的时间尽可能短，各交巡警服务平台的工作量尽量均衡，所增加平台个数最少等方面，建立了多目标规划模型。

问题二

问题二要求（1）根据该市的具体情况对其现有的交巡警服务平台设置的合理性进行评价；（2）如该市某地点发生重大案件，确定为快速搜索嫌疑犯调度全市交巡警服务平台警力资源的最佳围堵方案。针对交巡警服务平台设置的合理性进行评价，通过问题一可以得到各区出警时间，工作量均衡率的相关结果结合该市人口的影响因素可建立模糊综合评价模型对平台设置的合理性进行评价。针对最佳围堵方案的确定，为最快速的抓住犯罪嫌疑人，本文认为将所有嫌疑犯将要去的节点封锁，直到嫌疑犯被完全包围在警方的封锁内时，嫌疑犯被抓获，即警方封锁的路口越多嫌疑犯被抓住的可能性就越大。嫌疑犯在A区作案并逃跑因此要调动A区所有警力封锁各出入口，但是警方是在嫌疑犯逃跑三分钟之后接到的保案，因此警方几乎不可能把嫌疑犯完全封锁在A 区，因此警方必须保证封锁嫌疑犯从A区逃跑到的下一个路口。基于以上分析，本文建立以尽可能多的封锁路口为目标的整数规划模型。

五、模型建立与求解

5.1    分配各交巡警服务平台管辖范围

 5.1.1各巡警服务平台管辖范围分配模型建立

    题设要求在A区中交巡警服务平台确定的情况下为各交巡警服务平台分配管辖范围。根据对题目要求及实际情况的综合分析得：为及时对突发事件进行处理各交巡警服务台到所管辖范围各点的时间应该尽可能快，为合理分配警力资源各服务台工作量应该尽可能均衡。因此本文针对上述情况为使各交巡警服务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地及各交巡警服务平台的工作量尽量均衡为目标建立多目标规划模型。

第个交巡警服务台到达第节点所用时间为

                        （1）

其中，且，从第个服务台到节点所用时间。

各交巡警服务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地点，即事件发生时交巡警到达事发地点的所用时间在3分钟左右浮动，所用时间小于3分钟正式我们希望的，但是考虑实际情况当时间超过3分钟但超出的时间在某一范围内时是可以被接受的，为准确的给出交巡警服务平台到各节点所用时间，本本文引入时间偏差，，因此每个服务台到达所管辖的各节点的时间满足下述等式：

                     （2）

    为使各交巡警服务平台在其所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地点，应该使所用时间尽可能接近3分钟，即尽可能小。又由于各个点的事故发生率不同，发生率越大，希望交巡警到达的时间越短，也就是交巡警到达时间大于3分钟的部分越小，即越小，考虑实际情况本文根据各个节点的发生率对各服务台到达某节点的时间偏差赋予权重，因此以时间为目标的目标函数可以表示为：

                        （3）

    对于各个点的工作量，本文以各服务台管辖范围内节点事故的发生率作为该节点的工作量的指标，各服务台工作量应尽量均衡，但考虑实际情况，完全的平衡是不可能的，本文认为各服务平台的工作量对平衡工作量容许存在偏差，现引入工作量偏差，，因此各服务台的工作量应满足等式（4）：

                （4） 

其中，为节点的发生率。

    各服务台工作量尽量均衡，即越小各服务平台的工作量越趋于均衡，因此以工作量偏差最小为目标的目标函数可以表示为：

                        （5）

    分配管辖范围时，根据城市的实际情况与需求，出警所用时间和工作量均衡的影响大小不同，为使更合理的分配各平台的管辖范围，本文分别对时间偏差和工作量偏差赋权重，因此以超过3分钟的时间偏差最下及相对于均衡工作量的工作量偏差最小为目标的多目标规划模型可建立如下：

            （6）

 5.1.2各巡警服务平台管辖范围分配模型求解

  1．最短路径的求解

本文应用Floyd算法求解出各点之间的最短路径，得到一个的矩阵。

2．对时间偏差权重的求解

又由于各个点的事故发生率不同，发生率越大，希望交巡警到达的时间越短，也就是交巡警到达时间大于3分钟的部分越小，即越小，因此可将的节点的发生率作为时间偏差权重的衡量标准。本文利用极差变换发求解的值:

                    （8）

3．各交巡警服务平台分配管辖范围的确定

在最短路径矩阵中寻找既满足到各个服务台时间尽量在3分钟的点又满足总体工作量均衡的20组值。

模型的求解在LINGO中实现，所得结果如表一所示：

表一 模型结果

交巡警平台位置标号	管辖范围
1	1,68,69,73,75,77
2	2,43,71,72,78
3	3,44,65,66,67,70
4	4,60,62,63,
5	5,50,51,54,56,57
6	6,52,53,58,59
7	7,30,49,61
8	8,47,48,55
9	9,32,45,46
10	10,33,34,36
11	11,22,26
12	12,25,27
13	13,23,24
14	14,21,37
15	15,28,29,31
16	16,35,38,39
17	17,40,41,42
18	18,79,82,84,87,,90,91
19	19,74,76,80,81
20	20,83,85,86,88,92

4．分配管辖范围时，根据城市的实际情况与需求，出警所用时间和工作量均衡的影响大小不同，因此应分别对时间偏差和工作量偏差赋权重，以上给出解是在出警所用时间和工作量均衡的全中相同下的解。为适应不同城市的不同需求本文分别对出警所用时间和工作量均衡赋以不同权值，并相应的给出了两种方案，如表二、表三所示。

表二，时方案

交巡警平台位置标号	管辖范围
1	1,,69,73,75,76,79,80
2	2,43,74,78
3	3,44,55,65,67,70
4	4,60,62,63,66
5	5,51,54,56,57,58
6	6,50,52,53,59
7	7,30,49,61
8	8,36,47,48
9	9,32,35,46
10	10,33,34
11	11,22,26
12	12,25,27
13	13,23,24
14	14,21,37
15	15,28,29,31
16	16,38,39,45
17	17,40,41,42
18	18,81,84,87,,90
19	19,68,71,77,82,83
20	20,85,86,88,91,92

表三，时方案

交巡警平台位置标号	管辖范围
1	1,44,72,76,77,80
2	2,66,69,71,73,75
3	3,43,55,65,68
4	4,60,62,63,
5	5,53,54,57,59
6	6,50,51,52,56,58
7	7,30,49,61
8	8,36,47,48
9	9,32,35,46
10	10,33,34
11	11,22,26
12	12,25,27
13	13,23,24
14	14,21,37
15	15,28,29,31
16	16,38,39,45
17	17,40,41,42
18	18,78,79,85,88,,90
19	19,67,70,74,82,83
20	20,81,84,86,87,92

 5.1.3结果分析

    1．如图1所示为各服务平台工作量的偏差图：

图1各服务平台工作量的偏差图

    由图1可以看出除4个点有明显突起外，其余各点变化幅度都比较小，由时间偏差图可以看出能在在三分钟内到达节点的为81.6%。

    2．如图2所示为各服务平台工作量的偏差图：

图2各服务平台工作量的偏差图

由图1可以看出除4个点有明显突起外，其余各点变化幅度都比较小，由时间偏差图可以看出能在在三分钟内到达节点的为83.7%。

3．如图3所示为各服务平台工作量的偏差图：

图3各服务平台工作量的偏差图

由图1可以看出除3个点有明显突起外，其余各点变化幅度都比较小，由时间偏差图可以看出能在在三分钟内到达节点的为85.3%。

5.2确定重大事件突发时的A区交巡警服务平台警力合理的调度方案

 5.2.1交巡警服务平台警力合理的调度方案的模型建立

    当重大突发事件发生时快速、全面封锁各交通出入口是关键，因此针对A区的13条交通要道，每个出入口都必须有交巡警进行封锁，为满足该要求本文引入0—1变量并使。要快速的封锁所有出入口即封锁所有要道所用的总时间最短且使封锁路口所用的最长时间最短，因此在调动警力资源时应选择离出入口节点最近的服务平台。因此针对上述问题本文以封锁全部路口所用的总时间最短以及封锁路口所用的最长时间最短为目标函数建立多目标规划模型：

    

                     （7）

其中表示封锁每个路口所用的时间，为服务平台到出入口的距离。

在上述模型中每个出入口仅有一个服务平台对其进行封锁，同时每个服务平台也只能封锁一个出入口，显然有7个平台没有封锁任务，综合考虑实际情况，在各服务平台对各出入口进行封锁途中由于某些阻力如道路毁坏、交通拥堵等不能在预定时间对相应出入口封锁而造成损失。鉴于以上情况，以到某出入口时间最短为原则，将所有出入口分配给上述7个没有封锁任务的服务平台，使这7各服务平台最为机动平台在其他13个服务平台不能顺利到达封锁点事，对该封锁点进行封锁或进行其他支援，以保证封锁任务快速、顺利完成，避免或减少损失。

现将13个出入口分配给7个没有封锁任务的服务平台。以服务平台到出入口所用时间最少为目标函数建立0—1规划模型。

                         （8）

 5.2.2模型的求解

交巡警服务平台警力合理的调度方案的模型输入LINGO中对其进行求解可得到对于重大突发事件，对进出A区的13条交通要道实现快速全封锁时，实A区交巡警服务平台警力合理的调度方案如表四所示：

表四 交巡警服务平台警力合理的调度方案

节点	12	14	16	21	22	23	24	28	29	30	38	48	62
服务平台	12	14	16	9	10	13	11	15	8	7	2	5	3

机动调度安排

表五 机动调度安排

区	v1(很合理	v2(合理）	v3(较合理	v4(不合理	v5(很不合理	等级
	0.3425	0.6652	0.4576	0.56	0.425	合理
	0.779	0.3978	0.4432	0.445	0.334	很合理
	0.3542	0.656	0.4782	0.576	0.443	合理
	0.3423	0.676	0.495	0.4876	0.287	合理
	0.4674	0.327	0.499	0.6987	0.57	不合理
	0.8221	0.34	0.6788	0.65	0.2341	合理

5.3确定需要增加平台的具体个数和位置

 5.3.1确定增加平台的具体个数和位置建立

     根据模型一的结果分析可知即使在服务平台到管辖范围内时间最短及各服务平台的工作量尽量均衡的条件下优化分配管辖范围，依然存在某些服务平台的工作量过大或出警时间过长的结果，因此该市A区的交巡警服务平台的设置上存在一定的不合理性，为使巡警服务平台的设置更加合理化，今拟在该区内增加2至5个平台。对于新增服务平台的设置，遵循原则：（1）各服务平台到其管辖范围内的各节点的时间尽量在3分钟以内；（2）各交巡警服务平台的工作量尽量均衡；（3）新增的平台个数最少。

    本文以上述三条设置原则为目标函数，以每个节点必须有一个服务平台管辖，每个服务平台至少管辖一个服务平台，服务平台到其所管辖的各节点的时间与正负偏差的代数和为3，各服务平台的工作量与其正负偏差的代数和等于平均工作量等为约束条件建立多目标规划模型。

                 

            （9）

5.3.2模型的求解

    模型的目标函数和约束条件输入LINGO中进行求解可得新增点为三个，坐标分别为： 5.3.3结果分析

问题二

 5.4对该市现有交巡警服务平台设置方案的合理性评价

    本文以到达事发地点的时间 ，工作量的均衡率，各区人口密度，各区设置的交巡警服务平台的数量作为评价指标建立模糊综合评价模型对对该市现有交巡警服务平台设置方案的合理性评价。

1．主成分分析法确定主要因子

为了去除有相互联系因素所以本文采用了主成分分析法，其过程如下：

对相关数据进行处理，计算出相关矩阵和其特征值，再求主成份，通过精度分析，计算出主因子的荷载矩阵

（1）计算数据表的相关矩阵S。

    

表六  相关矩阵
		VAR00001	VAR00002	VAR00003	VAR00004
相关	VAR00001	1.000	.413	-.383	.134
	VAR00002	.413	1.000	.339	.721
	VAR00003	-.383	.339	1.000	.688
	VAR00004	.134	.721	.688	1.000

（2）计算出主因子的荷载矩阵

    表七 主因子的荷载矩阵

区域	最大时间偏差	最大工作量偏差	人口密度	交巡警服务台数
	4.859900	3.140000	2.727273	20
	1.149630	0.0750000	0.203883	8
	14.52475	3.753000	0.221719	17
	15.13090	1.756000	0.190601	9
	12.88400	1.756000	0.175926	15
	7.379220	2.950000	0.193431	11

由初始因子载荷矩阵可知：最大时间偏差、最大工作量偏差、人口密度、交巡警服务台数。

2．模糊综合评判

（1）建立影响该市现有交巡警服务平台设置方案因素域

（2）建立等级域

（3）在影响该市现有交巡警服务平台设置方案因素域U与等级域V之间进行隶属度分析，建立模糊关系矩阵

                  （10）

矩阵中：表示因素域U中第i个因素对于等级域中第j个等级的隶属度。

（4）模糊综合评价模型及其值的计算

 该市现有交巡警服务平台设置方案模糊综合评价B等于W与R两个矩阵的乘积，即

                            （11）

其中：为两个因素对该市现有交巡警服务平台设置方案影响指标的权重，且满足，因此B的该市现有交巡警服务平台设置方案影响评价结果等于,就是最终的评价结果，也就是此对象具体属于那个影响等级。

3．建立评价集

该市现有交巡警服务平台设置方案影响大小是相对且模糊的，不可能定性描述，是属于模糊集理论。那么根据模糊数学理论[1]，可以直接把主成分分析中提取的四个影响因素，根据指标大小不同分为五个等级分别为很不合理，不合理，较合理，合理，很合理。根据文献[3,4]的分级标准，我们可以把个指标的分级情况表示如下：

表八 等级划分指标

	很合理	合理	较合理	不合理	很不合理
最大时差	3	6	9	12	15
台数	10	13	16	19	21

4．建立隶属函数

该市现有交巡警服务平台设置方案影响是一个模糊概念，它分级标准也是模糊的，用隶属度来刻画分级界线较为合理。以各指标的五级标准，作5个级别的隶属函数。

（12）       （13）

    （14）          （15）

             

  （16）     （17）

   （18）      （19）

    （20）    （21）

  5．层次分析法确定权重系数

在主成分分析中最大时差与服务台数分别关于第一、第二主成分的关系度为：0.943,0.954，于是将其归一化处理可得两个因数的权重为：0.49,0.51  6. 该市现有交巡警服务平台设置方案

表九 该市现有交巡警服务平台设置方案

区	v1(很合理	v2(合理）	v3(较合理	v4(不合理	v5(很不合理	等级
	0.3425	0.6652	0.4576	0.56	0.425	合理
	0.779	0.3978	0.4432	0.445	0.334	很合理
	0.3542	0.656	0.4782	0.576	0.443	合理
	0.3423	0.676	0.495	0.4876	0.287	合理
	0.4674	0.327	0.499	0.6987	0.57	不合理
	0.8221	0.34	0.6788	0.65	0.2341	合理

5.5确定最佳围堵方案

 5.5.1最佳围堵方案模型的建立

    为最快速的抓住犯罪嫌疑人，本文认为将所有嫌疑犯将要去的节点封锁，直到嫌疑犯被完全包围在警方的封锁内时，嫌疑犯被抓获，即警方封锁的路口越多嫌疑犯被抓住的可能性就越大。嫌疑犯在A区作案并逃跑因此要调动A区所有警力封锁各出入口，但是警方是在嫌疑犯逃跑三分钟之后接到的保案，因此警方几乎不可能把嫌疑犯完全封锁在A 区，因此警方必须保证封锁嫌疑犯从A区逃跑到的下一个路口。基于以上分析，本文建立以尽可能多的封锁路口为目标的整数规划模型。

                      （22）

 5.5.2模型求解及结果分析

    由以上优化模型求得点12,14,16,21,22,23,24,62可以被区交巡警及时封锁，但是有五个点：28,29,30,38,48不能被封堵，又因为点28,29通入区，且间分别为：8.9,9.1，此时间内可以充分让区交巡警封堵此两入口，同理可得38点。对于30，48两点，在区交巡警还未开始追击时，已经可以流入市，于是，我们的建议方案是：在市交巡警开始追击时立刻围堵30,48这两点。

六、模型评价

6.1模型优点

    1．本文在第一问中同时考虑出警时间和工作量均衡，建立多目标规划模型，是结果更切合实际。

    2．本文分别对各平台到各点的时间偏差赋权值，并考虑出警时间于工作量均衡之间的权重关系，是模型可以对各种情况的城市惊醒管辖区域分配，是模型更加人性那个化。

    3．对重大事件发生时对全区的警力电动。本文不仅给出了调动方案并将没有封锁任务的7各平台作为机动部分随时支援不能顺利到达封锁点的平台，确保路北被快速全面封锁。

6.2．模型缺点

    在最佳围堵方案确定的模型中，本文假设嫌疑犯不走回头路，且认为封锁的路口越多嫌疑犯被抓住的可能就越大，因此忽略了一些实际情况，且时间上不够优化。

七、模型改进

    将嫌疑犯在逃跑种鸽各种可能性都考虑到模型中去，使模型更适用于实际，并且添加时间目标函数，以确保最快的抓住嫌犯。

八、参考文献

[1] 衷平，沈珍瑶等，石羊河流域水资源短缺风险敏感因子的确定，干旱区资源与环境，19（2）：81-86，2005。

[2] 韩宇平，阮本清，解建仓，水资源系统风险评估研究，西安理工大学学报，19（1）：41-45，2003。

[3] 刘涛，邵东国，水资源系统风险评估方法研究，武汉大学学报工学版，38（6）：66-77，2005。

[4] 黄明聪，解建仓，阮本清等；基于支持向量机的水资源短缺风险评价模型及其应用，水利学报，33（3）：255-299，2007。

[5] 阮本清，韩宇平，王浩等，水资源短缺的模糊综合评价，水利学报，36（8）：906-912，2005。

[7] 熊义杰，运筹学教程，北京：国防工业出版社，2004.[8] 宁艳梅，应急系统选址的模型与算法研究，西安：西安电子科技大学经管学院，2007.