1、交巡警服务平台的设置与调度摘要本文通过建立整数规划模型，解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题；通过建立线性加权评价模型定量评价了某市现有交巡警服务平台设置方案的合理性，并根据各个区对服务平台需求量的不同，提出了重新分配全市警力资源的解决方案。在计算交巡警服务平台到各个路口节点的路程时，使用了图论里的 floyd 算法。针对问题一的第一个子问题，首先假设交巡警服务平台对某个路口节点的覆盖度是二元的，引入决策变量，建立了 0-1 整数规划模型。交巡警出警应体现时间的紧迫性，所以选择平均每个突发事件的出警时间最短作为目标函数，运用基于 MATLAB 的模拟
2、退火算法进行求解，给出了中心城区 A 的 20 个服务平台的管辖范围，求得平均每个案件的出警时间为 1.013 分钟。针对问题一的第二个子问题，为了实现对中心城区 A 的 13 个交通要道的快速全封锁，以最短的封锁时间为目标，建立了 0-1 整数规划模型，利用 lingo 软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对 13 个交通要道实现全封锁最短需要 8.02 分钟。问题一的第三个子问题是交巡警服务平台的选址问题。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加最少的服务平台数和服务平台工作量方差最小为目标，采用集合覆盖理论
3、，建立了双目标 0-1 整数规划模型，用基于 MATLAB 的模拟退火算法求解出增加的服务平台数为 4 个，新增的服务平台具体位置为 A28,A40,A48,A88 ，并得到各个服务平台的工作强度方差为2.28。针对问题二的第一个子问题，通过建立线性加权评价模型定量评价了该市现有交巡警服务平台设置方案的合理性，结果发现全市服务平台覆盖率较低且各个区的工作量不均衡，得出全市服务平台的布局存在明显的不合理的结论。并确定各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为各区域对交巡警需求的指标，然后根据各个区对服务平台需求量的不同，提出了较为合理的分配全市警力资源的解决方案。对于问题二的
4、第二个子问题，以围堵范围最小和调动警力最少的原则，通过分析案发后嫌疑犯可能到达的位置，给出了围堵方案。关键词：交巡警服务平台 0-1 整数规划 模拟退火法 1一、问题重述“有困难找警察” ，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下
5、面的问题：（1）附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件 2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需
6、要增加平台的具体个数和位置。（2）针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型假设（1）每个交巡警服务平台的职能和警力配备基本相同；（2）警车的行驶速度恒定，不考虑实际交通状况的影响； （3）交巡警服务平台接到报警后能立即出警，中间没有延误；（4）每个节点只能被一个服务
7、平台管辖；（5）一个平台的警力最多封锁一个路口。2三、符号说明ijx服务平台 管辖第 个路口节点的决策变量；iAjt在中心城区 A 中，从第 个服务平台到第 个交叉路口节点的最短时ij间；jw中心城区 A 的第 个交叉路口节点的发案率；j1T在中心城区 A 内平均每个案件的出警时间；2在中心城区 A 内封锁 13 个出入城区的路口节点的最短时间；J中心城区 A 的 13 个出入城区的路口节点标号的集合；iq第 个服务平台的工作强度；ik第 区分配的服务平台资源比率。k四、问题分析在城市规划中，交巡警服务平台的布局是一项非常重要的内容。长期以来，由于种种原因，目前的城市建设大多对警务资源的规划缺
8、乏科学性。交巡警服务平台的选址、管辖区域的划分多依据经验进行，大多数城市均不同程度地存在服务平台布局不合理、管辖范围分配不均、警务资源调度困难等问题。另外，警务资源常常是有限的，设置交巡警服务平台也需要大量成本。所以更有效地分配和调度警务资源对于城市的长治久安有着重要的意义。本文着力解决的是合理地确定交巡警服务平台的数量及其位置，合理分配各平台的管辖范围以及当重大突发事件发生时快速有效地调度警务资源这三方面的问题。（1）对于问题一：在问题一中又有三个子问题需要解决。第一是要对中心城区 A 的 20 个现有交巡警服务平台分配管辖范围。首先假设每个交叉路口节点要么被其中一个服务平台完全管辖，要么被
9、完全不管辖，即覆盖度是二元的，所以考虑到用 0-1 整数规划模型。要使得案发后的损失减低到最小，就要求警方在接到报警后能在最短的时间内到达事故现场。这样就确定了平均每个突发事件警方出警时间的目标函数。第二是当重大突发事件发生后，要对中心城区 A 的 20 个交巡警服务平台的警力资源进行调度，从而对进出该区的 13 条交通要道实现快速全封锁。同样考虑使用 0-1 整数规划模型。因为要求对交通要道实现全封锁，所以问题的关键是合理调度警务资源使得封锁全部要道所需的总时间达到最小，也就是使得出警时间最长的服务平台所需的时间尽可能的小。第三是针对现有的中心城区 A 的 20 个交巡警服务平台进行分析后，
10、需要新增加25 个服务平台以解决工作量不平衡和部分路口节点出警时间过长的问题。这属于交巡警服务平台选址问题。一方面考虑采用集合覆盖模型 1，目的是在满足所有节点 3 分钟内都有警方到达的条件下，使新增设的服务平台数目尽可能得小，从而降低了建设成本。另一方面也要考虑新增设服务平台后，能够解决服务平台工作量不平衡的问题，所以把尽可能均衡各个服务平台工作量作为第二个目标 。因此考虑需要建立一个两目标的 0-1 整数规划模型。（2）对于问题二：问题二中有两个问题需要解决，一是根据已有的数据，评价全市六个区内现有的交巡警服务平台的数目和布局的合理性，如果不合理就给出解决方案；二是当该市 P3处发生重大刑
11、事案件时，调度全市警力资源设计出最佳的围堵方案。对于第一个小问题，要先按照设置交巡警服务平台的原则和任务，对全市的交巡警服务平台的数目和布局讨论其合理性。交巡警服务平台的选址应遵循尽量使每个交巡警服务平台的工作量基本均衡和每个节点突发事件发生时在 3 分钟内有警力到达的原则。所以选用各个服务平台平均每天的工作强度（平均每天处理的突发事件数）的方差和服务平台的覆盖率（区域内 3 分钟内有警方到达事发地的节点占区域内总结点的比率）为指标来进行评价。如果在全市范围内现有交巡警服务平台设置方案存在明显的不合理性，那么可能存在如下两种原因：第一，该市分配给各个区的交巡警服务平台比率不合理；第二，各个区内
12、的交巡警服务平台选址方案不合理。对于第二种原因，在第一问第三个子问题中对 A 区交巡警服务平台设置方案已经做过详细讨论，可推广到其他几个区中。现在设法解决由第一种原因引起不合理性的问题。据此，我们提出了依据各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为三个评判指标，在全市范围内重新分配警力资源，也就是重新分配每个区服务平台数量的解决方案。对于第二个小问题，首先分析出，在案发后的 3 分钟内，警方还未接到报警，即使嫌疑人开车驶过服务平台，警方不能识别出嫌疑人；而 3 分钟后警方已接到报警，设此时警方掌握了足够证据，故可以假设 3 分钟后只要警方与嫌疑人相遇就能够将其抓获。警方在接
13、到报警后，根据嫌疑人可能逃跑的路径，可以估计出嫌疑人逃跑的大致范围，所以问题就转化为，投入最少的警力以最快的速度形成包围圈，并确保嫌疑犯在这段时间内无法跑出包围圈，即可认为围堵方案成功。五、模型的建立5.1 问题一：（1）对于第一个子问题，考虑使用 0-1 整数规划模型，下面确定目标函数和约束条件。观察每个路口节点平均每天的发案率，发现发案率不是很大，所以追加假设为每个服务平台有足够的时间去处理管辖范围内的突发事件，即当某个服务平台处理一起突发事件的同时，在它所管辖的区域内不会发生其他的突发事件。设问题的决策变量为 是 0-1 变量，即ijx1,A0 iij j Ax当 中 心 城 区 的 第
14、 个 节 点 事 发 时 ， 由 服 务 平 台 管 辖 ，否 则1,20;1,29ij ( )为了及时高效地处理突发事件，警方到达事发地应争分夺秒，在满足时间紧迫性要求的前提下，使得平均每个案件的出警时间最短，所以确立了平均每个案件的出警时间最短作为唯一的目标。然后确定了两个约束条件，一是当每个路口节点有突发事件发生时，都至少有一个服务平台的交巡警到达现场处理事件；二是要求任一服务平台到达其所管辖的路口节点的时间都小于 3 分钟。于是问题就转化为求下面的 0-1 整数规划问题： 2091min,jiijjjwtxT4201(1,29);.30,2)ijijxjst j （2）对于第二个子问题
15、，我们仍考虑使用 0-1 整数规划模型。用 表示决策变量，即kijx1,0k ikij Ajx服 务 平 台 到 第 个 出 入 口 节 点 封 锁 交 通 要 道 ;否 则其中 1,20ikjJ,3根据对问题的分析，要实现对要道的快速全封锁，所以模型的目标是使封锁所有要道的总时间最短。所以关键在于控制封锁要道所需时间最长的服务平台的出警时间，使之达到最小值。确定了两个约束条件，其一是当每个路口节点有突发事件发生时，都至少有一个服务平台的交巡警到达现场处理事件；其二是一个平台的警力最多封锁一个路口。故，建立以下数学模型 2minax,kijTt2013,13;.,20kkijijxsti（3）
16、对于第三个子问题，首先分析现有的交巡警服务平台的分布，发现存在交巡警服务平台工作量不均衡和部分路口节点出警时间过长的问题。这时考虑新增加几个服务平台，使得各个交巡警服务平台的工作量尽可能相同以及使各个路口节点出警时间都被控制在 3 分钟内。新建服务平台需要成本，所以需要合理确定服务平台的选址，使需要建立的服务平台的数目最小。由此，我们参考集合覆盖模型，建立了一个两目标0-1 整数规划模型。设增加交巡警服务平台后，平台总数为 。n设平均每个交巡警服务平台的建设成本为 1。对这一问题需要引入决策变量 ，设决策变量 为ijaija1,0ijijt3;,29;,29 ( )定义服务平台的工作强度为平均
17、每天处理的突发事件数，则记 表示第 个服务平iqi台的工作强度。集合覆盖模型中考虑了建立服务平台的成本，在给定 3 分钟到达事发地的条件下，其目标之一是建设成本最小。另一方面，考虑到要使得各个服务平台的工作量基本平衡，所以确定第二个目标为各个服务平台平均每天工作强度的方差最小。模型描述为5921minjjy22();iiSq921,9.0,2ijjayst其中 921ijnyjjqw921,9ijijjay第一个约束条件说明所有路口节点都必须满足在突发事件发生 3 分钟内有警方到达事发现场的要求。第二个约束条件则说明如果在 点增设服务平台， 为 1，否则为j jy0。5.2 问题二：5.2.1
18、 对交巡警服务平台设置方案的合理性研究（1）首先建立线性加权评价模型来分析评价该市交巡警服务平台设置方案的合理性。根据第一问第一个子问题的模型，对六个区和全市可分别求出服务平台的覆盖率和平均每个服务平台工作强度的方差。确定两个评价指标，分别是各个区的服务平台覆盖率以及各个服务平台的工作强度。设各个区和全市的服务平台覆盖率为 ，做归g一化处理后的数据为 ；各个区内服务平台工作强度的方差为 ，方差的倒数 ，做gn ss1归一化处理后的数据为 。那么综合评价指标 为vhvngnh)1(其中， 为权重系数， 。1,0（2）如果在全市范围内，现有交巡警服务平台设置方案存在明显的不合理性，那么可能存在如下
19、两种原因：第一，该市分配给各个区的交巡警服务平台资源比率不合理；第二，各个区内的交巡警服务平台选址方案不合理。对于第二种原因，在第一问第三个子问题中对 A 区交巡警服务平台设置方案已经做过详细讨论，现在设法解决由第一种原因引起不合理性的问题。现要在全市范围内重新分配警务资源，也就是重新为每个区分配交巡警服务平台的数目。由于每个区的实际状况有所不同，那么每个区对交巡警服务平台的需求量也不尽相同。所以要根据每个区域内对交巡警的需求量的大小来确定每个区域设置服务平台数目占总的服务平台数目的比率。为此，需要引入各区域需求的权重来定量描述每个区对服务平台的需求量。下面确定各区域对交巡警需求的权重指标。从
20、服务群众的角度考虑，可假设每个人需要交巡警帮助的概率相同且相互独立。那么，一地区对交巡警服务平台的需求就与当地人口密度有关，人口密度越大，需求越大，所以引入人口密度为影响交巡警服务平台设置的第一个指标。由分析知，人口密度是极大型指标，即这个指标越大，对交巡警服务平台的需求越大。记这一指标为 ，则对应到 A，B，C，D，E，F 六个区为r。从交巡警服务平台覆盖率的角度考虑，当这个区域的公路总长度越长时，126,r6则要求交巡警服务平台的密度越大，也就是交巡警服务平台的需求量越大，于是引入公路长度作为第二个指标。此外，交巡警服务平台的工作强度考虑，发案率大的地方要多配备警力，于是引入发案率作为影响
21、交巡警服务平台设置的第三个指标。确定好指标后，对指标进行定量处理。1）各区域人口密度 ， ，其中， 为第ksnr )FE,DCB,A,621( 六 个 区对 应 着 kn区的总人口数， 为第 区的总面积；k2）主要交通干路总长度 ；kl3）发案率 ， 。kNiiwf )(区 的 节 点 集 合表 示 第这三个指标构成矩阵 rAlf其中 ),(r621rll,ffStep1：一致化处理。由于这里的三个指标均为极大型指标，故不需要一致化处理。Step2：无量纲化处理。分别求出每个指标的均值 和均方差 ，无量纲处理flr,flrs,为， ，61*)(rks61*)(lksl 61*)(fksfSte
22、p3:求权重。采用极差法求权重，为了求得权重，先求出，|max*6,1jijir同理可求得 和 ，令 ，则权重lfflrz),(),(flzflr则第 区分配的服务平台资源比率为k 616161ikfiklikrk5.2.2 最佳围堵方案为了解决问题，我们追加假设：犯罪嫌疑人逃跑的速度是恒定的，且等于警车的时速 60km/h。（1）方案一：考虑到一般嫌疑犯对作案周边环境比较熟悉，且嫌疑犯并不清楚是否有人报警以及报警的具体时间，故嫌疑犯会尽量选择避开交巡警服务平台所在的节点。那么嫌疑犯的逃跑的路线的组合就会减少很多。这样围堵方案的确定就简单很多。（2）方案二：方案一本身存在一定缺陷，因为嫌疑犯是
23、否对周边环境熟悉，熟悉程度是多少，以及嫌疑犯的心理和性格状态如何，这些都是不确定的。所以，嫌疑犯仍然可能随机选择逃跑的方向，这时嫌疑犯可选择的逃跑路径有很多种，围堵方案也较难7确定。但是两个模型的求解思路是一致的。最佳的围堵嫌疑犯的方案，就是在出动的警力最少的情况下，在最短时间内把嫌疑犯围堵在一个尽可能小的包围圈内，使嫌疑犯不能逃出这个包围圈。具体围堵方案的步骤如下：1）确定嫌疑犯 3 分钟内可以经过的最多的点数，由于嫌疑犯是从 P 点连续移动的，所以这些节点构成的图是连通图，设为 ，同时可以认为 就是嫌疑犯的活动范围。GG以外的点中是嫌疑犯尚未经过的节点，其中有若干节点与 直接相连，这些节点
24、就G是嫌疑犯下一步可能经过的节点，记它们的集合为 ，记在 内与 直接相连的节点BB构成的集合 ，它表示嫌疑犯可以从 中某点出发，前往与之直接相连的 中的某点，DD以扩大其活动范围。当 时，嫌疑犯就不能扩大其活动范围，这样，相当于嫌疑犯被限制在了一个有限的区域，即嫌疑犯被成功围堵。2）取 ，并取 ，且 可由 直接到达，这样就构成一个出逃的组合。以交kdibBikd巡警接到报警的时刻为时间的原点，这时计算嫌疑犯和距离 最近的交巡警到达 的ibib时间，分别记为 和 。当 ,表示嫌疑犯会先到达 ，而交巡警后到达 ，这样，xitjixijit交巡警就不能围堵成功，于是，嫌疑犯成功将活动范围扩大到 ，即
25、应该将 加入到i i活动范围 ，且 可以作为下一步扩大活动范围的起始点，于是还应该将 加入到 ，Gib D且与 直接相连且在 外围的节点加也要入 。注意此时 可能不再有 外的节点与i BkdG它直接相连，这时是需要将 从 中删除的。当 ，则嫌疑犯到达 的时间不kdDxijitib比交巡警早，这样交巡警就可以将嫌疑犯逃跑的这条路围堵死，调遣这些交巡警前往，且当他们被选定之后，就不能被再次调动，因为他们一旦被调走，可能使嫌疑人ib从这个节点摆脱围堵。在 的情况下，由于嫌疑人不能扩大活动范围到 ，于是xijit i就不能加入 ，这时要把 从 中删除。如果原先 向外只与 直接相连，那么当i GbBkd
26、ib把 从 中删除时， 就不能作为嫌疑人扩大活动范围的起始点，这时需要把 从Bkd kd中删除；如果原先除了 ， 还与 中其他节点直接相连，则不能把 从 中删除。Dik kD这样逐个对 和 中直接相连的节点组合（即出逃组合）进行如上分析，当D时，嫌疑犯被限制在了一个有限的区域，即嫌疑人被围堵成功。围堵成功时，各交巡警所在的位置即他们应该在接到报警时被派遣到的位置。这样就确定了围堵调遣的方案。综上所述，建立模型如下： min()1()FGHI582.0stI初始条件为 ， ，即初始时刻 的点集和 的点集。G0I I表示求 中点的个数的函数， 表示交巡警服务平台的集合， 表示求()xF ()HI中
27、改变位置的交巡警服务平台的个数的函数，即求调遣的交巡警服务平台的个数的I函数， 表示权重。0,1从初始条件开始，进行上面算法，直到 或者约束条件不满足停止。当 ，DD则围堵成功，从所有出逃组合中选出目标函数最优的围堵方案，就可以确定出最优调遣方案；当约束条件不满足，则表示嫌疑犯成功摆脱围堵。下面给出算法流程图。8开始初始化 0,IG并确定 D 和 B 直 接 相 连，且取 iibbkkd,d计算嫌疑犯和距离 最i近的交巡警到 的时间ibjixt和成 立 ？jiixt加入 G 和ibD从 B 中删除ib结束是 否判断 是否kd仍有 G 外的点与之直接相连是不做 从 D 中删除 kd否D 是否为空
28、集或者约束条件是否不满足？是 否图 1 围堵方案的算法流程图9六、模型的求解6.1 问题一：（1）第一个子问题需要先用 floyd 算法求解出各交巡警服务平台到各个路口节点的最短距离，在此基础上再求解 0-1 整数规划模型。这个整数规划模型的 0-1 变量有 1840个，考虑用基于 MATLAB 的模拟退火算法求解。根据约束“任一服务平台到达其所管辖的路口节点的时间都小于 3 分钟”来过滤可行域，发现某些路口节点并不能严格地满足“ ”这一约束条件，对于这类路口节点，可以放宽约束为 ，使3ijtx 3(1)ijjtx可行域不为空集。用模拟退火法求解模型时，设置初始温度 为 100000，终止温度
29、0T为 0.0001，温度衰减系数为 0.995，Markov 链长度为 100，求得一个较优解的目标fT值为 1.013 分钟，管辖范围如下：表一 A 区各服务平台的管辖范围依据这个较优解，可求得 A 区各个服务平台的工作强度（平均每天处理案件的次数）如下：表二 中心城区 A 各服务平台的工作强度（次/天）服务平台 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10工作强度 9.2 6.9 6 5.8 7.7 4.5 9.6 5.2 7.4 1.6服务平台 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20工作强度 4.6 4.0 8.5 2.5 4.8
30、 5.6 7.0 4.3 6.8 12.5服务平台节点 管辖的节点A1 A1,A64,A67,A68,A69,A71,A73,A74,A75A2 A2,A39,A40,A43A3 A3,A44,A54,A55,A66A4 A4,A57,A58,A62,A63A5 A5,A49,A50,A51,A52,A53,A56A6 A6,A58,A59A7 A7,A30,A31,A32,A48,A61A8 A8,A46,A47A9 A9,A33,A35,A36,A45A10 A10A11 A11,A26,A27A12 A12,A25A13 A13,A21,A22,A23,A24A14 A14A15 A15,A28,A29A16 A16,A37,A38,A34A17 A17,A41,A42A18 A18,A81,A84A19 A19,A65,A76,A77,A78,A79,A80A20 A20,A82,A83,A85,A86,A87,A88,A89,A90,A91,A92
