交巡警服务平台的设置与调度摘 要：近年来，随着令世界瞩目的中国建设高速发展，城市二次开发如雨后春笋般地建设起来，随之而来的人口、道路和楼宇密集、复杂化，直接点亮了交巡警服务平台设置-调度系统的重要性。本论文通过对交巡警服务平台设置与调度问题的抽象和简化，分别建立了多个明确、完整的数学模型，综合采用搜索-计算机模拟、图论、贪婪算法、层次分析法、逐步逼近等方法，用以解决题干中的各个子问题。最后，设计出了系列便于操作的交巡警服务平台的设置与调度方案。对题干五个阶段问题分别建立五个模型。 对于模型一，首先通过对图一的直观分析，首先确定其为归点问题，并通过图论WARSHALL-FLOYD算法,再通过穷举,让A区的非平台路口点尽可能选择离其寻道路径最近的平台作为其管辖服务平台。最终确立了每个平台的管辖区域，使93.5%的交通区域范围在出现突发事件时，有相应的交巡管辖平台点能在3分钟内迅速到达，不到7%(6个交通路口)的区域其所需到达时间不超过5.7分钟。 对于模型二，根据A区重大突发事件的调度需求，我们先定性分析20平台选13平台对13个交通要道进行封锁的所有可行方案的规模，目标为最短封锁时间：由于其方案空间大，我们用贪婪算法初步确定最优解范围在9分钟以内，过滤掉9分钟以外的路径(使方案空间缩小3个数量级)，通过递归搜索匹配求得最优解。在发生重大突发事件时，通过如下调度，最短分钟可以封锁A区所有交通要道:交巡平台v1v2v3v4v5v7v10v11v12v13v14v15v16交通要道38166248302912212224232814 对于模型三，为解决平台过载、出警超时两个问题，通过一般化数据层层筛选和细致化考量，得到需要在4个交通路口v29、v39、v48、v89增设交巡服务平台的结论。 对于模型四，为评估现有交巡平台设置方案的合理性，按刑事、治安、交管和服务群众的交巡警4个职能作为评判标准，建立模型四-层次分析评估子模型1。我们首先对直接或间接影响交巡警平台原则和职能的刑事、治安、交管和服务群众的因素进行定性分析，确定以“最优评价方案”为目标层，以“刑事执法、治安管理、交通管理、服务群众”为准则层，从而利用层次分析法建立层次目标模型。通过引入“标度方法”，构造出了、五个判断矩阵。在通过了一次检验之后，最终得到权重，从中可知，犯罪率和人口的权重最大。对子模型1，我们分别对六个区的四准则作综合量化评价，在推出现有交巡警服务平台设置的合理性欠佳，有改进空间后，进一步通过权重，参考查阅城市交通巡查配备相关准则和资料，分别计算出6个区各需合理平台数的量化数据，最终得出城区合理的平台数分配向量： 。并进一步构造基于遗传算法的模型四-设置子模型2确定各城区的平台位置选取方案模型。 对于模型五，引入“子图界点定理” ，综合二分逐步逼近策略及BFS算法，追踪嫌犯脱逃面积随时间变化的路口集合序列（逃逸的可能所在区域点集）。最后，联合模型二得到最佳围堵方案。关键词 图论 搜索匹配 层次分析法 综合性评价方案 遗传算法 时间二分序列逐步逼近 子图界点定理一 问题的提出1. 背景“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 根据某市设置交巡警服务平台的相关情况，需要我们建立合理的数学模型解决题目涉及的若干问题。2. 问题 我们把问题按语义直接分解成5小问。 （1）针对图1-A区的交通网络以及附件2中的数据，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地（交巡警时速6km/h）。 （2）对重大突发事件，调度全区20个平台警力资源，对A区13条交通要道实现快速全封锁。一个平台警力最多封锁一个路口，给出该区平台警力合理的调度方案； （3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的个数和位置。 （4）针对全市（主城六区A-F）的具体情况，按照设置交巡警服务平台的原则和任务，分析平台设置方案（参见附件）的合理性。如有明显不合理，给出解决方案； （5）如果该市地点P（第32个节点）处发生重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人驾车逃跑。为快速搜捕嫌犯，给出调度全市交巡平台警力资源的最佳围堵方案。二 问题的假设1假设题干所给两幅图和三张附表数据均为实际情况；2题干所提供的交通道路图并无坏道、维修道，道路时刻畅通；3所有道路均为双向车道；4交巡警公务出行无需受红绿灯限制；5交巡警在接收到突发事件到开始出发无时间延迟；6各区不被交通道路覆盖的面积无需考虑管制问题；7嫌疑犯驾车逃跑只能通过交通道路，无可能在图中未体现的其它巷道；8. 假设嫌疑犯驾车市区内逃跑的时速受车流和道路限制不会超过90km/h。三 问题的分析 交巡警设置和调配问题事关市民出行、人身安全以及意外发生后的处理效率, 直接或间接地影响到一个城市的居民生活质量、城市品牌形象和发展建设，但平台设置与调配是一个考虑多因素的正确选取方案的策略问题。本文将针对每一个阶段问题的目标和条件，分别分解其问题内在结构和情况，通过合适方法建立科学的模型。首先逐个分析2大问题中的5小问，第一小问、第二小问为最优化问题，第三小问要通过增设2-5个平台，消除掉3分钟以外的交巡警平台到路口出行的情况以及分摊高发案率负载的平台。第四小问要针对各区已有平台位置、数量设置，结合各区实际情况，建立合理评估体系。由于情况复杂，可以从两个层面考虑，一类宏观，一类微观：从微观上，以各个路口突发事件的时间处理效率以及平台负载发案率为标准，这二者目标需要尽可能优秀，但是考虑到每增加一个平台都是不小的公共成本负担，不可能无限增加平台（虽然平台越多必然导致这二者同时最优），所以要在合理的平台数范围的情况下，尽可能使其最优。从宏观上，按照设置交巡警服务平台的原则和任务，不仅仅是微观上的两个可具体量化的目标，还包括刑事执法、治安管理、交通管理、服务群众中的其它情况，比如刑事执法总需要平台尽可能不要过于集中，这样能够方便铺网追捕；服务群众需要根据一个区的人口数、区面积作为依据确定平台数；交通管理需要通过面积、路口数（交通路口往往是交管的焦点）来考虑平台数。宏观确定平台数的范围，微观通过宏观的确定范围，分配位置与管辖区域。在宏观方面确定平台数的合理范围受不同因素影响方面，由于不同因素的评价无全国性统一的标准，故可利用模糊数学结合数据对各方案评价因素进行量化。在通过宏观确定了一个区平台数合理范围后，微观方面通过遗传算法模型建立确定平台位置。第五小问和第二小问类似，都是围堵封锁问题（围堵了关键路口就可以彻底防止嫌疑犯逃脱，并能以最快速度的抓住逃犯），但是第二小问是静态的，只需要根据20个平台和区要道位置信息进行最优化搜索匹配。第五小问是动态的，随着时间的推移，由于不知道嫌疑犯具体逃跑路线，嫌疑犯驾车逃跑的所有可能范围是随着时间的推移逐渐增大，而我们需要尽快抓住逃犯（时间拖延越长，对抓捕行动越不利），所以增加了问题的复杂度。但是，我们可以把嫌疑犯出逃后3分钟的瞬间作为时间起点，分割之后的时间序列为不同的瞬间，对于每一个瞬间，存在一个嫌疑犯最大逃脱子图（在那个瞬间，嫌疑犯不可能处于那个子图之外的结点或道路中）。设某一个瞬间离逃跑3分钟的时候时间间隔为，那么就转化为类似第二小问的静态问题的强化版本：从逃跑后3分钟开始，在时间内，是否存在围堵方案能够锁定住第秒时间的嫌疑犯最大逃脱子图的边界要道，若不能，继续往后推移时间，直到获取一个可能的最短时间。把逐步逼近作为第五问的主线（原则）方法，广度优先搜索算法结合图论中确定子图边界逃逸点算法作为每个逼近瞬间的副线（具体处理）算法，确保嫌疑犯能在最短时间被封锁并限制在一个区域无法继续逃离，从而得到最优围堵方案。四 符号说明符号 符号说明 20x92最短出警路径矩阵 20x13最短时间矩阵 20x13 0-1分配矩阵 层次分析四因素权值向量 比重矩阵 相对量化比， 各区合理化分配平台数向量 特征值 权 重 n阶矩阵() 平台增设的可能样本空间 合理范围的逃逸时间上限 平均随机一致性指标 嫌疑犯逃跑3分钟后再经过的时间 逃逸子图五 模型的建立与求解5.1 模型一:最短出警时间 平台归点我们首先根据A区交通图形图对小问一进行目标和条件分析，确定其为单目标最优化问题，由于该问暂不考虑其它因素，只以出警时间最短为唯一准则，每个交通路口所属的交巡警服务平台就是唯一确定的，具体步骤如下：图一 A区交通网络图(1) 确定A区20个平台到其92个交通路口（包括平台本身）的最短距离：这里我们使用图论中的WARSHALL-FLOYD算法，MATLAB直接对92x92邻接矩阵进行处理，得到A区对应的92x92最短距离矩阵（编程见附录1）。由于前1-20序号的交通路口是A区所有交巡警平台，我们取92x92最短距离矩阵的前20行作为处理对象20x92的矩阵。 (2) 求每个交通路口的最短归属平台： 矩阵的任意一列k数据为k号交通路口到1-20号交巡警服务平台的最短距离。我们运用MATLAB进行数据处理，很容易得到一个20x10矩阵，第行代表第号平台所管辖的所有交通路口序号，0元素为无（每个平台也管辖自身，包含自身序号）：把矩阵中0元素消去，我们得到最优管辖范围分配方案 如下表所示：表一 最优管辖关系交巡警平台(序号)管辖的交通路口序号（包括平台作为路口自身）11、67、68、69、71、73、74、75、76、7822、39、40、43、44、70、7233、54、55、65、6644、57、60、62、63、6455、49、50、51、52、53、56、58、596677、30、32、47、48、6188、33、4699、31、34、35、4510101111、26、271212、251313、21、22、23、2414141515、28、29161