2011高教社杯全国大学生数学建模竞赛B题参考答案

交巡警服务平台的设置与调度优化分析

摘 要

本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。并分别对题目的各问，作了合理的解答。

问题一： （1）、根据题目所给数据，确定各节点之间的相邻关系和距离，利用Floyd算法及matlab编程求出两点之间的最短距离，使其尽量满足能在3分钟内有交巡警平台警力到达案发结点的原则，节点去选择平台，把节点分配给离节点距离最近的平台管辖，据此，我们得到了平台的管辖区域划分。

（2）、我们对进出该区的13条交通要道实现快速全封锁的问题，我们认定在所有调度方案中，某种方案中耗时最长的的围堵时间最短即最佳方案，利用0-1变量确定平台的去向，并利用线性规划知识来求解指派问题，求得了最优的调度方案。

（3）、在确定增添平台的个数和具体位置的问题中，我们将尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。我们先找出到达每个平台的时间都超过三分钟的节点，并尝试在这些节点中选取若干个作为新的平台，求出合理的添加方案。

问题二： （1）、按照设置交巡警服务平台的原则和任务，分析现有的服务平台的设置是否合理，我们以各区覆盖率作为服务平台分布合不合理的评价标准，得到C、D、E、F区域平台设置不合理。并尝试一些新的设置方案使得设置更为合理，最后以覆盖率最低的E区为例，使用一种修改方案得到一个比原方案更合理的交巡警服务平台的设置方案。

（2）、追捕问题要求在最快的时间内抓到围堵罪犯，在罪犯和警察的行动速度一致的前提假设下，我们先设定一个具体较小的时间，编写程序检验在这个时间内是否可以成功抓捕罪犯，不行则以微小时间间隔增加时间，当第一次成功围堵时，这个时间即为最佳围堵方案。

关健字： MATLAB软件，0-1规划，最短路，Floyd算法，指派问题

一、问题重述

“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在

市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

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

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

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

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

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

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

二、模型假设及符号说明 2.1、模型假设

1、假设各服务台职能，警力配备足以处理辖区内正常事故。 2、假设不考虑人口密度对警察办案的具体影响。 3、假设突发事件只发生在路口节点。

4、假设警察出警的地点都是平台处，不考虑巡警的情况。

5、假设交巡警接到报警后立即出警，且不考虑路面交通状况。 6、假设嫌疑人逃跑速度与警车的速度相同。 2.2、符号说明

n1(a,b)

道路起点坐标

n2(c,d) 道路终点坐标

?xi,yi? 第i平台的坐标

d?i?

DA

第i条道路，起点到终点一步可达的距离

各个节点的最短路距离

分配矩阵

B 中间过渡矩阵 出口到平台的距离 案发率距离 增加节点矩阵

CFGco 计数

mm 每行中除了0以外的最小值

gg 每行中除了0和mm的最小值

三、模型建立及求解

3.1、为了模型的建立与分析，先模拟出道路图

400380360340320300280260200250300350400450

图1 A区交通图

程序：lp1003

6005004003002001000050100150200250300350400450500

图2 全市交通图

程序：shitu

3.2、问题1的模型建立及求解：

3.2.1、管辖范围的求解

此问要求我们利用数据及附图，将各路口节点划分给最适合的服务平台，并要求各服务台管辖的范围内有突发事件发生时，尽量能在3分钟内有交巡警到达事发地（此时交巡警的行驶距离为3km），换算到比例图上，也就是30mm。本题，不考虑其他因素，只注重唯一因素——距离。所以，我们第一步用floyd算法求出各个节点之间的最短距离D。

1、根据题中所给的各个节点的坐标，用matlab计算出任意两点之间的距○

离，得到92*92的邻接距离矩阵：

?d11??d21d????????d92?1d12d22??d92?2????????d1?92??d2?92??? ????d92?92?其中dij分两种情况：当第i个节点与第j个节点相邻时，dij为两个节点的相邻距离。不相邻时，dij为一个充分大的数。

②、运用Floyd算法，求出任意92个节点到任意92个节点的最短距离，得

到最短距离矩阵，根据问题需要，我们截取所得矩阵前20行，即任意20个服务平台间到任意72个节点（没有建立平台的节点）的最短距离矩阵D：

?D11??D21D????????D20?1D12D22??D20?2????????D1?72??D2?72??? ????D20?72?因为服务平台的编号为1到20，所以取D的前二十行，后七十二列为观察对象。在观察对象中，取出每列的最小值，计入到原本为设为全0的20?72的矩阵A的相应的位置。

对于每一列而言，每列的最小值是最有可能小于3分钟的，如果最小值都不满足这个条件，那么对于这列对应的节点而言，就不存在三分钟可以到达的平台。

程序：pingtai ③由此，最后每个节点都会归属于某个服务平台，用matlab编程得出结果并绘制了管辖区域图如表1

服务平台编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

管辖范围（节点编号） 1、67、68、69、71、73、74、75、76、78 2、39、40、43、44、70、72 3、54、55、65、66 4、57、60、62、63、64 5、49、50、51、52、53、56、58、59 6、47 7、30、32、48、61 8、33、46 9、31、34、35、45 10、26 11、27 12、25 13、22、23、24 14、21 15、28、29 管辖容量 10 7 5 6 9 2 5 3 5 2 2 2 4 2 3

本文来源：https://www.bwwdw.com/article/slqv.html