基于floyd算法的交巡警服务平台优化调度研究.docx

基于floyd算法的交巡警服务平台优化调度研究 为了更好地履行刑事诉讼、公共安全管理、交通管理和服务人民服务的职能，本研究应根据城市的实际情况和需要，合理配置交巡警察服务平台，分配每个平台的管辖权范围，并组织公共安全资源。文献给出了某市的相关数据:全市6个区共582个交通路口节点的坐标、所属区域和发案率;现有80个交巡警服务平台所在的节点标号;全市交通网中各路口节点的相邻情况;17个出入市区的路口标号和13个出入中心城区A区的路口标号。下面即按照文献的要求建立数学模型,解决交巡警服务平台的设置与调度问题,并给出数值结果。 1 运营和中心城市服务平台的配置 1.1 运行结果分析和分配管辖 为中心城区(A区)现有的20个交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3 min内有交巡警(假设警车的速度为60 km/h,即1 km/min)到达事发地。 假设每个交巡警服务平台接警后均采取最短路径前往事发现场。G表示市区交通网络图,路口节点构成顶点集U0,交巡警服务平台所在的顶点集合记为V,图G是以道路长度为权的赋权图。用节点编号表示顶点,利用Floyd算法可求出图G中任意两节点i与j间最短路径的长度,记为di j。 节点i处的发案率(次数)记为ci,则服务平台j的工作量为cifi j的累计。A区内每个服务平台工作量的均值为6.225次,不妨假设平台允许的最大工作量为cm a x=8.5。由此建立分配管辖范围的优化模型一: 由此获得交巡警服务平台分配的管辖范围如表1所示。 此方案的工作量方差为4.83,平均出警时间为1.15 min,最长出警时间为5.7 min,出警时间不超过3 min的节点数所占比重为93%,即绝大多数满足要求。作为对比,考虑将各节点均归属距离自身最近的服务平台,这种方案的工作量方差为7.90,平均出警时间为1.12 min,最长出警时间为5.7 min。可见,表1的方案在平均出警时间增加不多的情况下,较大幅度地降低了各服务平台的工作量方差,改善了均衡性。 1.2 全封闭调度方案 若遇重大突发事件,需要调度全区的警力资源,对进出A区的13条交通要道实现快速全封锁。实际处理时,一个平台的警力最多封锁一个路口,按此条件给出该区交巡警服务平台警力合理的调度方案。 设U2为13个待封堵路口构成的集合,具体为: 引入封堵变量fi j:fi j=1表示点i∈U2由服务平台j封堵,否则fi j=0。以完成全封堵的时间最短为目标,建立优化模型二: 求解模型二,得到目标最小值为dm i n=8.02 km,说明实现交通要道全封锁的最短时间为8.02 min,但有多组调度方案满足此项要求。进一步以dm i n为约束条件,以各警务平台的出警距离之和最小(即出警时间之和最小)为目标,再做选择,建立优化模型三: 求解模型三,获得实现快速全封锁的最佳调度方案如表2所示。 1.3 交巡警服务平台设置 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在A区内再增加2至5个平台,下面确定需要增加平台的具体个数和位置。 引入平台增设变量pj:对于j∈V,固定pj=1;对于j∈U0-V,pj=1表示在j点处设有服务平台,否则pj=0。增设后的交巡警服务平台总数不超过25。这样就可应用前面的模型一,不过警务台设置的选择需扩大到U0。fi j的含义相同,但还要增加一个约束cifi j≤20 pj,以控制fi j不能随便取1,该约束出于所有节点的发案率都小于20。由此建立优化模型四: 求解模型四,结果为增加4个交巡警服务平台,具体位置的节点编号为29、39、48、88。此方案与模型一的方案相比,最大工作量由9.1次减少到8.5次,工作量方差由4.83减少到3.73,平均出警时间由1.15 min减少到0.89 min,最长出警时间由5.7 min减少到2.7 min。 2 全市6个区的布局和设计模式 2.1 af区内服务平台数目的确定 针对全市6个区A、B、C、D、E、F的具体情况,按照设置交巡警服务平台的原则和任务的科学性,分析研究该市现有交巡警服务平台设置方案的合理性。如有明显不合理,则给出解决方案。 交巡警服务平台的设置应兼顾各平台工作量的均衡性和出警时间长短,因此我们给出2条标准:尽量缩小各平台工作量的差异;尽量减少出警时间超过3 min的情况发生。 根据原始数据计算各区警务平台的工作量(即发案次数)如表3所示;利用优化模型一获得各区出警时间超过3 min的节点数如表4所示。 由表3可看出,各区平均工作量的方差不大(计算值为2.5),说明各区服务平台的工作量比较均衡;但由表4可看出,各区出警时间超过3 min的情况差异较大,有些区域出警时间过长。因此,有必要对各区的服务平台数目进行调整,并确定各区内