2011年全国数模竞赛B题论文

2011高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：J4504

所属学校（请填写完整的全名）：西北工业大学 参赛队员 (打印并签名) ：1.张昊 2.程少光 3.王正磊 指导教师或指导教师组负责人 (打印并签名)：吕全义

日期：2011 年 9 月 12 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

交巡警服务平台的设置与调度

摘要

交巡警作为一种全新的警务模式正越来越多地为大众所认识。本文以交巡警服务平台为研究对象，针对不同的问题背景，对其设置与调度方案进行探讨，为如何有效利用现有警务资源，合理设置交巡警服务平台、分配各平台管辖范围提供了切实有效的方案。

本文解决的是关于交巡警服务平台的设置与调度的数学规划问题。根据不同的目标建立优化模型，分别采用LINGO、MATLAB软件求得最优结果。首先由Floyd算法计算得到A区各节点之间的最短距离，并以此为基础完成各种优化方案的设计。具体工作如下：

问题一：首先，在尽量保证出警时间小于三分钟的条件下，分配交巡警平台管辖范围。我们根据时间最短原则建立了道路节点分配模型，得到A区各交巡警服务平台的管辖范围，且发现节点28,29,38,39,61,92等六个节点距平台的时间大于3分钟；然后设计出快速封锁的调度方案。此问题为最优指派问题，我们建立0-1规划模型并使用LINGO编程计算得到完成封锁的最短时间为8.015分钟，且得到出警方案；针对设计增加平台的具体方案，应用0-1整数规划模型，得出新增5个平台，且将它们设置在节点29，38，48，91，70处为最优方案。

问题二：我们以时间和均衡度为衡量标准，在分析研究该市现有交巡警服务平台设置方案合理性的基础上，针对不合理的平台设置给出解决方案；对于设计最佳围堵方案的问题，我们建立动态围堵模型，使用LINGO软件，以罪犯逃逸速度V=80km/h进行模拟，求得在接到报案后8.3分钟以15个平台的警力实现完全围堵，并采用逐步缩小包围圈的方法对罪犯进行抓捕。

本文解决问题的方法简单易行，但适用范围不广，尤其当计算规模很大时，难以求得最优解。

关键词：交巡警 均衡度 0-1整数规划 方案

1

1.问题重述

为了更有效地贯彻实施人民警察刑事执法、治安管理、交通管理、服务群众的四大职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源的限制，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

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

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

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

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

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

2问题分析

2.1问题一的分析

问题一可分为三个小问题：（1）交巡警服务平台分配管辖范围问题：为达到题目要求的约束时间，我们可将问题转化为图论中的最短路问题，求出以时间作为权重的邻接矩阵，使用Floyd算法进行最短路搜索，选择满足约束条件的点归入管辖范围内，对剩余的奇异点按最短时间原则归入相应的平台范围内。（2）快速封锁的调度问题：此问题实质上为最优指派问题，引入0-1整数规划进行求解。（3）新增平台数量与设置问题：为达到最优目标，可从以下三个方面进行分析：（1）仅将出警时间作为必要条件；（2）仅将均衡度作为必要条件；（3）同时将出警时间和均衡度作为必要条件。 2.2问题二的分析

问题二可分为两个小问题：（1）城市现有交巡警服务平台设置方案评价问题：我们主要从三个方面进行考虑，（1）从城区间的工作量均衡度进行评价，（2）从城区间的出警时间进行评价，（3）从城区内的工作量和均衡度进行评价。（2）围堵方案问题：我们主要从减少警力分配和搜索面积最小进行考虑，能通过编程给出罪犯以的速度v逃逸时最佳围堵方案。

2.3数据的分析与处理

针对题目中设置交巡警平台的具体要求，以及附件2中的相关位置信息，首先由MATLAB编程计算得到A区各节点之间的距离，并将主要考察指标由距离因素转换为时间因素（见8.1.1）。

3.模型假设

为简化模型，便于量化与计算，现作假设如下： （1）假设题目所给的数据真实可靠；

2

（2）不考虑交巡警的反应时间，假设接警的瞬间，交巡警即向案发地点出发；

（3）不考虑路况，转弯，各路段加减速情况。假设警车一直匀速运动，因此行车距离的衡量可简化为时间的衡量。

（4）每个交巡警服务平台的职能和警力配备相同； （5）案发地点均位于道路或交叉路口的节点处； （6）忽略案发时刻到接警时刻的时间间隔。 （7）警车时速保持不变，为60km/h

4.定义与符号说明

d i,j ：i到j的距离；

