1、交巡警服务平台的设置与调度交巡警服务平台的设置与调度摘要 本文建立了交巡警服务平台设置与调度的优化模型，将出警时间和工作量作为考虑因素，设置城市交巡警服务平台，分配各平台的管辖范围，并在发生突发事件时对警务资源进行调度。针对问题一的第一小问，根据出警时间的条件限制，初步确定城区A中20个服务平台对92个交叉路口节点的相应管辖范围，以交巡警服务平台的工作量方差最小为目标进行优化，使用lingo程序求解得到20个交巡警服务平台的管辖范围，工作量方差为2.9479。对于第二小问，从全区20个交巡警服务平台中选取13个平台对全区13个交通要道实现了全封锁，以服务平台到达节点的最长时间最短为目标，用li
2、ngo求得封锁时间为8.015分钟，并给出了具体的封锁方案（即选定的13个交巡警服务平台与13个被封锁要道的一一对应关系）。对于第三小问，由于存在工作量不平衡和出警时间过长的情况，以交巡警服务平台的工作量方差最小为目标，经分析至少需要增加4个平台（节点编号分别为29,39,48,91）才能满足出警时间限制，经lingo求解得到具体服务平台分配方案，且最小方差为1.99。针对问题二的第一小问，在全市范围内，以出警时间限制和各服务平台均衡工作量为依据，使用lingo程序计算，得到工作量方差为27.21，且有138个节点不满足出警时间要求，可知现有交巡警服务平台设置方案是不合理的。经lingo程序计
3、算至少需要增加54服务平台才能使这138个节点满足出警时间要求，经优化使用lingo程序求得增加平台后的方差为5.098，明显优于原方案，此分配方案更加合理。但是由于实际警力资源的限制，增加54个平台的个数相对较多，对此我们给出对现有警力配置，重新分布并适当增加平台数目的数学模型。对于第二小问，该模型利用蚁群算法1的思想，通过matlab程序模拟犯罪嫌疑人的逃窜路线，文中定义了一个新名词，即封堵有效性，以此为依据，提出一个有效且合理的嫌犯围堵方案，并且对该方案进行了可行性分析和封堵有效性检验，结果显示该模型很好。封堵有效性包括两方面：一是封堵任务顺利完成，封堵圈无疏漏；二是确认犯罪嫌疑人仍在封
4、堵圈之内。关键字：全局最优 多目标规划 方差 封堵有效性一、 问题重述1.1问题引言警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，则需根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。1.2题目所给信息（1）该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图以及相关的数据信息；（2）全市包括主城六区A，B，C，D，E，F；（3）警车的时速为60km/h；1.3需要解决的问题(1）为A城区20个交巡警服务平台分配管辖范围，使其
5、在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。对于重大突发事件，调度A区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。(2）按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑
6、。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、 问题分析根据城市的实际情况与需求，对城市交巡警服务平台进行分配，使其在发生突发事件时可以对警务资源及时合理的进行调度。问题一，主要是对该市中心A城区的所有交巡警服务平台位置分布进行优化。可分为三个问题：1、根据城区A的20个交巡警服务平台以及92个交叉路口节点的分布情况，确定各交巡警服务平台的管辖范围。由于出警时间存在限制，故需在满足时间条件的基础上，使92个交叉路口节点尽可能的分配给所有服务平台，同时必须满足一个节点只能由一个交巡警服务平台来管辖。2、针对重大突发事件，要求合理调度城区A的20个交巡警服务平台警力资
7、源对全区13条交通要道实现全面封锁，同时一个平台的警力最多封锁一个路口。对此，问题可转化为，从20个交巡警服务平台中寻找13个平台对相应的13各交通要道进行封锁的问题，运用全局最优的规划方法使封锁时间最短。3、根据现有交巡警服务平台的分布情况，由第一小问可知，存在总体工作量不均衡以及个别平台出警时间过长的情况，为此考虑增加2至5个平台，来处理该问题。首要条件必须满足出警时间的限制，其次尽可能地均衡各平台的工作量。问题二，对全市所有交巡警服务平台的位置分布进行优化。可分为两个问题： 1、按照设置交巡警服务平台的原则和任务，从出警时间、工作量均衡两个方面进行考虑，分析该市现有交巡警服务平台设置方案
8、的合理性。如果不合理，可通过增加平台或移动平台处理该问题。2、犯罪嫌疑人从P点开始逃窜，交巡警服务平台在三分钟后开始进行围堵。对此，以P点为中心，犯罪嫌疑人3分钟所能逃窜的最大路程为基准向外辐射邻接节点，找出所有外层端点，所涵盖的范围即为犯罪嫌疑人可能到达的最大逃窜区域。以该区域为基础，逐步分析该区域之外的相邻节点，判断该节点能否在第一时间被封锁，以此达到合围的目的。三、 模型假设1、 不考虑警务人员的拦截能力。2、 犯罪人员的驾车速度近似等于警车时速60km/h。3、 不考虑白天晚上时间与路况的区别。4、 警务人员出警时均从交巡警服务平台出发。5、 每个交巡警服务平台的职能和警力配备基本相同
9、。6、 相邻两节点间的道路为直线。四、 符号说明：表示节点i的横纵坐标：交巡警服务平台的平均发案率：第i个交巡警服务平台的发案率五、 模型建立与求解4.1模型I4.1.1前期准备（1）根据A区92个节点坐标，用matlab作出交通网络图（见程序1），如图1：图1 A区的交通网络与平台设置的示意图其中图中实线表示市区道路；实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；星号“*”表示出入城区的路口节点；圆圈“”表示现有交巡警服务平台的设置点；圆圈加星号“* ”表示在出入城区的路口处设置了交巡警服务平台。（2）求出全市582个节点的距离矩阵由附件2可得到582 582的0-1邻接矩
10、阵，其中i=1，2582，j=1，2582 根据两点间距离计算公式：和Floyd算法，通过matlab编程（见附录程序2，3）得到任意两节点间的距离。4.1.2模型的建立与求解通过分析可知，该问题的关键在于出警时间小于3分钟的情况下，对A区的20个服务平台确定其可管辖的范围。（一）初步划分管辖范围对于附表2中全市582个节点的距离矩阵，从中提取的距离矩阵，其中92为A区中92个交叉路口节点，20为A区中的交巡警服务平台，截取前5个节点的距离矩阵如下表1：表1 A区部分交叉路口节点与服务平台距离（mm）编号12345671018.9874938.8388445.3521793.7428995.3
11、7518115.0035218.98749021.1165456.8506878.3371198.4207797.28119338.8388421.11654040.4338557.2205877.3042376.16465445.3521756.8506840.43385049.2004450.0230176.5669593.7428978.3371157.2205849.20044029.4262927.36647编号891011121314190.2262592.25438146.4957190.8793222.3615220.0175160.2847272.5039474.532071
12、28.7734173.157204.6392201.03141.2972351.387453.41554107.6568152.0404183.5227187.4051127.6723483.2728389.86668144.108188.4916219.9738209.8179150.0851535.3568546.95427100.4161144.7997176.2819186.5506129.6963编号1516171819201142.493292.8681235.9120525.6457217.5834652.631992124.770973.8806325.9111243.8476
13、36.5709570.833873103.654360.2556647.0276558.949141.9425785.935364114.750782.6685374.7052563.8436246.8370967.9888565.5502362.27967104.2482112.234395.22781117.0395警车时速60km/h，地图比例为1:100000，即1mm对应100米，那么可将要求的出警时间3分钟，转化为行驶距离3km,使用地图比例尺换算成地图上的距离为30mm（以下可将时间与距离进行等价代换）。若节点到平台的距离小于30mm，说明该节点在此服务平台的管辖范围内，记=1，
14、否则=0。定义：i=1,292，j=1,220 通过matlab编程（见程序4），得到一个0-1矩阵，即得到初步划分城区A各服务平台管辖范围。（二）逐步优化管辖范围通过对矩阵数据观察可知，存在三种情况，节点仅对应一个服务平台，节点不在任何一个服务平台的管辖范围内和节点同时在多个服务平台管辖范围内的情况，易知第一种情况不需再对其进行优化。下面针对剩下两种情况进行优化：节点不在任何服务平台的管辖范围内观察矩阵的数据，其中节点28，29，38，39，61，92不在这20个平台中任一个平台的管辖范围内。此时根据就近原则，筛选出距离每个节点路程最近的服务平台（见程序4），则该节点可视为在此服务平台的管辖
15、范围内。结果如下表3： 表2 最短距离确定服务平台节点标号282938396192对应服务平台标号1515162720节点同时在多个服务平台的管辖范围内以均衡各服务平台的工作量为目标，求20个服务平台发案率的方差最小作为最终结果，对此情况进行优化，具体步骤如下：第一：根据矩阵以及附件2中给出的各节点案发率，用matlab列出各节点的发案率矩阵，并求得平台的平均发案率：其中，表示第i个节点的案发率，n为平台总数。则平台的平均发案率为6.225。第二：为平衡各平台的工作量，使平台发案率的方差最小，列出如下目标函数：同时，对于矩阵，仍需满足一个节点只能在一个平台的条件，如下式： i=1，292第三：
16、由以上对目标的分析，通过lingo编程可得最终服务平台分配方案（见程序5），如下表3：表3 交巡警服务平台分配方案平台编号管辖的节点编号平台编号管辖的节点编号平台编号管辖的节点编号平台编号管辖的节点编号平台编号管辖的节点编号119，69,73,75，77,79,8056,49,50,53,56916,36,45，461313,21,22,23,24172,40,41,42，7221,3,17,3964,48,51,52,58,59101014141883,84,85,87,88,90,91343,44,54，55,68,70,76730,34,47,611111,26,271515,28,29
17、,311964,67,71,74,78,81,8244,57,60,62,63,65,6687,9,32,371212,25168,33,35,382018,20,86,89,92由此即可得到在满足3分钟内有交巡警到达事发地以及各平台工作量均衡的条件下，中心城区A的20个交巡警服务平台管辖范围，并求得方差为2.9479。4.2模型II4.2.1模型分析根据题目约束，一个平台的警力最多封锁一个路口，且由图1可得对13条交通要道的封锁即为13个出入城区的路口节点的封锁，那么，本问题的关键即为在全区20个交巡警服务平台中寻找13个服务平台，以对该区的13个出入城区的路口节点实现全封锁，且必须满足时间
18、最短。4.2.2模型的建立与求解有题可知13个出入城区的路口点，若使13个交巡警服务平台实现全封锁，必须满足13个服务平台中到达时间最长的点也对出入城区的路口点实现封锁。其中一个交通要道对应一个服务平台，而一个服务平台至多对应一个交通要道，可列出下式：i=1,213,j=1,220其中，表示第I条交通要道到第j个交巡警服务平台的距离且交巡警服务平台警力的合理调度方案如下表4：表4 全区封锁警力调度方案服务平台345710111213141516189封锁要道164830292224122321281462384.3模型III4.3.1问题分析由题意可得，为使资源得到充分利用，在增加平台尽可能少
19、的基础上，首先满足每个平台出警时间全部在3分钟内（路程为3公里）增加相应平台，其次在增加平台后对工作量进行均衡。在模型I的最终求解结果中，以方差最小为目标函数，20个平台的工作量已经得到尽量均衡，那么针对出警时间过长的情况找到六个亟待改进的问题节点，将其作为目标点，分别是28号节点、29号节点、38号节点、39号节点、61号节点和92号节点。 那么在这些目标点或目标邻近点处增加服务平台，使A区20个平台到达相应节点的时间在3min之内。4.3.2模型的建立与求解（一）增加平台由图1可知，根据目标点的聚集情况划分出四个区域：28,29、38,39、61、92以这四个目标区域为中心，3公里路程为半
20、径，向外辐射邻近节点，这样就得到了四个可供安置平台的目标结点选择范围，分别标记为：p1=28,29、p2=38,39,40、p3=48,61、p4=87,91,92由此，以这些点为中心，路程长度3公里为半径进行区域覆盖，要求所覆盖的区域内包含的非平台结点越多越好，以此为依据选定目标安置点建立平台。这里对可能出现的情况做出规则限定：1、 不允许跨平台设置覆盖点，即如果某个点的覆盖区域内有其他平台，则将跨过该平台之后才能覆盖的点剔除该区域；2、 面对未决点，即点的覆盖区域范围内包含的非平台点数目相同，在要求的情况下无法确定哪个点为安置点的时候，遵循以下原则：1） 设置平台的新结点要求尽可能靠近市中
21、心；2） 设置平台的新结点要尽可能地与其他平台分散开，不要出现平台扎堆现象；3） 以上两条先执行条件1），若条件1）无法明确满足再执行条件2）。根据上述设置新平台结点的规则，得到下表5：表5 候选节点覆盖范围内拥有的非平台节点数节点标号28293839404861879192覆盖范围内结点数2244810214146非平台结点数224467212126剔除跨平台的非平台结点后的结点数224444212126为使增加平台个数尽可能少，对平台个数进行逐个分析：当增加2个服务平台时，将其放置在以上任何候选节点，都不能满足使这两个平台到6个目标点的时间同时在3min以内。当增加3个服务平台时，同，无法
22、保证这3个平台到6个目标点的时间同时在3min之内。当增加4个服务平台时，将其分别设置在p1，p2，p3，p4的可选范围内，即可满足这4个平台到6个目标点的时间同时在3min之内。通过对A区图1的比对以及各节点坐标数据进行分析，可知29号比28号更靠近市中心，91号比87号更靠近市中心。由上述规则可以得到，在四个目标区域内分别设置四个交巡警服务平台的设置点分别为：29号结点、39号结点、48号结点、91号结点。（二）均衡工作量此时，平台总数达到24个，再次利用模型I，遵循发案率方差最小的思想，建立目标函数，如下式： i=1，292其中表示服务平台的平均发案率，其值为5.1875，表示第i个节点
23、的案发率，n为平台总数。即可得到工作量均衡情况下的交巡警服务平台的分配方案（见程序6），见下表6：表6 服务平台分配结果平台节点号管辖的节点号11，18,65，77，7922，44,69,70,7833，54,55,64,7644，57,60,62,6354，57,60,62,6366,47,52,5675,9,33816,35,37,4697,32,4510101111,26,271212,251313，21,22,23,2414141515，31168,34,361717,41,42,721820,71,74,80,841919，66,67,68,73,752081,82，83,88,90
24、,912128,292238，39,40,432330，48,49，612485，86,87,89,92并求得方差为1.99，波动值不大，分配结果较好。4.4模型IV4.4.1问题分析本问题是针对全市六个区交巡警服务平台的设置进行合理分析，按照交巡警服务平台的设置原则和任务，从出警时间和工作量均衡角度，运用模型III的思想分析现有设置方案的合理性，并通过增加平台的方案给予解决。4.4.2模型的建立与求解（1）合理性分析对于以上平台设置方案，从两方面对其合理性进行分析：首先出警时间必须满足3分钟原则。对于某一个节点，若其不属于任一个服务平台，表示不满足时间限制，即为不合理点。通过matlab编程
25、可得该市共存在138个不合理点（见程序7）。可知不合理点占总节点的比例为23.7%，不合理点相对较多。其次可得服务平台的方差为27.21，该方差值也相对较大，表示各个交巡警服务平台的平均发案率波动相对较大，各平台工作量不均衡。由以上分析可判断，该市现有交巡警服务平台设置方案是不合理的。（2）解决方案根据模型III的思想，选取增加服务平台的方法来满足时间与工作量均衡的限制，方法如下：首先对138个不合理点根据模型III的划分原则进行划分，共可划分为17个区域，根据模型III的服务平台划分原则，可增加54个服务平台（见附表1），至此138个不合理点即可全部满足3min的时间限制。其次，增加服务平台
26、后全市共存在192个服务平台，将这些服务平台的管辖范围进行重新划分，以均衡各平台的工作量，建立如下目标函数：i=1，2582求得交巡警服务平台的方差为5.098（见程序8），并获得最终平台设置方案，截取部分数据，见下表7（详见附表1）：表7 最终部分平台设置方案平台管辖节点平台管辖节点平台管辖节点平台管辖节点平台管辖节点平台管辖节点1196127180180383470184187408413118961281802703844651841884194181199797180297384468199199419419173971291802983844721992084204202397130
27、1803063844732012004213792179713118031038538520120142141726997137181266385449201202421421275971481812673854502042034394394.5模型V4.5.1问题分析第五问提出了一个实际需要解决的问题，即在某个节点处发生案件需要的围堵方案。从案件发生开始，到之后接到报警，交巡警服务平台第一时间接到布防通知，马上封锁目标节点。这里要求安排方案，让所有交巡警服务平台在第一时间能够知道自己需要布防的节点位置。由此分析布防的基本思想：首先需要满足以下基本原则：（1）必须在最快时间完成围堵方案，即最后
28、一个待封锁路口完成围堵封锁任务的时间要尽可能的短；（2）在时间短的前提下，尽可能少的调动警力资源；（3）在遇到多个节点可以被一个平台实施封锁的情况下，优先选择后续分支较多的节点路口进行封锁；（4）在遇到一个节点可以被多个平台实施封锁的情况下，优先满足原则（1），其次满足原则（2）。4.5.2模型准备下面对一些基本变量以及参数进行定义：t：事件发生到接到报警的间隔时间；：犯罪嫌疑人驾车逃窜的速度，；（在假设中指明）：警车速度，；表示罪犯逃窜t时间的路程；：抢点时间；4.5.3模型建立（1）事发地点（某个节点）标记为P，以P节点为中心，犯罪分子h时间所能逃窜的最大路程为指标q，确定一个以p点为中心的区域，标定该区域内的所有外层节点（与该区域外部节点相邻的节点或城市的边界节点），将这些节点构成的集合记为Q；（2）以Q中的每一个节点为端点，向外辐射其邻接节点，若节点为普通节点，记为起始节点，若节点为平台节点，则排除。将所有起始节点做成集
