小组人数：3

模型建立： 

程序编写： 

论文撰写： 

目录

一．摘要

二．问题重述

三．问题分析与建模思路

四．基本假设

五．符号说明

六．模型的建立与求解

七．模型的评价与推广

八．参考文献与附录

一．摘要

是现代社会不可或缺的角色，肩负着执法、治安、提供社会服务等重要职责。为了更好更有效的实现这些只能，必须设立交巡警服务平台。这些平台需要合理地分布在城市的各个地区和交通要道，这样不仅可以及时响应出警到达案发现场，在遇到重要的或者突发的事件时也能高效的通过联合调度行动起来。

该论文就交巡警服务平台的设置与调度等实际问题，针对提出的5个问题分别给出具体的解决方案并给出结果。

问题一：

（1）题目要求根据已知20个交巡警服务平台的位置，为它们分别分配各自的管辖范围，使其能在3min内到达自己管辖区域内的事发地点。

对于此问题本文建立最大集合覆盖模型，建立了A区街道结点连通性的邻接矩阵。通过对该邻接矩阵进行优化，建立了带权边邻接矩阵。借助floyd多源最短路算法并利用数学软件MATLAB进行分配求解，最后得到A区现有每个巡警服务台的管辖范围如表1。

（2）题目要求对13条交通要道实现快速全封锁，我们以所用时间最少为目标，引入0-1变量，建立该问题的0-1规划模型，并借助数学软件LINGO进行求解，求解结果表明需要8.05分钟可以实现快速封锁。

（3）题目要求以交巡警服务平台工作量尽量均衡以及出警时间尽量短为前提，确定增设平台（2~5）的具体数目及位置。              

     由问题（1）的分配结果可知，在现有巡警服务台的设置下：①还有6个路口在案发时巡警不能在3min之内到达，即某些地方出警时间过长；②我们根据巡警服务台的工作量的方差定义工作量不均衡度，结果显示：此时服务台的工作量不均衡度为8.4314。

为了解决上述出警时间过长与工作量不均衡的问题。我们建立集合覆盖的0-1规划模型，求解结果表明：在增加4个平台的情况下，可以解决出警时间过长的问题。在此基础上我们优化分配方案：在增加4个巡警服务台的情况下，使平台的工作量的不均衡度降为3.0742。增加的4个巡警服务台的路口标号见表8。

问题二：

（1）题目要求针对全市六个城区的具体情况，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。这里本文设定了两条原则，原则一：警力必须在案发3分钟之内到达案发地点；原则二：交巡警服务台的工作量尽量均衡，出警速度尽量快。

根据以上两个原则对该市现有交巡警服务台的设置方案的合理性 进行评价，评价结果显示 ：①全市有138个路口，在案发时交巡警不能在3min之内到达；②此时的不均衡度已达40.3。基于上述两点，现有的交巡警服务台设置不合理。

由于我们认为现有的交巡警服务平台的设置略有不合理，所以我们你拟定以下两个调整部署的优化方案。

方案一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；方案二：保持现有巡警服务台的个数，但对其位置进行调整。 

（2）题目假设市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。设计总体调度全市交巡警平台的最佳围堵方案，使其能够尽快地抓捕嫌疑人。

 本问题实质是单目标规划问题，我们建立0-1规划模型，以交巡警围堵时间最短为目标，以成功围堵条件 。对于巡警的成功围堵，可以转化为二部图的完全匹配，求得最佳围堵方案完全匹配，原始方案和两种优化的求解结果见表15、表16和表17。

 关键字：最大集合覆盖  0-1规划模型 FLOYD算法   MATLAB软件  LINGO软件

二．问题重述

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

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

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

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

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

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

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

三．问题分析与建模思路

问题一：

（1）题目要求为A区各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。本文引入经典离散定位理论中的最大集合覆盖模型进行求解。

记I={1，2，3，…,92}为城区A的所有路口节点集合，J={1，2，…，20}为城区A巡警服务台的节点集合，ｃij为i交巡警服务台到达j路口的最短距离。

引入0-1 变量i∈∈I,j∈∈J，当路口i分配给巡警服务台j管辖是为1，当路口i不分配给巡警服务台j 管辖是为0。即：

由题目的要求可知，当ｃij＜3min时，路口ｉ可能分配给巡警服务台ｊ，也可能分配给其他可在3min 到达i 路口的其他巡警服务台，而不分配给平台j ，故此时s i j＝0。

根据上述的分配原则及每个路口只由一个巡警服务台进行管辖、每个巡警服

务台至少要管辖一个路口，可建立最大集合覆盖模型，并借助数学软件MATLAB

进行求解。