r i,j ：i到j之间的插入点； Qi：第i个交巡警服务平台； ：所有奇异点的集合； Q

𝑊：带权邻接矩阵； 𝑋：指派矩阵；

x(i,j)：交巡警平台j出警至道路节点i的时间； Pi：节点i处的发案率；

Si：原始交巡警平台管辖范围内的所有节点案发率之和； ：所有交巡警平台按法律之和的平均值； S

Sik：为新增平台的总案发率； M：均衡度； η：出警效率;

β：某一城区内出警时间大于5分钟的道路节点的案发率总和； γ：某一城区内所有道路节点的案发率之和；

5.模型的建立与求解

5.1问题一的模型与求解

在解决交巡警服务平台的设置与调度问题中，需要遵循出警时间短、各平台工作总量均衡的原则。在此基础上，我们建立了划分交巡警平台管辖范围模型、快速封锁的调度模型和新增交巡警平台模型分别求解出不同问题下的交巡警平台设置与调度方案。 5.1.1划分交巡警平台管辖范围模型

针对题目要求及现实状况，交巡警服务平台管辖范围的划分方案需要满足在接警后三分钟内到达案发地点的要求。本模型根据Floyd算法编写MATLAB程序，求解得到各节点到交巡警平台的最短时间。筛选出时间长度大于3分钟的节点，并将其分配到距离最近的交巡警平台的管辖区域内，最终达到题目要求。 Floyd算法[1]：求任意两定点间的最短路。 设G是赋权图，权为实数， 𝑉 =n d i,j ：i到j所需时间 r i,j ：i到j之间的插入点

输入：带权邻接矩阵𝑊=(𝑑 𝑖,𝑗 )𝑛×𝑛

（1）赋初值：对所有i,j, 𝑑 𝑖,𝑗 ←𝜔 𝑖,𝑗 ,𝑟 𝑖,𝑗 ←𝑗,𝑘←1；

（2）更新𝑑 𝑖,𝑗 ，𝑟 𝑖,𝑗 ：对所有i,j,若𝑑 𝑖,𝑗 +𝑑 𝑘,𝑗 <𝑑 𝑖,𝑗 ，则：

𝑑 𝑖,𝑗 ←𝑑 𝑖,𝑘 +𝑑 𝑘,𝑗 , r 𝑖,𝑗 ←k；

（3）若k=n,停止。否则k←k+1,转至（2）。 模型一：道路节点分配模型：

3

d i0,j =mind(i,j) j∈Qi0， ， mind(i,j)>3 𝑗∈Q

i

i

i=1,2,…,20 ， (j=21,22,…,92)

若出现某一节点到多个交巡警平台的距离相等，则随机分配改节点至任一上述平台。

将A区各节点之间的时间邻接矩阵代入上述MATLAB程序，求解得到A区各道路节点到达各交巡警服务台的最短时间矩阵（见附表8.1.2）。首先根据此时间矩阵筛选出到达任一交巡警平台时间长度均大于三分钟的6个道路节点（28,29,38,39,61,92），并根据出警时间最短原则，将其合理分配至各交巡警平台管辖区域，其中28、29节点划分至第15交巡警管辖区，38节点划分至第16区，39节点分至第2区，61节点分至第7区，92节点分至20区；然后对符合最短出警时间小于3分钟的道路节点，将其分配至距离最近的交巡警平台管辖区域。最终得到A区各交巡警服务平台的管辖范围，如表1。

表1 A区各交巡警服务平台管辖范围 交巡警平台道路节点标号 位置标号 1 69 74 75 2 39 40 43 44 70 71 72 73 76 3 54 55 65 66 67 68 4 57 60 62 63 64 5 49 50 51 52 53 56 58 59 6 7 30 32 47 48 61 8 33 46 9 31 34 35 45 10 11 26 27 12 25 13 21 22 23 24 14 15 28 29 16 36 37 17 41 42 18 80 81 82 83 19 77 78 79 20 84 85 86 87 88 89 90 91 92 5.1.2快速封锁的调度模型 （1）模型二的建立

此问题为最优指派问题，引入如下变量：

1， 分派第j个交巡警平台出警至节点iaij=

0，不分派第j个交巡警平台出警至节点i

设矩阵𝑋13×20为指派矩阵，其中x(i,j)为第j个交巡警平台出警至第i个道路节点的时间，则可建立如下0-1规划模型：

4

20

min⁡(max 𝑎𝑖𝑗𝑥𝑖𝑗)； 𝑎≤1，(j=1,2,…,20)

𝑖𝑗

i=1

2013

