摘要

由于警务资源有限，针对城市实际情况与需求，合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源问题建立相应的数学模型.首先在分配问题上，要得出各交巡警服务平台到每个路口节点的最短距离，使其存在在3分钟之内能够尽量到达的服务平台，我们用floyd算法建立了图论模型，解决了两点之间最短路线问题。然后在调度问题上，要实现服务平台在最短的时间内到达案发地，需要服务平台与路口节点的最长距离尽量的小,我们在对0—1模型和匈牙利模型改进的基础上建立了遗传算法优化模型II，可直接得出最优解。最后在设置问题上，我们用最大工作量最小化思想使服务平台在尽量节约警力资源前提下，每个节点都有能在3分钟之内到达的服务平台，且服务平台工作量尽可能均匀。

第二题中，我们利用对A区的前期分析和研究推广到全市，从可在3分钟之内到达路口节点和工作量的均衡两方面分析交巡警服务平台设置方案的合理性。同时对于围堵问题进行速度分区，给出了犯罪嫌疑人的逃跑路线以及对应的围堵方案。

关键字： floyd算法   遗传算法   速度分区    最大工作量最小化

一、问题的重述

为使所肩负起其职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：

（1）参考该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图（附件1中的附图1），相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件2）的合理性。如果有明显不合理，请给出解决方案。

如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、问题分析

本题是一个根据城市的实际情况与需求合理地分配各交巡警服务平台的管辖范围、调度警务资源、设置交巡警服务平台的问题。在分配问题上，就是需要得出各交巡警服务平台到每个路口节点的最短距离，使其存在在3分钟之内能够尽量到达的服务平台。在调度问题上，要实现服务平台在最短的时间内到达案发地，这就需要服务平台与路口节点的最长距离尽可能的小。在设置问题上，服务平台在尽量节约警务资源的前提下使每个节点都有能在3分钟之内到达的服务平台，并且让服务平台的工作量尽可能的均匀。

第一题分为三问，第一问要给每一个交巡警平台分配管辖节点，使交巡警在3分钟内赶到突发事件地。可以以交巡警平台为中心，算出警车在3分钟中内能赶到的最远的点。该问题可以通过foldy算法计算出平台周围3分钟内能到达的最远距离的节点。

 第二问中提到一个平台的警力最多封锁一个路口，设置合理的调度方案，则只需考虑完全封锁交通要道所需的时间尽量少，即各平台到对应进出口节点中最长路程应尽量短，用遗传算法优化思想或0—1规划模型都可解决这类问题，得到最优解。

第三问中，由第一问中得出六个节点是任何平台都无法在3分钟内到达的，所加平台应保证可以在3分钟到达这六个节点。可通过分别以这六个节点为圆心，30毫米为半径在A区的交通网络与平台设置的示意图上作圆，实现缩小增加节点位置的范围（圆内的节点为所要考虑增加的节点），由操作后的图形可以分析出四个区域，即得到增加平台的最佳个数；再针对交巡警服务平台工作量不合理及有些地方出警时间过长的实际情况，我们需要以均衡各平台的工作量和出警时间为原则确定所要增加平台的位置，通过最大工作量的最小化依次排除的方法定出需要增加平台的具体位置。

第二题中分为两问，第一问从两方面分析交巡警服务平台设置方案合理性：是否有不在任何平台管辖范围内的路口节点；是否各平台的工作量均衡，并针对以上两个方面提出解决方案。

第二问中，因为交巡警平台是在3分钟后接到报警的，所以犯罪嫌疑人在出动警车时，已经行驶了3分钟的路程。当犯罪嫌疑人的车速小于警车的车速时，只要最近的警车去追堵，是一定可以完成的。当车速相等是就必须警车提前赶到犯罪嫌疑人的逃跑线路节点去堵截。当警车的车速小于犯罪嫌疑人的车速是，警车是围堵不到的，所以要进行全城封锁。

三、模型假设

1.每个交巡警服务平台的职能和警力配备基本相同。

2.警车行驶过程中不受任何外界因素影响，时速为60km/h。

3.假设区域的每一条道路都是双行线，不考虑转弯对结果造成的影响。

四、符号说明

cost：带权邻接矩阵

:图的顶点

：权矩阵

map[i,j]：节点i到j的最短距离

k：穷举i,j的断点

五、模型的建立与求解

5.1  问题一、为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地，即事发地在3千米以内有交巡警服务平台。

由于附件中图与具体的数据分离，使得图形不具有直观性，故此需对数据与图形进行处理。我们根据附件1中的附图1以及附件2中的相关的数据信息，采用MATLAB编程对附图1进行图像处理，使A市路口节点标号与图中A市路口节点相对应，处理后的图像如下所示：

