交通点设置优化讲述.docx

 PAGE \* MERGEFORMAT 21 交巡警服务平台的设置与调度 摘要 针对交巡警服务平台的管辖范围分配及警力调度问题。首先利用图论里的Floyd算法建立A区服务平台与路口节点的的路径关系模型，在此基础上对服务台进行局部调整，并将该方法应用到全市6区的服务平台设置分析与调整中。然后，利用整数规划理论建立了快速全封锁的最优方案。最后，对发生重大刑事案件的嫌疑犯的追踪案例，根据不同的情况给除了两种最佳围堵方案。 对于问题一：第一小问首先利用“画圆”思想排除最不可能最短路径在3km范围内的交通节点。接着通过最短路径算法求出每个平台与对应节点之间的最短路径，根据最短路径的长度是否小于3km，确定各平台能够及时到达的所有交通节点。继而将共有的交通节点在各服务平台之间进行合理分配。对于无法在3分钟内到达的交通节点，按照就近原则划分给最近的平台。 第二小问本质上是不平衡指派问题最优解的求解。本文运用整数规划的方法，使用LINGO软件进行编程，得到被封锁的每个路口对应的服务平台。利用MATLAB画出其最佳封锁路线图，并得到最快完成封锁的时间为8.24min。 第三小问要解决各平台工作量不均衡和有些地方出警时间过长的情况，即要尽量让每个交巡警服务平台的管辖范围和工作量都保持平衡。根据定量性原则，有效性原则，在各个平台3min内能够到达的交通节点的数据基础上，对各个平台辖区内的重复交通节点进行分配，然后再考虑孤立点，在合适的的地方添加交巡警服务平台，最后再综合各辖区的累计发案率适当增加交巡警服务平台。得出结果，在28、40、48、92 对于问题二：第一小问以上述模型和计算方法，找出每个区各自的盲点以及只能管辖自身的交通警卫平台针对这些节点和平台进行交通警卫平台的增设和删减，并给出最终的改善方案。 第二小问以两个方案来对罪犯进行搜捕。A方案以通过以32号结点为起始点，求出罪犯逃逸速度为80km/h时候6min内可能到达的所有交通节点。让警察在罪犯可能到达的交通节点外围封锁所有可能的逃逸结点形成一个闭合的曲线。B方案首先通过最短路径的分别计算罪犯在不同逃逸速度时的活动范???，确定嫌疑犯的活动范围在A,C,F区。对A,C,F区的出口进行封锁，使警察从接到报警开始封锁路口需要的时间,和嫌疑犯逃跑到路口所需要的时间满足即可。得出结果当罪犯的逃逸速度为60km/h时可以在罪犯逃出ACF区之前完成封锁；如果罪犯的逃逸速度为80km/h;90km/h；100km/h时,在ACF区的盲点位置始终存在封锁迟于逃逸的情况。 关键词：Floyd算法、非平衡指派问题、整数规划法、最短路线规划 问题重述 1.1背景概要 中国警察为有效贯彻实施刑事执法、治安管理、交通管理、服务群众四职能，往往要在一些交通要道和重要部位设置交巡警服务平台。由于警务资源有限，如何根据城市情况与需求合理设置交巡警服务平台、分配各平台管辖范围、调度警务资源是警务部门履行职能的关键。 1.2问题简述 1.2.1问题一 已知该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图以及相关的数据信息。要求解决问题如下： 为交巡警服务平台分配管辖范围，使其面对辖区内突发事件时，能够3min内到达（警车时速：60km/h）。 面对重大突发事件，要求20个交巡警服务平台能够对13条交通要道实现快速封锁，其中一个交巡警服务平台只能封锁一个路口，给出交巡警服务平台警力合理的调度方案。 改善交巡警服务平台的工作量不均衡和有些地方出警时间过长的现状。增加2至5个平台，给出增加平台数目及位置。 1.2.2问题二 已知交巡警服务平台的设置情况示意图以及相关的数据信息。要求解决问题如下： 根据设置交巡警服务平台的原则和任务分析交巡警服务平台设置现状合理性，如不合理，给出解决方案。 若该市P点发生重大刑事案件，嫌犯驾车逃跑，案发3min后接到报警，为拦截嫌犯，给出调度全市交巡警服务平台警力的最佳围堵方案。 问题分析 2.1问题分析 该市的警务资源，如何根据交巡警服务平台的反应速度以及犯案率管控能力合理分配管辖范围是解决问题的关键。 问题一：该部分要解决的问题可以分成三小问进行分步解决。 对于第一小问：首先以每个交巡警服务平台（以下称为平台）为圆心以3km为半径“画圆”（即求出路口节点到平台的距离，然后与3km作比较）。然后求出各个平台到“圆内”各个节点的最短路径，保留3km以内的，对于大于3km的路口节点（以下称为孤立点），分配给出到其最短路径最小的平台。 对于第二小问：通过指派问题的解决思想，将20个交通平台指派封锁13个交通要道，利用LINGO软件通过匈牙利算法求出使得封锁的用时最短的最优解。 对于第三小问：要解决各平台工作量不均衡和有些地方出警时间过长的情况，即要尽量让每个交巡警服务平台