搜索
模型的建立:第一问：最优警车布控问题我们把警车放在路口的交叉处，目标函数为最少警车。约束条件为赶到事发位置的警车大于1.写目标函数时我们用0-1矩阵，街口有警车的为1无警车的为0。约束条件那个街口能到达事发地点的为1不能的为0.具体约束见下：设i表示图上的310个点，令前307个点表示307个路口，而最后3个点表示3个重点部位；ijd表示第i个点到第j个点的最短距离。ix为0-1变量，表示在第i个点是否安排警车,则有:，否则个路口安排警车值守在第0i,1ix,其中i=1,2…307maxL表示警车在规定的时间内所能行的最大距离,则有：310307,35000307,2500maxiiLijp为0-1变量，表示从第i个点能否在规定的时间内到达第j个点，则有maxmax,0,1LdLdpijijij，其中i=1,2…307;j=1,2…310以安排最少警车为目标函数，以每个点在发生情况时至少有一辆车可以赶到，建立如下0-1整数规划模型：3071miniixZs.t3071310,...2,1,1iijijpx在编程的过程中使用“割”来实现对Lingo程序实现任意次求解第二问巡逻警车安排方案们采用循环式巡逻方式。因此我们可以转化问题为一个TSP问题。巡逻的时候走遍全部的点。这样我们就可以每20分钟发一辆警车进行巡逻，这样每个点每20分钟就可以巡逻一次。最少警车数量=20km/h)/(20min个点的最短路307遍历。因此最小警车数为171855/2000*3=25.7783。所以，向上取整，最终得到需要26辆警车就可以实现。一共只有31条道路没有被TSP路径覆盖，TSP路径的覆盖率为93.23%。覆盖率已经很大，所以不用考虑通过分区求解局部TSP。拓展：如果不是这个地图，城市的特点有所改变，我们这里可以备选的方案有大循环，小循环，往返。在点比较密集的情况下可以采取小循环或者往返的方式进行巡逻，之后再在稀疏的点上采用大循环。第三问：要求每一段被巡视的间隔时间不得超过20分钟的比例不低于90%。针对这个问题我们首先想到的是中国邮递员问题。然后通过求欧拉回路，求得最大路径。要求解欧拉回路问题必须每个顶点的度数都是偶数才可以，这里我们首先找出度数为奇数的顶点，然后求出任意两个顶点的最短距离，再用0-1变量求最小完美对集，最后用用Fleury算法求Euler回路。0-1规划：设ijx为0-1变量，表示是否取将奇度点ji、匹配，ijw表示奇度点ji、在原图中的最短距离。以匹配代价最小为目标函数，以每个奇度点都要有一个匹配，奇度点自己不能和自己匹配以及两个奇度点的匹配要一致这三个条件为约束。建立0-1整数规划模型，则有：目标函数：min16211621ijijijxwW约束条件：s.t，否则匹配表示将奇度点0,,101162...1116211621jixxxixijiiiijjij第四问：堵截犯罪分子问题：我们要把犯罪分子在一个街口上围堵起来，也就是说找出一个街口可以使任意一个逃窜方向都已经有警车在守候。针对这个问题我们首先要知道犯罪分子的逃跑路线，然后在其路线上找出一个这样的街口。我们假设犯罪分子的逃跑路线遵循：距离最短，逃跑路线上的街口离警车最远。（这里我们可以进行改进，犯罪分子在行进之中离犯罪分子距离近的三辆警车中最远的一辆到街口的距离最近。当然这里不一定是三辆警车，这里要看街口的度数）