论文部分内容阅读
摘 要：由于警务资源有限，提高交巡警服务平台的工作效率至关重要。本文讨论了如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源等问题。本文结合图论的相关知识，建立相应的优化模型，对相关问题进行分析和讨论。
关键词：Floyd算法；0～1整型规划；单位工作量
一、问题重述
“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
二、问题分析
1.分配管辖范围的问题分析
发生突发事件之后，警车能以60km/h 的速度赶往现场。要求尽可能在3 分钟之内到达，也就是说，每个路口节点距离与交巡警平台的距离都不能超过3km。可以采用Floyd 算法思想，依据动态规划原理和逐步优化技术，借助MATLAB编程，求出最短距离和最短路程矩阵，根据题中所给的数据计算出各标志点两两之间的最短距离建立模型，找出各个交巡警平台3km范围内的路口节点，即得到各个交巡警平台的管辖范围和最大覆盖时间。但是，对于相近的平台会有重复的覆盖域，对于比较偏远的路口可能不包含于任何管辖区内，所以需要再定义一个分配原则再次分配。
2.快速封锁A区的问题分析
要求对进出该区的13条交通要道实现快速全封锁，即要求封锁时间最短，而封锁时间由到达最后一个路口所用时间决定。因此，需从全局的综合调度进行考虑，得到优化的调度方案。把合理的调度警力资源封锁路口看成是指派问题，并建立0-1整型规划模型，用lingo对模型进行编程求解，求出最优解，从而得到封锁A区的交巡警最优调度方案。
3.优化交巡警服务平台的问题分析
要确定增加交巡警服务平台的个数和位置，我们必须遵循两个原则：一是增加交巡警服务平台以后各个交巡警服务平台的出警时间应尽量短。二是增加交巡警服务平台以后各个交巡警服务平台的工作量应达到相对均衡。
三、问题一模型的建立与求解
1.基于Floyd算法的“最短路径模型”的建立
根据附录1.2做出A区的交通网络与平台设置的示意图，并标注交巡警台的编号，交巡警平台的编号A1-A20分别与全市路口节点编号1-20相对应。
为了最快能到达事故地点，所以有效地建立覆盖区域，对此本文采用图论中的Floyd算法来求得最短路径从而建立模型。通过设计求出无向加权图中每一对顶点之间（即路的节点）的最短路径算法，求出任意两点之间的最短路径。具体步骤如下：
（1）根据附录2中所给的各个路口节点的坐标，城区内任意相邻点（两点之间直接有路的前提下）的距离计算公式为：
（2）求遍每一个节点，得到92*92的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用无穷代替。
（3）在matlab环境下利用floyd算法即可求出两两之间的最短路程和最短路径。
2.交巡警服务平台管辖范围的分配及城区A的最大覆盖时间
通过求解，得到A区92个路口节点任意两点之间最短路径和路线。针对问题一，只考虑设有20个交巡警平台的路口A1-A20与其他72个路口节点的最短距离。
要实现各交巡警服务平台管辖范围的分配，需满足要求“当所管辖的范围内出现冲突事件时，尽可能在3min内有交巡警到达事发地点”的时间约束条件。在假设警车匀速行驶的前提下，把“时间约束条件”转化为“距离约束条件”即交巡警平台与所管辖的路口的距离不超过3Km。
以每一个交巡警平台作为原点做一个半径为3Km的圆，然后找到每个圆内的点，并判断其是否小于3Km，根据之前求得的任意点间的最短距离进行筛选。初步得到满足距离约束条件的路口节点所属平台的分布。
数据进一步分析：除了筛选出初步符合要求的点外，还有另外6个路口节点编号分别为28、29、8、39、61、92，它们与20个平台的距离均超过了3Km，不满足距离约束条件。此外，还存在在着一个节点在满足距离约束条件的情况下所属的交巡警平台不唯一，例如上表中的42、43、44、66、67、68、69等节点与平台A1.A2间的距离均小于3Km。
对于这些特殊点，若单根据最短路径出发即根据路径总和最短，将这些点划给与其最近的交巡警平台管辖，则存在着警力资源有限的约束，譬如A1和A2比较，即使满足距离约束条件，但由于节点在A1处较密集，导致A1交巡警平台所管辖的节点较多。又因为，从附录2中所知，每个节点都有一定的案发率，所以附近有密集节点的平台所需要更大的管辖力度。对此需优化模型，我们建立了以最短路程为目标，以服务平台的发案率均衡为限制条件的模型来划分区域。
利用Matlab软件作出了1.5到2.5之间的所有不同的偏差值与目标最优解的坐标图。经分析在1.9-2.0附近，目标函数值变动最小。所以我们选择1.9作为偏差限。
根据与20个平台间的距离超过3Km的路口节点，找出这些节点与所属平台的距离的最大值，从而确定为城区A的交巡警平台的最大覆盖区域距离：。由筛选结果可得：A15到路口节点号为29的路口节点的距离即为城区A的交巡警平台的最大覆盖距离，故最大到达时间为。
参考文献：
[1]姜启源.数学模型[M].北京：高等教育出版社，1993.
[2]袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用[M].北京：清华大学出版社，2009.
[3]王志平，超网络理论及其应用，北京：科学出版社，2008.
[4]陆化普，石京，城市交通规划案例集，北京：清华大学出版社，2006.
[5]陈文博，数据结构及应用算法教程，北京：清华大学出版社，2001.
[6]何坚勇，最优化方法，北京：清华大学出版社，2007.
[7]褚洪生，MATLAB7.0优化设计实例指导教程，机械工业出版社，2007.
关键词：Floyd算法；0～1整型规划；单位工作量
一、问题重述
“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
二、问题分析
1.分配管辖范围的问题分析
发生突发事件之后，警车能以60km/h 的速度赶往现场。要求尽可能在3 分钟之内到达，也就是说，每个路口节点距离与交巡警平台的距离都不能超过3km。可以采用Floyd 算法思想，依据动态规划原理和逐步优化技术，借助MATLAB编程，求出最短距离和最短路程矩阵，根据题中所给的数据计算出各标志点两两之间的最短距离建立模型，找出各个交巡警平台3km范围内的路口节点，即得到各个交巡警平台的管辖范围和最大覆盖时间。但是，对于相近的平台会有重复的覆盖域，对于比较偏远的路口可能不包含于任何管辖区内，所以需要再定义一个分配原则再次分配。
2.快速封锁A区的问题分析
要求对进出该区的13条交通要道实现快速全封锁，即要求封锁时间最短，而封锁时间由到达最后一个路口所用时间决定。因此，需从全局的综合调度进行考虑，得到优化的调度方案。把合理的调度警力资源封锁路口看成是指派问题，并建立0-1整型规划模型，用lingo对模型进行编程求解，求出最优解，从而得到封锁A区的交巡警最优调度方案。
3.优化交巡警服务平台的问题分析
要确定增加交巡警服务平台的个数和位置，我们必须遵循两个原则：一是增加交巡警服务平台以后各个交巡警服务平台的出警时间应尽量短。二是增加交巡警服务平台以后各个交巡警服务平台的工作量应达到相对均衡。
三、问题一模型的建立与求解
1.基于Floyd算法的“最短路径模型”的建立
根据附录1.2做出A区的交通网络与平台设置的示意图，并标注交巡警台的编号，交巡警平台的编号A1-A20分别与全市路口节点编号1-20相对应。
为了最快能到达事故地点，所以有效地建立覆盖区域，对此本文采用图论中的Floyd算法来求得最短路径从而建立模型。通过设计求出无向加权图中每一对顶点之间（即路的节点）的最短路径算法，求出任意两点之间的最短路径。具体步骤如下：
（1）根据附录2中所给的各个路口节点的坐标，城区内任意相邻点（两点之间直接有路的前提下）的距离计算公式为：
（2）求遍每一个节点，得到92*92的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用无穷代替。
（3）在matlab环境下利用floyd算法即可求出两两之间的最短路程和最短路径。
2.交巡警服务平台管辖范围的分配及城区A的最大覆盖时间
通过求解，得到A区92个路口节点任意两点之间最短路径和路线。针对问题一，只考虑设有20个交巡警平台的路口A1-A20与其他72个路口节点的最短距离。
要实现各交巡警服务平台管辖范围的分配，需满足要求“当所管辖的范围内出现冲突事件时，尽可能在3min内有交巡警到达事发地点”的时间约束条件。在假设警车匀速行驶的前提下，把“时间约束条件”转化为“距离约束条件”即交巡警平台与所管辖的路口的距离不超过3Km。
以每一个交巡警平台作为原点做一个半径为3Km的圆，然后找到每个圆内的点，并判断其是否小于3Km，根据之前求得的任意点间的最短距离进行筛选。初步得到满足距离约束条件的路口节点所属平台的分布。
数据进一步分析：除了筛选出初步符合要求的点外，还有另外6个路口节点编号分别为28、29、8、39、61、92，它们与20个平台的距离均超过了3Km，不满足距离约束条件。此外，还存在在着一个节点在满足距离约束条件的情况下所属的交巡警平台不唯一，例如上表中的42、43、44、66、67、68、69等节点与平台A1.A2间的距离均小于3Km。
对于这些特殊点，若单根据最短路径出发即根据路径总和最短，将这些点划给与其最近的交巡警平台管辖，则存在着警力资源有限的约束，譬如A1和A2比较，即使满足距离约束条件，但由于节点在A1处较密集，导致A1交巡警平台所管辖的节点较多。又因为，从附录2中所知，每个节点都有一定的案发率，所以附近有密集节点的平台所需要更大的管辖力度。对此需优化模型，我们建立了以最短路程为目标，以服务平台的发案率均衡为限制条件的模型来划分区域。
利用Matlab软件作出了1.5到2.5之间的所有不同的偏差值与目标最优解的坐标图。经分析在1.9-2.0附近，目标函数值变动最小。所以我们选择1.9作为偏差限。
根据与20个平台间的距离超过3Km的路口节点，找出这些节点与所属平台的距离的最大值，从而确定为城区A的交巡警平台的最大覆盖区域距离：
参考文献：
[1]姜启源.数学模型[M].北京：高等教育出版社，1993.
[2]袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用[M].北京：清华大学出版社，2009.
[3]王志平，超网络理论及其应用，北京：科学出版社，2008.
[4]陆化普，石京，城市交通规划案例集，北京：清华大学出版社，2006.
[5]陈文博，数据结构及应用算法教程，北京：清华大学出版社，2001.
[6]何坚勇，最优化方法，北京：清华大学出版社，2007.
[7]褚洪生，MATLAB7.0优化设计实例指导教程，机械工业出版社，2007.