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

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

    交巡警服务平台的设置与调度^[1]

    谢滨璜　李亚玮　赵向阳

    摘　要:摘要交巡警对维护城市治安，保障市民生活有重要作用，而合理的交巡警服务平台的设置和调度对于提高交巡警的执勤效率有重要意义。本文即对这一问题进行量化分析，得出交巡警服务平台设置和调度的最佳模型。

    问题一，给A区平台分配管辖路口，尽量使各路口都有交巡警在3分钟内到达。这实质是一个最优分配问题，目标是各平台到它所辖各路口的总时间最短。首先用弗洛伊德算法可得出A区任意两路口的最短路径，也就得出了任意两路口的最短时间，再用lingo软件根据0-1规划的方法建立了最优分配模型。

    问题二实质上也是一个最优分配问题，即要从A区的20个平台中选出13个去封锁A区的13个出口，使得封锁时间最短。同样用Lingo软件根据0-1规划的方法求得最优分配模型，得出最短封锁时间为8.274 2分钟。

    问题三是要改善A区平台设置的不合理之处。我们引入量化指标平台i所辖路口发案率总和x_i和到达所辖路口的平均出警时间y_i，用相对比较法赋予这两个指标权重w₁和w₂，根据层次分析法建立了每个平台工作压力指数u_i的量化模型。分析压力指数u_i，要增加4个平台分担压力指数明显偏大平台的工作压力。最后检验有一个平台不能满足问题1中3分钟到达的条件，因此要再增加一个平台，所以最终需要增加5个平台。增加平台的具体位置根据穷举法和就近原则来确定。

    关于问题四，我们首先用各城区人口密度和发案率占全市总和的比例p_i和q_i两个指标，根据层次分析法建立了各区的平台需求量化模型，计算出了各区所需平台数。根据平台到所辖各路口平均时间最短的原则建立了平台的最佳位置设置模型，以B区为例进行了求解，得出了B区平台的最佳设置位置，再对模型进行推广得到了任一个城区的最佳位置设置模型。根据模型计算结果与目前全市的平台设置方案进行对比，科学评价了全市平台设置方案的合理性，并给出了不合理部分的解决方案。

    针对问题五，根据疑犯逃跑速度，可以确定报警时疑犯在一个以P点圆心的圆形区域内。通过分析实际地图，可得出疑犯下一步可能通过的路口。为了能最大限度地使疑犯不逃出该市，并实现快速搜捕的目标。我们调动全市平台警力同时围堵全市出口和疑犯下一步可能通过的路口。具体平台的调度与问题二相同，也是一个最优化问题，根据问题二的思路用Lingo软件求解可得到最佳围堵方案。

    关键词:平台设置与调度;弗洛伊德算法; 0- 1规划;层次分析法;穷举法

    一、问题重述

    (一)问题的提出

    “交巡警合一，并不是将交警、巡警部门简单合并，而是要实现‘ 1 +1＞2’的效能” 。自从我国实行交巡警模式以后，路面抢夺案件大幅度下降，交通违章事故明显减少。可见如何正确地在市区的一些交通要道和重要部位设置交巡警服务平台是多么的重要。但警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台的位置、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。如何借助数学的思想方法建立数学模型实现交巡警平台最有效率的设置和调度即是本文要研究的内容。

    (二)要解决的问题

    1.A区各交巡警服务平台管辖范围的分配

    根据A区交通网络的实际情况，利用相关数据为A区20个交巡警服务平台分配具体的管辖范围，使其在所管辖的范围内出现突发事件时，能尽量保证有交巡警在3分钟内到达事发地。

    2.对A区实行快速全封锁的最佳调度

    如果在A区内有重大突发事件发生，就需要调度全区内的20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。

    3.确定A区增加交巡警服务平台的个数和位置

    A区现有的交巡警服务平台有工作量不均衡和有些地方出警时间过长的问题，A区打算再增加2至5个平台以解决该问题，需要确定增加平台的具体个数和位置。

    4.评价全市现有交巡警服务平台设置的合理性

    针对全市(主城六区A，B，C，D，E，F)交巡警服务平台设置的具体情况，按照交巡警服务平台的设置原则和任务，分析评价该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，给出解决方案。

    5.确定快速搜捕疑犯的最佳围堵方案

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

    二、模型假设

    (1)在发生重大紧急事件时，各区交巡警可以跨区行动。

    (2)交巡警在行驶过程中不会遇到阻碍。

    (3)由于可能的事件发生点在街道上均匀分布，因此假设每一条街道上发生的事件都集中在路口上。

    (4)在同一警点管辖范围不会同时发生两个事件。

    (5)当连接两路口的最短路径不止一条时，可以任选一条。

    (6)假设疑犯逃跑速度与警车速度相同为60km/h。

    三、模型变量与符号说明

    a_i:A区第i个交巡警服务平台

    a_j:A区第j个路口

    b_i:B区第i个交巡警服务平台

    b_j:B区第j个路口

    a_k:A区第k个出入口

    s_ij:A区第i个交巡警服务平台到A区第j个路口的最短路径长度

    t_ij:第i个交巡警服务平台到第j个路口的最短时间

    t_ik:第i个交巡警服务平台到第k个出入口的最短时间

    v:警车速度和嫌疑犯逃跑速度

    x_i:A区交巡警服务平台i管辖的所有路口每天发生案件数总和

    y_i:A区第i个交巡警服务平台到管辖的所有路口的平均时间

    w₁:A区平台i管辖的所有路口每天发生案件数总和指标x_i的权重

    w₂:A区平台i到管辖的所有路口的平均出警时间指标y_i的权重

    u_i:A区平台i的工作压力指数

    p_i:第i个城区的人口密度占全市各区人口密度之和的比例

    q_i:第i个城区各路口发案数总和占全市各路口发案数总和的比例

    w₃:第i个城区的人口密度占全市各区人口密度之和的比例指标p_i的权重w₄:第i个城区各路口发案数占全市各路口发案数的比例指标q_i的权重

    r_i:第i个城区交巡警服务平台的需求系数

    四、问题分析

    (一)问题1的分析

    A区现有交巡警服务平台20个，要负责全区92个路口的突发事件处理，给现有的20个交巡警服务平台分配管辖范围，使得所管辖的范围内出现突发事件时尽量能保证在3分钟内有交巡警到达事发地，首先的考虑就是确定一种分配，使得每个路口发生突发事件时都能有交巡警在3分钟内到达，但在具体实现时发现无论何种分配总有若干个路口不能满足3分钟到达的条件。

    这样，为了保证尽可能在3分钟内有交巡警到达事发地，我们把问题转化成最优化问题，即寻求一种最优分配使得A区的第a_i个交巡警平台到A区第a_j个路口的总时间最短，也就是平均时间最短，这样就建立了A区各平台管辖各路口的最优分配模型。具体算法实现上，可以采用弗洛伊德算法求出最短路径，也就求出了最短时间，这样就可以确定20个交巡警服务平台的最优管辖范围。

    (二)问题2的分析

    题目要求在发生重大事件时，全区20个平台的警力资源需快速封锁全区13条交通要道，由于实际中一个平台警力最多只能封锁一个路口，故要从20个交巡警服务平台中抽调13个平台警力去封锁交通要道的13个路口。考虑到发生重大事件的地点和犯罪分子从哪个路口逃逸不确定，我们认为犯罪分子从每个路口逃逸的概率是相等的，因此我们要给出的调度方案应该使得13个交巡警平台到达13个路口的总时间最短，也就是平均时间最短，可以用0—1规划来实现，利用lingo软件分析确定了A区交巡警服务平台警力最优的调度方案。最后将得到的数据联系现实评价其合理性，若发现结果有不合理的地方，则要对模型进行优化改进。

    (三)问题3的分析

    1.如何确定需要增加平台的个数

    A区现有的交巡警服务平台设置存在的具体问题是:各平台的工作量不均衡和有些地方出警时间过长。

    针对这个问题，可以设置A区平台i所辖路口发案率总和指标x_i和平台i到达管辖的所有路口的平均出警时间指标y_i，然后分别赋予这两个指标权重w₁和w₂，根据层次分析法建立每个平台工作压力指数u_i的量化模型，求出每个平台的工作压力指数u_i，这样得出了工作压力指数明显偏大的平台，为了分担这些平台的压力，就要增加一些平台来分担压力较大平台的管辖路口。

    然后对模型进行检验，第一问中不能满足在突发事件发生时有交巡警在3分钟内到达事发地点的路口是否得到了满足，如果仍有路口不满足3分钟到达的这一条件，就要额外增加一些平台来满足所有路口都能3分钟到达的条件。

    这样，根据这两个原则就可以确定需要增加平台的具体个数。

    2.如何确定增加平台的具体位置

    如果增加的平台是为了分担压力较大平台的管辖路口，我们可以用第一问中的最优分配模型，在压力较大平台的管辖范围内增加一个平台后，重新分配这两个平台的最优管辖范围。但实现这种最优分配的前提是两个平台的位置要具体确定下来。为此，我们采用穷举法，即求出新增平台在各个位置最优分配管辖范围后的最短总时间，在求出的最短总时间中选择总时间最小的那个方案，此方案对应的位置即为新增平台应该设置的位置。

    如果对模型检验后发现仍有一些点不能满足在3分钟内有交巡警到达的条件，就要额外设置交巡警服务平台满足这一条件。为实现这一目的设置的平台，要确定其具体位置我们可以采用就近原则，即在距离不满足3分钟到达的点最近的路口设置平台。

    (四)问题4的分析

    要问题4的解决，首先要明确设置交巡警服务平台的原则，通过查询相关资料，我们确定交巡警服务平台设置的原则为:

    (1)按需设置原则:根据各个区的实际需求合理配置各区的交巡警服务平台个数。此原则可以评价各区的平台个数是否合理。

    (2)快速出警原则:合理设置平台位置，接到报警后快速到达所管辖的路口。此原则可以评价各区平台位置设置是否合理。

    根据以上两个原则，可以建立各区交巡警服务平台的需求模型r_i，根据此模型计算出各区实际需要的交巡警服务平台个数，然后与各区目前实际存在的平台数对比，以此来评价各区服务平台个数的设置是否合理。

    然后建立交巡警服务平台的最佳位置模型，求出各区交巡警服务平台的最佳设置位置，对比各区目前平台的实际位置来评价各区平台位置设置是否合理。

    关于建立各区交巡警服务平台的需求模型r_i，通过查询相关资料，一个地区需要的交巡警服务平台数目主要受该地区的人口密度和发案数量的影响。所以我们选取这两个因素为指标，并赋予每个指标一定的权重，用层次分析法来确定各城区交巡警服务平台的需求系数r_i，然后用需求系数r_i乘以全市现有的交巡警服务平台总数，得出每个区最合理的交巡警服务平台个数。

    关于交巡警服务平台的最佳位置模型，我们基于快速出警原则的考虑，要使每个平台到达所辖路口的总时间最短，即平均时间最短。

    (五)问题5的分析

    P处发生重大刑事案件，在案发3分钟后接到报警，此时犯罪嫌疑人已驾车逃跑。根据模型假设，嫌疑人逃跑速度和警车速度相等，在接到报警时嫌疑人应在以P点为圆心，以3分钟里程3km为半径的圆形区域内。所以，为了最快搜捕嫌疑犯，应在圆形区域以外的路口进行围堵。我们可以先求出嫌疑犯下一步可能到达的路口，然后调动离可能到达路口最近的平台警力去围堵该路口，这样可以把嫌疑人围堵在一个最小区域内，实现快速搜捕嫌疑犯的目的。但考虑到交巡警服务平台设置的具体现状和各平台警力在去围堵各路口的同时嫌疑人也在移动，只能实现最大可能性地把嫌疑人围堵在该区域内，仍有可能有极个别路口在警力实现围堵前嫌疑人已经逃过该路口。针对这种可能的漏洞，我们可以在得到报警的第一时间调动全市警力快速封锁出入全市的各个出口，这可以借助问题2中的模型，得到对该市实现快速全封锁的最佳警力调度方案，这样就弥补了上述漏洞。

    根据以上分析，该问题的关键点有两个:一是要保证能最大限度地抓捕嫌疑人，二是要尽量缩小围堵区域的范围，使得搜捕时间最小。

    基于以上两点思考，我们同时进行两种调度来围堵嫌疑犯:一是在得到报警的第一时间调动全市警力快速封锁出入全市的各个出口，二是围堵嫌疑犯下一步可能达到的路口。

    五、模型的建立与求解

    (一)问题1的解决

    根据问题1的分析，问题1是一个最优分配问题，即建立A区各平台管辖各路口的最优分配模型，使得A区的第a_i个交巡警平台到A区第a_j个路口的总时间最短，也就是平均时间最短。根据弗洛伊德算法可以求出第a_i个交巡警平台到A区第a_j个路口的最短路径，这样也就求出了最短时间，确定了20个交巡警服务平台的最优管辖范围。

    建立的最优分配模型如下:

    目标函数:M = min∑∑t_ij.x_ij1≤i≤201≤j≤92

    计算的每个平台最佳管辖范围如下表1所示:

    

    表1　A区各平台的最佳管辖范围

    

    管辖范围用图形表示如下:

    “⊙”表示平台到该平台的时间大于3分钟

    

    (二)问题2的解决

    根据问题2的分析，该问题是要用0—1规划的方法从20个交巡警服务平台中选出13个去封锁A区的出口，并使得到达的总时间最小，即平均时间最小。

    第一步:建立模型

    目标函数:M = min∑∑t_ik.x_ik1≤i≤201≤k≤13

    

    通过lingo软件(附录三)求出最优解，如下表2所示:

    

    表2　实现快速全封锁的最佳调度方案

    

    

    续表

    第二步:分析数据

    分析上一步得出的数据，发现第8个平台和第9个平台到达自己所要封锁的路口最短时间分别为:T₈=10.493分钟、T₉=11.539分钟

    与其他数据相比，这两个平台的出警时间过长，不符合快速封锁各路口的原则，因此我们在原模型的基础上进行改进。

    第三步:模型改进

    在原模型的基础上，我们增加一个限制条件:max(x_ij， t_ij)＜9

    得到新的模型:

    目标函数:M = min∑∑t_ik.x_ik1≤i≤201≤k≤13

    通过lingo软件编程(附录四)求出最优解，如下表3所示:

    

    表3　模型改进后实现快速全封锁的最佳调度方案

    

    第四步:模型比较

    改进后模型的数据:

    　　max(x_ij， t_ij) =8.274 2，总时间M = 46.188 5

    原模型数据:

    　　max(x_ij， t_ij) ' =11.539，总时间M' =46.188 1

    通过比较二者之间的数据发现，两者的目标函数相差值

    　　M- M' =0.000 4

    差距可以忽略不计，而两者的最大值的相差值

    　　max(x_ij， t_ij) '- max(x_ij， t_ij) =3.264 8

    　　3.264 8》0.000 4

    与原模型相比，两者的目标函数相差值很小，而两者的时间最大值的相差值却很大，这意味着在保持平均时间基本不变的前提下，可以更快的实现所有路口的全封锁。因此，改进后的模型比原模型更加合理，更加符合快速封锁各路口的原则。

    (三)问题3的解决

    根据问题3的分析，问题3的解决可以选择两个量化指标:平台i所辖路口发案率总和指标x_i和平台i到达所辖路口的平均出警时间指标y_i。通过赋予这两个指标一定的权重w₁和w₂，运用层次分析法建立A区每个平台i的工作压力指数量化模型，求出每个平台i的工作压力指数量化值u_i，选出工作压力指数明显偏大的平台，通过增加平台个数分担这些平台的工作压力。最后还要对模型进行检验以验证是否满足了问题1中3分钟到达的条件。若仍然有不满足的平台，还可以考虑再次增加平台个数。确定需要增加平台的具体个数后，根据问题分析中的穷举法和就近原则确定增加平台的具体位置。

    1.确定需要增加平台的个数

    按下面六个步骤确定增加平台的个数:

    第一步:建立平台i所辖路口发案率总和指标x_i

    根据题目附件数据，求出每个平台i所辖路口发案率的总和x_i，求出的结果如下表4所示:

    

    表4　每个平台i所辖路口每天发生案件数的总和x_i

    第二步:建立平台i到达所辖路口的平均出警时间指标y_i

    根据附件数据，求出每个平台i到达所辖路口的平均出警时间指标y_i，求出的结果如下表5所示:

    

    表5　每个平台i到达所辖路口的平均出警时间指标y_i

    

    第三步:确定两个量化指标的权重

    根据相对比较法确定平台i所辖路口每天发生案件数总和指标x_i和平台i到达所辖路口的平均出警时间指标y_i的权重值w₁和w₂。

    求得w₁=0.4和w₂=0.6

    第四步:建立平台i的工作压力指数量化模型

    用两个评价指标的量化值分别乘以对应的权重得出每个平台i的工作压力指数量化值u_i，其模型如下:

    即u_i= w₁·x_i+ w₂·y_i

    Matlab计算(附录五)得出的每个平台i的工作压力指数量化值u_i如下表6所示:

    

    表6　每个平台i的工作压力指数量化值u_i

    第五步:选出工作压力指数明显偏大的平台

    分析A区20个交巡警服务平台的工作压力指数发现，明显偏大的数据是0.568 7、0.566 7、0.729 3、0.610 0。其对应的平台分别是2、7、15、20，所以因该在平台2、7、15、20管辖范围内各增加一个平台来分担这些平台的工作压力，这样需要增加4个服务平台。

    第六步:对模型进行验证

    经验证，在平台2、7、15、20管辖范围内各增加一个平台后，仍有路口38不能保证有突发事件发生时有巡警在3分钟内到达事发地。为此，仍要再增加一个平台解决这个问题，根据就近原则直接在路口38处增加一个平台。

    综上所述，最终需要增加平台的个数为5个。

    2.确定增加平台的具体位置

    利用穷举法，求出增加的平台在所有可能位置时对应的新旧平台到所管辖路口的最小总时间，选取这几个最小总时间中最小值的位置即为新增平台应该在的位置。

    我们的计算结果如下表所示:

    

    表7　在平台2所辖区域新增一个平台

    

    表8　在平台7所辖区域新增一个平台

    

    续表

    

    表9　在平台15所辖区域新增一个平台

    

    表10　在平台16所辖区域新增一个平台

    

    表11　在平台20所辖区域新增一个平台

    

    续表

    (四)问题4的解决

    1.各城区交巡警服务平台需求模型

    我们认为发案情况这一因素的重要性远大于人口密度因素，故我们设置的指标p_i的权重w₃=0.25，指标q_i的权重w₄=0.75。

    根据附件数据计算的结果如下表12所示:

    

    表12　各区实际需要平台数

    

    续表

    取整数后每个城区需要的交巡警服务平台数为:

    A25B7C18D7E12F11

    2.交巡警服务平台最佳位置设置模型

    根据快速出警的原则，交巡警服务平台的设置要满足这样的条件:使得每个平台到达所辖路口的平均时间最短。

    下面以B区为例建立最佳位置设置模型:

    B区的平台数根据实际需要经调整后为7个，B区共有路口73个，建立模型如下:

    目标函数:M = min∑∑t_ij， x_ij1≤i， j≤73

    约束条件:

    用Lingo进行计算(附录七)可以求得7个平台的位置。

    最佳位置设置模型的一般化扩展:

    假设i区有n个路口，实际需要m个交巡警服务平台，其最佳位置设置的一般化模型如下:

    目标函数:M = min∑∑t_ij， x_ij1≤i， j≤n

    约束条件:

    以上模型即为最佳位置设置的一般化模型。

    3.交巡警服务平台设置不合理的解决方案

    根据上面建立的模型计算出的实际需要平台数和最佳位置设置与目前该市平台设置方案对比结果如下:

    

    表13　各城区实际需要的平台数和目前平台数对比表

    根据上表，为使全市交巡警服务平台设置更加合理，首先要调整各区的平台数，具体调整结果为:A区增加5个平台　B区减少1个平台　　　　　　　　　　

    C区增加1个平台　D区减少2个平台　　

    E区减少3个平台　F区保持现有数目不变

    

    表14　B区平台设置的最佳位置与目前位置的对比表

    

    

    图1

    根据上表，B区目前平台位置设置不合理，解决方法是把平台设置在路口93、99、102、114、124、136、151处。

    根据一般化的最佳位置设置模型，可以求出全市其余5个城区平台的最佳设置位置。

    (五)问题5的解决

    针对围堵疑犯的问题，交巡警要同时封锁整个市区出口和在A区可能通过的路口，就能保证疑犯不能逃出市区，并且尽快抓捕。我们将问题分为两步求解:(1)封锁A区中疑犯可能通过的路口; (2)封锁全市。

    由于是在案发t =3mins后接到报警，犯罪嫌疑人已驾车逃跑。我们假设疑犯的逃跑速度也是v =60km/h，据此假设计算出疑犯最远可以逃出的距离为:

    d = vt =3km

    可推出疑犯能逃离以P点为中心，半径为3km的范围。交巡警应该在此圆外设下围堵点才能最大概率的抓住疑犯。因此我们将A区中的点用Excel筛选后分为四类:

    1.与P点的路程在3分钟以内的路口集合:●= { 7， 8， 9， 30， 31， 32， 33， 34，35， 36， 45， 46， 47， 48} ;

    2.通过●经过一条路能够到达的A区中的路口集合:●= { 3， 5， 6， 10， 15， 16，29， 39， 55， 61} ;

    3.交巡警能在疑犯之前到达，从而封锁的路口:●= { 3， 5， 6， 10， 15， 16，55} ;

    4.交巡警不能在疑犯之前到达，只能放弃，借助其他区警力封锁:●={ 29， 39， 61， 235， 237} 。

    结果如图1:

    “O”内数字是从P点出发3分钟可以到达的路口U₁

    “→”是从U₁路口出发可以到达的第一个路口U₂

    以最少警力投入最快抓住疑犯为原则，可以得出封锁策略如下:

    对于U₃类路口，交巡警必须提前围堵;对于U₄类路口，我们通过对市区地图分析可知路口29，30，48，60都通往C区，39通往F区，在第一步中我们已经封锁C区两个出口和F区唯一一个出口，这样疑犯就已经完全被包围，且耗费警力最少。

    设t₁=歹徒到达U₃中路口的时间(案发3min后开始计算) ，t₂=交巡警到达U₃中路口的时间。则必须有t₁≥t₂，警察才能提前到达路口。通过Excel进行计算，结合图表分析可以得出表15，即总时间为2.111 7分钟。

    

    表15

    第二步可以归结到0-1规划的问题，也就是调度全市的80个警点警力围堵17个出口。我们封锁的原则是平均时间最短，这样可以节约警力资源并且交巡警一定可以在疑犯到达出口之前赶到。规划方程如下:

    目标函数:min∑∑T_ij.x_ij， 1≤i≤80， 1≤j≤17

    用Lingo软件编程(附录八)可得到封锁配对结果:

    

    表16

    【注释】

    [1]本文为2011高教社杯全国大学生数学建模竞赛参赛作品。