（2）该问题要求当发生突发事件时，要调度全区20 个交巡警服务平台的警力资源，对进出A 区的13 条交通要道进行快速全封锁，且每个平台的警力最多封锁一个路口。本文将问题转化为：从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）可知现有巡警服务台的工作量极其不均衡且有些地方出警时间过长。针上述问题，题目要求再增加2—5个巡警服务台来解决上述问题。

本文首先按照（1）、（2）中的方法建立集合覆盖的0-1规划模型，然后利用MATLAB 对模型进行求解，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加巡警服务台的数目与位置。

问题二： 

（1）本文定义了两个评价原则： 

原则一：巡警能在3min之内到达案发路口 

原则二：巡警服务台的工作量均衡度尽量小。 

根据以上两个原则对该城区现有巡警服务台的设置方案的合理性进行评价。     

若现有巡警服务台的设置不合理，本文则提出三种方案对全城的巡警服务台

设置进行优化：  

方案一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；     

方案二：保持现有巡警服务台的个数，但对其位置进行调整； 

方案三：不考虑现有巡警服务台的设置情况，重新确定全城的最佳巡警服务

台数目与位置。 

2）当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发

3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台 警力围堵嫌疑犯。因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌 疑犯逃跑方向，所以此问题可转化为以下模型：对于任意时间t，嫌疑犯驾车跑的最大范围为：在t+3时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，记为Q将Q的边界点集记为。所谓最快围堵方案，即寻找一个最短时间t,适当的调配巡警警力，使其在时间t内能够到达边界点，这样嫌疑犯就被控制在区域Q中了，此时嫌疑犯将无法逃脱。

四．基本假设

1.假设每个巡警服务台的职能和警力配备基本相同；

2.假设每个路口只由一个巡警服务台进行管辖；

3.假设每个巡警服务台至少管辖一个路口；

4.假设巡警都按最短路径到达各案发路口；

5.假设犯罪案件都在路口上发生；

6.假设在重大案件发生时，每个平台都有能够封锁一个路口的能力；

7.工作量：每个巡警服务台所管辖范围内的所有路口案发率之和；

8.出警时间：巡警到达案发路口所需时间；

9.假设逃犯的逃跑速度等于警车的行驶速度；

10.假设巡警在接到报案后并不知道逃犯的逃跑方向；

五．符号说明

1.Cij：为交巡警服务平台j到达路口i的最短距离，其中：i=1,2…92，j=1,2…20；

2.uij：为路口i与路口j之间的最短距离，其中：i=1,2…92，j=1,2…92；3.                                      ，其中：i=1,2…92，j=1,2…20； 

4.                      ，其中：i=1,2…20，j=1,2…92；

5.                                     ，其中：i=1,2…20，j=1,2…92；

6.Cj：j交巡警服务平台的工作量，其中：i=1,2…92；

7.  ：平均工作量；

8.Ini：i路口的发案次数，其中：i=1,2…92；

9.p：工作量不均衡度；

10．

11.Iisolated：C类路口的集合；

12.Qi+3：嫌疑犯在（t+3）min内行驶的最大区域；

13.    ：嫌疑犯在（t+3）min内行驶的最大区域边界点集；

六．模型的建立与求解

6.1问题一（1）：管辖区域的确定---最大集合覆盖模型

6.1.1模型建立：

最大覆盖函数：根据问题一（1）的分析确定最大覆盖函数为：

满足条件：

1）因为每个路口只由一个巡警服务台管辖，所以： 

2）根据实际情况每个巡警服务台管辖的路口数至少等于1，所以。

综上所述，得到最大集合覆盖模型为：

满足：

                                （1）

6.1.2 模型求解：

1.最短路径矩阵 U92×92的建立

本文选用floyd算法确定城区A任意两个路口之间的最短路径矩阵U92×92。

floyd 算法为：任意两点(i, j)之间的最短路径（记为Dij ）等于从i 出发到达j点的以任一点为中转点所有可能方案中，距离最短的一个。即：

Dij=min(Dij,Dik+Dkj,…),1≦k≦n,n为节点总数。

算法为：

U(1)ii=0,

U(1)ij=wiji≠j,

U(k+1)ij=min{u（k）ij,u(k)ik+u(k)kj}，i,j,k=1,...,n

在上式中，临时标号u（k）ij是不通过k,k  1, ,n节点（i, j除外）时从节点i到节点j 的最短路径。

通过上述算法，利用数学软件MATLAB 计算出各节点的最短路径，组成一个最短路径矩阵U92×92。矩阵中，元素ui1j为从路口i1 到路口j的最短距离，其中i1=1…92,j=1…92。

2.集合覆盖矩阵的建立K92×92   

以巡警服务台能否在3min内到达案发路口为分配标准，将上述最短路矩阵转化为集合覆盖问题，即0-1覆盖问题。转化方法为：                                               (2)