𝑗=1

𝑎𝑖𝑗=1，(i=1,2,…,13) j=1

𝑎𝑖𝑗=0或1.

根据上文中Floyd算法计算得到指派矩阵𝑋13×20（见8.1.3），使用LINGO编程计算得到minmax=8.015，并得到出警方案结果如下：

表2 快速封锁调度方案 出警平台标号 12 16 6 14 10 13 11 15 7 9 1 4 2 封锁路口标号 12 14 16 21 22 23 24 28 29 30 38 48 62 （2）封锁成功概率的计算 对附件1中A区的交通网络与平台设置的示意图进行分析，计算各节点案发后罪犯的逃逸时间并与出警时间进行比较，可知案发地点位于节点47、25、38、40的罪犯将在成功封锁路口之前逃逸。根据A区各节点案发率计算可得封锁成功的概率P为：

P47+P25+P38+P40

P=1−=94.94%

92Pi=1i

其中，Pi表示节点i处的发案率。 5.1.3新增交巡警平台模型

（一）节点分区调整

由表1可知：第2、20交巡警平台管辖区域内道路节点数量较多，而第10、14平台管辖区域无道路节点；同时，由图1可知各平台管辖区域内案发率差别较大，并由此导致个别服务平台出警时间过长的问题，可得到交巡警工作量分配不均衡的结论。

s.t

8区域案发率与平均案发率差值6420-2-4-6交巡警服务平台1234567891011121314151617181920图1交巡警服务平台工作量波动曲线 针对这一问题我们对交巡警服务平台的管辖范围进行调整，调整结果如下： 将道路节点71、73由2区划分至1区（节点71、73到达节点1的时间分别为1.1，1.0296），将76节点由2区划分至19区（节点76到达节点19的时间为1.4321），将49、50、58、59节点划分至第6区（四个节点到达节点6的时间分别为3.3195，2.2755，2.3841，

5

1.8947），将节点21划分至14区（节点21到节点14的时间为3.2650），将节点24划分至12区（节点24到节点12的时间为3.5916）；其中时间单位均为分钟；而由于10号、14号平台位于城市边缘，且道路节点唯一，所以对10、14区不作调整。依据此调整方案调整后的A区各交巡警服务平台的管辖范围如表2：

表2 调整后A区各交巡警服务平台管辖范围 交巡警平台位置标号 管辖节点标号 1 69 74 75 71 73 2 39 40 43 44 70 72 3 54 55 65 66 67 68 4 57 60 62 63 64 5 51 52 53 56 6 49 50 58 59 7 30 32 47 48 61 8 33 45 46 9 31 34 35 10 11 26 27 12 24 25 13 22 23 24 14 21 15 28 29 16 36 37 38 17 41 42 18 80 81 82 83 19 77 78 79 20 84 85 86 87 88 89 90 91 92 （二）模型三的建立 活动点概念的引入：我们将能脱离原服务区并有可能成为新的巡警服务区平台的节点称作活动点。

仅考虑均衡度达到最优的因素，则目标函数为：

2s2 min nS−S+ S−S ； i=1ik=1i

1 j∈i定义决策变量xij=

0 j∉i

设增加S个平台，ik为活动点，则新增平台的总案发率为：

92

k

S ik = xikjPj i1,i2,…,is∈ 21,22,…,92 , 2≤s≤5

j=1

因为每一个节点必须归属于一个区，且到所属平台的时间小于等于3分钟，故约束条件为：

x+ x =1 j=1,2,…,92

ijikj

k=1 i=1

xijtij ≤3

综合以上各式，得到总的模型为：

6

20

s

目标函数：

2s2 min nS−S+ S−S ； iii=1k=1k

S i = 92j=1xijPj i=1,2,…,20,

20

s

S ik = 92 j=1xikjPj i1,i2,…,is∈ 21,22,…,92 , 2≤s≤5 s.t.

xij+ xikj =1 j=1,2,…,92 i=1k=1

xijtij ≤3

为所有交巡警平台按法其中，Si为原始交巡警平台管辖范围内的所有节点案发率之和，S

律之和的平均值，Sik为新增平台的总案发率。Pj表示节点j处发生案件的频率。 均衡度M的计算：

max Si−S

M= S

的计算需要将奇异点（所在区域中只有服务平台本身的节点）排除在外 上式中，S

根据不同的约束条件，我们将交巡警服务平台的新增方案分为以下三种情况： 1. 将时间作为必要条件