从直观的图像信息中，可以认为满足问题的点必须是到达平台的距离小于等于三千米的节点，而这样的点必在以某平台为圆心，以三千米为半径的圆域内。然而用matlab编程实现后发现（见附件1），由于最短路径可能以折线的形式存在，使得圆域内的点到达平台的距离超过三千米，显然这是不符合要求的。

为避免折线出现的可能，从几何上，可以认为到达平台最近的点是与平台直接相连的点。用matlab对数据处理后（附件2），发现存在有一些节点不属于任意一平台的管辖范围，而一些点又同时受到几个平台的管辖。故对上述点利用最邻近的原则做处理，可以得到以下结果（见附表）

显然上述方法对于小规模的问题是比较方便的，但对大规模的问题的处理，它的结果就不尽如人意了。但可以发现节点受某平台管辖，要求满足的条件为：节点到各平台的路径中，最短的是到该平台的路径。为此需要求出 附图1各节点到各平台的最短路径及其长度。

用Floyd(弗洛伊德)算法可以求得任意两点间的最短路：

定义：带权图：两点间不仅有连接关系，还标明了数量关系（距离、费用、时间等）。 

图的阶：图中结点的个数。

路（径）：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边组成的序列，叫“路”或者“路径”。

Floyd(弗洛伊德)算法，是一种用于寻找给定的加权图中顶点间最短路径的算法。其核心思路是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

弗洛伊德算法从图的带权邻接矩阵cost 出发，其基本思想是： 

    假设求从顶点到的最短路径，如果从到有弧，则从到存在一条长度为cost[i,j]的路径，该路径下一定是最短路径，尚需进行n次试探。首先考虑路径（, ,）是否存在（即判别弧（, ,）和（,）是否存在）。如果存在，则比较（,）和（, ,）的路径长度，取长度较短者为从到的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个   顶点，也就是说，如果（,...,）和（,...,）分别是当前找到的中间顶点的序号不大于1的最短路径，那么（,..., ,...）就有可能是从vi到的中间顶点的序号不大于2的最短路径。将它和已经得到的从到中间顶点诒不大于1的最短路径相比较,从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点v3,继续进行试探。依次类推，在一般情况下，若（,...,）和（,...,）分别是从到和从到的中间顶点的序号不大于k-1的最短路径，则将（......）和已经得到的从到且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从到的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从到的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

Floyd(弗洛伊德)算法采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3); 其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}        

map[i,j]表示i到j的最短距离，k是穷举i,j的断点。                              Floyd(弗洛伊德)算法过程：     

定义赋权图的权矩阵：，这里   式中表示。

算法1：(1)令k=0，输入权矩阵D。

(2)令 k=k+1，计算,k=1,2,…,n ,  式中

(3)如果k =n，终止算法；否则，返回步骤(2)。

上述算法的最终结果中元素就是从顶点到的最短路程。如果希望计算结果不仅给出任意两点间的最短路程，而且给出具体的最短路径，则在运算过程中要保留下标的信息，即。

根据上述算法，利用MATLAB编程可以得到A区任意两节点之间的距离（附件3）。

然后通过数据比较，就可以解决上述问题。

用MATLAB编程实现该过程，得到每个交巡警服务平台的管辖范围，如下表所示：

从上述过程中还可以知道：实际上路口节点28、29、38、39、61和92距离任何一个交巡警服务平台均在3分钟之外，即如下图所示

图中蓝色星点表示距离任何一个交巡警服务平台均在3分钟之外的路口节点。

问题二：对于发生重大突发事件时，能以最短的时间调度全区20个交巡警服务平台的警力资源对进出该区的13条交通要道实现快速全封锁，要求交巡警服务平台到进出口节点的最长距离尽可能的短，且一个平台的警力最多封锁一个路口。

该问题表面上看来是球最短路径的问题，而问题一中已经求得了92各节点相互之间的最短距离，故以进出口节点序号为列，以服务平台序号为行选取数据，即可得表，

若该问题满足平台个数与进出口节点数相同，则是一个典型的分配问题，可以采用匈牙利算法来求解；若要求的是各交警服务平台到各进出口节点距离最短的调度方式，则是典型的0-1规划问题，可以采用0-1规划模型来处理。显然其条件具有典型特征，然而目标函数却不符合标准问题的要求。