此时将得到集合覆盖矩阵K92×92。此时从矩阵中可以得到巡警服务台在只考

虑能在规定时间内到达的初始分配情况。

3.最终分配方案的确定

由集合覆盖矩阵K92×92将92 个路口分为A、B、C 三类：

A 类：已只由一个巡警服务台进行管辖；（直接分配）

B 类：可被多个巡警服务台进行管辖；(按就近原则分配)

C类；还不能被任何巡警服务台进行管辖；（按就近原则分配）

处理的时候按照A、B、C的顺序依次进行；可以看出在处理完B类之后仍有标号为28、29、38、39、61、92的6个任何巡警服务台都不能在规定时间内到达规定路口。

最终分配方案如下表所示：

表2     最终分配方案

6.2.1模型建立：

记20个巡警服务台分别为i=1...20，记13条交通要道分别为j=1…13。记巡警服务台i与要道j间的距离为cij。 

决策变量：引入0-1变量xij，若选择巡警服务台i对要道j进行封锁，记xij=1,否则记xij=0，即:

        (3)

此为问题的决策变量，共260个。

目标函数：本题要求对13条要道进行快速封锁，即要求巡警服务台对13条交通要道进行全部封锁所需时间最短的调度方案。在假设警车行驶速度相同的条件下，可转化为求巡警服务台与要道最大距离最短的调度方案。则本题目标函数为f2=max(cijxij),其中i=1…20,j=1…13。

约束条件：根据问题的要求，每个交通要道必须有一个巡警服务台对其进行封锁，即对于j=1…13, 应有：      ，对于i=1…20, 应有：      。

综上所述，此问题的优化模型为

6.2.2模型的求解：

本文利用MATLAB和Lingo进行编程求解，程序见附录，具体步骤如下：

1.求解cij。整理附件2中的数据，根据Floyd算法，利用MATLAB编程，得到20个巡警服务台距离13条交通要道的最短距离cij。 

2.按照附件2中20个巡警服务台和13条交通要道的顺序进行编号，引入决策变量xij，根据已经建立的模型中的约束条件和目标函数，利用Lingo9.0求得全局最优解。 

3.求解结果显示，目标函数的最小值为8.0155，即封锁13条交通要道的最少时间为8.0155分钟。下表列出了A区交巡警服务平台警力合理的调度方案。

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

6.3.1模型建立与问题求解：

1.初步分配方案的确定

同样运用问题一（1）中的方法可得到：距离C类各个路口小于3km的路口集合，如下表：

表4     距离C类各个路口小于3km的路口集合

集合覆盖模型的建立

首先，建立覆盖矩阵T6×13，其元素：

        （5）

i=1,2…6,j=1,2…13。

其次，建立集合覆盖模型：

        满足：

其中，

    最后，利用MATLAB运用搜索法得到：至少从候选集Q中选出4个路口来设置巡警服务台，才能解决出警时间过长的问题。此时共有48种可能的分配方案。分别如下表所示：

表5     72种分配方案

1）为每种方案中的24个巡警服务台分配管辖范围。

步骤一：

同样按照问题一（1）中的求解过程1和2可得到有24个巡警服务台的集合覆盖矩阵K92×24。 

步骤二：

此时由上述集合覆盖矩阵可将城区A的92个路口分为A、B两类：

A类：已只由一个巡警服务台进行管辖；

B类：可被多个巡警服务台进行管辖；

将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。对于B类的路口，在综合距离最近与工作量平均的情况下来进行分配。即：首先选择距离路口i最近的巡警服务台j(j=1,2…24),然后利用公式            ,计算巡警服务台j的工作量cj，若cj≦  ,则将路口i分配给巡警服务台j管，否则选择次短距离的服务台进行同样考虑。最后得到每种分配方案中24服务平台的管辖范围。

步骤三：

根据平局工作量公式          与工作量不均衡度公式             利用MATLAB分别对48种分配方案中服务台的工作量不均衡度计算得：

表6     72种分配方案的工作量不均衡度

表7     满足题目一（3）要求的4个巡警服务台的路口标号

表8     24个交警服务台的管辖范围

6.4.1现有巡警服务台设置的合理性的讨论

本文定义了两个评价原则：

原则一：巡警能在3min之内到达案发路口

原则二：巡警服务台的工作量均衡度尽量小。

依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。

讨论现有设置方案是否满足原则一

全城六区A，B，C，D，E，F现有个80巡警服务台、582个路口，运用问题一（1）中的算法，得到全城C类路口的数目与位置，如下表：

表10     C类路口的位置标号

讨论现有设置方案是否满足原则二

运用问题一（3）中的方法，为每个巡警服务台分配管辖范围，并计算工作量及巡警服务台的工作不均衡度。结果如下：