新增交巡警平台应尽量符合分布在交通要道和重要部位的原则，同时由5.1.2中快速封锁的调度模型的结论可知平均出警时间大于三分钟，为了提高警效率，同时也是为了限制时间，我们规定当城区出入口节点出现在奇异点处时，则必须设置交通服务平台。由此可知，至少需新增4个交巡警平台，新增平台的位置分别为节点29、38、61、92。结合附件中A区的交通网络与平台设置的示意图可知节点29、38为出入A城区的路口节点，在此处设置新增平台同时也将缩短节点28、39的出警时间。在61、92节点处设置交巡警平台同时也遵循了缩短出警时间的原则。

图2为将时间因素作为必要条件时得到的交巡警服务平台工作量波动曲线。

86区域案发率与平均案发率差值420-2-4-6-8123456789101112131415161718192021222324

交巡警服务平台图2交巡警服务平台工作量波动曲线

计算得到均衡度为M1=79.23%

2. 将各服务平台的工作量均衡度作为必要条件 根据调整后的交巡警服务平台工作量波动曲线，（如图3所示），可知2区、3区、7区和20区的工作量相对过大，所以我们以20区为例，应用上文0-1整数规划模型 根据活动点定义，可选取出活动点为节点84、87、88、89、90、91、92七个点，可设

7

出14个变量代入0-1整数规划模型，可求出84、87、89、90、91、92将从原来所在区域被除去，然后根据时间最短原则，选择节点91作为新的交巡警平台设置点。将此方法沿用到7区中可求出节点30、48、61将出区，根据交巡警服务台设置的效率原则得到节点48为新的交巡警服务平台。由附件1中的图1可知交巡警平台2、3相距较近，且知2、3区工作量较大，将2、3区合并，选取活动点，沿用0-1整数规划模型求解得到节点66、67、68、70、72将从原来所在区域被除去，并以节点70作为新的交巡警服务平台。得到交巡警服务平台工作量波动曲线图，如图4。 8区域案发率与平均案发率差值6420-2-4-6交巡警服务平台1234567891011121314151617181920 图3交巡警服务平台工作量波动曲线

8区域案发率与平均案发率差值64201234567891011121314151617181920212223-2-4-6交巡警服务平台 图4交巡警服务平台工作量波动曲线

计算得到均衡度为M2=42.96%

3. 同时将时间及均衡度作为必要条件

8

若综合考虑时间及均衡度因素，根据我们的定义，节点29、38处必须设立交巡警服务平台；然后在2区，3区，7区，20区内选择活动点，带入模型求解得到节点30、48、61将出区并组合为一个新区，节点66、67、68、70、72将出区并组合为一个新区，节点84、87、89、90、91、92将出区并组合成为一个新区。

因为节点48为城区出入路口，所以选择48为新的巡警服务平台设置点。在节点66、67、68、70、72内搜选出到其余各点距离总和最小的点即节点70作为新的交巡警服务平台设置点。选择节点92作为新的交巡警服务平台设置点既满足了时间的必要条件又符合了均衡度最低的必要条件。所以选择节点92。图5为同时考虑时间及均衡度因素得到的交巡警平台工作量波动曲线。 8区域案发率与平均案发率差值642012345678910111213141516171819202122232425-2-4-6交巡警服务平台 图5交巡警服务平台工作量波动曲线

计算得到均衡度为M3=29.47%

经比较可知：将时间及均衡度同时作为必要条件所得到的结果为最优，于是选择平台数量为5，并将他们设置在节点29，节点38，节点48，节点91，节点70. 5.2问题二的模型与求解

在问题二的求解过程中，我们以各城区交巡警平台工作量平均值、均衡度、以及各区内部平台出警时间为考察因素，应用0-1整数规划模型分析研究现有交巡警服务平台设置方案合理性

5.2.1交巡警服务平台设置的合理性模型

判断交巡警服务平台的设置是否合理，主要应分析工作总量的均衡度和交巡警平台到达案发节点的时间长度。

（1）首先应确定六城区内所有交巡警服务平台工作总量之和的均衡性。由全市六区交通网路和平台设置的数据表可得到各城区内交巡警平台的平均工作量，如表3 所示（以案发率为考察指标）。

表3 各城区交巡警平台工作量平均值 城区 A B C D E F 平均工作6.225 8.3 11 7.664 7.96 9.92 量 9

六城区所有交巡警平台工作量平均值为8.457。

根据以上分析可知A区、D区、E区工作量平均值低于六城区所有交巡警平台工作量平均值，C区、F区工作量平均值高于六城区所有交巡警平台工作量平均值，B区平均值于六城区所有交巡警平台工作量平均值差别较小。同时可求得城区之间交巡警工作平台工作量的均衡度为30.07%，因此现有交巡警服务平台设置方案不够合理，仍需进一步完善。

