2011高教社杯全国大学生数学建模竞赛
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
交巡警服务平台的设置与调度
摘要 随着社会的发展，特别是在建设社会主义和谐社会中，警察担负着维护
国家安全，维护社会治安秩序，保护公民的人身安全，保护公共财产，预防、制止和惩治违法犯罪活动的重任。可以说，警察在社会中扮演着非常重要的角色。交巡警也是如此，但是警务资源是有限的，为了更有效地贯彻发挥警察的职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台，假设每个交巡警服务平台的职能和警力配备基本相同。那么如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源就显得尤为重要了。本文利用整数规划、弗洛伊德算法等相关知识帮忙解决以下问题。
针对问题（一）我们根据已给出该市中心城区A的交通网络和现有的交巡警服务平台，及相关数据的分析，给出各交巡警服务平台分配管辖范围，使其在3分钟内有交巡警到达事发地。
针对问题（二）在现有交巡警服务平台上，对于重大突发事件，调度全区警力资源，对该A区的13条交通要道实现快速全封锁。同时对现有交巡警服务平台不合理的地方，增加一定量的平台数目，并确定需要增加平台的具体个数和位置。
针对问题（三）按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案是否合理。对不合理的地方，请给出解决方案。同时给出调度全市交巡警服务平台警力资源对P（32）处发生重大刑事案件的犯罪嫌疑人的最佳围堵方案。
最后对模型进行了检验，通过比较模型求得的与实际统计数据比较允许在误差容许范围内，证明所建立的数学模型符合题目要求。
关键词：弗洛伊德算法、整数规划、lingo、C++
一、 问题重述
在现代社会中，警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。但是警务资源是有限的，为了更有效地贯彻发挥警察的职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。那么如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源就显得尤为重要了。
本题已经提供了本市交通网络相关的数据和交巡警服务平台，以及主城六区的具体情况和数据等。要求解决以下几个问题：
1. 在题目的要求下，给出各交巡警服务平台分配管辖范围，使其在3分
钟内有交巡警到达事发地。
2. 对于发生重大突发事件，调度全区警力资源，对该区的13条交通要道
实现快速全封锁。同时对现有交巡警服务平台不合理的地方，增加一定量的平台数目，并确定需要增加平台的具体个数和位置。 3. 分析研究该市现有交巡警服务平台设置方案是否合理。对不合理的地
方，请给出解决方案。同时给出调度全市交巡警服务平台警力资源对P处发生重大刑事案件的犯罪嫌疑人的最佳围堵方案。
二、 符号说明
1. 2. 3. 4. 5.
N表示所确定的交巡警平台的数目；
xij表示分配i处的交巡警服务平台到j处入城路口节点封锁要道；
dij表示第i个交巡警服务台到第j处入城路口节点的距离； wij表示最小生成树中i节点到j节点的权值；
~di,p表示i到事发地P点的权值；
6. 7. 8. 9.
y表示i处为关键路口节点；
iaij表示Ci和CJ对目标层O的影响程度之比；
v1 , v2 , ?, vn表示该市中所有交巡警服务平台的集合； E表示市区中所有交通路线集合；
三、 模型假设
1. 假设每个交巡警服务平台的职能和警力配备基本相同；
2. 假设每个入城路口最多只能设有一个平台的交巡警；
3. 假设交巡警平台只搬迁到本区入城路口节点或交通街道上； 4. 假设用交叉路口的节点表示交巡警的管辖范围；
5. 如果两个交巡警在3分钟之内都能到指定的交叉路口的节点，把交巡警
能最快到的交叉路口的节点作为它的管辖范围； 6. 不考虑现实中的堵车，天气等现实情况；
四、模型的进一步分析及建立
针对问题（一）
由题目要求，我们可以认为只要是交巡警能在3分钟能到的交叉路口的节点就是他的管辖范围，那么我们只需求出A区中所有路口节点之间的距离，再求出交巡警在3分钟能到达的交叉路口节点。整理题目所给的数据，由附录（一）我们可以得出A区交通网络图，同时运用附录（二）的C++源代码求出A区所有路口节点间的距离，见附录（三）则我们计算可得出下表所有交巡警能在3分钟能到达的路口节点。 针对问题（二）
由问题2.1
由附录（三）的A区路口节点间距离，同样我们可以算出每个交巡警服务平台到每个入城区路口节点的距离见下表：