交巡警服务平台的设置与调度数学建模论文_.doc

交巡警服务平台的设置与调度摘要 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文主要目的是是对现有的交巡警服务平台设置方式进行评价、改善，以及解决平台的指派问题。 针对问题一，本题属于典型指派问题，首先我们使用了floyd算法计算出最短距离矩阵，基于案发率最小，到达时间最短的原则，根据发案点仅在节点上的假设对平台指派进行规划，使得在各个交巡警服务平台到其管辖区内各路口节点的时间总和尽可能的短的情况下，得到指派方案（见表1）。 针对问题二，基于“一个平台最多封锁一个路口”的限制 ，为在突发重大情况时，得到合理的调度方案，从警力分配最优，到达时间路口最短的原则出发，我们引入0-1整数规划模型，通过对第路口节点到第个交通路口的最短距离的分析，得出在封锁13条交通要道的时间为8.015分钟，以及封锁13个路口的的合理封锁方案（见表2）。 针对问题三，用层层筛选的方法，从各服务平台的工作量不均衡和有些节点需要出警时间过长两个角度进行分析。引入工作量的不均衡度，筛选出来工作量负荷的平台，从而得出需要的出警时间过长的路口节点，在图中标出筛选出来的点，综合分析后定量定位的增加交巡警服务平台。由于考虑到成本的因素，10号服务平台出现工作量过低的情况，在与附近各平台的工作量、距离对比后，将10号服务平台撤销，由11号服务平台管辖；合并后的11号服务平台工作量虽然仍略低于平均工作量，但是出警时间有所增加，有一定程度的可行性。 针对问题四，首先从全市范围内考虑，以人口密度、人均案发率两个主要影响因素作为权重（各个影响因素在总体中的重要程度），由变异系数赋权重法得出两个因素的影响权重，求出各个城区所需交巡警平台的个数，再以能否3分钟到达为依据评价该市当前服务平台安排的合理情况，用类比法对当前交巡警服务平台安排进行优化。针对问题五，在犯罪嫌疑人已逃窜3分钟的情况下，基于警力占用最少，封锁盲点最少，封锁时间最短的原则，本文在图论的基础上建立了围捕逃犯模型，该模型可分为三个子模型：“封锁可行性模型”，“逃窜分层模型”和“交巡警力分配模型”，通过对三个子模型的分析，采用了分层围堵的方案，在节省警力，争取的时间的原则下，给出调度全市交巡警服务平台警力资源的最佳围堵方案。关键词：指派模型；层层筛选；变异系数赋权；类比法；围捕模型；floyd 算法；图论一、问题重述 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。面对实际情况我们得出要解决的问题：1、为该市中心城区a各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。2、对于发生重大突发事件，需要调度全区20个交巡警服务平台的警力资源，进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。3、根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。4、针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。5、如果该市地点p（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。问题一要求求解各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为）到达事发地。我们首先求出从各个节点到各个交通巡警服务平台节点间的距离矩阵，再根据图论中的floyd算法，利用matlab可以计算出第路口节点到第个交通路口的最短距离进而得到有路口节点到交通巡警服务平台节点间的最短距离矩阵，最后用指派模型对交巡警各个服务平台管辖范围进行约束安排。问题二要求在突发情况下，给出区的13个路口的最佳封锁方案，基于“一个平台最多封锁一个路口”的限制 ，从警力分配最优，到达时间路口最短的原则出发，我们引入0-1整数规划模型，通过对第路口节点到第个交通路口的最短距离的分析，得出对13个路口的最佳封锁方案。 问题四要求评价该市现有交巡警服务平台设置方案的合理性，首先从各区分配平台数的均衡性和能不能保证全市3分钟内可达，分析其合理性，之后在对平台设置方案进行优化，以全市3分钟内可达为要求，得到最少需要平台为105个，且按区内工作量均衡原则将各区节点分配给各区平台。以人口数量与日均案发率按各0.5的权重定义工作量，警台数量与各区工作总量成正比，求得在保证全市3分钟内可达，且保证区间均衡条件下最少需要平台总数为136，此时各区以案发率为标准定义的工作量记为最优平均工作量，接着以105为基础，136为目标，对各区内工作量为其最优平均工作量1.5倍的平台，把其管辖节点中离其最近的节点设为新平台，3倍时则增加2个平台，以此类推。得到最终需要144个平台来保证预设的目标。 问题五要求给出调度全市交巡警服务平台警力资源的最佳围堵方案，基于此我们在图论的基础上建立了围捕模型，该模型可分为三个子模型：“封锁可行性模型”，“逃窜分层模型”和“交通警力分配模型”。封锁可行性模型”可以确定包围圈，但是会产生封锁盲点（巡警无法封锁的路口，行程包围圈的漏洞）和封锁重复点（多个巡警封锁同一个路口，造成警力浪费及其他不良影响）。“逃窜分层模型”可以消除封锁点盲点彻底封锁逃逸路线；“交巡警力分配模型”可以消除封锁重复点，解决了警力浪费等缺点。三、问题假设1.题目所给的数据真实可靠，所有道路均为双行道；2.出警时道路恒通畅（无交通事故、交通阻塞等发生），警车以恒定时速）行驶正常；3.警车行驶的整个路途中，通过各种交通工具，走的路程都是最短路程，转弯处不需要花费时间；4.一个交巡警服务平台的警力能且只能封锁住一个路口；5.发案点仅在各个节点上；6.犯罪嫌疑人的逃窜速度为。四、符号说明:第路口节点到第个服务平台的最短距离；：第路口节点由第个服务平台管辖；:区所有路口节点所构成的集合；:交巡警服务平台节点所构成的集合；:节点就是交巡警服务平台节点；:节点到任何交巡警服务平台节点的最短距离大于；:至少存在一个交巡警服务平台节点到节点的距离大于0且不超过；:交巡警管辖服务平台的管辖区域内路口平均案发率；:各交巡警服务平台到其管辖区内个路口节点的平均时间；:巡警服务台与要道最短距离；:误差函数；:人口密度所占权重；:人均案发率所占权重；:整个a区服务平台每天的平均案发率即服务平台每天的平均工作量；:路口节点每天的案发率；:各服务平台工作量与平均工作量的偏离度；：案发路口到其他路口的距离；：判定矩阵；：关联矩阵。五、模型的建立与求解5.1 交巡警服务平台分配管辖范围5.1.1 求最短距离矩阵 因为每个交巡警服务平台的职能和警力配备基本相同，所以要考虑每个平台在工作量均衡的条件下能最短时间内到达突发事件现场，主要考虑的方向是各个平台管辖范围内的总的时间最短（最短时间可转化为出警的最短路程）与均衡每 个 平 台 的 发 案 率 这 两 个 因 素 ，显 然，这 是 个 双 目 标 问 题，为 了 方 便 求 解，把 双 目标函数单一化，将各个平台发案率的均衡转化为约束条件建立模型，进而划分出区域。其中，我们引入了0-1规划模型，采用了floyd算法求出图中任意两个站点之间的最短距离，再根据所建立的模型划分出具体区域，首先根据题中所给的a区所有节点坐标和a区所有路线的首尾节点算得该区各节点间的距离矩阵,并画出该区交通网络与平台设置图，如图1所示，。表示一般路口结点；。表是交巡警服务平台结点；比例尺：1mm=100m图1 该区交通网络与平台设置图 其次由各节点间的距离矩阵和图论中的floyd算法，利用matlab可以计算出第路口节点到第个服务平台的最短距离，是一个的邻接矩阵，然后从中抽出92个节点分别到20个服务平台的最短距离，进而得到有路口节点到交通巡警服务平台节点间的最短距离矩阵。5.1.2 最优分配方案的确定 根据题目中“尽量能在3内有交巡警到达出发地”和“警车的时速为的假设，可以算出的车程对应的是，结合图中的比例尺，对应图中的距离为。即若某个路口的节点到某个交巡警服务平台节点的距离小于等于，则该路口就有可能被该交巡警服务台所管辖。由此可以根据最短距离矩阵可以将a区的节点分为三类:第一类：，即节点就是交巡警服务平台节点，这样的节点有。则。为区所有路口节点所构成的集合。第二类：，即节点到任何交巡警服务平台节点的最短距离大于，这样的节点有,将其转化为所对应的交巡警服务平台，则。第三类：，即至少存在一个交巡警服务平台节点到节点的距离大于0且不超过，除了第一类和第二类以外的所有节点都属于这样的节点。 根据原始数据整理我们得出交巡警服务平台节点所构成的集合,为了确定约束条件，运用运筹学上的指派模型建立变量：其中。得出了三种分类情况下各个路口的管辖情况：1） 若，则。即交巡警服务平台由自己管辖。2） 若，则根据时间最先的原则，节点应由它最近的服务平台管辖，不妨设该交巡警服务平台的节点数，即。3）若则至少存在一个交巡警服务平台节点到节点的距离大于0且不超过，不妨设满足该条件的服务平台有个，记为，那么节点最终肯定由其中一个服务平台所管辖，所以有。 以上就是变量的约束。目标函数的建立主要是依据各交巡警服务平台的任务量即管辖区域内的个路口案发总和表示应该相对均衡，即各交巡警管辖服务平台的管辖区域内路口案发率总和不应该过分偏离平均案发率，根据这一思想，构造如下目标函数： 其中，则各交巡警管辖服务平台的管辖区域内路口案发率总和不应该过分偏离平均案发率，结合上述的约束条件得到如下管辖范围分配模型： 利用lingo软件编程求解，得到最优值为 0.655。该模型只考虑了案发率平均绝对偏差最小，没有考虑时间因素，可以在平均案发率绝对偏差为0.655的前提下，将出警时间考虑进去，使得各交巡警服务平台到其管辖区内个路口节点的时间总和尽可能的短。由于题目中假设警车的速度恒定，所以时间问题可以转化为距离问题进而得到如下优化安排模型： 利用lingo编程求得最优值为1114.07，再根据最优解的取值可以得到管辖范围分配的合理方案如表1所示表1 交巡警管辖范围的合理分配方案服务平台节点管辖的路口节点服务平台节点管辖的路口节点11 67 68 69 71 73 741111 26 2722 39 43 70 721212 2533 44 54 55 65 661313 21 22 23 2444 57 60 62 63 64141455 49 51 52 531515 28 29 3166 50 56 58 591616 35 36 37 3877 30 48 611717 40 41 4288 33 46 471818 81 82 83 8499 32 34 451919 75 76 77 78 79 8010102020 85 86 87 88 89 90 91 92 由上述结果可看出，在案发当时交巡警服务平台即接到报警并立即派出警力前往的情况下，仍不能保证在3分钟内有交巡警到达事发地的路口有28,29,38,39,61,92共6个；管辖范围仅有一个路口的有平台6，10，14；平台20,1,5的管辖路口数较多，分别为10个，10个，9个。由此可以看出存在交巡警平台的工作量不均衡和有些地方出警时间过长的问题。5.2 警力合理的调度方案由问题一可知，区交警服务平台有20个，将交警服务平台的个数记为，则，记要封锁的出口数为，。基于“一个平台最多封锁一个路口”的限制 ，从警力分配最优，到达时间路口最短的原则出发，可以将20个交警服务平台封锁13个出口问题转化为13个交警服务平台调度到13个节点的问题。基于以上分析，引入0-1整数规划模型，记0-1变量，表示巡警服务平台对要道进行封锁情况，若表示巡警服务平台对节点进行封锁，记，否则记为，即：，其决策变量有260个。本题要求对 13 条要道进行快速封锁，即要求巡警服务台对13条交通要道进行全部封锁所需时间最短的调度方案。从警力分配最优，到达时间路口最短的原则出发，在假设警车行驶速度相同的条件下，可转化为求巡警服务台与要道最大距离最短的调度方案。则本题目标函数，其中为20个服务平台到13个交通要道的最短距离，为一个的矩阵。则目标函数为。根据问题的要求，每个交通要道必须有一个交警服务平台对其进行封锁，即对于，应有，对于，应该有。综上所述，可以得到此问题的优化模型为 按照附件2中20个巡警服务台和13条交通要道的顺序进行编号，引入决策变量，根据已经建立的模型中的约束条件和目标函数，利用 lingo软件求得全局最优解。从求解结果显示，目标函数的最小值为8.015，即封锁13条交通要道的最少时间为8.015分钟，基于此，给出了区交巡警服务平台警力合理的调度方案如下表2表2 a区交巡警服务平台警力封锁13条交通要道的调度方案出入a区的路口标号交巡警平台位置标号交巡警到达路口的时间（分）12107.58614166.7411666.25921115.07222126.88223146.47324132.38528154.7522978.0163083.06138197.6394847.39662206.4485.3 交巡警服务平台的合理增添方案用表示整个a区服务平台每天的平均案发率即服务平台每天的平均工作量，表示路口节点每天的案发率，则有，表示平台管辖范围内每天的案发率，则为服务台管辖范围内的案发率与全区平均案发率的偏离度。根据偏离度的表达式可知，若，则说明平台有工作量负荷的情况，反之说明没有工作量负荷的情况。利用附件所给数据和已求出各平台所管辖的范围，可以计算出全区服务平台的平均工作量。利用excel将全区20个平台目前的工作量与全区的平均工作量画成折线图如图 所示：图2 各个服务平台工作量与平均工作量比较通过图2,只能看出各个平台的工作量与平均工作量的大致差别，为了更详细的了解各服务平台的工作量与平均工作量的差别，进而通过计算求出了全区各服务平台工作量的偏离度，如表3表3 各交巡警服务平台的工作量偏离度123456789100.220.110.080.06-0.02-0.020.040.060.08-0.7411121314151617181920-0.26-0.360.37-0.600.180.030.120.010.110.69通过以上统计，我们可以进行第一步筛选，从表3中可找出20个交巡警服务平台中工作量负荷的服务台，将各服务台工作量负荷程度由大到小进行排列有：20号、13号、1号、17号、2号、19号，这里我们只筛选了一些工作量负荷相对较大的平台。通过各平台工作量不均衡进行了第一步筛选，然后以各路口节点出警时间不同进行第二步筛选。根据各交巡警服务平台到各节点的最短距离矩阵，我们筛选出了一些出警时间超过三分钟的路口节点，即节点距离管辖自己的交巡警服务平台超过。得到的目标有：，。此筛选表明39、61、28、29、38、92这些节点的出警时间过长，需要通过增加交巡警服务平台来解决此问题。综合前两步的筛选结果，就可以进行综合考虑确定增添服务平台的数量与位置了。由于工作量不均衡没有定性的评价指标，本文引入了偏离量来衡量工作量不均衡的程度，因此，在设置交巡警服务平台的时候，优先考虑偏离量，进而考虑出警时间控制在三分钟以内。在a区的交通网络示意图中标识出工作量负荷的交巡警服务平台位置，再标识出出警时间超过三分钟的路口节点位置。在工作量负荷与出警时间过长的两个方面，对临近标记点进行试点和博弈，可以发现，合理增加服务平台不但可以解决工作量负荷的问题，而且可以解决出警时间过长的问题，当然，也要遵循增加量最小的原则，以控制成本。经过逐步的试点与修正，最终我们确定了在28、39、61、88号路口节点增加服务平台。在增加四个服务平台的基础上，我们再次对各平台管辖的范围进行划分，不但使全区的工作量有所下降，而且也使各平台工作量的不平衡度明显下降。另外，由图 可知，10、11、12、14号服务平台的工作量明显低于平均工作量，这样就造成了人力资源的浪费，无形中也增加了过多的成本。由全区各节点最短距离矩阵可知：，在工作量没有负荷的前提下，选择合并距离最短的平台。经过筛选，可以将10号服务平台去除，归11号平台管辖，通过计算知道此时11号服务平台的工作量偏离量为-0.004，即工作量仍低于平均量。虽然出警时间略高于三分钟的标准，但工作量并没有增加，并且有效降低了成本，此方案有较高的可行性。5.4 模型的建立与求解5.4.1 评价当前交巡警安排1）从各区分配平台数的均衡性,分析其合理性首先从全市范围内考虑，由分析知服务平台的个数主要受该区人口总数和日均案情发生率的影响。以人口密度、人均案发率两个主要影响因素作为权重（个影响因素在总体中的重要程度），我们由变异系数赋权重法求两个因素的影响权重，算法如下： 经过计算，得到以下结果：；基于此，得到各个区域所需平台数为：。详见表4 表4 各城区现有平台数与所需平台数平台数城区abcdef现有平台数2081791511所需平台数351114578相差平台数1533483 表4中相差平台数为负数表示不满足所需平台数，为正数表示超过所需平台数，即a区所需35个平台而实际只有20个，实际平台数与所需平台数相差15,b区需要11而现有平台数为8，相当于不足3个平台。c区需要14个平台而实际有17，相当于浪费3个平台，d区需要平台5，实际拥有平台数为9，有4个平台浪费，e区需要7个平台，而实际拥有平台数9个，f区需要个8平台，实际拥有平台数11个平台，浪费3个平台。由上述分析，求出各区分配的平台数与现有各区的平台数进行比较，定义误差函数：查阅相关资料得若存在，则认为分配不均衡。计算得到各区的误差函数分别为所以区最不合理，其次是e区，再次是d区和b区，最后是f区，只有c区交巡警满足要求。2）从效率方面，分析其合理性本模型已全市所有节点3分钟内可达为效率的硬性指标，若全市存在任意三分钟内不可达的点就可认为分配不合理，再此进一步说明原方案的不合理性。通过matlab求出全市各个城区三分钟可达的最少平台的分配位置如表5表5 基于效率的各区分配交巡警平台所在节点位置表城区位置平台所在节点位置a10，11，12，13，14，15，17，28，33，38，48，54，58，70，87b98，102，103，116，117c169，170，174，175，176，177，179，183，193，200，201，204，206，214，231，238，240，249，250，255，261，263，268，285，307，314，315d323，327，329，332，333，344，347，358，362，363，368，370e373，374，375，378，379，380，381，386，387，388，390，391，402，407，416，417，418，420，440，450，457，462，471，473f479，482，483，484，485，488，491，504，509，521，525，539，541，544，559，541，544，559，561，567，573，574，575，582由上表可知至少需要105个平台才能保证有突发事件时全市有交巡警到达，而全市现有平台数为80，显然交巡警平台显然不足。由此可知该市在各个区内的交巡警安排方案在平台数量及位置分配上都存在不合理现象。5.4.2给出全市交巡警平台设置的最优方案1） 确定三分钟全市可达情况下各区所需的最少交巡警平台数量 首先以区为例，建立区内节点间的距离矩阵：从方阵的每行筛选出值小于的元素，将这些元素的列标放入一个新的行向量中，则为节点作为交巡警平台在三分钟内可达的所有节点。将两两合并，挑选出合并后元素最多的集合，记作，以记录两节点的序号，继续将与合并，挑选出合并后元素最多的集合，以记录三节点的序号，重复以上步骤，直到集合中的元素个数为92，这样就可在三分钟内可达的到要求下以最少的平台覆盖全区。即：保证均衡此时不考虑权重的条件下，通过matlab将上述105个平台在全市进行配置结果如下表6表6 基于效率和均衡的分配台数城区平台数每区最少分配的平台数按均衡型性分配的平台数a1518b511c2721d1218e2520f2117 可得，在总的平台数为105个时，依然不能保证工作量的均衡。2）以区内工作量均衡为原则，确立各区新增平台数量。由问题分析中已经知道，区内的平台工作量仅以发案率为衡量指标。通过1）已经可以确定挑选出的个节点作为平台时，各个平台可以管辖的范围，把平台可以管辖范围的节点发案率总数作为各个平台的工作量，设为，如果存在节点与两个甚至三个以上平台的距离都小于时，则把分配给最小的平台，重新计算每个平台的，分配下一个被重复管辖的节点，直到每个节点都被分配给这个平台管辖，然后求出各个平台的工作量。接着求出问题分析中所述的平均工作量，即在保证全市三分钟可达与区间工作量均衡条件下各区以案发率为指标的的工作量，以区内平台为例：若其工作量不超过平均工作量的,则不在其三分钟可达范围内增加平台；若其工作量为平均工作量的，则将平台的管辖范围分为两块，也就是说添加一个平台。若其工作量为平均工作量的，则将平台的管辖范围分为三块，也就是说添加两个平台。若其工作量为平均工作量的，则将平台的管辖范围分为四块，也就是说增加三个平台。 基于上述分析，可以求出既保证三分钟出警又能保证每个区工作量均衡的最少平台数，如表7 表7 保证各区效率均衡分配表城区平台数每个区最少分配的平台数按均衡性分配的平台数a1524b514c2727d1223e2526f21223）以区内工作量均衡为原则，确立各区新增平台位置以a区内平台为例，由以上两步，可以确立平台管辖范围内节点变成新增平台的数量，设为。把管辖范围内距离最近的个节点设为新增的平台，这样可以保证新增平台对管辖范围内尽量多的节点是三分钟内可达的（当新增平台与重合时，新增平台对管辖范围内任一点3分钟内可达），也就使新增平台能最大程度分担的管辖任务。这样就确立了全市所有新增平台的具体位置。利用matlab，对3）进行求解，按照效率与均衡并重的原则确定新增平台的位置，具体优化方案如下表最终得到需要144个平台既保证了全市3分钟可达到，也保证了区间和区内整体工作量的均衡，各城区新增平台位置情况如表8表8 各城区新增平台数a23,30,34,41,55,57,69,88,91b118,128,142,145,147,150,164c225,244,269,288,292d336,338,341,349,359,361,364e403,430,432,451,463f514,520,5375.5 最优围捕方案 本文在图论的基础上建立了围捕模型，该模型可分为三个子模型：“封锁可行性模型”，“逃窜分层模型”和“交通警力分配模型”。封锁可行性模型”可以确定包围圈，但是会产生封锁盲点（巡警无法封锁的路口，行程包围圈的漏洞）和封锁重复点（多个巡警封锁同一个路口，造成警力浪费及其他不良影响）。“逃窜分层模型”可以消除封锁点盲点彻底封锁逃逸路线；“交巡警力分配模型”可以消除封锁重复点，解决了警力浪费等缺点。5.5.1 封锁可行性模型本模型主要讨论，某一时刻对犯罪嫌疑人所处的范围进行封锁的可行性，最终确定哪些交巡警平台可以成功封锁那些逃窜路口。为便于分析，某市区的交通图如下图3图3 全市交通图由5.1的floyd算法我们可以得到第个路口到第个交巡警平台的最短距离矩阵,案发路口到其他个路口的最短距离：；由于该市有587个路口，基于现实情况分析，我们选择了30分钟内嫌疑人能够到达的路口，对其进行封锁，由图2分析，30分钟内嫌疑人能够到达的路口有33个，基于此，建立0-1判别矩阵,设犯罪嫌疑人从被发现到开始围捕驾车可行驶的路程为,假设嫌疑人的移动速度为，犯罪嫌疑人从被发现到开始围捕驾车可行驶的路程为为，将加上得到，用减去，若结果小于0，则，表示交巡警平台能够在犯罪嫌疑人到达之前堵住该路口；若结果大于0，则，表示交巡警平台不能在犯罪嫌疑人到达之前封锁该路口，即 。通过判定矩阵可以看出，犯罪嫌疑人所在范围的外围路口：有的路口，无法赶在犯罪嫌疑人到达之前封锁，成为“封锁盲点”；有的路口可以对应多个可用的交巡警平台，这些路口可以称为“封锁重复点”。对于“封锁盲点”的问题，将在“逃窜分层模型”中处理。对于“封锁重复点”的问题，将在“交巡警分配模型”中进行处理。5.5.2 逃窜分层模型 由5.1.1得出封锁可行性模型中存在“封锁盲点”问题，为对此问题进行处理，引入逃窜分层模型。首先设定0-1关联矩阵，其中表示：节点与节点通过公路直接相连；若，其表示：节点与节点不直接相连。将犯罪嫌疑人逃窜距离后可以到达的路口集合设定为向量，包括个路口，每个路口记为：，则犯罪嫌疑人案发三分钟后能够到达的路口集合。通过以上的封锁可行性模型，得到判断矩阵;由可以看出，一层包围圈是否能封锁犯罪嫌疑人所处的所有区域。当犯罪嫌疑人从第一层包围圈的漏洞中逃出来以后，立即启用下层“封锁可行性模型”，即可以认为“逃窜分层模型”相当于“封锁可行模型”的一个序列。基于上述分析，我们选取了第一层当中，不能成功封锁的路口，作为新的集合；与通过公路直接链接的点，作为新集合;取非集合与的交集，作为：，表示：通过前一层次中不能封锁的路口，向外逃窜，并且通过一条公路直接连接的路口组成的集合，以封锁可行性模型中的33个路口分析，我们得出了，即。假设中有个路口，再次以这些路口为犯罪嫌疑人出发点，可以得到个新的距离向量，作为一个序列，合称为；以上中的每一个向量，按照封锁可行性模型再次计算，以此类推，一直到某一层没有封锁盲点为止。5.5.3 交巡警分配模型在为交巡警分配封锁路口时，面临了两个问题，一个事路口可能有多个交巡警平台对其进行封锁，二是一个交巡警平台可以封锁多个路口，引入交巡警分配模型，即构建二维整数目标规划，首先使每层被封锁的路口达到最大，其次使封锁各层时交巡警的移动距离达到最小。设第层有个路口，共有个交巡警服务平台可供调度，由此可以从封锁可行性模型中抽取出判别矩阵其中：由于一个交巡警平台只能被调度到一个路口，所以有约束；同时建立一个实际调度矩阵，其中表示是否由第个交巡警平台向第个路口调度警力，其值为1表示调度，为1时表示不调度。每个出口只需要一名巡警，所有：，。每个巡警把守一个出口过着该巡警闲置，其中为距离矩阵，令：;。第一目标是使得每层可能多的路口被围堵：；第二目标是使封锁各层时交巡警的移动距离最小，即：。基于以上分析，我们得出总约束条件和目标函数： 基于上述分析，我们通过对逃窜分层模型的分析，得出嫌疑人能够达到的路口编号，给出了交巡警平台对每个路口围堵的具体方案，见表9；由图3上的可包围点中我们可以看出逃窜分层模型的第六层中犯罪嫌疑人的行动范围被彻底包围，无路可逃。表9 逐层包围的具体方案层次围堵路口调用巡警平台第二层101029155535566235173161632第三层604414017第三层3711672461714118561475第五层244172240169248166第六层168176171170六、模型的评价和改进6.1 模型的评价6.1.1 问题一模型的评价 针对问题一，利用图论中的算法和运筹学中的指派模型可以很好地解决指定地区交巡警服务平台管辖范围的合理分配问题，得到了案发率平均绝对偏差最小和总移动时间最小原则下的最优分配方案，为管辖范围的合理分配提供了一个参考，同时也为进一步研究交巡警服务平台的合理设置问题做了准备。6.1.2 问题五模型的评价 针对问题五，我们利用图论和整数规划的理论建立了一种在市区内围捕罪犯的方法，通过了分层围堵的方案，在节省警力，争取的时间的原则下，对嫌疑人的逃跑路径进行分析，得出了最优合理的警力调用围堵方案。模型全面完整，算法简单易懂，动态围堵闭集的提出和使用具有较大的实际意义和应用价值，为快速围堵犯罪嫌疑人提供了一种有效的方法。6.2 模型的改进本文中的模型也有一定的局限性，如现实中不能时刻保证道路的时刻畅通，也不能保证出警时间和罪犯逃逸的速度，本文中忽略了现实中的一些不定因素，且问题五中只反映了犯罪嫌疑人逃窜的情况，未考虑到其隐藏或躲避的情况，不能完全反映巡警的真是出动。七、模型推广 本模型建立了在理想条件的交巡警平台的最优设置，可给生活中交巡警平台的设置予与参考，有一定的实际价值，可使交巡警在接到任务后更好的利用较短时间分配救援力量和选择最佳行进路径。并且该模型也可运用到其他最优选址问题中去，比如关于消防救援工作最 优路径问题、重大生产安全事故应急救援问题、公共交通的最优路径问题等。 参考文献1于晶贤 李金秋 田秋菊，交巡警服务平台管辖范围的合理分配研究，第 34期， 2011年12月。2姜启源，谢金星，叶俊.数学模型m，高等教育出版社，2008。3王海英，黄 强，李传涛等，图论算法及其 matalb 实现，北京航空航天大学出版 社，2010年。4谢金星，薛 毅，优化建模与 lindo/lingo软件,清华大学出版社，2007年。5肖华勇，基于 matlab 和 lingo 的数学实验，西北工业大学出版社，2009 年。6严蔚敏，吴伟民，数据结构，清华大学出版社，2006年12月。7董金哲，罪犯围捕中的数学模型，第18期，2012年。8黄湘宁,祝延波,基于图论的节点分析,青海师范大学学报,2011年。附录1）画出a去交通网络的程序；data1=;%a区路口节点坐标data2=;%a区起（终）点节点号c=413 403 383.5 381 339 335 317 334.5 333 282 247 219 225 280 290 337 415 432 418 444;d=359 343 351 377.5 376 383 362 353.5 342 325 301 316 270 292 335 328 335 371 374 394;e=219 280 337 251 234 225 212 243 246 314 371 315 381;f=316 292 328 277 271 265 290 328 337 367 330 374 381; for i=1:140 x1=data1(data2(i,1),1); y1=data1(data2(i,1),2); x2=data1(data2(i,2),1); y2=data1(data2(i,2),2); a=x1,x2; b=y1,y2;plot(x1,y1,b*,x2,y2,b*,c,d,ro,a,b,e,f,r*); hold onendhold onx=data1(1:end,1);y=data1(1:end,2);plot(x,y,.)hold onfor i=1:92 c=num2str(i); c=,c; text(x(i),y(i),c)endhold onx,y=getpts2）全市交通图的程序；b=xlsread(cumcm2011b.xls,1,a2:c583);c=xlsread(cumcm2011b.xls,2,a2:b929);c1=xlsread(cumcm2011b.xls,3,b2:b81);c2=xlsread(cumcm2011b.xls,4,b2:b18);m n=size(c);a=zeros(m,m);for i=1:m a(c(i,1),c(i,2)=sqrt(b(c(i,1),2)-b(c(i,2),2)2+(b(c(i,1),3)-b(c(i,2),3)2); a(c(i,2),c(i,1)=a(c(i,1),c(i,2);endm n=size(b);d=b(:,2:3);gplot(a,d,k)hold onplot(b(c1,2),b(c1,3),ro);plot(b(c2,2),b(c2,3),r*);plot(b(:,2),b(:,3),.);hold offhold onfor k=1:m text(b(k,2),b(k,3),leftarrow,num2str(k);endhold off3） 求各节点之间距离的matlab程序node_data=xlsread(cumcm2011b.xls,1,b2:c93); %载入a区路口节点的左边数据 routine_data=xlsread(cumcm2011b.xls,2,a2:b144); %载入路线节点标号数据 record_data = cell(92,1); %创建包体，用来保存92个节点，每点的最大覆盖区域count = 0;%更急路线节点标号数据创建邻接矩阵for i = 1 :92 node_index = routine_data(find(routine_data(:,1)=i),2); node_index = routine_data(find(routine_data(:,2)=i),1);node_index; node_index = node_index(find(node_index =92); n = length( node_index); count = count + n; record_datai = zeros(n,2); for j = 1 : n record_datai(j,1) = node_index(j); record_datai(j,2) = 100*sqrt(node_data(i,1) - node_data(node_index(j),1)2+(node_data(i,2) - node_data(node_index(j),2)2); endendadjoin_matrix = zeros(count,3); % 邻接矩阵index_adj = 1;for i = 1 :92 n1,n2 = size(record_datai); n = n1; for j = 1 : n adjoin_matrix(index_adj,:) = i,record_datai(j,1),record_datai(j,2); index_adj = index_adj + 1; endendadjoin_matrix%根据邻接矩阵数据创建图论的稀疏矩阵a1=adjoin_matrix(:,1);a2=adjoin_matrix(:,2);a3=adjoin_matrix(:,3);dg=sparse(a1,a2,a3);%建立稀疏矩阵，图论求解 for i=1:92 for j=1:92 if dg(i,j)=0 dg(i,j)=inf; if