2011高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 陇东学院
参赛队员 (打印并签名) ：1. 任耀辉 2. 魏斌 3. 邵文娟 指导教师或指导教师组负责人 (打印并签名)： 冯积社 董文瑾
日期： 2011 年 9 月 12日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
交巡警服务平台的设置与调度的设计方案
摘要
由于平面区域不能用圆来不重不漏地覆盖，我们采用正六边形来覆盖，但根据道路口疏密状况和人口数量、区域面积的差异，最后决定对于不同区域采用不同尺寸的正六边形，来覆盖城区各道路的方法来进行各个交巡警服务平台的管辖范围的初次预分配，对于初次预分配的结果按各个道路口到各服务平台的最短路的里程乘以发案率的和，得到各个服务平台的总工作量。按相邻区域内服务平台工作量相当的标准进行调整，用Dijkstra算法求得那些重复包含和漏掉的路口，及那些距离邻近的路口节点重新分配到邻近的正六边形内，从而得到最终的管理范围。由于要力求工作量均衡，就目前的服务平台而言数量不足，通过采用最短路的选址方法来确定，应就需再增加3个服务平台，具体位置分别在标号为29、72、90的三个路口。
对于重大突发事件，需要调整全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，采用最优化及规划法得到了调度方案。
根据六个区人口密度，交通路口的疏密程度不同的现状。采用与A区相同的方法来计算，发现多个区的不同交巡警服务平台的工作量相差悬殊，极不平衡。这说明若仅考虑路程和发案率及仅坚守自己的城区的调度方案是不合理的，应将六个区的各个服务平台的管辖范围适时作出调整，既有分工又要注意合作，协同作战，要有全市全局的思想和行动。
如果该市地点P处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。我们可以求得一个半径为2km、P点为圆心的圆域，对于这个区域内的服务平台，要求采用追的办法，赶向P点，对于圆周外的服务平台，要求其派车堵住相应的路口，采用堵的策略。
本文的方案是静态的，而警车始终在服务平台内，没有考虑到实际警车在返程途中的情形。可以采用GPS定位与先进的通讯手段，采取动态发布出警信息给警车，让其根据自己所处的位置，随时调整出警的路线，这样更能高效地完成自己的职责。
关键词
服务平台、初次预分配、Dijkstra算法、调度
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. 平台内有足够的警车可供调用（A区每个服务平台有5辆警车，B区有9辆等）； 3. 本模型中仅考虑出警的问题没有考虑到达了事发地处理时间和返程等问题； 4. 假设突发事件在各个道路上的发案率就是其路口的发案率； 5. 假设交巡警在接到报警后，以最短路径到达事发地点。
三、符号说明
d： 表示任意两点(xm,ym)、(xn,yn)之间的距离；
wi： 第i个服务平台的工作量，(i?1,2,,20)； ci： 第i节点的发案率；
wj： 第j个交叉路口到它管辖的平台的最短路； Bi： 第i个服务平台的总工作量；
L?vi?： 与它连通道路中的两个节点之间的距离； tmax： 13个交通要道全部被封锁所需的最大时间；
2
Q(i)： 第i个服务平台所覆盖的节点集合。 C(i)： 集合Q(i)中元素之和；
L(k)： 第k个区域内所有节点，?k?A,B,C,D,E,F?。
四、问题分析
对于问题（1），如何为A区交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。
我们按常规思考方法是：以服务平台为中心，以3分钟警车所走的路程为半径画圆，由题意知警车速度为60km/h，即D=3km，即以各个服务平台为中心以D=3为半径划分管辖范围（见图一），
这种作法没有实际意义，重复率太高，另外也没有考虑每个路口的发案率.我们必须另找办法，从相关知识有，对于平面内的一区域，若用圆来划分是无法实现的，我们可以用正六边形来划分.
图1 用圆来初步覆盖区域图
图3
图2
但由于具有地理位置和道路的变化，发案率的不同，我们不可能在A区（全市范围）用完全大小尺寸的六边形来划分，我们可以根据到路口的疏密程度在不同的地域选用不同大小的六边形来划分。
3