数学建模参考论文-110警车配置及巡逻方案.docVIP

全国第六届研究生数学建模竞赛题 目 D题：110警车配置及巡逻方案摘 要：本文主要讨论了110警车配置及巡逻方案的问题，利用分支定界、仿真模拟等方法对各问题进行分析，建立模型求解得到所需结果，并对结果的合理性做出分析。针对本题的特点，将真实地图中的交叉路口和道路抽象为由点线组成的无向图，而道路长度即作为无向图中节点间权值，以便处理错综繁复的道路选取问题。对问题一，在D1条件下，考虑警车的初始状况，假设警车初始位置均位于某一道路交叉点上，每辆警车的有效接警范围是以其为中心，道路距离2km范围。计算此时覆盖整个城市90%的道路交叉点所需的最少警车数量，同时要保证以重点部位为中心，道路距离1334m范围内至少有一辆警车。采用非线性0-1规划计算得所需最少警车为23辆。对问题二，巡逻效果显著程度的有关指标：接警后警车平均能达例。对问题三，鉴于问题一的讨论，加上问题二定义的指标，由0-1规划寻找最优巡逻方案，并给出评价指标值。对问题四，考虑D3的条件，由于在第三问中所采用的仿真巡逻路径是随机产生的，所以对于D3约束，第三问方案已具有相当的不确定性和隐藏性。对问题五，将警车数量置为定值10，确定警车位置，使总覆盖点数最大，以此为巡逻方案的目标。对问题六，将问题三中的约束条件修改即可，每辆警车的有效接警范围是以其为中心，道路距离2500m范围的道路点，重点区域策略为以重点部位为中心，道路距离1667m范围内至少有一辆警车。对问题七，考虑到实际情形较复杂，仅列举一些常见因素，并给出相应的解决方案。最后，本文对以上模型进行了相应的评价。参赛密码 （由组委会填写）关键词：警车巡逻 floyd 整数规划 模型仿真参赛密码 （由组委会填写） 参赛队号 1029103 队员姓名 高山岳 龚松建 葛启承 1、问题提出110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126， 4266），（7434 ，1332）（见下图红点部位，蓝色部分为水域，道路数据见附件,相邻两个交叉路口之间的道路近似认为是直线）。某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：D1. 警车在接警后三分钟内赶到现场的比例不低于90；而赶到重点部位的时间必须在两分钟之内。D2. 使巡逻效果更显著； D3. 警车巡逻规律应有一定的隐蔽性。请回答以下问题：一. 若要求满足D1,该区最少需要配置多少辆警车巡逻？二. 请给出评价巡逻效果显著程度的有关指标。三请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四. 在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。五如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？ 六. 若警车接警后的平均行驶速度提高到50km/h，回答问题三。七. 你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。2、模型分析与求解2.1问题一2.1.1问题一重述若要求满足D1,该区最少需要配置多少辆警车巡逻？2.1.2问题一分析根据题意，假定事件均发生在道路的端点上，警车在接警后，车速提升至40公里/时，并要求3分钟以内到达事发地点。应此要求，一辆警车覆盖的道路长度为2公里。在警车覆盖范围内的顶点视为警车初始顶点的邻域。考虑警车的初始状况，假设警车初始位置均位于某一道路交叉点上，此时警车处于静止状态，每辆警车的有效接警范围是以其为中心，道路距离2km的道路点。计算此时覆盖整个城市90%的道路交叉点所需的最少警车数量，同时要保证以重点部位为中心，道路距离1334m范围内至少有一辆警车。仿真巡逻时，采用前进路线随机选择的方法，保证在下一时刻，仍然满足D1条件，同时车辆必须移动。2.1.3模型建立根据以上分析和假设，做以下符号定义：警车所在顶点位置为，为0-1变数，；所有顶点的集合为；连接到的道路长度为2公里邻域点集合为；连接到的道路长度为2公里邻域路长集合为；道路总长度为E；3个重点部位设为；size（）为所求矩阵的长度；条件D1可用数学表达式表示为： （1） （2） （3）由分析可以看出，以（2）、（3）式表示约束条件更符合题意。目标是令总警车数量最小，那么目标函数即为： （4）综上所述，问题一可以转化为带有约束条件的0-1规划问题：目标函数： （5）或 （6）其中（5）式是以警车覆盖90%道路交叉点为指标的约束，（6）式是以警车覆盖90%道路为指标的约束。2.1.4模型求解求解模型时，首先需要知道任意两点间的最短距离。考虑到Dijkstra算法只能求某一点到其它各点的距离，而不是任意两点间的距离，所以使用Floyd算法求解两点之间的最短路问题。这里，利用excel表格里的数据得到各相邻点间的带权值的对称矩阵，即Floyd算法中需要的邻接矩阵。得到邻接矩阵之后，利用Floyd算法进行n次迭代即可求得各点之间的最短路径矩阵以及求取最短路径途经结点的矩阵，各点之间的最短距离保存为矩阵。Floyd算法如下：把带权邻接矩阵W作为距离矩阵的初值，即D(0)=W。（）D(1)= ，其中，是从i到j的只允许以1作为中间点的路径中最短路的长度。（2）D(2)= ，其中，是从i到j的只允许以1 、 2作为中间点的路径中最短路的长度。（）D()=，其中，是从i到j的只允许以1、2、作为中间点的路径中最短路的长度。即是从i到j中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵。通过进一步编程可得到距离矩阵，P矩阵中的元素表示第i个顶点到第j个顶点间的距离是否在2公里以内，如是则为1，否则为0，T矩阵中的元素表示第i个顶点到第j个顶点间的距离是否在43公里以内，如是则为1，否则为0。即前期的数据处理到此为止，具体程序参见附件“Model_1.m”及相关程序 。模型所需数据得到后，就可以利用软件来求解，首先用lingo编程求解，主要约束条件是以警车为中心的邻域内包含的街道总交叉点数应大于街道总交叉点数的90%，三个重点区域用离其最近的街道交叉点代替，所选警车点与T矩阵的乘积应包含替代点的坐标。由于软件搜索算法的局限性，可能得到的只是可行解，而不是全局最优解。具体程序参见附件“ddd5.lg4” 随即采用matlab软件编程，求解0-1规划，当添加所有约束条件时，软件亦无法得到可行解，所以采用部分约束的方法加快模型求解速度，先添加D1中的第一个约束条件，利用分枝定界法求解模型，得到最优解22，再判断D1中第二个约束条件是否满足，经计算发现，103，277两点在此解集内，123点不在，所以再添加一个警车点，得到次优解23。具体程序参见附件“Model_2.m” 。巡逻方案：采用动态寻优算法，确保满足D1条件。巡逻仿真时采用道路方向随机尝试法，在交叉路口处（即节点处），根据邻接矩阵数据等概率随机选择相邻点作为前向目标节点。以固定的小步长尝试预算每辆警车的行进到未来下一刻的位置坐标，如果所有警车的预算坐标满足D1所描述的约束，则接受这一预算值并作为下一刻的真实值，否则，不接受预算值，随机改变警车的前进方向（即可能掉头行驶），以此迭代，模拟真实的巡逻情况，并可作为题中所要求的巡逻路线的设计过程。程序参见附件“fangzhen2.m”。下图为巡逻仿真流程图。图1 巡逻仿真流程图2.2问题二2.2.1问题二重述请给出评价巡逻效果显著程度的有关指标。2.2.2问题二解答评价巡逻效果显著程度的有关指标：警车到达道路交叉点的平均比例。2.3问题三2.3.1问题三重述请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。2.3.2问题三分析鉴于问题一的求解，加入约束条件D2，根据题意，D2条件是一个弱约束条件。数学模型：目标函数： 2.3.3问题三求解巡逻方案的具体程序见附件“fangzhen2.m”。评价指标（警车到达道路交叉点的平均比例）为91.01%。图2所示为警车到达道路交叉点图，图中黄线表示原地图道路，蓝线表示警车巡逻所行经的道路，仿真行驶时间为5小时左右（下图3线条表示意义同此所述，不再赘述）。图2 警车到达道路交叉点图2.4问题四2.4.1问题四重述在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。2.4.2问题四分析D3条件，即隐蔽性条件，由于在第三问的求解中，巡逻仿真算法采用的是方向随机搜索算法，故每辆警车的行车路线均是随机产生的，不具有规律性，在某种程度上满足了隐蔽性的条件，所以巡逻方案与问题三相同。2.5问题五2.5.1问题五重述如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？ 2.5.2问题五分析这是一个典型的多目标规划问题，给定条件为警车只有10辆，那么显然不可能满足D1条件，同时，D2所表述的指标也将降低，由于我们所选取的指标与D1中第一个条件有相同趋势，所以目标定为2个，模型如下所示：目标函数： 具体到此处模型的求解为双目标规划，附件中“Model_3.m” 是对其建模，但在尝试使用matlab求解时，无论是单目标或者将目标加权合并都无法得到可行解，时间仓促，故没有使用lingo计算。2.6问题六2.6.1问题六重述若警车接警后的平均行驶速度提高到50km/h，回答问题三。2.6.2问题六分析接警后平均速度的提高对应在模型上表现为P，T矩阵的改变，P，T矩阵中更多的点被置1。数学模型：目标函数：2.6.3问题六求解巡逻方案的具体程序见附件“fangzhen3.m”。评价指标（警车到达道路交叉点的平均比例）为92.90%。图3 警车到达道路交叉点图2.7问题七2.7.1问题七重述你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。2.7.2问题七分析实际情况比较复杂，仅列举一些常见因素：1. 某一时段某一区域有多起事件发生，该区域只在某一辆警车的邻域范围内的情况，由于处理事件需要一定的时间，在此时间段内附近警车应当动态调整行车线路，争取最大范围的覆盖率，特别是在重点区域出现该情况时，更应注意考虑，必要时应当有备用车辆，以供调遣。2. 最优路径交通堵塞的状况，可以将邻接矩阵中警车与事故处对应的两点间的权值赋值为无穷大，重新计算，选择一新的最优路径。3. 任一时刻警车故障时，该区域发生事件的情况，附近警车到该区域支援，使用备用警车。3 模型评价针对所建立的模型进行总结：由原始地图坐标数据和相邻节点的数据，我们画出整个城市的道路复原图，图中，道路用直线表示，各交叉路口用节点表示。画出这样的复原图有助于我们进行建立模型时，我们采用的是以交叉点覆盖90%来简化约束条件D1，据此得到的是一个简化的次优解，也可以采用道路覆盖90%来建立模型，也许可以得到更小的全局最优解。对比问题三与问题六得到的警车到达道路交叉点的图，可以明显看到，警车接警后时速的加快使得警车到达的道路交叉点更多，行经的道路也几乎覆盖了整张地图。从此图的仿真结果可以看出，警车的巡逻路径可以行经所有道路，而不仅仅有限的覆盖。巡逻仿真算法的优点：对于一组满足约束条件的初始点，利用计算机的高速计算性能可以动态的预算未来半个小时、一个小时甚至一天的运行路线，具体到警车巡逻方案上，就可以确定警车的行驶路线，由于仿真时采用道路方向随机搜索法，所以每次确定的路线均不一样，这样就有很好的隐蔽性，很好的解决了第四问的问题。另外结合实际应用，由于警车均装上了GPS，运用本文中的巡逻仿真算法，可以直观的观察警车的行进路线，以及巡逻路线占城市总路线的百分比，对于提高警车巡逻效率，保障城市安全方面有了一个数据的衡量。巡逻仿真算法的改进：算法要求初始点满足约束条件，无法对不满足约束的初始点进行计算，可以定义一个类似于遗传算法中适应度函数的目标函数，从而对于不满足约束条件的预算数据点进行判定，以其适应度函数来判定是否取该点作为下一个移动点，如果没有这样的一个适应度函数，那么没一步的预算，都得使得其满足约束条件才能确定，否则重新以一定概率随机预算数据。结合实际情况，警车有处理事件或是车辆故障的停止时间，在仿真程序中也是