表11     现有配置下每个服务台的工作量

由表中数据可得：在现有配置下，其中有个7巡警服务台的工作量已达到40.4，而其中还有10巡警服务平台的工作量仅为1.6，所有巡警服务台的工作量不均衡度为40.3。可见，此时巡警服务平台的工作量极其不均衡。

根据上述1、2的讨论可知：现有巡警服务台的设置极其不合理。

6.4.2巡警服务台设置的优化

由现有巡警服务台的分配不合理的情况，我们提出两种优化方案。

方案一——“静态增加”优化方案

此方案的优化思想为：在不改变现有巡警服务台的位置的情况下，适当增加巡警服务台的数目，从而使城区A中无C类路口且每个巡警服务台的工作量尽量均衡。

由上题6.4.1中的计算结果可知，全城共有138个C类路口。将其组成需求点的集合，同样利用求解问题一（3）中的方法与步骤，得到新增加的最小巡警服务台数目与位置、此种方案下巡警服务台的工作量和工作量的不均衡度。

方案二——“动态”优化方案

此方案的优化思想为：在不改变现有巡警服务台数目的情况下，对80个巡警服务台的位置进行重新定位，从而使城区A中的C类路口数目尽量少且巡警服务台的工作量尽量均衡。

模型的建立

根据此方案的优化思想，首先确定候选集为：J={1,2,…582},需求点集为：

I={1,2,…582}。然后，建立最大集合覆盖模型，从候选集中选出80个点以满足使城区A中的C类路口数目尽量少且巡警服务台工作量尽量均衡。模型如下：

                    满足：

                                      （7）

其中：

6.5问题二（2）：围堵方案的确定

6.5.1模型建立

按照问题分析，本文定义相关概念如下：

Qt+3:嫌疑犯在（t+3）min内行驶的最大区域;

:嫌疑犯在（t+3）min内行驶的最大区域边界点集；

P：现有所有服务台集合

本文以时间t为目标，建立优化模型如下：

Min t

模型的条件中，对于是否可以适当分配P 中的警力，可以在t 时间内到达

中所有点。可以抽象为图论中二部图的完全匹配问题，如果可以分配警力使其和中的边界点一一匹配，则。

七．模型的评价与推广

1.优点：

1.本文把具体的实际问题抽象成函数模型、集合模型、规划与优化模型、图论与表格模型，有效的解决了实际问题吗，有助于交巡警服务平台的设置以及案发时候对案发现场及周边道路的封锁。

2.本文采用离散的定位模型对城区交巡警服务平台进行优化布局，较为全面地考虑了一些影响因素，如案发率、出警速度、交巡警服务平台的工作量等，采用的算法也是精度高、效率高，较为形象，使处理实际问题时能够如鱼得水、方便快捷。

3.整个模型的建立思路清晰，遵循可操作性原则，可比性原则及科学性原则，该模型建立了在较为理想状态下交巡警平台的最优设置，缩短了出警时间，提高了效率。

2.缺点：

    1.本文还未对案发的时间段进行综合考虑。由于各个时间段案发几率不同，尤其是夜晚突发事件会较多，警力的部署和工作量的均衡方面还有待优化，例如在夜晚加强对路口地点的工作量分配。

    2.本文还未对人口密度进行综合考虑。在城区，人口密度有较大差异也是一个实际情况，在设置交巡警服务平台时还应该对居民区及其附近重点布置，以保证城市居民的安全，使交巡警能在最快的时间内赶到现场处理问题。

    3.考虑到交不能同时，以防交的时候有突发事件发生，这点上应该根据每片交巡警服务平台设置的均衡性，分配不同的交时间，保证相邻的两个交巡警服务平台不会同时交。

    4.本文在服务台设置优化的步骤中没有涉及在不考虑现有巡警服务台的设置情况下，重新确定全城的最佳巡警服务台数目与位置的优化方案。

    5.在实际应用中，还应考虑道路是否通畅，交通工具是否能够通过等诸多现实问题，才能真正运用于实际的生活中。

3.模型推广：

    本题模型较好的解决了交巡警的出警问题，追捕逃犯的封堵路口的分配问题，本模型除此之外，还可用于消防救援的最优安排问题，安全事故的应急救援问题，出租车省油的最佳路径问题以及加油站的点位设置问题等现实生活中。

总的来说，在实际生活中有很大的利用价值，一定程度上可作为参考。

八．参考文献与附录

[1] 谢金星，优化模型与LINDO/LINGO软件，北京：清华大学出版社，2006年。

[2] 王沫然，MATLAB与科学，北京：电子工业出版社，2008年。

[3] 方世昌，离散数学，西安：西安电子科技大学出版社，2009年

附录见附件下载本文