问题 5： 对于设计最佳围堵方案，本文给出最佳围堵方案的原则，即在保证围堵 成功的基础上尽量使搜捕时间最短；并假设嫌疑犯与警车的速度一致。因此本文在安 排警力对全市出入市区节点进行封锁，这样可保证围堵一定成功；在此同时，也从 P 点开始建立树状模型，得到搜捕时间尽量短的封锁方案。该树状模型是依次对由 P 点 出发的每条可能路线上每个节点搜索离该节点最近的平台，以 P 点到该节点的路程与 3 分钟路程的差和平台到该节点的路程比较，来判定是否能够成功围堵，直到找到这样 的节点为止。
其方案如下：B 区：在节点 153 增设一个平台；C 区：在节点 317,239,207 处各增 设一个平台；D 区：将节点 321 号处的平台改建在 369 号节点处；E 区：在节点 392 号 增设一个平台，再将 430 号节点的平台改建在 438 号节点处；F 区：在节点 518 增设一 个平台。
问题 3：为评价 A 区交巡警平台设置的合理性，给出增设平台的具体个数和位置， 提出工作力度指标。某节点的工作力度为其所属平台到其的出警路程与该点发案率的 乘积，某平台的工作力度为其管辖范围内的所有节点的工作力度之和。根据模型算出 各个平台的工作力度并计算出平均值，在工作力度较大的几个平台的邻接区域节点处 确立增设平台数及其准确位置，使得各个平台工作力度达到平衡。得出在节点 29、30、 39、92 处增设平台。
L3 ：警车 3 分钟的行车路程；
nj ：节点 j 处的发案率；
WAi ：交巡警服务平台 Ai 的工作力度；
W A ：A 区增设新平台之前的交巡警服务平台的平均工作力度； ΔWi ：第 i 平台的工作力度与平局工作力度差值的平均值； Ln ：第 n 种搜索方案中的最长路程； Ln−m ：第 n 种搜索方案中的所有路程和；
2011 高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。
二、问题分析
本题为交巡警服务平台优化问题，需要结合警务资源有限的客观因素以及城市道 路、案发率等具体情况，合理分配平台管辖范围、调度警力资源、判断平台设置合理 性以及规划平台分布。
问题 1：为了满足在突发事件发生时，警车尽量在 3 分钟以内到达的具体要求，本 文制定了平台管辖范围的分配原则：(1) 突发事件发生时，警车到达事发地的行车路程 尽量在 3km 以内；(2) 对于某些同属于多平台管辖范围内的路段和节点和某些不属于 任何平台管辖范围内的路段和节点，采取路程最短原则进行分配；(3) 使用城市道路作 为管辖范围的界线，便于标识和指挥调度；(4) 对于相邻的两个交巡警服务平台，尽量 使其管辖范围界线上的点距这两个交巡警服务平台的距离相等。依据原则首先运用弗 洛伊德算法确定离平台 Ai 路程在三千米以内的节点集 SA′ i ，同属于多个节点集 SA′ i 的节 点依据就近原则确定其所属平台，两平台之间的距其都超过三千米的道路部分按平均 分配原则进行分配。由此可得到 A 区平台管辖范围。
问题 1：确定 A 区各交巡警服务平台管辖范围。本文根据题目要求制定了平台管辖 范围的分配原则；依据原则首先运用弗洛伊德算法确定离平台 Ai 路程在三千米以内的 节点集 SA′ i ，同属于多个节点集 SA′ i 的节点依据就近原则确定其所属平台，两平台之间 的距其都超过三千米的道路部分按平均分配原则进行分配。由此得到平台管辖范围如 图 1 所示。
2011 高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度
摘要
由于警务资源有限，各个城市的实际情况不同，则需要考虑如何合理的设置交巡警 服务平台，如何评价交巡警平台设置的合理性，如何恰当的分配交巡警服务平台的管 辖范围，如何在突发事件发生时最快最好的调度警务资源。本文即针对这些问题建立 了相应的数学模型。
问题 3：平台工作量不均衡和有些地方出警时间过长，主要是由发案率大小和出警 路程的长短决定；为此本文提出 A 区工作力度指标：将某节点的发案率和其所属平台 到其出警路程的乘积作为该节点工作力度；某平台的工作力度为其管辖范围内的所有 节点的工作力度之和。首先利用 MATLAB 实现所有出警路线的长度计算，然后通过计算 每个平台的工作力度以及平均值，求出每个平台工作力度与平均值的差值的绝对值的
三、模型假设
1、假设突发事件只发生在交叉路口（全文简称节点）处； 2、假设相邻两个节点之间的道路为直线； 3、假设单一管辖区域内某一时间无并发事件； 4、假设警车到事发地之间道路通畅，无特殊路况，且警车能由最短路径到达事发 地点； 5、假设出警过程中警车无故障发生； 6、假设该市所有道路都是双行道路； 7、假设犯罪嫌疑人逃跑的车速与警车的车速相等。
关键词：最短路径；弗洛伊德算法；工作力度；树状模型；
1
一、问题重述
为了更有效地贯彻实施警察职能，需要在市区的一些交通要道和重要部位设置交 巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源有限， 需要根据实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围和调度 警务资源。该类问题都是图论中的典型问题。根据题意，本问题可细分为如下问题：
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
西南大学
参赛队员 (打印并签名) ：1.
汪娅
2.
李玲
3.
史江南
指导教师或指导教师组负责人 (打印并签名)： 彭作祥
日期： 2009 年 9 月 12 日
赛区评阅编号（由赛区组委会评阅前进行编号）：
问题 2：突发事件需要封锁全部出入城区节点属于最优化问题。按 A 区 13 个交通 要道节点的分布以及道路情况将 A 区分为三个区，分别对其进行搜索最优路径。用 MATLAB 搜索出所有调度方案，将每一方案中的最长路径作为该方案的路径，比较所有 方案的路径，取最短路径的方案为最优调度方案；若存在多个方案最短路径相等，则 取方案中所有路径和最小的为最优调度方案（见表 2）。
最佳的管辖范围，那么如何才能使得警车最快到达案发地是最重要的，因而在这一问
中我们主要考虑交巡警服务平台到其管辖范围内的节点路径最短，为此制定如下平台
管辖范围分配的原则：
（1）突发事件发生时，警车到达事发地的行车路程尽量在 3km 以内；
（2）对于某些同属于多平台管辖范围内的路段和节点和某些不属于任何平台管辖
3
五、模型的建立与求解
5.1 问题 1 的模型建立与求解
该问题要求在交巡警平台管辖范围内发生突发事件时，能尽量使交巡警能在 3 分
钟内到达，而题目给出警车的时速为 60km/h，则可得警车在 3 分钟内的行车路程为：
L3 = V *T =3km
(1)
由于这一问题中主要是为了处理突发事件而给 A 区中的 20 个交巡警服务平台分配
2
平均值，并将差值的绝对值与差值平均值进行比较，如果差值的绝对值大于平均值则 表明平台的工作力度过大，需要调整。最后为了使得各个平台工作力度达到均衡，在 工作力度较大的几个平台的邻接区域节点处确立增设平台数及其准确位置。
问题 4：考虑全市的具体情况，将问题 3 中工作力度指标进行改进推广，增加了人 口密度因素对工作力度的影响，即将某节点的工作力度定义为其所属平台到其的出警 路程、该点发案率及其所属区域的人口密度的乘积。为了实现对全市平台合理性的判 断并提出最佳平台规划方案，首先类似问题 1 的分析，将全市的各个交巡警服务平台 划分管辖范围，然后类似问题 3 的分析，实现对全市平台合理性的判断并提出最佳平 台规划方案。
四、符号说明
vj ：标号为 j 的节点；
Ai ： A 区中标号为 i 的交巡警服务平台， i = 1,..., 20 ；
SAi ：与交巡警服务平台 Ai 的最短距离不大于 3km 的节点集合；
S
′
Ai
：交巡警服务平台
Ai
管辖范围内的节点集合；
LAi− j ：由交巡警服务平台 Ai 到节点 j 警车行车路程；
(1) 要求节点 vj 到 Ai 的最短路径。如果 vj 到 Ai 有折线，则从 vj 到 Ai 存在一条长度
为 cos t[ j,i] 的路径，该路径不一定是最短路径，尚需进行 n 次试探。
(2) 考虑路径 (v j , v1, Ai ) 是否存在，即判别折线 (v j , v1) 和 (v1, Ai ) 是否存在。如果存
范围内的路段和节点，采取路程最短原则进行分配；
（3）使用城市道路作为管辖范围的界线，便于标识和指挥调度；
（4）对于相邻的两个交巡警服务平台，尽量使其管辖范围界线上的点距这两个交
巡警服务平台的距离相等。
根据第一条分配原则，本文首先采用弗洛伊德算法确定与平台 Ai 的最短距离不大 于 3km 的节点集合 SAi 。具体算法如下：
问题 5：对于设计最佳围堵方案，本文给出最佳围堵方案的原则，即在保证围堵成 功的基础上尽量使搜捕时间最短；并假设嫌疑犯与警车的速度一致。因此本文在安排 警力对全市出入市区节点进行封锁，保证围堵一定成功的同时，也从 P 点开始建立树 状模型，得到搜捕时间尽量短封锁方案。该树状模型是依次对由 P 点出发的每条可能 路线上每个节点搜索离该节点最近的平台，以 P 点到该节点的路程与 3 分钟路程的差 和平台到该节点的路程比较，来判定是否能够成功围堵，直到找到这样的节点为止。 围堵方案见表 5、表 6。