（2）从出警时间的角度进行分析。我们参考欧美国家接警后5分钟内到达案发现场[2]

的标准，探讨该市现有交巡警服务平台设置方案的合理性。

沿用Floyd算法， 筛选出各区域内部到达各交巡警平台时间长度均大于三分钟的道路节点，见表4。

表4 区域内部到达各交巡警平台时间均大于三分钟的道路节点 城出警时间大于3分钟的道路节点及最短出警时间（单位：分钟） 区 A 28（4.75），29（5.70），38（3.40），39（3.68）,61（4.19），92（4.4294）； B 130（3.29），131（3.37），132（3.21），159（3.19），160（3.37），161（4.47）； C 200（4.08），216（5.51），217（5.20），218（3.69），220（4.45），222（4.86），223（5.96），224（6.86），225（5.71），226（4.61），227（3.51），232（3.63），255（3.96），256（6.57），257（4.90），264（3.41），265（3.68），268（3.77），269（3.81），270（5.83），274（3.23），276（3.46），278（3.57），279（3.21），280（5.12），281（6.62），285（3.98），286（3.00），302（3.53），303（4.83），304（5.33），305（3.87），316（3.82），317（4.65），318（5.36），319（4.75）； D 338（11.11），339（11.85），340（9.10），341（15.99），345（3.22），346（3.66），348（4.72），353（4.84），371（8.11）； E 402（19.11），403（12.52），404（14.41），405（8.57），406（5.02），407（4.31），408（3.28），410（3.11），422（4.81），423（3.24），424（4.44），426（3.82），427（4.08），428（3.50），432（4.08），433（7.42），434（8.12），435（6.30），453（3.20），454（3.72），485（3.01），460（3.31），461（4.13），466（3.12），467（3.51），470（3.25），473（4.22），474（4.86）； F 497（3.95），498（4.12），516（3.96），517（4.52），518（3.22），519（3.89），520（4.84），521（6.61），523（4.74），524（5.57），525（4.27），526（5.57），527（4.97），528（4.36），529（4.54），530（3.07），533（4.69），534（5.24），535（5.06），536（3.71），537（5.57），538（3.06），540（3.28），544（3.24），551（3.35），552（7.04），570（3.53），571（4.77），572（4.35），577（3.09），580（3.07）； 现根据上表中数据对各城区进行分析，以5分钟为标准且不考虑奇异点归属，最终筛选出各城区中距离交巡警服务平台时间大于5分钟的道路节点（若在节点处发生案件，无法在5分钟内到达案发现场，即未达到出警要求）

10

表5 区域内部到达各交巡警平台时间均大于五分钟的道路节点 城出警时间大于5分钟的道路节点 区 A 29； B C 216 ,217 ,223 ,224 ,225 ,256 ,270 ,280 ,281 ,304 ,318； D 338 ,339 ,340 ,341 ,371； E 402 ,403 ,404 ,405 ,406 ,433 ,434 ,435； F 521 ,524 ,526 ,534 ,535 ,537 ,552；

我们定义出警效率η= 1−γ ×100%，其中β为某一城区内出警时间大于5分钟的道路节点的案发率总和，γ为该城区内所有道路节点的案发率之和。分析计算表5中所

列数据可得各城区交巡警平台出警效率如下表：

表6 各城区交巡警平台出警效率 区域 A B C D E F 均衡度 31% 37.6% 33.1% 42.1% 37.5% 36.7% 由表6可知城区D内的交巡警平台的出警效率相对较低，从而发现D区现有交巡警服务平台设置方案存在明显缺陷。我们建议在D区338节点处增加交巡警服务平台。 （3）综合考虑各区内部的均衡度和出警时间 模型一的建立

以各区间的工作量的方差为目标函数，时间为限制条件，应用0-1整数规划模型

1 将第j个节点归入第i个平台引入变量： xij=

0不将第j个节点归入第i个平台

设矩阵P582×1为案发频率矩阵，其中Pj1为第j个节点的案发频率，则可建立如下模型： 目标函数为：

