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

1交巡警服务平台的设置与调度摘要本文建立了交巡警服务平台设置与调度的优化模型，将出警时间和工作量作为考虑因素，设置城市交巡警服务平台，分配各平台的管辖范围，并在发生突发事件时对警务资源进行调度。针对问题一的第一小问，根据出警时间的条件限制，初步确定城区A中20个服务平台对92个交叉路口节点的相应管辖范围，以交巡警服务平台的工作量方差最小为目标进行优化，使用lingo程序求解得到20个交巡警服务平台的管辖范围，工作量方差为2.9479。对于第二小问，从全区20个交巡警服务平台中选取13个平台对全区13个交通要道实现了全封锁，以服务平台到达节点的最长时间最短为目标，用lingo求得封锁时间为8.015分钟，并给出了具体的封锁方案（即选定的13个交巡警服务平台与13个被封锁要道的一一对应关系）。对于第三小问，由于存在工作量不平衡和出警时间过长的情况，以交巡警服务平台的工作量方差最小为目标，经分析至少需要增加4个平台（节点编号分别为29,39,48,91）才能满足出警时间限制，经lingo求解得到具体服务平台分配方案，且最小方差为1.99。针对问题二的第一小问，在全市范围内，以出警时间限制和各服务平台均衡工作量为依据，使用lingo程序计算，得到工作量方差为27.21，且有138个节点不满足出警时间要求，可知现有交巡警服务平台设置方案是不合理的。经lingo程序计算至少需要增加54服务平台才能使这138个节点满足出警时间要求，经优化使用lingo程序求得增加平台后的方差为5.098，明显优于原方案，此分配方案更加合理。但是由于实际警力资源的限制，增加54个平台的个数相对较多，对此我们给出对现有警力配置，重新分布并适当增加平台数目的数学模型。对于第二小问，该模型利用蚁群算法[1]的思想，通过matlab程序模拟犯罪嫌疑人的逃窜路线，文中定义了一个新名词，即封堵有效性，以此为依据，提出一个有效且合理的嫌犯围堵方案，并且对该方案进行了可行性分析和封堵有效性检验，结果显示该模型很好。封堵有效性包括两方面：一是封堵任务顺利完成，封堵圈无疏漏；二是确认犯罪嫌疑人仍在封堵圈之内。关键字：全局最优多目标规划方差封堵有效性2一、问题重述1.1问题引言警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，则需根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。1.2题目所给信息（1）该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图以及相关的数据信息；（2）全市包括主城六区A，B，C，D，E，F；（3）警车的时速为60km/h；1.3需要解决的问题(1）①为A城区20个交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。②对于重大突发事件，调度A区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。③根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。(2）①按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，给出解决方案。②如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析根据城市的实际情况与需求，对城市交巡警服务平台进行分配，使其在发生突发事件时可以对警务资源及时合理的进行调度。问题一，主要是对该市中心A城区的所有交巡警服务平台位置分布进行优化。可分为三个问题：1、根据城区A的20个交巡警服务平台以及92个交叉路口节点的分布情况，确定各交巡警服务平台的管辖范围。由于出警时间存在限制，故需在满足时间条件的基础上，使92个交叉路口节点尽可能的分配给所有服务平台，同时必须满足一个节点只能由一个交巡警服务平台来管辖。2、针对重大突发事件，要求合理调度城区A的20个交巡警服务平台警力资源对全区13条交通要道实现全面封锁，同时一个平台的警力最多封锁一个路口。对此，问题可转化为，从20个交巡警服务平台中寻找13个平台对相应的13各交通要道进行封锁的问题，运用全局最优的规划方法使封锁时间最短。3、根据现有交巡警服务平台的分布情况，由第一小问可知，存在总体工作量不均衡以及个别平台出警时间过长的情况，为此考虑增加2至5个平台，来处理该问题。首要条件必须满足出警时间的限制，其次尽可能地均衡各平台的工作量。问题二，对全市所有交巡警服务平台的位置分布进行优化。可分为两个问题：1、按照设置交巡警服务平台的原则和任务，从出警时间、工作量均衡两个方面进行考虑，分析该市现有交巡警服务平台设置方案的合理性。如果不合理，3可通过增加平台或移动平台处理该问题。2、犯罪嫌疑人从P点开始逃窜，交巡警服务平台在三分钟后开始进行围堵。对此，以P点为中心，犯罪嫌疑人3分钟所能逃窜的最大路程为基准向外辐射邻接节点，找出所有外层端点，所涵盖的范围即为犯罪嫌疑人可能到达的最大逃窜区域。以该区域为基础，逐步分析该区域之外的相邻节点，判断该节点能否在第一时间被封锁，以此达到合围的目的。三、模型假设1、不考虑警务人员的拦截能力。2、犯罪人员的驾车速度近似等于警车时速60km/h。3、不考虑白天晚上时间与路况的区别。4、警务人员出警时均从交巡警服务平台出发。5、每个交巡警服务平台的职能和警力配备基本相同。6、相邻两节点间的道路为直线。四、符号说明,iixy：表示节点i的横纵坐标10iji第个节点在第j个平台管辖范围内其他10jijiai点和点j相邻点和点不相邻P：交巡警服务平台的平均发案率iK：第i个交巡警服务平台的发案率五、模型建立与求解4.1模型I4.1.1前期准备（1）根据A区92个节点坐标，用matlab作出交通网络图（见程序1），如图1：图1A区的交通网络与平台设置的示意图其中图中实线表示市区道路；实圆点“·”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；星号“*”表示出入城区的路口节点；圆圈“○”表示现有交巡警服务平台的设置点；圆圈加星号“○*”表示在出入城区的路口处4设置了交巡警服务平台。（2）求出全市582个节点的距离矩阵由附件2可得到582582的0-1邻接矩阵1582582[]ijAa，其中10jijiai点和点j相邻点和点不相邻i=1，2…582，j=1，2…582根据两点间距离计算公式：2211tan()()iiiidiscexxyy和Floyd算法，通过matlab编程（见附录程序2，3）得到任意两节点间的距离。4.1.2模型的建立与求解通过分析可知，该问题的关键在于出警时间小于3分钟的情况下，对A区的20个服务平台确定其可管辖的范围。（一）初步划分管辖范围对于附表2中全市582个节点的距离矩阵，从中提取9220的距离矩阵，其中92为A区中92个交叉路口节点，20为A区中的交巡警服务平台，截取前5个节点的距离矩阵如下表1：表1A区部分交叉路口节点与服务平台距离（mm）编号12345671018.9874938.8388445.3521793.7428995.37518115.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.53207128.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.847636.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，说明该节点在此服务平台的管辖范围内，记ij=1，否则ij=0。定义：10iji第个节点在第j个平台管辖范围内其他i=1,2…92，j=1,2…205通过matlab编程（见程序4），得到一个0-1矩阵29220[]ijA，即得到初步划分城区A各服务平台管辖范围。（二）逐步优化管辖范围通过对矩阵29220[]ijA数据观察可知，存在三种情况，节点仅对应一个服务平台，节点不在任何一个服务平台的管辖范围内和节点同时在多个服务平台管辖范围内的情况，易知第一种情况不需再对其进行优化。下面针对剩下两种情况进行优化：①节点不在任何服务平台的管辖范围内观察矩阵29220[]ijA的数据，其中节点28，29，38，39，61，92不在这20个平台中任一个平台的管辖范围内。此时根据就近原则，筛选出距离每个节点路程最近的服务平台（见程序4），则该节点可视为在此服务平台的管辖范围内。结果如下表3：表2最短距离确定服务平台节点标号282938396192对应服务平台标号1515162720②节点同时在多个服务平台的管辖范围内以均衡各服务平台的工作量为目标，求20个服务平台发案率的方差最小作为最终结果，对此情况进行优化，具体步骤如下：第一：根据矩阵29220[]ijA以及附件2中给出的各节点案发率，用matlab列出各节点的发案率矩阵，并求得平台的平均发案率P：921iidPn其中，id表示第i个节点的案发率，n为平台总数。则平台的平均发案率P为6.225。第二：为平衡各平台的工作量，使平台发案率的方差最小，列出如下目标函数：2221220()()+()min20KPKPKPz…同时，对于矩阵29220[]ijA，仍需满足一个节点只能在一个平台的条件，如下式：2011ijji=1，2……92第三：由以上对目标的分析，通过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，72621,3,17,3964,48,51,52,58,5910101414188