《2011高教社杯全国大学生数学建模竞赛b题参考答案》由会员分享，可在线阅读，更多相关《2011高教社杯全国大学生数学建模竞赛b题参考答案（25页珍藏版）》请在金锄头文库上搜索。
1、交巡警服务平台的设置与调度优化分析摘 要本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。并分别对题目的各问，作了合理的解答。问题一：（1）、根据题目所给数据，确定各节点之间的相邻关系和距离，利用Floyd算法及matlab编程求出两点之间的最短距离，使其尽量满足能在3分钟内有交巡警平台警力到达案发结点的原则，节点去选择平台，把节点分配给离节点距离最近的平台管辖，据此，我们得到了平台的管辖区域划分。（2）、我们对进出该区的13条交通要道实现快速全封锁的问题，我们认定在
2、所有调度方案中，某种方案中耗时最长的的围堵时间最短即最佳方案，利用0-1变量确定平台的去向，并利用线性规划知识来求解指派问题，求得了最优的调度方案。（3）、在确定增添平台的个数和具体位置的问题中，我们将尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。我们先找出到达每个平台的时间都超过三分钟的节点，并尝试在这些节点中选取若干个作为新的平台，求出合理的添加方案。问题二：（1）、按照设置交巡警服务平台的原则和任务，分析现有的服务平台的设置是否合理，我们以各区覆盖率作为服务平台分布合不合理的评价标准，得到C、D、E、F区域平台设置不合理。并尝试一些新的设置方案使得设置更为合理，最后以
3、覆盖率最低的E区为例，使用一种修改方案得到一个比原方案更合理的交巡警服务平台的设置方案。（2）、追捕问题要求在最快的时间内抓到围堵罪犯，在罪犯和警察的行动速度一致的前提假设下，我们先设定一个具体较小的时间，编写程序检验在这个时间内是否可以成功抓捕罪犯，不行则以微小时间间隔增加时间，当第一次成功围堵时，这个时间即为最佳围堵方案。关健字： MATLAB软件，0-1规划，最短路，Floyd算法，指派问题一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个
4、交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快
5、速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型假设
6、及符号说明2.1、模型假设1、假设各服务台职能，警力配备足以处理辖区内正常事故。2、假设不考虑人口密度对警察办案的具体影响。3、假设突发事件只发生在路口节点。4、假设警察出警的地点都是平台处，不考虑巡警的情况。5、假设交巡警接到报警后立即出警，且不考虑路面交通状况。6、假设嫌疑人逃跑速度与警车的速度相同。2.2、符号说明道路起点坐标 道路终点坐标 第平台的坐标第条道路，起点到终点一步可达的距离 各个节点的最短路距离 分配矩阵 中间过渡矩阵 出口到平台的距离 案发率距离 增加节点矩阵 计数 每行中除了0以外的最小值 每行中除了0和mm的最小值三、模型建立及求解3.1、为了模型的建立与分析，先模拟
7、出道路图图1 A区交通图程序：lp1003图2 全市交通图程序：shitu3.2、问题1的模型建立及求解：3.2.1、管辖范围的求解此问要求我们利用数据及附图，将各路口节点划分给最适合的服务平台，并要求各服务台管辖的范围内有突发事件发生时，尽量能在3分钟内有交巡警到达事发地（此时交巡警的行驶距离为3km），换算到比例图上，也就是30mm。本题，不考虑其他因素，只注重唯一因素距离。所以，我们第一步用floyd算法求出各个节点之间的最短距离D。、根据题中所给的各个节点的坐标，用matlab计算出任意两点之间的距离，得到92*92的邻接距离矩阵：其中分两种情况：当第i个节点与第j个节点相邻时，为两个
8、节点的相邻距离。不相邻时，为一个充分大的数。、运用Floyd算法，求出任意92个节点到任意92个节点的最短距离，得到最短距离矩阵，根据问题需要，我们截取所得矩阵前20行，即任意20个服务平台间到任意72个节点（没有建立平台的节点）的最短距离矩阵：因为服务平台的编号为1到20，所以取D的前二十行，后七十二列为观察对象。在观察对象中，取出每列的最小值，计入到原本为设为全0的的矩阵A的相应的位置。对于每一列而言，每列的最小值是最有可能小于3分钟的，如果最小值都不满足这个条件，那么对于这列对应的节点而言，就不存在三分钟可以到达的平台。程序：pingtai由此，最后每个节点都会归属于某个服务平台，用ma
9、tlab编程得出结果并绘制了管辖区域图如表1服务平台编号管辖范围（节点编号）管辖容量11、67、68、69、71、73、74、75、76、781022、39、40、43、44、70、72733、54、55、65、66544、57、60、62、63、64655、49、50、51、52、53、56、58、59966、47277、30、32、48、61588、33、46399、31、34、35、4551010、2621111、2721212、2521313、22、23、2441414、2121515、28、2931616、36、37、3841717、41、4231818、80、81、82、83519
10、19、77、7932020、84、85、86、87、88、89、90、91、9210表 1 服务平台管辖范围3.2.2、调度方案的求解本题，我们使用运筹学中的指派方法来解决。如果发生重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全面封锁。在全面封锁时，既需要使用最短的时间，还必须保证一个平台的警力只能封锁一个路口，这样就必然会多出7个平台。先根据给出的数据，设立出指派问题的条件矩阵C。C为，其中前十三列是A区13个出口到二十个平台的最短路距离，剩余的七列用零补齐。得到C之后，使用linprog算法，就得到我们需要的调度方案。程序：zhipai根据前
11、一问的解答我们可以得出任意服务平台到任意出口的最短距离，引入0-1变量：据此我们建立关于服务平台调度的目标函数Z：约束条件：第一个约束表示要求每个服务台只能去1个或0个出口。第二个约束表示每个出入路口有且仅有一个服务平台的警力支持。综上，我们利用linprog编程得出了最优调度方案（程序见附件），结果见表2： 平台编号24578910111213141516出口编号38624830291422241223212816距离:mm393.5245.81048277380532470表 2 出口平台调度方案通过分析这些线路，我们知道线路最长的组合为8号平台到达29号节点，它所花的时间即为封锁路口的最
12、终时间，且这个时间约为10分钟。3.2.3、平台增加个数及位置的求解本问要求在第1小问的前提下，根据服务平台的工作量不均衡及出警时间的不合理来增加服务平台的具体个数及位置，使整个交巡警服务平台系统趋于合理化。在第一小问中，我们选择D每一列的最小值，把该节点划分给离他最近的平台管辖。但这样的话，一方面会导致一部分的平台管辖的节点过多，其辖区内部的总案发率过高，而现实中，各平台辖区案发率应该相差不大。另一方面，少量节点到每个平台的最短距离都大于30mm，即到任何平台的时间都超过3min，所以，我们就需要增设一些平台。对于平台添加的原则是添加平台后使得所有节点都有平台可以在三分钟内到达。首先，我们以
13、距离出发，选择D前二十行中，其最小值大于30的列，把这些节点之间的距离从D中提取出去，组成一个方阵。在这个方阵中，选择两节点之间距离小于30mm，小于30说明此两点可以在3min内到达彼此。故可以任意删去一列，删去先出现的列。现在得到需要添加的最多平台数就是上面剩下的那些列对应的节点n。提取这些节点D中所在行，加上之前的20行，组成一个新的最短距离矩阵B。其中A,B均为20+n*92的矩阵，A是全0阵，B是D中的一部分，进行五次迭代，出现我们需要的平台及对应的辖区。迭代的规则是：在B中选取每列的最小值，赋给A中相应的行列位置。找到A中不为0的位置对应的案发率，把每个位置的距离数字乘以各自的案发
14、率，并除去速度10，平台自身案发率*0.5加上。所得数字为每一个平台的判断数。逐行判断，如果某行的判断上数大于所有节点案发率平均数*2的话，就把该行中的最大数字在B中置为0。重复上述三步，五次。图 1 迭代前综合指标曲线分布与直方图服务平台编号管辖范围（节点编号）管辖容量11、67、68、69、71、73、74、75、76、781022、43、44、70、72533、54、55、65、66544、57、60、62、63、64655、49、50、51、52、53、56、59866、58277、30、32、47、48588、33、46399、34、35、4541010、2621111、2721212、2521313、22、23、2441414、2121515、3121616、36、3731717、41、42、9241818、80、81、82、83、9161919、77、7932020、84、85、86、87、88、89、9082929、2823939