1

)2 min (Si−S

n

xij=0或1 i=1,2,…n,j=1,2,…m ,

xij∗tij≤t.

以各区间的工作量的方差为目标函数，时间为限制条件，应用0-1整数规划模型进行区域分配，则可以实现在现有已给定交巡警服务平台的基础上所能达到的最优管辖节点的分配，则然后以第一问所得到的最佳均衡度指标和节点增加原则来判断各区内部现有交巡警服务平台设置方案的的合理性。

用Lingo软件编程进行求解得到各区内的工作总量均衡度为：

表8 各城区均衡度 区域 A B C D E F 均衡度 31% 37.6% 33.1% 42.1% 37.5% 36.7% 最大时间4.19 3.366 4.903 5.053 6.58 5.125 （分钟） s.t.

11

n

β

Si= mj=1xijPj1, ni=1xij=1 j=1,2,…m ,

j=1

从表可以看出：与第一问所得到的最佳均衡度指标相比有些不合理,于是需要进行调整和节点增加原则进行均衡度调整

在考虑到费用最小的前提下，调整方案如下：

表9 方案调整表 区域 增加节点 调整节点 A 29 38 48 70 91 无 B 无 148->99 C 206、245、302 165->262、177->201 D 330、362、371 无 E 387、418 无 F 479、505、575、581 无 5.2.2围堵方案设计 围堵模型

v

罪犯逃逸半径 R= t′+t ∗ 601， 分派第j个交巡警平台出警至节点iaij=

0，不分派第j个交巡警平台出警至节点i

目标函数min(max⁡( Ni=1aij∗d i,j −t)) N=80

aij≤1,(j=1,2,…N) i=1s.t.

N

k

aij=1, j=1

aij=0或1.

t′为报警时刻距案发的时间，aij为决策变量，i为以R为半径搜索到的可能逃逸路口，可用编程得出范围。t为接到报案后搜捕到罪犯所用的最短时间。由题目可知，犯罪嫌疑人沿公路逃跑，因此在设计围堵方案时仅考虑犯罪嫌疑人在道路上的情况。

为设定最小的包围圈，我们用逃逸半径R去搜索出可能到达的路口，此时问题转化为5.1.2中的调度问题，即对罪犯可能到达的所有节点进行快速全封锁。由模型中的目标函数的意义知，我们的围捕方案为逐步缩小包围圈方法。

在不考虑道路状况的假设下，我们使用围堵模型，取逃逸速度为v=80km/h，t′=3min，用计算机编程模拟。若罪犯正向可能围堵的路口处逃脱，可模拟出在接到报案后的8.3分钟时实现完全围堵。对v取不同的值可以得到不同的抓捕时间。

其他方案：

（1）因罪犯的逃逸速度是不确定的，因此可以给出罪犯逃逸阈值，模拟出此时罪犯可能逃脱的路口，然后同样应用快速全封锁问题求解方法进行调度，但此时并不能恰好在节点处围住罪犯，此时，若在封口处的巡警发现了罪犯的踪影，则需及时报告此时罪犯的估计位置及车速，此时在估计点处按照上面的方法缩小包围圈范围，按照此方法进行下去，则最终会将罪犯包围在某一点处。

（2）若在调度完毕后，等待n分钟，并未发现罪犯出现在任意的包围点得观察中，则包围圈由外向内进行包围，则在此过程中的某一点必会出现上面的情况，继续按上面的方法缩小包围圈，最终实现围捕目的。

12

（3）在（1）、（2）的方案中，为能更好地追捕放罪犯，但并不将成本考虑在内，我们可以再调度包围圈内的剩余警力，将原本的警务平台移到多交叉路口处，观察罪犯行踪，然后报告，再利用（1），（2）的方法进行搜捕。

在实际的生活中，我们还可以考虑用电子眼帮我们确定罪犯的车辆速度，则此时应用搜捕模型就可快速围捕到罪犯。

使用LINGO编程得到围堵方案如表7：

表10 围堵方案 出警平台 11 7 15 4 8 20 19 175 174 172 179 170 476 477 478 围堵路口 21 28 29 43 61 89 90 192 213 220 274 277 476 490 517 所需时间 0.97 8.3 5.7 5.6 5.9 0.95 3.7 2.6 1.7 4.0 1.5 2.2 0 3.9 4.2

6．模型评价与推广

问题一中的模型

分配方案模型虽然在满足题目要求的前提下，为各交巡警服务平台分配了管辖范围，但是由于此算法的单约束条件，使得A区内交巡警服务平台的工作量均衡度较差。我们可以采用问题二的模型一，对分配问题进行求解，用此方法可以提高各平台工作量均衡度，同时也能达到题目要求。模型二和模型三针对特定类型问题具有普适性。

问题二中的模型

围堵模型虽然能够提出一个最优化的模拟方案，但是此模型在求解过程中假定报案

v

距案发时间t′=3min，但随着t′的取值增加，罪犯逃逸半径为R= t′+t ∗也随之增

60

加，到一定阈值后，则此算法所得到的围堵方案将不能成为最佳的围堵方案，警力消耗大，方案不符合实际。因此可知此围堵模型具有一定的局限性。

7.参考文献

[1] 周炳生，Floyd算法的一个通用程序在图论中的应用，杭州应用工程技术学院学报，1999

[2] 陈永洮，梅建波，南箔，GIS在多功能警务平台和警力配置中的应用——以重庆市北碚区为例，科教导刊，2010(24)：103-104,2010

8.附录

8.1附表

路线起点 1 1 2 3 3 4 4 5 5 6 7 7

8.1.1距离因素转化为时间因素 路线终点 时间（min） 路线起点 路线终点 75 78 44 45 65 39 63 49 50 59 32 47 0.930053762 0.640312424 0.948683298 4.246469122 1.523975065 4.560975773 1.030776406 0.5 0.848528137 1.603121954 1.140175425 1.280624847 13 时间(min) 1.019803903 1.486606875 1.456021978 2.9 1.044030651 0.670820393 0.380788655 0.430116263 0.291547595 0.424264069 0.854400375 2.28035085 45 46 46 47 47 47 48 49 49 50 51 51 46 8 55 48 6 5 61 50 53 51 52 59

8 8 9 10 11 11 12 12 14 15 15 16 16 17 17 17 18 18 19 20 21 22 22 23 23 24 24 25 26 26 27 28 28 29 30 30 31 31 32 33 33 34 35 36 36 36 36 37 38 38 39 40

9 47 35 34 22 26 25 471 21 7 31 14 38 40 42 81 81 83 79 86 22 372 13 13 383 13 25 11 27 10 12 29 15 30 7 48 32 34 33 34 8 9 45 35 37 16 39 7 39 41 40 2 1.15974135 2.079663434 0.424264069 4.921635907 3.269556545 0.9 1.788854382 3.264965543 3.818376618 2.968164416 6.741661516 3.405877273 2.687936011 0.98488578 4.022437072 0.670820393 0.538516481 0.447213596 0.360555128 1.802775638 0.905538514 0.5 2.385372088 1.802775638 2.002498439 0.743303437 3.538361203 3.304920574 0.948683298 4.751841748 7.43236167 0.58309519 0.707106781 1.170469991 1.553222457 0.509901951 0.756637298 0.827647268 0.502493781 0.670820393 0.5 0.509901951 0.608276253 3.50142828 3.041381265 0.3 4.007804885 1.767766953 1.914418972 0.85 4.631684359 0.806225775 14

52 53 53 54 54 55 56 57 57 57 58 60 61 62 62 63 64 64 65 66 66 67 67 68 68 69 69 69 70 70 71 71 72 73 73 74 74 75 76 77 77 78 79 80 81 82 82 83 84 85 86 86 56 52 54 55 63 3 57 58 60 4 59 62 60 4 85 64 65 76 66 67 76 44 68 69 75 70 71 1 2 43 72 74 73 74 18 1 80 76 77 78 19 79 80 18 82 83 90 84 85 20 87 88 1.004987562 2.418677324 1.26589889 1.23794184 0.75 0.81394103 1.868154169 0.781024968 1.389244399 3.471310992 0.35 6.001666435 0.905538514 0.58309519 1.315294644 0.316227766 0.424264069 0.921954446 1.476482306 0.412310563 0.707106781 0.452769257 0.538516481 0.640312424 0.5 0.860232527 0.761577311 0.5 0.610327781 0.806225775 0.403112887 1.972308292 0.626498204 1.691892432 0.353553391 0.447213596 1 0.98488578 0.670820393 0.447213596 0.806225775 0.502493781 0.540832691 0.87321246 0.98488578 0.728010989 0.447213596 1.104536102 0.934077085 0.403112887 2.137755833 0.403112887

41 41 42 43 43 44 0 1.898749 3.883884 4.535217 9.374289 9.537518 11.50035 9.022625 9.225438 14.64957 19.08793 22.23615 22.00175 16.02847 14.24932 9.286812 3.591205 2.564572 1.758346 5.263199 1.898749 0 2.111654 5.685068 7.833711 9.842077 9.728119 7.250394 7.453207 12.87734 17.3157 20.46392 17 92 43 2 72 3 3.883884 2.111654 0 0.8 0.806225775 1.162970335 0.6 0.930053762 2.942787794 4.535217 5.685068 4.043385 0 4.920044 5.002301 7.65669 8.327283 8.986668 14.4108 18.84916 21.99738 20.98179 15.00851 11.47507 8.266853 7.470525 6.384362 4.683709 6.79888 9.374289 7.833711 5.722058 4.920044 0 2.942629 2.736647 3.535685 4.695427 10.04161 14.47997 17.62819 18.65506 12.96963 6.555023 6.227967 10.42482 11.22343 9.522781 11.70395

15

87 87 88 88 89 89 9.537518 9.842077 7.730423 5.002301 2.942629 0 2.767232 3.56627 4.726012 10.07219 14.51055 17.65878 18.68565 13.00021 6.585608 6.258552 12.43319 11.38666 9.68601 11.78621 11.50035 9.728119 7.616465 7.65669 2.736647 2.767232 0 2.477725 2.909208 7.328351 11.76671 14.91494 15.94181 10.90122 3.818377 4.159559 11.50841 13.51137 11.81072 14.4406 88 92 89 91 20 84 9.022625 7.250394 5.13874 8.327283 3.535685 3.56627 2.477725 0 1.159741 6.50592 10.94428 14.09251 15.11938 9.433943 5.476184 2.692282 9.841506 11.03365 9.332997 13.73228 0.304138127 0.948683298 0.3 0.353553391 0.474341649 2.002498439 9.225438 7.453207 5.341554 8.986668 4.695427 4.726012 2.909208 1.159741 0 5.42413 9.862491 13.01071 14.03759 8.274202 5.023881 1.53254 8.881395 11.23646 9.53581 13.93509 14.64957 12.87734 10.76568 14.4108 10.04161 10.07219 7.328351 6.50592 5.42413 0 4.438361 7.586585 8.613456 12.77566 9.443023 6.95667 14.30553 16.66059 14.95994 19.35922 8.1.2最短时间矩阵 4.043385 5.722058 7.730423 7.616465 5.13874 5.341554 10.76568 15.20404 18.35227 18.74020.103 51 14.12912.76772 23 12.47710.36509 43 7.38806.025563 66 2.591114.70272 65 4.38475.89496 1 3.65704.194295 57 7.08338.593587 36

8.1.3指派矩阵 222.4 160.3 204.6 141.3 183.5 127.7 220 150.1 176.3 129.7 176.6 130 149.1 109 140.9 130.1 75370 .9 .9 11599..8 5 242.5 18591367140 5..7 3 .4 9 1 12116765817.0 7..4 .6 .6 1 7 1610182127325.0.1.7..1 .6 6 1 7 8 171119239.501.8.9.5.1 .7 5 1 7 8 18132124645 5.2.3.9..7 6 1 8 9 1722238315246.5..9 .6 1 9 9 5 2218111821478.0.3.6.0..5 1 5 1 6 1 23181219217.9.57 1.5.5.6 2 8 2 3 16111214475.4.44 0.0..4 2 8 9 9 1610973447831.1..5 .1 .6 .7 2 5 1712515412132.1..1 .5 8 7 3 9 2115118678673.3.8..2 .2 .3 3 6 1 170.3 145.4 218.9 225.5 169.6 102.2 202.3 220.3 234.3 232 193.1 198.3 123.9 269.5 212.1 144.7 244.8 262.8 276.9 276 1294827..3 .7 8 9273608262624126.9 .9 .3 .7 .3 .6 .6 .9 192.9 211 225 228.9 190 195.2 120.8 173.9 192 206 211.2 172.3 177.4 103.1 160.3 178.3 192.4 190.1 151.2 156.3 182.7 200.8 214.8 226.5 162.3 155.4 162.3 177.5 191.6 182.9 113.1 106.2 162.7 177.8 191.9 183.2 113.4 106.5 141.7 150.4 164.4 155.7 127 142.1 156.2 147.5 10852..7 3 10804..2 9 30.6 82 81 31325..8 .1 8 5839604894947358.8 .8 .9 .6 .2 .5 .5 .9 118.5 103.1 82 74 24251231 .8 .1 .9 52537986.6 .4 .9 .8 4860433..9 .4 .9 5 11839..4 5 141569115..3 .6 4 4 119550865..1 .7 .9 4 137732681..1 .7 .8 3 149146645..1 .8 .8 4 138238356..4 .1 .9 7 141821971.6.7..8 9 3 8 101519227.1.5.7.2 4 8 3 123479153..9 .1 5 5 101417471.5.7..3 5 9 4 13168642 0.2..2 6 1 142293197.3..4 2 6 5 230.1 223.2 148.9 11760..4 7 14121.0 8 5064.3 .5

16