在此用遗传算法来实现选择方法的优化。遗传算法是模仿生物遗传和进化机制的一种最优化方法，它把类似于遗传基因的一些行为,如交叉重组、变异、选择和淘汰等引入到算法求解的改进过程中。遗传算法的特点之一是,它同时保留着若干局部最优解,通过交叉重组或者解的变异来寻求更好的解。与贪婪算法相比,遗传算法更可能找到全局最优解,而贪婪算法则容易限于局部最优而达不到全局最优。

算法2：

（1） 初始化：设置进化代数计数器t=0，设置最大进化代数T，初始群体P(0)。 

（2）个体评价：计算群体P(t)中各个个体的适应度。 

（3）选择运算: 利用轮盘赌选择法，把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

（4）交叉运算；利用单点交叉方法，设定交叉概率为0.1，把两个父代个体的部分结构加以替换重组而生成新个体。 

（5）变异运算：事先设定的编译变异概率为0.01，对群体中的个体串的某些基因座上的基因值作变动，即随机将个体0转换为个体1或将个体1转换为个体0。 

　　群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 

（6）终止条件判断:若t>T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

   采用遗传算法的思想用MATLAB编程即得到该城区交巡警服务平台警力合理的调度方案，如下表所示：

由问题一可发现路口节点28、29、38、39、61和92距离任何一个交巡警服务平台均在3分钟之外的。增加平台首先使得所有节点都在交巡警服务平台均在3分钟之内，同时又要保证增加的服务平台的工作量尽可能小。

对上述几个节点与最近服务平台的数据分析后可知（从到其他节点距离判断），上述数据可分为两类：

（1）节点对周围节点不产生影响或影响很小（如28,29,38,39）

（2）节点对周围节点会产生影响（如61,92）

对第一类节点的平台选择主要在于自身的发案率，而第二类则需要考虑周围受影响节点的发案率。考虑到处理事情的一般性，将节点都作为第一类来考虑：

首先分别以每个未被管辖到的路口节点为圆心，以3千米为半径做圆，被包含在圆内的路口节点即为新增设平台的待选择点，记个数为N。从图中可以明显看出六个圆大体分布A城区的四个区域内，即增加平台的最佳个数是4个。

其次从N个待选择点中任意选取四个点作为一组，共有M个组。计算出每组中每个待选择点的工作量，即待选择点到其所在圆内的其它各个点的时间与案发率的乘积之和。

最后通过最大工作量的最小化依次排除工作量最大的几个组，当剩下的每个组中的最大工作量相同时，比较每个组中次大工作量进行又一轮的排除，以此类推，最后剩下的一组中的四个待选择点即为所确定需要增加平台的具体位置。

通过以上的分析，用MATLAB编程计算可得在该区内需要增加的服务平台的个数和具体位置，如下表所示：

由于在发生案件3分钟后接到报警，固在次犯罪嫌疑人已经驾车逃跑3分钟的路程。     （1）车速相同

现假设犯罪嫌疑人的车速与警车的车速相同，为60km/h。则现在犯罪嫌疑人可能在●1，●2，●13，●4，●5，●6，●7，●8，●12，●10，●11。（他们的位置见图）。

现在按照就近原则，在犯罪嫌疑人停靠的点的附近调动交巡警平台去堵截。经过计算可知交巡警到达犯罪嫌疑人下一个节点之前到达。(具体见表)

（2）当犯罪嫌疑人的车速大于警车车速时

因为不管怎样警车的都追不上犯罪嫌疑人，所以必须进行全城封锁。

（3）当犯罪嫌疑人的车速小于警车车速时

按照就近原则，让距离最近的平台派警力围堵，因为犯罪嫌疑人的车速小于警车的车速，固可以追上。

对模型的评价

本题主要运用图论中的Floyd算法与解决组合优化问题的遗传算法的相关知识建模数学模型，进而求解出交巡警平台的设置和管辖范围。在模型求解最短距离过程中用了MATLAB软件编程，把大量的运算交给计算机处理，提高了计算的准确性。其中组合优化问题的遗传算法的操作对象是一组可行性解，而非单个可行解；搜索轨道有多条，而非单条，因而具有良好的并行性；只需要利用目标的取值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性；目标函数解释为编码化个体的适应值，因而具有良好的可操作性与简单性；

模型的推广

（1）在交巡警平台处理突发事件时，可以很快的找到去突发事件点得最短路径，可以有效及时的处理突发事件。

（2）在一个区域可以设置最合理的交巡警平台数量，但同时又能有效地处理这个地区的突发事件。这样就可以有效地节省国家警力资源。

（3）在发生重大案件时，可以根据模型中的速度比较法，基本确定围堵方案。这样有利于安定民心。

    下载本文