警车配置及巡逻方案

全国第六届研究生数学建模竞赛题 目 110警车配置及巡逻方案摘 要：针对110警车配置及巡逻方案问题，通过引入算法、贪心算法以及捕食者算法等相应知识，建立了警车优化配置的搜索模型，然后利用软件求解，得出满足相关要求的结论。首先将巡逻方案问题转化为图论中节点与边的覆盖问题，通过调整节点的覆盖率来调整道路的覆盖率，研究了在满足相关出警条件下，警车巡逻的道路覆盖率、巡逻方案的路线，以及提出了刻画巡逻效果显著程度的个指标：节点覆盖率、道路覆盖率、规定时间内单位车辆走过的不同节点数和规定时间内单位车辆走过的不同道路数，然后根据上述引入的相关算法，搜索出符合条件的结论，静态时最少需配置14辆警车，而动态时需17辆警车，具体巡逻路线及相关评价指标值参见正文。最后考虑了影响巡逻效果的各种因素及情况，提出了警车巡逻的增援模型，并给出了求解的算法与策略。关键词：警车优化配置 贪心算法 捕食者算法 增援模型参赛密码 （由组委会填写） 参赛队号 队员姓名 仲伊 刘文杰 刘祥鹏 目录摘要一、问题重述3二、问题分析42.1问题一的分析：42.2问题二的分析42.3问题三的分析42.4问题四的分析42.5问题五的分析42.6问题六的分析.42.7问题七的分析.5三、问题假设5四、符号说明5五、模型建立与求解55.1问题一的模型建立与求解55.2问题二的解答95.3问题三的模型建立与求解95.4问题四的模型建立与求解145.5问题五的模型建立与求解165.6问题六的模型建立与求解175.7问题七的解答19参考文献：22附录123附录224附录326附录429一问题重述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.1问题一的分析 问题一是在满足警车在接警后三分钟内赶到现场的比例不低于,而赶到重点部分的时间必须在两分钟之内的条件下，求该区最少需要配置的警车数。首先把城区地图抽象化为一个无向赋权图，图中节点为交叉路口，边为城区街道，将警车巡逻问题转化为图论中图的节点、边等覆盖问题，利用算法处理相关数据。然后通过假定每条道路上案件发生的概率相同，将“警车在接警后三分钟内赶到现场的比例不低于”转化为图论中的数学约束条件，即警车接警后所能到达的道路条数占总道路条数的比例不低于，而“赶到重点部位的时间必须在两分钟之内”作为首先满足的条件，进而把研究道路条数的覆盖问题转化为研究交叉口节点的覆盖问题，利用节点覆盖率的调整来达到道路条数的覆盖范围不低于的要求。最后分析知在静态状态下，即定点巡逻时所需配置的警车数量最少，故通过引入贪心算法思想来求出所满足条件的最少警车数及其初始坐标位置。2.2 问题二的分析问题二要求给出评价巡逻效果显著程度的指标，而警车巡逻的目的是起到震慑作用，降低犯罪率，增加市民的安全感，因此衡量巡逻效果显著程度的指标应围绕这个目的而定，故依据警车在接警后三分钟内赶到现场百分比的要求，选取巡逻方案的节点覆盖率、道路覆盖率、规定时间内单位车辆走过的不同节点数和规定时间内单位车辆走过的不同道路数等4个指标来刻画巡逻效果显著程度。2.3问题三的分析基于问题一和问题二的分析，欲求在满足条件且尽量满足情况下的警车巡逻方案，在引入贪心算法思想的基础上，依据题目特点，再引入捕食者算法，即运用贪心算法找到初始点(满意解)，然后运用捕食搜索迭代运算实现警车移动，达到动态分组的目的，进而求出满足问题所设条件下的警车的巡逻方案及其评价指标值。2.4问题四的分析问题四是在问题三的基础上，考虑巡逻的隐蔽性问题，因本文采用的贪心算法和捕食者算法本身在搜索时具有极强的随机性，而警车均配有卫星定位系统和先进的通讯设备，故警车在选路时可有很强的动态随机性，每一辆警车在相应的时间间隔后有多种不同巡逻道路选择。所以警车巡逻时的隐蔽性的问题会同时得到很好的改善。2.5问题五的分析 在问题三分析的基础上，将巡逻车辆减少至10辆，在尽量满足和条件下，同样利用贪心算法和捕食者算法来求得相关的结论。2.6问题六的分析 基于问题三的分析，将接警后的速度提升为，按照问题三的分析求解过程求得警车的巡逻方案及其评价指标值。2.7问题七的分析 在原问题的基础上，适当排除理想的假定，考虑现实生活中影响巡逻效率的相关因素和情况，从众多因素的解决方案中归纳出增援问题模型，并加以详细讨论。三.问题假设1.假设道路全是双行道；2.假定所有事发现场均在原图的道路上；3.假定警车在某个连续4个小时内巡逻过程中不休息；4.假定在各个警车初始位置设定在各交叉路口;5.假定警车在巡逻过程中不发生汽车故障；6.假定警车在巡逻过程中不受道路阻塞的限制；7.假定警车处理完案件后回到原巡逻路线；8.假定警车在巡逻过程变速行驶，但保持平均速度。四.符号说明表示第个评价指标值表示城市巡逻图中所有的交叉路口数表示街道的长度表示第个交叉口到第个交叉口的距离表示最少需要配置的警车数量表示第辆警车所在位置的向量表示第个案发点五.模型建立与求解5.1问题一的模型建立与求解5.1.1模型准备 模型说明1) 把整个城市的街区抽象化为一个图： 据题意和附录数据知，城区只有街道存在，警车可以沿着街道的两个方向行走，为方便讨论，将这个城市的街区图抽象化为一个无向图。街区中的每条街道可以看作是无向图的边，而街区中的路口可以看作是无向图的节点。那么所提出的巡逻问题就可以理解为若干个警车在这个无向图中行走巡逻。2) 图形符号标注： 城市的街区图用图论中的符号表示为无向图：为图中的有限非空顶点数，即巡逻图中的路口，表示这个巡逻图中所有的交叉路口数；为图中的有限边集合，即街区巡逻图中的街道，表示这个巡逻图中所有街道数，边的权值表示街道长度，即街道的长度为；利用题中给定的数据生成图，将交叉路口的编号添加上，图形参见图一：图一. 交叉路口的编号图3) 建模原则：原则一：假定每条道路上案件发生的概率相同；原则二：为了能够方便快速出警，将各个警车初始位置设定在各交叉路口；原则三：警车巡逻过程中的变速行驶是为了使得同时到达各个交叉路口。 数据处理：1) 数学原理：计算赋权无向图中各对顶点之间最短路径，利用算法，其基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后，当时，即是各顶点之间的最短通路值。即图权的邻接矩阵为来存放各边长度： 变量说明：；之间没边，在程序中以各边都不可能达到的充分大的数代替；是之间边的长度，；对于无向图，是对称阵，。2) 每对顶点之间的最短路径： 根据题中地图数据中各个交叉路口的坐标数据，利用算法，程序参见附录1，将每对顶点之间的最短路径求出，得到各个交叉路口的邻接距离矩阵，部分数据结果如下(单位：米，结果保留整数)： 5.1.2模型建立： 引入贪心策略： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的一般步骤如下：1) 将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2) 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择 的安全；3) 说明在做出贪心选择后，剩余的子问题具有这样的一个性质。即如果将子问题的最优解和所作的贪心选择联合起来，可以得出原问题的一个最优解。 目标分析：1) 将警车在事件发生后赶到重点部位的时间必须在两分钟之内作为优先考虑的对象，必须首先满足；2) 基于上述建模思想原则一的说明(假定每条道路上案件发生的概率相同)，将警车在接警后三分钟内赶到现场的比例不低于理解为警车接警后所能到达的道路条数占总道路条数的比例不低于；3) 将研究道路条数的覆盖问题转化为研究交叉口节点的覆盖问题，利用节点覆盖率的调整来达到道路条数的覆盖范围不低于的要求；4) 对于在满足的条件下需要最少配置多少辆警车巡逻问题，经分析可知，在静态状态下，即定点巡逻所需的车辆是最少的，故研究在静态状况下所需的最少车辆即可。 初始化警车位置交叉路口分组原则： 对307个交叉点进行分组，首先对三个重点部位进行分组，使得每个分组中警车可在两分钟内到达案件现场；然后对剩余交叉点进行分组，使得每辆警车都可在三分钟之内到达其分组中的所有节点，且被覆盖的交叉点数占总数的90%以上，进而通过调节交叉点的覆盖率来满足道路条数的覆盖率不低于的要求；最后所得的交叉路口分组数即为最少所需的警车数。分组方法：因问题一是最优问题，具有最优子结构，依据上述引进的贪心策略的思想，故构造“贪心算法”对交叉点进行分组。贪心算法是使所做的选择都是当前最佳的，期望通过所做的局部最优选择来产生一个全局最优解。1) 最大分组的定义：用表示个待分组点，的一个子集，满足，。则为的最大分组。2) 算法流程：找出距离重点部位两分钟车程的交叉点，将他们按重点部位分为三组，非重点部位一组;从待分组中找出满足警车在接警后三分钟内赶到现场的条件的最大分组，将以分组点从待分组中删除;如果以分组点占交叉点总数大于，而且道路条数覆盖率不低于，则停止；否则跳到。每次都选出局部最大的分组，最后即得最优解。 结果分析根据上述的算法和贪心算法流程，利用软件求解，程序参见附录2。求解过程发现，经过有限次迭代，辆警车的巡逻道路覆盖数没有达到的条件，而辆警车的巡逻道路覆盖数存在高于的状态，故最少需要配置辆警车巡逻，然后根据捕食者算法模拟警车移动时道路数的覆盖率证明此结论的正确性，具体模拟对比参照图二。图二. 辆警车与辆警车的道路覆盖率对比由图二分析知：辆警车的道路覆盖数有个别点突破，因问题一在静态时具有最优解，利用贪心算法确定的这些个别点就是问题一的所求的警车配置位置，使其满足道路数的覆盖率不低于的要求。各个参数参见表1，具体的初始位置参见图三。表1：辆警车与辆警车的参数对比车辆数覆盖节点数节点覆盖率覆盖道路数道路覆盖率辆2830.92184110.8974辆2890.94144180.9127 图三.14辆警车的初始位置5.2 问题二的解答 安排警车在街区巡逻的目的是起到震慑作用，降低犯罪率，增加市民的安全感，因此衡量巡逻效果显著程度的指标应围绕这个目的而定，本文依据警车在接警后三分钟内赶到现场百分比的要求，选取巡逻方案的节点覆盖率、道路覆盖率、规定时间内单位车辆走的不同节点数和规定时间内单位车辆走过的不同道路数等4个指标来刻画巡逻效果显著程度，具体含义如下：a) :巡逻方案中所有警车接警后所能覆盖的节点数占总节点数的比例；b) :巡逻方案中所有警车接警后所能覆盖的道路数占总道路数的比例；c) :在规定的某段时间内，单位车辆所能够遍历的不同节点的总数；d) :在规定的某段时间内，单位车辆所能够遍历的不同道路的总数；5.3问题三的模型建立与求解： 算法选择问题中每辆警车可以认为是解空间的一个维度，每辆警车移动时道路覆盖比例可以认为是连续变化的函数，在最优解附近覆盖率都比较高，此特点符合捕食者算法的搜索特性。 捕食算法基本思想 模拟动物的捕食过程中的搜索策略，提出了一种新的针对组合优化问题的仿生算法，即捕食搜索()算法，如图三所示。应用捕食所搜算法时，先在整个搜索空间进行全局搜索，直到找到一个较优解；然后在较优解附近区域进行集中所搜，直到搜索很多次也没有找到更优解，从而放弃局域搜索；然后在整个搜索空间进行全局搜索。如此循环，直到找到最优解(或近似最优解)为止，具体的捕食者算法流程图参见图四。YN全局搜索(在整个解空间内)内)找到更好的解？邻域搜索(在邻域内)找到更好的解？YN图四.捕食者算法流程图 模型的算法转化问题三是寻求在满足条件且尽量满足情况下的警车巡逻方案，确定警车数时具有动态分组的特性，故可利用前述的贪心算法和捕食者算法进行求解，即运用贪心算法找到初始点(满意解)，然后运用捕食搜索迭代运算实现警车移动。从搜索结果看贪心算法有较好的性质，贪心算法的结果接近最优值，具体参见图五(红线代表的道路覆盖率)。图五.16辆警车模拟移动结果 于是模型的具体算法转化如下：1) 把组合优化问题定义为一个二元组，这里是解的集合，函数代表每个解到对应的适应值的变换。假设每个解存在一个邻域，定义这里包含中元素的5%。中一个解到另一个解的变换成为一个移动。2) 在规模为辆警车的巡逻问题中，用从1到的个自然数组成的集合中的每个元素表示一个警车，交叉口用表示，例如，状态，表示辆警车所在位置的向量。3) 一个解为全体警车所在城区位置的状态，给定一个解，根据已知道路联通数据，每辆车选择一个交叉口移动一步则得到一个新的解，所有车可选择的交叉口的组合就得到的邻域。4) 算法的主要迭代来自警车位置的移动，从邻域中随即取300个样本，根据事先定好的各指标权数计算适应值大小，选取适应值最大的移动警车。 算法流程Step1:运用贪心算法搜索一个初始点，；Step2:根据现有解随机产生300新解，并计算适应值函数；Step3:选取适应值最大的解，警车移动一步；Step4:判断停止条件，若且移动400次停止计算，否则跳到Step1； 结果输出分析根据上述贪心算法和捕食者算法的算法步骤，利用软件求解，程序参见附录3。求解过程中分别对15辆、16辆、17辆和18辆警车的巡逻情况进行了模拟，具体模拟图形参见图六、图七、图八和图九，15-18辆警车的各个参数结果对比参见表2。 图六.15辆警车的模拟移动情况 图七.16辆警车的模拟移动情况 图八.17辆警车的模拟移动情况 图九.18辆警车的模拟移动情况注解：红色点划线代表道路覆盖率90%；蓝色点划线代表道路覆盖率平均值。 表2：15-18辆警车的各个参数值对比车辆数覆盖节点数节点覆盖率覆盖道路数道路覆盖率辆27790.32%40588.45%辆28291.75%41089.52%辆28392.25%41590.54%辆28793.40%41991.47%经分析上述图表中辆警车的模拟情况和各个参数值知：选择17辆警车时可达到问题的要求，即满足条件且尽量满足。利用软件模拟17辆警车巡逻时的行走方案(以模拟行走400步为例)，具体巡逻方案结果参见图十和表3，评价指标值参见表4，而白天任意连续4小时内的各警车的正常巡逻位置数据参见附录-Result3.txt，计算程序参见附录4，各个评价指标值参见表5。 图十.17辆警车的巡逻方案的移动坐标表3：17辆警车时的巡逻方案 警车号巡逻方案1841168411612312214114813614822802772792772652772942852942853143125127125118134981011031044711811811474484885194185194210194169512951506397739373937273027772602111672111672117173716682425242524251391381391499136148141215197215226242226215109211192676667661671311131311160596069655826333233122532572372572962951863613295129515288454963491430129330130029228826425026427115263262263243263262291289287270162472582472582472582342122342121791226122630292291276281表4：17辆警车时巡逻方案的指标值(400步)指标指标值92.25%90.54%16.6522.59表5：17辆警车时巡逻方案的指标值(任意连续4小时)指标指标值92.25%90.54%8.477.53 算法验证 在极端条件下验证算法的收敛速度，前三辆警车分布在重点部位，其它14辆警车全部位于交叉口1，迭代400步结果如图十一，在30-40步时就收敛到巡逻方案，说明本问题采用的算法鲁棒性强、可行性很高。图十一.17辆警车算法收敛性验证5.4问题四的模型建立与求解： 因本文采用的贪心算法和捕食者算法本身在搜索时具有极强的随机性，而警车均配有卫星定位系统和先进的通讯设备，故警车在选路时可有很强的动态性，故警车巡逻时隐蔽性的问题可以得到很好的改善，以下以任意截取的2个连续4小时内警车的巡逻方案为例，求得其巡逻方案和各个评价指标值，进行比较，具体比较结果参见表6，图十二，表7，图十三及表8。表6：17辆警车时的巡逻方案一警车号巡逻方案111612311612311612311684116842294303294290294303294290294285390987698961041101019896477394039403521244945515517117218421421616914915415065288848883915022292273027301030603833321482572962952532512532512282512592262422412422262152412612412421011310911112813012810297949211282228228115487545612172425152523292286132145814521242425242514204190204208204208199208212234152502642502492502302432492502641619818618717618719519321116721117363833261291210727图十二.17辆警车的巡逻方案一的移动坐标表7：17辆警车时的巡逻方案二警车号巡逻方案1116841161231161231411231221232277285277280277280277280277279313314214314213314210510687904172449484425492421375224216214184214194185194185194650565455545628342019773899589738911112815712883072962953062953062512362512539251228251253251253272242241242101571931571581571582602552602701115414913911711588918351521231275727302782938260132313361861323252414247258276258276281292291276281152822842822882922882822882822881618119020419019120821220820420817331491432143326129图十三.17辆警车的巡逻方案二的移动坐标表8：17辆警车时巡逻方案一和方案二的指标值(任意连续4小时)指标方案一91.25%90.36%8.417.53方案二92.02%90.76%9.187.53 通过分析上述图表可知，依据本文的算法设计的巡逻方案，通过的道路的规律具有很强的随机性，因此在巡逻的隐蔽性可以得到很好的改善，进而回答了问题四，警车的巡逻方案及其评价指标值分别参见上述的表6或表7、表8。5.5问题五的模型建立与求解： 在问题三的算法基础上，减少车辆的数目至10，根据上述的贪心算法和捕食者算法，利用软件模拟10辆警车巡逻时的行走方案，具体巡逻方案结果参见表9和图十四，评价指标值参见表10，而白天任意连续4小时内的各警车的正常巡逻位置数据参见附录-Result5.txt。 表9：10辆警车时的巡逻方案警车号巡逻方案184116841168411611612314112322902942902942902782772792862793143125143125127125101103101103429222822292222292229512952472342472582472342122342122086605958655958383332367194214194214194169194185194185824252325152525242524925325125325125319586137136148109211192679211194109113131表10：10辆警车时巡逻方案的指标值(任意连续4小时)指标指标值84.83%82.29%8.35.9图十四.10辆警车的巡逻方案的移动坐标5.6问题六的模型建立与求解：基于问题三，将接警后的行驶速度提高到，依据问题三中讨论的求解思想，以及贪心算法和捕食者算法，对问题六进行解答即可。利用软件求解，程序参见附录3。求解过程中分别对8辆、9辆、10辆和11辆警车的巡逻情况进行了模拟，具体模拟图形参见图十五、图十六、图十七和图十八，8-11辆警车的各个参数结果对比参见表11。 图十五.8辆警车的模拟移动情况 图十六.9辆警车的模拟移动情况 图十七.10辆警车的模拟移动情况 图十八.11辆警车的模拟移动情况注解：红色点划线代表道路覆盖率90%；蓝色点划线代表道路覆盖率平均值。 表11：8-11辆警车的各个参数值对比车辆数覆盖节点数节点覆盖率覆盖道路数道路覆盖率辆26887.32%39586.26%辆27790.16%40688.71%辆28191.66%41590.58%辆28693.27%42492.47%在接警后的速度为的情况下，分析上述图表中辆警车的模拟情况和各个参数值知，10辆警车时可达到问题的要求，即满足条件且尽量满足。利用软件模拟10辆警车巡逻时的行走方案(以模拟行走400步为例)，具体巡逻方案结果参见表12和图十九，评价指标值参见表13，而白天任意连续4小时内的各警车的正常巡逻位置数据参见附录-Result6.txt，各个评价指标值参见表14。表12：10辆警车时的巡逻方案警车号巡逻方案18411684116841161221231168422382402382402382402402382402383143125127133127119879087904302630603026261210125236235236251236251394035406186182918296181318730130230130230130230130030129382111672111671311671111099410992912762582562592312122082122081021242124212449242124图十九.10辆警车的巡逻方案的移动坐标表13：10辆警车时巡逻方案的指标值(400步)指标指标值91.66%90.58%28.338.4表14：10辆警车时巡逻方案的指标值(任意连续4小时)指标指标值91.66%90.58%14.412.85.7问题七的解答： 考虑巡逻效率的因素、情况：现实生活中，在警车巡逻时，会有很多不确定的因素，影响着案件的处理，使得不能在规定的时间内到达，如以下所列的因素等等：1) 警情太多，指挥中心只能依次派警；2) 接警警车在半路上又遇到他人拦车报警，只能下车处置，指挥中心只好另派 别的警车处警；3) 负责报警现场辖区的警车已经有现场，指挥中心只好从别的管区临时调派其他110；4) 案件需要多辆警车参与处理，而其他巡逻警车因距离偏远，未能及时赶往现场；5) 管区内的警车及周边单位的警车全有现场，指挥中心会让派出所处警，而派出所要临时组织车辆与警力，有时到达现场会不及时；6) 有的现场属于移动现场，因为种种原因，报警地点不断变换，警车到达之后，报警人又转移到别处了；7) 同一报警地点附近有两个相同或类似的现场，其中一个现场的当事人报了警，而民警却先遇到了那个没报警的现场，很容易导致误会；8) 部分民警不负责任，延误处警时间；9) 社会犯罪率高，加重案件处理的工作量。 解决方案：针对上述考虑到的因素、情况，对于1)、7)、8)、9)各个情况，提出如下的解决方案： 提高公民的素质水平，加大法制宣传，降低犯罪率； 加强警务人员的职业素质要求，提高责任感； 设置备用警车，应对突发事件。 对于2)、3)、4)、5)、6)各个情况，建立巡逻警车增援模型以完善巡逻方案。警车增援问题的讨论如下：.增援问题1) 问题分析首先为了方便处理增援问题，将警车设为不同的状态，一般的巡逻街道的警车的状态为巡逻状态，发现某条街道上发生案件的警车必然离案件点最近，本文称它为组织者；让其负责组织召集其他警车来解决这个增援任务.被这个组织者召集来增援案件点的警车就称之为增援者，它的状态为增援状态。 增援问题的实质就是当巡逻街区中某一条街道发生案件，就近的的警车正好发现这个案件点，就将自己设为组织者，成立增援联盟，根据解决这个案件需要的警车数，召集离这个案件点最近的若干警车来解决案件.由此可知，增援任务中的难点就是组织者如何在其他的警车中选择离案件地点最近的警车以及如何高效地计算各个警车到案件点的最短距离和最短路径。那么解决这个问题最直接的思路就是当某条街道发生案件时，计算所有警车到街道的案发点的最短距离和最短路径，然后按照距离由小到大的顺序选出所需的个警车让这个警车沿着计算出来的最短路径去增援街道。所以问题就转变为如何求各个警车到发生案件的点的最短路径。2) 模型建立以图二十(某条街道案发地点不一定在路口，而且案发时每个警车所在的位置也不一定是路口)为例，对增援模型进行讨论： . 街道K案件点街道j警车m街道l警车i图二十.增援情况讨论 任一条街道都一定是在两个路口之间的，那么不管在哪个位置的警车若要增援街道的案件点，警车都必须要从，中的某一个路口进入该街道； 所以计算某个警车到案件点的最短距离可以转化为计算警车到路口的最短距离加上路口到案发点的距离，警车到路口的最短距离加上路口到案发点的距离，然后找出这两个距离之间的最小值； 同样警车如果正好在某个路口，那么计算警车到路口的最短距离就转变为计算路口之间的最短距离，那么可以直接使用算法； 如果警车不在路口，而是在某条街道上，那么同上分析，警车只能从与街道相连的两个路口出去，增援案发点，那么计算警车到路口的最短距离就可以同上转化为计算路口到路口的最短距离。经过这些讨论处理，计算警车到案发点的最短距离实际上就转化为计算： 那么计算每个警车到街道上案发点的最短路径可以转化为求每个警车所在街道两端的路口节点到发生案发的街道两端节点的最短路径。3) 算法流程当某条街道上发生案件，需要增援的算法流程为:当某个处于巡逻状态的警车在巡逻的过程中发现街道上发生案件，那么将警车设为这个案件处理任务的组织者。警车首先估算街道上的案件处理是否需要其他警车增援，如果不需要其他警车增援，那么自己直接解决这个案件，解决后恢复为巡逻状态。如果这个案件需要其他警车增援，那么估算需要增援的警车数，成立增援任务联盟；计算处于巡逻状态的各个警车到案件点的最短路径和最短距离，按照距离由近到远的顺序和增援需要的警车数选择增援的警车，并告知选出的警车参与到增援任务联盟中。如果组织者发现处于巡逻状态的警车数不够完成增援任务，那么解散增援联盟，将自己的状态转为巡逻状态，并继续巡逻；各个处于巡逻状态的警车从组织者那里获得召集信息，就将自己的状态设为增援状态，并沿着计算出的最短路径前去完成增援任务；一旦增援所需的警车全部达到案件点，组织者安排处理案件，案件处理完毕，组织者宜布联盟解散，原联盟中的各个成员转变为巡逻状态，继续巡逻任务。 参考文献1 Thoms H.Cormen,算法导论，北京：机械工业出版社，2006.92汪定伟，王俊伟，智能优化方法，北京：高等教育出版社，2007.43Liu C,Wang D.Predatory search algorithm with restriction of solution distance J. Biological Cybernetics,2005(92):293-3024Smith J N M.The food searching behavior of two European thrushes.II.The adaptiveness of the search patterns J .Behavior,1974(59):1-615 胡运权，运筹学教程（第二版），北京：清华大学出版社，2003.5附录1clear;clcroadpointm n=size(way);for i=1:m D(way(i,1),way(i,2)=1; D(way(i,2),way(i,1)=1;endm n=size(D);for i=1:m loc=find(D(i,:)=1); la=length(loc); for j=1:la dis(i,loc(j)=sqrt(dian(i,2)-dian(loc(j),2)2+(dian(i,3)-dian(loc(j),3)2); endenddis(find(dis=0)=realmax;for i=1:m dis(i,i)=0;endn=size(dis);dis=dis+dis;path=zeros(n);for k=1:n for i=1:n for j=1:n if dis(i,j)dis(i,k)+dis(k,j) dis(i,j)=dis(i,k)+dis(k,j); path(i,j)=k; end end endenddis;path;附录2clear;clcroadlimit1=84 116 122 123 136 141 148;limit2=238 240 265 266 268 274 277 278 279 280 285 286 290 294 303;limit3=72,74,75,76,87,90,96,98,99,101,103,104,105,106,110,112,118,119,120,121,124,125,127,129,132,133,134,135,142,143;load dis.mat;dis=dis./2;s=40000*3/60;reach=1:307;P=zeros(1,307);for l=1:1000 kk=randperm(8); load dis.mat; dis=dis./2; clear num clear P clear nn P=zeros(1,307); for k=kk clear num if k4 for i=limitk num(i)=length(find(dis(i,:)s); end m n=max(num); nn(k)=n; reached=find(dis(nn(k),:)s); dis(:,reached)=realmax; dis(reached,:)=realmax; P(reached)=1; sum(P); else for i=reach num(i)=length(find(dis(i,:)s); end m n=max(num); nn(k)=n; reached=find(dis(nn(k),:)s); dis(:,reached)=realmax; dis(reached,:)=realmax; P(reached)=1; sum(P); end end res1(l)=sum(P)/307; load Dist.mat Cover=find(P=1); SUM=0; k=0; length(Cover); for i=1:length(Cover)-1 for j=i+1:length(Cover) if Dis( Cover(i),Cover(j) )=0 SUM=SUM+Dis( Cover(i),Cover(j); k=k+1; end end end SUM; SU