全国数模竞赛

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 杭州电子科技大学 参赛队员 (打印并签名) ：1. 费科斌 2. 杨志伟 3. 张佃鹏 指导教师或指导教师组负责人 (打印并签名)： 数模组 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要为了更好地利用警务资源，需要根据城市的实际情况进行合理的分配，本文研究的就是如何合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源等五个问题。针对问题一，首先用Floyd算法求出任意两点之间最短路径，然后对每个节点进行讨论，找出离每一路口节点最近的服务平台作为该节点的服务平台，其次根据每一条路线和路线两个端点的性质进行了分类讨论：如果路线的两个端点归同一服务平台管辖，则这条路线归该服务平台管辖；如果端点不归同一平台管辖，那么在该条线段太长的情况下，就把该路线平均分给两个服务平台管辖；在该线段不长的情况下，就直接把该线段分给其中一个距离较近的平台管辖。这样既对节点又对路线进行了管辖范围的划分，最后对模型的合理性进行了分析，有92.5%长度的路线能够在三分钟之内到达。针对问题二，要实现A区13个交通要道快速全部封锁，必须使要调动的13个服务平台中所有到达交通要道出口所花时间的最大值最小化，以此为目标建立0-1规划，可以求得该最短封锁时间为8.02分钟，并进一步在目标值不变的情况下使总调度路程最小化建立0-1规划的目标函数求得最终的调度方案。针对问题三，我们首先对A区根据各个节点的最短路径进行了聚类分析，把A区四次分成2,3,4,5块，为了方便计算和求解，根据实际情况人为的对分好类的选址范围中可能选到的点进行了筛选，对于两个不同的选址目的，我们将一个作为目标函数，另一个作为约束条件，从聚类好的每一块中选择一个节点作为新的平台，建立0-1规划，最终求得最合理的方案是再新增加四个服务平台，分别对应的节点序号为：29，39，60，87。针对问题四，依照设置服务平台的原则和任务，首先我们规定了四个评价指标分别为：距离服务平台小于3千米的节点占总节点的比例；所有节点距离服务平台的最长距离；人口密度与服务平台密度的比例；以及整个区域的综合发案率。我们用问题一的方法分别对六个区域中这些指标进行了求值，然后基于这四个指标对每个区域以及全市的服务平台设置进行了模糊综合评价，评价结果为较差，最后基于最小顶点覆盖问题对不合理的地方进行了局部优化。针对问题五，根据具体情况我们首先把嫌疑犯的活动限制在少数的几个城区内，然后利用动态规划的思想，将对嫌疑犯的包围圈逐渐往小缩，根据交警和嫌疑犯所花费的时间进行比较，直到嫌疑犯恰好不能逃出包围圈的那一刻，停止往小缩，最终得到的包围圈确定在A,C区某一小片区域内。关键词：Floyd算法 0-1规划 聚类分析 模糊综合评判 最小顶点覆盖一问题重述 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二.模型的假设（1）假设发生突发状况时，警员能够以60km/h的平均速度赶往现场。（2）假设各个交巡警服务平台的职能和警力配备基本相同。（3）假设线段上的案发率可以用端点上的案发率进行表示。（4）假设在逮捕犯罪嫌疑人时，犯罪嫌疑人的逃跑速度也为60km/h。（5）假设同一个交巡警服务平台同时不能兼顾两个节点。三城区A交巡警服务平台优化方案的设计3.1 符号说明任意一条路线的长度任意两个交通路口节点之间的最短路径原有的20个交巡警服务平台对应的140条路线服务平台在三分钟之内能够到达出事地点的满意度能够在三分钟之内到出事地点所有线路总长所有线路总长在分配服务平台是对应的选址0-1变量在进行对13个交通要道封锁时，所有路线中最长路线全部封锁各个要道所花费的最短时间警车行驶的平均速度全部封锁好各个要道所走的总路线长度第个节点对应的发案率第个服务平台对应的总的工作量各个服务平台的总工作量的方差在选址时决定是否要选择的0-1变量3.2 各交巡警服务平台管辖范围的分配3.2.1 问题分析要想让各交巡警服务平台使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地，我们认为是在不考虑各个交巡警服务平台工作量的情况下，使A区每条路线上的点和各个交通路口节点都可以在20个服务平台内找到路线离自己最短的服务平台，这样我们分别对各条路线和各交通路口节点进行了分析和讨论。对于各个交通路口节点来说，为了找到任意两个节点之间的最短路线，我们首先根据已知数据求出了图中相邻两个节点之间各个路线的长度，然后Floyd算法就可以求出任意两个交通路口节点的最短路线，最后对每一个交通路口节点到各个服务平台最短路线求最小值，这样就可以得出每个交通路口节点对应的平台管辖范围以及对应平台的巡警到该节点所用的最短时间。对于各条路线上的点来说，根据实际情况我们尽量想把一条路线分在同一个管辖范围之内，因此我们对140条路线中每条路线的两个路口节点进行讨论，如果这两个路口节点在同一管辖范围之内，这条路线就在该管辖范围内；如果这两个路口节点在不同的管辖范围内，要再次进行分情况讨论，根据路线的长短以及该条路线的节点是否就是服务平台进行讨论，最后确定是否要把这条路线分开进行管辖。最后我们对结果进行了验证，对于所有能在3分钟之内到达的路线的长度和能再3分钟之内达到的交通节点的个数在整体中所占的比例进行了分析，对结果进行了合理的验证。3.2.2 基于Floyd算法每个服务平台所管辖的交通节点的求解（1）每两点之间距离矩阵的建立首先建立一个距离矩阵，取任意两个节点，如果这两个节点有且仅有一条路线连接，则就等于该条路线的长度，即：否则认为该两点的距离为，即：如果，则该两点的距离为0，即：最后代入数据编程（程序见附录）可求得该最短路径矩阵，见附录。（2）用Floyd算法求解。Floyd是一种动态规划算法，对于每一对顶点 i和j，看看是否存在一个顶点i使得从i到k再到j比己知的路径更短，如果是最短就更新它，最后把所有的可能的点都找完，就可以找到点i到点j的最短路径path（i，j），其状态转移方程如下： 这样根据其算法流程用matlab软件编程（程序见附录）可以求得这92交通节点中每两个点的最短路线矩阵path，见附录。在以上求出任意两个交通节点最短距离的基础上，可以在20个交巡警服务平台中找到离每个交通节点最近的交巡警服务平台。求公式如下：根据上式可以求得对于第i个交通节点都有一个服务平台与其相对应。这样就求出了每一个交巡警服务平台所管辖的交通节点的所有数目如下表：交巡警服务平台序号 各个服务平台所管辖的交通节点序号11676869717374757678223940434470723354556566445760626364554950515253565859667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889909192表 3-2-1 每个平台所管辖的交通节点序号3.2.3 每个交巡警服务平台所管辖的交通路线的求解对于各条路线上的点来说，根据实际情况，我们尽量想把一条路线分在同一个交巡警服务平台管辖范围之内，但是有些路线会太长，有些路线还会直接与交巡警服务平台相连接，针对这些情况，我们不能把一条路线分在同一个服务平台的管辖范围之内，因此我们按照140条路线中每条路线的两个交通路口节点的情况不同进行了分类讨论：（1） 如果某条路线两个交通路口节点A,B在同一交巡警服务平台M管辖范围之内，如下图：MmA1B 图 3-2-1这样我们就把线段AB划分在M交巡警服务平台管辖范围之内。（2）如果某条路线的两个交通路口节点A,B在不同的两个交巡警服务平台管辖 范围之内，如下图：MmA1BNB图 3-2-2其中 A节点属于M服务平台管辖，B节点属于N服务平台管辖，在这种情况下，我们首先要判断一下这条线路的长度，如果太长，则不能归同一个服务平台管辖，因为线路太长对其行驶时间的影响很大；反之，我们就可以把归同一服务平台管辖，根据实际情况，我们对线段的长度按照一下规则进行分类讨论：在放在一个服务平台范围内管辖时，我们比较一下两个节点离其对应服务平台的最短路径的大小进行判断来确定归那个服务平台管理：（3）还有一种情况是线段AB的两个端点中本来自身就是服务平台。如下图： MMA1BN 图3-2-3 针对这种情况，我们同样要把线段AB平均分为两段分在M,N两个不同的服务平台管辖范围之内。根据以上算法和思路，我们用matlab软件编程（程序见附录），可以求得每一个交巡警服务平台所单独管辖的各条路线的序号，如下表：交巡警服务平台序号各个平台所管辖的交通线路的序号11,2，197,99,100,102,103,104,105,106,107,110,111,112,114,115,116,117,12023,60,61,64,65,66,101,10935,67,83,85,96,9847,84,86,87,88,89,91,92,93,9558，9,71,75,76,77,78,79,80,81,82,90610,72711, 21,44,45,46,57,73,74814,48,49,68,69,70915,47,50,51,52,5410381117,18,37,391219,36,401332,33,34,3514201522,41,421624,53,55,56,581725,26,62,1828,29,113,124,125,126,1271930,118,119,121,1222031，128,129,130,131,132,133,134,135,137,138,139,140表3-2-2 每个平台单独管辖的交通路线序号并得出有些路线平均分开归两个交巡警服务平台管辖的情况如下表：由两个平台公共管辖的路线序号46131621232743596394这条路线对应的两个服务平台的序号3 94 28 910 915 716 1417 1815 716 1717 204 20表3-2-3 由两个服务平台共同管辖的路线序号3.2.4 结果的分析和比较在解决该问题时，我们的最终目标是在为了让交巡警服务平台能尽量在三分钟之内到达事发地，为此，我们从各个方面对所求结果进行了验证和分析：（1）首先我们对所有到达时间超过三分钟的道路上的最长达到时间进行了统计（程序见附录）如下表：道路序号5786420174023948482到达对应服务平台所需要的最长时间（分钟）3.04 3.11 3.22 3.26 3.27 3.30 3.37 3.45 3.45 3.45 道路序号3836587056925963643到达对应服务平台所需要的最长时间（分钟）3.54 3.59 3.71 3.87 4.11 5.21 5.41 5.92 5.96 9.42 表3-2-3 最长达到时间的统计结果由以上表格中的数据可以发现，在140条路线中，交巡警力到达的最大时间超过3分钟的只有20条路线，而且这些时间都在3分钟附近，所以以上数据可以发现都够尽量满足三分钟内到达。（2）然后为了验证结果做的是否满意，我们规定了满意度的公式为：即：通过matlab软件编程（程序见附录四）可以求得： 将其带入得： 有上述分析可知，有92.5%的线路可以满足在三分钟之内到达，所以结果基本符合要求，满意度很高，这样也同样验证了我们解题方案的合理性。（3）在以上结果的基础上并结合每个点的案发率的大小，在超过3分钟到达的线路上，我们可以人工调整调度方案，犯罪嫌疑不会又逃脱的可能性，所以即使超出三分钟也关系不是很大。3.3 根据0-1整数规划制定服务平台警力的调度方案3.3.1 问题分析为了实现A区13个交通要道快速全部封锁，我们需要从20个交巡警服务平台中调动13个服务平台的警力分别去封锁A区交通要道的出口，而且使13个平台中所有到达交通要道出口所花时间的最大值最小化，这样可以建立目标函数用0-1整数规划解决该问题，并用lingo软件编程求出要花费最长的时间。但是在该所花费的最长时间的前提下，同样还有很多种调动方案，为了尽快使每个路口都要交警到达，同时尽量节约时间和成本，我们需要让所有服务平台到达对应的交通要道出口的总时间最短，这样既可以进一步减小嫌疑目标逃离的可能性，同时减少了成本代价的付出。同样以这个总时间最小化为目标函数，建立0-1整数规划方程，用lingo软件可以求出最终的调度方案。3.3.2 各个平台所花时间的最大值最小化模型的建立和求解我们所要解决的问题是从20个服务平台中选择13个服务平台进行调度分配到13个交通要道出口处，为了尽快实现全部交通要道的封锁目的，我们让服务平台警力到达每个交通要道出口的时间中的最大值最小化，这样就可以实现我们的目的。设表示的内容如下：由于每个服务平台行驶的速度是一定的，因此我们可以把关于时间的目标函数转化成关于所有路程中最大值最小化的问题，这样我们可以建立目标函数如下： 在以上目标函数建立的基础上，我们用lingo软件编程（程序见附录）可以求得：再将代入公式： 可求得实现全部封锁各个交通要道所用的最短时间为：3.3.3 在最短时间封锁要道的基础上调度方案的进一步优化在上述所求出实现全部封锁各个要道所用最短时间的情况下，同样还存在很多种调动方案，为了尽快使每个路口都有交警到达，我们需要让所有服务平台到达对应的交通要道的总时间最短，这样同时可以减少成本的浪费和进一步减小嫌疑目标逃离的可能性，同样设：以这个总时间最小化为目标函数，建立0-1整数规划方程如下：用lingo软件编程（程序见附录）求得实现全部封锁各个交通要道，各个交巡警服务平台所花费的时间和为：并很容易得出最终的调度方案如下表：交通要道序出口号12345678910111213交通要道所对应的路口节点序号12141621222324282930383962对应的调度服务平台序号12169141013111578254表4-3-1 交巡警服务平台警力进行快速全城封锁合理的调度方案3.4 基于聚类分析的新服务平台的选址优化方案3.4.1 问题分析如果要再选择2到5个节点作为新的交巡警服务平台，这属于一个选址优化问题，由于整个A区的节点太多，这样给选址问题带来了许多不便，为了使问题变的容易一点，我们对A区中所有节点进行了欧氏距离聚类分析，聚类的依据是每两个节点之间的最短路径。这样根据不同情况，可以对A区进行不同数目的分块。要选择若干个节点作为新的交巡警服务平台，就把A区分为若干个块，这样我们只需要从每一块中选择其中的一个节点就可以了。但是这样聚类分块以后，仍然会出现节点太多的情况，然后我们根据实际情况，一些显而易见不会作为选址点的节点直接人为排除掉，这样就大大减小了选择的范围，解决起来很方便。我们的最终目标是希望交巡警服务平台的工作量尽量均衡和出警时间尽量短，我们把出警时间作为约束条件，把工作量尽量均衡作为目标函数，同时工作量可以认为是每个区域内所管辖的节点对应的发案率的和，使各个交巡警服务平台的工作量的方差最小化，建立0-1整数规划，进行求解，针对要选择2到5个点分别进行求解，最后比较结果进行分析，决定要再选择几个交通服务平台。3.4.2 基于最短距离聚类法对A区进行分块聚类分析需要依据节点的相似性能进行分块，根据实际情况，我们考虑到了每两个节点间最短路径，把离的比较近的一些点分在一块，这样先将92个节点各自分为一类，计算它们之间的最短路径长度，选择长度最小的两个节点归为新的一类，再计算这个新类与其它节点的距离，选择距离小的两个节点（或两个新类）归为新的一类，每次合并缩小一个以上的类，直到所有样本都划入一个新类为止。这里规定两点间的距离，两类间的距离。步骤如下：（1） 看各数据量纲是否一致，如果不一致要对数据进行正规化处理，并选择一种计算距离的方法，我们这里选择的是欧氏距离法。（2） 计算各样本之间的距离，并记在分类距离对称表中。（3） 选择上述对称表中的最短距离，设为，则将合成一个新类记为： （4） 计算新类与其它类之间的距离，并将第p，q行和列删掉，作为一个新的对称表。（5） 重复以上步骤，直到最后只剩下要实现的最终分类结果为止，并作聚类图。基于以上思路和流程，我们用matlab软件进行了编程（程序见附录），分别得出在把A区分为2,3,4,5块的情况下，各类中包含节点的数目和序号，用图表示如下：A区10,11,12,13,14,15,21,22, 23,24,25,26 27,28,29 1,2,3,4,5,6,7,8,9,16,17,18,19,20,30,31,90,91,92图3-4-1 将A区分为两类的情况A区1,2,3,4,5,7,8,9,16,17,18,19,20,30,.37,41,60,62,91,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 图3-4-2 将A区分为三类的情况A区7,8,9，16,30，32,33,34,35,36,37,45,46,47,48,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 1,5,17,20,41,44, 49,61,62,91图3-4-3 将A区分为四类的情况A区7,8,9,16,30,32,3334,35,3637,45,4647,486,31,38,39,40,6110,11,1213,14,1521,22,2324,25,26 27,28,29 1,2,3,4,1720,31,384144,5455,59,62,915,49,50,51,52,5356,57,58,60,92图3-4-4 将A区分为五类的情况3.4.3 人为减小选址的范围由于选址范围过大，导致编程很难实现，就难以做到很精确的选址。我们采取人为的方法对选址范围进行了调整。调整方法具体如下：（1）从地图上很容易发现有些点距离已有的交巡警服务平台很近，这些点我们就认为是归原有的交巡警服务平台管辖，所以把这些点从选址范围内排除掉。我们给予的条件是把那些和已有的服务平台最短路径小于1.5千米的节点都排除掉，即如果第j个节点到原有的第i个服务平台的距离：就把对应第j个节点排除掉，这样就减小了选址范围。（2）在地图上还可以找到一些处于出口位置的节点，如果在这些节点设置成服务平台的话，周围的节点太少，这样其工作量就很低，不符合实际要求，因此我们同样把这些点也排除掉。经过以上重重筛选后，选址范围大大减少了，选址也变的容易了。3.4.4 新增服务平台的0-1整数规划选址经过上述聚类分析和人为减小选址范围的情况下，我们就可以建立选址模型，对目标进行优化。我们增加交巡警服务平台的主要目的，是为了解决各个交巡警服务平台工作量不均衡和有些地方出警时间过长的实际存在的问题。这是一个多目标优化问题，解决起来不是很方便，因此我们把其中一个目的作为目标函数，把另一个目的作为约束条件，这样就把复杂的多目标优化选址问题转化为简单的单目标优化选址问题。(1)目标函数的确定我们把工作量尽量均衡作为目标函数，首先考虑到影响工作量的因数既有所管辖范围内每条线路的长度，也有每条线路对应节点发案率的大小，这两个因素都与工作量成正相关关系。我们这两个因素的乘积作为每条线路的工作量。即第i个节点到第j个服务平台的工作量大小可以用公式表示如下（其中表示第i个节点的发案率）：对于第j个服务平台的总工作量可以表示为在它管辖范围之内的工作量之和：公式如下： 为了尽量使各个服务平台的总工作量均衡，我们可以用方差表示目标函数，方差越小，说明各个服务平台的总工作量越均衡。方差可以如下表示：这样就可以确定目标函数了。(2)另一个目标变为约束条件 对于另一个目标是使各个平台出警时间尽量短，我们把出警时间作为一个约束条件，对于每一个平台到其每一个管辖节点的出警时间都应该在4分钟之内，也就是转成路程的话就是在4千米之内即：这样就成功的把多目标问题转化成了单目标优化问题。(3)建立0-1规划进行求解 在对各种情况分类分好以后，设在每个选址范围内共有n个点供选择，其中k个点是原有的服务平台，我们需要从余下的n-k个点中选取一个点使目标函数最优。建立0-1规划如下：根据以上目标函数和约束条件可以用lingo软件编程（程序见附录）求得结果（见附录）。最后对选择的2,3,4,5个地址分别运行程序，最终求得在选择四个新服务平台的情况下，目标已经很优化了。下面是我们所选择的这四个服务平台所对应的节点的序号和坐标如表：新选服务平台的位置29396087坐标(246,337)(371,333)(369,388)(448,381)表3-4-1 新选交巡警服务平台的位置我们把所选择的新的服务平台标在地图中如下：注：(1)大的五角星代表新选的服务平台。(2)小的星号代表各个交通路口节点。图3-4-5 新选择的服务平台四六区服务平台的综合评价和围堵问题4.1 符号说明4.2 基于模糊综合评价对全市六区服务平台设置的评价4.2.1 问题分析能够反应交巡警服务平台设置是否合理的指标有很多，我们根据实际情况选择了其中四个指标对其进行评价，这四个指标分别为在管辖范围内距离服务平台小于3千米的节点占总节点的比例；在管辖范围内所有节点距离服务平台的最长距离；在管辖范围内的人口密度与服务平台密度的比例；在管辖范围内节点综合的发案率。首先根据题目中给的数据我们可以编程求得这些指标对应的值，然后我们根据各个指标的重要性人为的对这些指标赋予不同的权重，最后用模糊综合评价的方法对六个区域服务平台设置方案进行了各自评价和综合评价。根据评价的结果可以发现有些地区的平台设置方案明显不合理，但是对整个区域进行调整很难，也不是很经济，所以我们依据最小割集，连通度，最小点覆盖等方法依次举例，对不合理的服务平台设置进行了调整。4.2.2 各个评价指标的计算按照问题一中的解题思路，我们以同样的方法可以对六个区域对管辖范围都进行合理的分配，并用matlab软件编程可以实现目的，最后求得各指标。(1) 距离服务平台小于3千米的节点占总节点的比例的计算由定义可知：第一指标公式如下： 用matlab软件进行编程（程序见附录）可求得结果如下表：区域ABCDEF0.93480.91780.69480.76920.67960.6296表4-2-1 各区域指标一的计算结果(2) 所有节点距离服务平台的最长距离的计算公式如下： 同样用matlab软件编程（程序见附录）可求得结果如下表：区域ABCDEF27.686413.399136.089830.863941.248938.8427表4-2-2 各区域指标二的计算结果(3) 人口密度与服务平台密度的比例的计算人口密度的计算公式是该区域的总人口与该区域总占地面积的比例，公式如下： 服务平台密度计算公式是总得服务平台的个数与总占地面积的比列，公式如下：所以该指标最终计算公式如下：代入数据求得结果如下表：区域ABCDEF32.6252.8828.1115.0674.818表4-2-3 各地区指标三的计算结果(4)节点综合发案率的计算针对第四种指标的计算我们做了这样的假设，我们把某路口的发案率和该路口附近地区的发案率都归结到该路口处，以下图为例，说明一下我们的计算方法:1234图4-2-1图中四个圆为四个路口且第三路口只和这三个圆直接相连，每两个圆之间的线段为三条道路，它们的长度分别用，来表示，第个节点的发案率用来表示，为了方便计算，我们把所有线段上的发案率都归结到一个点上，这样第三个节点的平均发案率我们可以这样计算： 根据以上表达式，将数据代入并编程求得结果如下：区域ABCDEF472812312722081表4-2-4 各地区指标四的求解结果4.2.3 基于上述四个指标对服务平台设置的模糊综合评价(1) 各指标的正规化处理 由于在以上求出的各个评价指标的量纲不一样，因此在这里我们对各指标进行了正规划处理，公式如下：由matlab编程（程序见附录）计算结果如下表：区域ABCDEF指标一10.940.210.460.160指标二0.2410.070.1600.03指标三0.0700.0510.450.4指标四0.5410.120.1100.25表4-2-5（2）综合评价的评价矩阵的确定这些量纲化后的值就可以作为单因素评价的评价结果，例如A区单因素评价后的结果为：由此可得综合评价的评价矩阵为：R=（3）综合评价权重的确定由于A为市区，所以占得比重应该很大，其它的五个区域相对较少，所以平均可以进行平均分配，这样就可以得到评价的权重如下：W=0.5 0.1 0.1 0.1 0.1 0.1（4）进行综合评价通过权重矩阵W和评价矩阵R的模糊变换得到模糊评判集S的公式如下：其中为模糊合成算子，在四种模糊合成算子中，我们选择的是算子，因为该算子综合程度比较强，利用信息比较全，属于加权平均型的。由上述算子求出了集合如下：S=0.68 0.25 0.23 0.42最后通过对模糊评判向量S的分析作出综合评论，我们这里采用的是加权平均原则，可表示为：其中k为待定系数（k=1或k=2），目的使控制较大的所起的作用。如对S=（0.68 0.25 0.23 0.42），评价等级集合为V=很好，一般，较差，差，各等级赋值分别为4,3,2,1，仿照普通加权法的计算公式，有即该市交巡警服务平台巡逻的情况综合评价结果为较差，有许多需要解决的地方。4.2.4 基于最小顶点覆盖定理对市区进行局部优化由上述评价结果可以发现，该市区的交巡警分布平台布置并不是很合理，尤其是地图上有些局部的服务平台的设置很不合理。我们选取该地图上的一部分为例，利用最小顶点覆盖定理对其进行了局部优化。最小顶点覆盖是指一个顶点能够覆盖的范围越广越好，我们利用这个思想，认为与一个顶点连接的路线的数目越多越好，选择这样的点作为服务平台的话，可以使该服务平台在三分钟之内可以到达的节点个数增加，但是同时我们又要考虑到发案率的问题，如果覆盖太多路线的话，其总体发案率也会提高，这样无形的增加了服务平台的工作量。我们选取了C区中的局部地图如下：图4.2.4从图4.2.4可以很明显看出，显然画上圈的那个交巡警服务平台设置的不合理，因为该点只与一条线路相连接，其覆盖线段的数目太少了。如果我们将其移动到和它间隔一个节点的另外一个节点上的话，这样该覆盖中心就与三条线路相连接了，显然可以增加能在三分钟之内到达的节点的个数。这样借助最小顶点覆盖问题的思想，我们对图中某些不合理的地方进行的局部的优化和改进，方法很机动和方便。4.3 调度全市警力资源对嫌疑犯进行围堵的最佳方案4.3.1问题分析 对于此题，我们假设交巡警在搜捕之前已经对目击者进行了询问，能够确定嫌疑人的相貌，体型，和车的牌照和颜色，这样，巡警就只要堵住关键的路口节点，根据具体情况把嫌疑犯的活动限制在少数的几个城区内，实现快速搜捕。由于交巡警是案发后3分钟才接到报警，所以首先要确定嫌疑犯在3分钟的的活动范围。但这里我们要考虑一个问题，就是嫌疑犯能否在3分钟之内逃离A区，这就要我们对嫌疑犯的驾车速度进行讨论，如果他的驾车速度不过于快，在报案前未能逃离A区，就只要调动A区的交巡警可以先堵住出入A城区的入口，然后根据嫌疑犯所有可能的逃跑路线运用不断减小包围圈的地毯式搜捕方法对嫌疑犯进行搜捕。但如果嫌疑犯的驾车速度很快，3分钟后能够逃离A区，根据嫌疑犯的作案地点，在考虑他的驾车速度符合常理的情况下，比如和警车的速度一样，那么根据下面的计算，可以知道嫌疑犯最多只能活动在A城区和C城区，这就需要动用这几个区的警力进行搜捕，方案也比前面所说的复杂的多，因为这是嫌疑犯的逃跑路线非常的多，但各区的交巡警只要确定包围圈，然后不断减小这个包围圈，就能达到目的，搜捕到嫌疑人。下面就是我们根据嫌疑犯是否能够逃离A区制定的围堵方案。4.3.2 嫌疑犯未能逃离A区 发生重大刑事案件的地点位于第32节点上，根据分析A城区的交通网络图，通过第一题已经编号的程序可以求出这个节点与16节点城区出入口和30节点附近的7节点交巡警平台的距离，分别为1.14km和3.31km。所以当嫌疑犯的驾车速度小于22.8km/h时，嫌疑犯无法逃离A区，由于这个速度值比较小，不是很符合实际，只要嫌疑犯以正常的驾车速度逃离，并且熟悉城区的地形，他就能逃离A区，所以我们在这里简单地讨论一下嫌疑犯被困在A区内时的搜捕方案。Stept1接到报案后迅速从最近的服务平台派出一部分警力封锁城区出入口。Stept2同时确定在3分钟内嫌疑犯能够逃离的范围。Stept3根据嫌疑犯所有可能的逃离方向，所有可能到达的节点，从最近的服务平台派出警力进行围堵。Stept4不断缩小搜捕范围，直到嫌疑人被捕。 以上就是交巡警搜捕嫌疑犯的总体方案，在这种情况下就不具体计算了。下面我们主要要研究的就是嫌疑犯能够逃离A城区，动用全市警力，对其所有可能藏身的城区进行快速搜捕的最佳方案。4.3.3嫌疑犯能够逃离A城区我们知道，嫌疑犯只要驾车速度超过22.8km/h就能够逃离A城区，在这里，我们不妨先假设嫌疑犯的驾车速度和警车时速一样为60km/h。所以3分钟内，嫌疑犯能够逃跑的距离为3km，通过分析附图一中A城区的交通路线图，得出嫌疑犯有可能逃离A区经过的所有出入口，通过观察与计算，并运用前面得出的公式，可得p点与这些节点的距离：所以嫌疑犯能够在3分钟之内从16和48节点逃离A区，我们假设各交巡警服务平台能够行动及时，将城区出入口这些关键节点给封锁，所以我们只要考虑在A城区和C城区进行搜捕即可。(1)具体逮捕方案一、犯罪嫌疑人想尽快逃出市区，可以从在3分钟内经过服务台或没有服务台的的地 方逃走，经计算3分钟内经过的服务台为7,8,9服务台。此时可能从38,28,29,30,48等出入A区的路口逃走，但是经计算d(16,38)d(32,38)-3d(15,28)d(32,28)-3d(15,29)3d(48,235)+ d(48,32)3由此可知在去往C区的路上警察已开始行动。三、由d(173,235) d(30,237)+ d(30,32)-3得，嫌疑犯从30点逃到C区，但由于他到达237点时，236点已被173点占据，所以只能另去别处。四、从长远目标看摆在眼前有两条路，一条须经过239点，另一条需经过247到246点，但很显然第二条路行不通，因为d(173,246)d(246,247)+d(247,237)所以只能去239点。五、表面上到了239有三条道，但239-29点这条道已被15点服务台封锁，而且d(239,240)d(237,240)+d(237,32)-3所以只能选择248目标点。六、经计算d(248,167)d(237,248)所以只能被逮捕。(2) 结果分析下面是嫌疑犯最优逃跑路线：目标序号123456嫌疑犯所经过的点32730237238239表5-4-1 最优逃跑路线最优交巡警服务调配方案;（1） 第一时间把市区一些路口封锁，具体分配如下表：交通警服务台32415716封锁的路口55406028,2930,4838表5-4-2 分配方案（2） 对C区第一时间一些路口封锁，下表是各服务台需要去封锁的路口：交巡警服务台173169167封锁的路口235,245,246240248表5-4-3（3） 如此之后对所限制的路线进行地毯式全面搜索A区和C区。第一步：对A区虚线以上部分进行搜索图5.4.2注：虚线以上区域就是A区交巡警搜捕的范围第二步：对C区虚线一下部分进行搜索图5.4.3注：虚线以下的区域就是C区交巡警的搜捕范围五.模型的评价与改进5.1 我们建立的模型和方案的优点：（1）在解决第一问分配各服务平台管辖范围时，我们考虑的比较全面，把每个节点分配到里各自最近的平台后，还分析了几种特殊情况，比如我们分配好各节点的“归宿”后又考虑了当一条街道的两各节点不归同一个平台管辖时，怎么分配这条街道；还有当一条街道过长或者一条街道的两个节点就是交巡警服务平台时，怎么合理得将这条街道分配给两个服务平台管辖。（2）在得出结果后，我们还对其做了合理度分析