数学建模比赛论文交巡警服务平台的设置与调度

《数学建模比赛论文交巡警服务平台的设置与调度》由会员分享，可在线阅读，更多相关《数学建模比赛论文交巡警服务平台的设置与调度（53页珍藏版）》请在装配图网上搜索。

1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置

2、报名号的话）： B1609 所属学校（请填写完整的全名）： 福州大学 参赛队员 (打印并签名) ：1. 郑榕新 2. 赖春燕 3. 叶鎏芳 指导教师或指导教师组负责人 (打印并签名)： 竺吴辉 日期： 2011 年 09 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要本文讨论城市交巡警服务平台的最优化设置与调度问题。问题

3、一中，通过floyd算法可得到任意两个交通口节点间的最短路径。然后考虑每个节点到服务平台的距离，节点受离它最近的服务平台进行管辖。当遇到突发事件时，为了最快地将A区进行封锁，即要求所有节点完全封锁的时间要最小，因此，构造了0-1规划整数模型，利用Lingo进行求解，得到最佳的调度方案。由于A区存在工作量分配不均的情形，因此本文引入了居民满意度以及交巡警的幸福感指数作为本文的参考因素，利用民众的满意度首先筛选出40个节点，然后利用交巡警的幸福感指数的变化情况，确定出的新增平台数以及具体的节点。 问题二中，考虑到各个区的具体情形各不相同，因此本文按照问题一中的方式来考虑各个区域，计算出各个区域的幸

4、福感指数以及相应的方差，再综合人口、面积和总的案发率等因素，进行综合分析，并对某些地区的不合理情况给予了相应的建议与改进方案。针对最后一问的围堵问题，本文结合floyd算法、DFS算法和SPFA算法给出了一种最佳围堵方案，在本文的基本前提下，且当罪犯的逃逸速度与交巡警的速度相等时，本文得出至多38.998分钟，可将罪犯围堵。关键字：0-1整数规划 Floyd SPFA DFS 幸福感指数 满意度一、 问题重述与背景分析1.1问题重述： “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职责，是城市安全与和谐的象征。交警巡逻，对违法分子起威慑作用降低发

5、案率，同时缩短接警出警时间，关系人民切身的生命财产安全，是城市安全和谐发展的重要保障。为更加有效地贯彻实施警察职能，特在市区交通要道及重要部位设置交巡警服务平台。由于警务资源有限，合理设置交巡警服务平台、分配平台管辖范围、调度警务资源成为警务部门面临的重要课题。现在就某市设置交巡警服务平台的相关情况，建立数学模型研究下列问题：(1)根据该市中心城区A的交通网络及现有的20个交巡警服务平台设置情况，为各服务平台分配管辖范围，尽量使其管辖范围内出现突发事件时能在3分钟内到达。（警车时速为60km/h）(2)出现重大突发事件，实现对20个交巡警服务平台的警力资源调度，完成对进出该区的13条交通要道的

6、快速全封锁。（一个平台的警力最多封锁一个路口）(3)根据现有交巡警服务平台工作量不均衡、各别平台出警时间过长的实际情况，确定该区需要增加的平台个数和位置。（增加25个平台）(4)针对全市具体情况，参照设置交巡警服务平台原则和任务，研究该市现有平台设置方案的合理性。对不合理的地方，提出解决方案。(5)该市地点P(第32节点)发生重大刑事案件，案发3分钟后接到报案，犯罪嫌疑人已驾车逃逸。提出调度全市交巡警服务台警力资源的最佳围堵方案，快速搜捕嫌疑人。1.2问题分析分析一：此问题为最短路程优化问题，采用Floyd算法求解。本文对管辖范围的划分包括A区的所有节点与路段，分别从节点归属，路段归属两个方面

7、进行管辖范围分配。每个节点可以找到与之最近的服务台并受其管辖，每条路段的归属问题有两种情况。其一，路段两段的两个节点受同一警点管辖，则该路段也属该交巡警服务平台管辖；其二，路段两段的两个节点分别受不同服务平台的管辖，则该路段需要分段管理，考虑用定比分点进行分段。分析二：此问题为0-1整数规划问题，应用Lingo解决。对20个平台警力调度封锁13个交通要道，约束条件有以下两点：1、确保13个交通要道必须都有一个或一个以上警力封锁2、为了节约资源，每个交巡警平台不一定要出警。在约束条件下，使最迟到达路口的警力所耗时最小，即封锁时间最短。在13个交通要道被最快封锁后，可考虑从交通复杂度、交巡警工作量

8、、封锁力度等方面，对剩余7个平台警力做出补充部署调度。分析三：要增设交巡警服务平台，需要确定所增设交巡警服务平台的具体位子和个数，在考虑在何路口建立时，根据每个交巡警服务平台的工作量为依据，而在考虑要建几个服务平台时，主要考虑多增加平台对评价指标的影响大还是小。 分析四：若选取全市范围内路口和交巡警平台作为研究对象，这样计算量大，很可能无法得出结果，因此采用分区域的模型。对于是否合理的判断，通过对每个平台平均服务人数、交巡警平台每天接案子的平均数量、每个平台平均服务的面积、城区每个交巡警服务平台的平均幸福感指数以及幸福感指数的方差这些因子。通过对这些因子的数值的比较，得出是否合理的结论。 分析

9、五：p点处嫌犯要逃离，采用中心转移的方法简化，使得嫌犯车与警车同时出发。在此应用了DFS深度优先搜索算法,确定在三分钟内疑犯可能到达的节点，通过SPFA算法可以求出到达一个交巡警平台的最短路径，以达到平台最短路径的节点为研究对象，若在它与平台之间还有节点满足：中间节点到它的距离小于最短路径的一半时，将改点转移，如何找不到改点的话那么久原地待命。二、符号说明：连通图中节点的总数；：连通图中边的总数；：第个节点与第个节点的直接连通距离；：警车及犯罪嫌疑人的逃逸速度；：第个交通路口节点到第个交通路口节点的最短距离；：第个交通路口节点；：交巡警服务平台可以出警到第个交通路口节点的最短距离；：0-1整数

10、规划中的方案矩阵；：方案矩阵中的第i行，第j列的元素；：第个交通路口节点的发案率；：第个交通路口节点的满意度；：两点间最短路径的源点；：第个单源最短路径三、模型假设1.假设该市所有道路都是直线，并且畅通无阻，在执勤过程中警车车速不变。2.假设在同一时间内，每个交巡警服务平台管辖范围内只出现一件案件。3.假设在同一城区中，人口是均匀分布的。4.假设无重大事件发生时，六个城区的交巡警服务平台不得跨区工作。5.假设交巡警服务平台的工作人员以及罪犯都是理性人，且所获得的信息都对称的。四、A区交巡警服务平台的设置、分配和调度4.1 确定20个交巡警平台的管辖范围4.1.1 模型分析Floyd算法又称为弗

11、洛伊德算法，是一种用于寻找给定的离散点间最短路径的算法。它的基本思想是：对一个路口而言，i到 j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1,2,3,n（n为路口的数目），再检查dij与dik+dkj的值；dik与dkj分别是目前为止所知道的i到k与k到j的最短距离，因此dik+dkj为i到j经过k的最短距离。所以，若有dij>dik+dkj，表示从i出发经过k再到j的距离比原来的i到j距离短，则把i到j的dij重写为dik+dkj，每查完一个k值，dij就是目前的i到j的最短距离。重复这一过程，最后当查完所有k时，dij里面存放的就是i到j之间的最短距离。

12、就“A区的交巡警分配管辖范围问题”而言，A区共有交通路口节点92个，交巡警服务平台20个。由于每一个交巡警服务平台在A区的分布是固定的，因此，问题转化为求每一个交巡警服务台到每一个交通路口节点的最短出警时间。由假设可知，警车的速度是确定的，那么问题可以转化为每一个交巡警服务台到每一个交通路口节点的最短距离。从而，划分出每一个交巡警服务台的管辖区域。因每一个交巡警服务台设在交通路口节点处，故可以先根据题目所给数据算出任意两个交通路口节点间的最短距离，然后针对一个特定的路口节点对20个交巡警服务台所在节点进行遍历，若取到该节点由其中一个服务台出警的最短距离，则该节点由此服务台管辖。这样即可划分出每

13、一个交巡警服务台对所有节点的管辖区域。分段算法。虽然题目只提供各道路节点的案发率，然而实际情况中，案件完全有可能在路段上发生。因此，交巡警平台除了对A区所有路口节点进行管辖范围划分外，还将对A区所有路段进行管辖范围划分。对完全路段，即路段和端点属于同一交巡警服务台管辖的路段，此路段也归此平台管辖。对不完全路段，采用分而治之的思想，即路段端点属于不同的两个交巡警服务台管辖的路段，将对该路段进行分割管理。因此在具体的求解划分管辖范围时，采用以路口为主，路段为辅的区域规划方法。4.1.2 模型的建立与求解确定交巡警服务平台对节点的管辖范围中，设为交巡警服务平台，为路口节点。首先，若有边将它们直接相连

14、，它们之间的最短距离就等于几何距离，即。接着，若交巡警服务平台与节点之间没有边将它们直接相连，对这些点进行预处理，让它们的初始值为一个无穷大的数，对任意的i均满足，即每一个交通路口节点到达它们本身的最短距离为0。对给定的任意交巡警服务平台和路口节点，枚举它们之间的节点，使和是通过中间节点连通的， 且满足关系式：。根据上述Floyd算法以及题目所给A区路口节点的坐标值数据，编写C+程序（见附录1），得到以下结论： 表4-1：A区中交巡警平台所管辖范围A区交巡警服务平台编号管辖区域内节点编号A区交巡警服务平台编号管辖区域内节点编号11，67，68，69，71，73，74，75，76，781111，

15、26，2722，39，40，43，44，70，721212,2533，54，55，65，661313,21,22,23,2444，57，60，62，63，64141455，49，50，51，52，53，56，58，591515,28,29661616,36,37,3877，30，32，47，48，611717,41,4288，33，461818,80,81,82,8399，31，34，35，451919,77,7910102020,84,85,86,87,88,89,90,91,92确定交巡警服务平台对路段的管辖范围中，路段可分为两类。设路段中，表示节点在交巡警服务台的管辖范围内，表示节点在交

16、巡警服务台的管辖范围内。如图所示，若与相同（图4-1），则路段显然也归服务台亦即管辖；若与不相同（图4-2），即路段两端归属于不同服务台，则将路段进行分段划分。图4-1 图4-2采用路段划分的方法可以解决某路段无人管辖的问题。假设为交巡警服务平台到它所管辖的路口之间的距离，同样地为交巡警服务平台到它所管辖的路口之间的距离，为路口与路口之间的距离，两个路口的分点记为，为满足两个交巡警服务平台到分点的距离相等，则分点到其中一个平台的距离应为。通过定比分点的公式： 其中 （1）那么，路段管辖的分界点点的坐标可以求出。以点为界，靠近的路段归平台管辖，靠近的路段归平台管辖。根据以上算法求解得A区交巡警服

17、务台对该区所有路段的管辖范围。综合第一步对管辖范围的划分，得到最终结果（表4-2），示意图如（图4-3）所示：表4-2：各个交巡警平台所管辖的范围交巡警服务台编号交巡警服务台管辖范围1管辖节点编号1676869717374757678管辖区间V67->(398.72,361.28); V67->(399.09,355.45); V69->(408.33,350.83); V71->(417.90,347.14); V73->(418.57,348.00); V73->(424.39,358.06); V74->(421.54,364.85); V76-

18、>(395.27,366.50); V76->(399.39,363.19); V76->(405.66,368.33); V78->(411.62,368.03); V78->(418.07,366.14); 2管辖节点编号2394043447072管辖区间V44->(393.03,346.46); V39->(371.96,337.29); V40->(392.31,331.15); V39->(368.86,333.06); V39->(371.00,332.88); V43->(415.92,343.61); V44-&

19、gt;(399.09,355.45); V70->(408.33,350.83); V72->(417.90,347.14); V72->(418.57,348.00); 20管辖节点编号20848586878889909192管辖区间V92->(437.30,353.40); V85->(410.98,386.59); V90->(439.76,378.33); V84->(437.29,383.41); 注：（） 路段两端节点属同一交巡警服务台管辖的线段也归该服务台管辖。（） 交巡警服务台在3分钟内无法赶到的区域共6个，标注为蓝色，分别为39,61

20、,28,29,38,92节点。图4-3：1号交巡警服务平台管辖范围示意图4.2确定对13个交通要道封锁的调度方案4.2.1 模型分析以交巡警平台为研究对象，其到一个固定的节点是否出警存在简单的是否关系。因此，利用0-1整数规划模型，将实际问题数字化处理，便于分析。运用0-1整数规划模型，用矩阵形式表示某一种调度方案。根据题目给出的条件设定相应的设置条件，然后利用LINGO获得最优的快速封锁方案。4.2.2 模型建立与求解由题意可知，一个交巡警的服务平台智能控制一个交通要点，但一个路口不一定只去一个平台的警力。不妨记，其中 （4-2-1） 有条件可知，每个路口必须有一个交巡警服务台负责，因此可得

21、。又因为，警力是否出动是根据情况而定（而非必须出动），故有式子。不妨记时间矩阵，其中表示第个服务平台到达第个路口所花的时间。又因为本文的目是时考虑最晚一个到达交通要道的时间间隔作为该问题的目标。综上所述，可得式（4-2-2）： （4-2-2）最后，运用Lingo（Lingo程序详见附录2）求解可得方案矩阵。根据所得到结果，对其数据进行研究可以发现，其快速封锁13个交通要道的限制条件为警点7 节点9的时间：8.015(min)该最优方案矩阵表示含义如下：警点标号前往路口标号时间（min）警点标号前往路口标号时间（min）1>134.88522 11>73.80527 2>136

22、.03507 12>56.88254 3>116.09384 13>65.00000 4>114.86098 14>43.26497 5>103.18993 15>84.75184 6>122.50641 16>26.74166 7>98.01546 17>137.82052 8>123.09947 18>136.73436 9>31.53254 19>135.03371 10>17.58656 20>136.44888 注：1.灰色图像为最快到达每个交通要道的警点线路。2.警点7至节点9为封

23、锁此13个路口时间的限制条件。对上表数据进行研究分析，可以得出结论： 由于警点7 节点9的时间8.015(min)为快速封锁13个交通要道的限制时间，因此这个方案剩下的点要如何调动都不会影响最终的结论。快速封锁13个要道的所需的最短时间都是8.01546分钟。4.2.3 模型优化由于13个交通要口地段的不同，其交通复杂情况的差异将直接影响警察的工作质量。例如一个交通要口若有多条路段与其连接，以十字路口为例，抓捕对象很可能从任意路段进入该入口，而警力很难同时监控4个方向，于是我们考虑对这类复杂度高的交通要道增补警力。可增补警力的交通要道为：11,12,13 图4-4：A区各节点标注示意图观察地图

24、发现，11,13节点为岔口地段，交通较复杂，且13节点为出入该A区的进出口，12节点交通较为简单。考虑避免警力资源浪费，12节点没有必要增加警力。由此决定，为11节点增加1个警力点，为13节点增加2个能尽快到达的警力点。结合上述图标，得出最后方案（需要出警的警点标号）：1,4,5,6,7,9,10,11,12,13,14,15,16，3,19,2,；这16个交巡警服务平台的出警路线按最优方案矩阵图表所示。4.3幸福感指数模型4.3.1模型的分析在A区内总共有92个节点，其中有20个节点已建立了交巡警服务平台，剩下的72个节点都有可能作为增设的交巡警服务平台，对于在哪增设交巡警服务平台的问题，本

25、文提出“满意度”这个概念作为辅助的筛选原则，此处所定义的“满意度”是考虑群众对各个交巡警服务平台的执勤情况的评价，主要是依据案发率和出勤时间长度，因此将满意度的定义为。考虑到每个交巡警服务平台的负荷率，也就是当一个交巡警服务平台管辖的范围越广，且管辖区域的案发率越高，就会导致这个交巡警平台出警次数多，工作量大，同时也会影响到工作效率，这样就会造成各个交巡警服务平台工作的分配不均，因此需要增设平台来权衡各个交巡警服务平台的工作负荷。就如何增加平台的问题上，需要提出一个标准来衡量当平台的位置增设在何处以及增加多少个平台时达到最佳的方案，而不是增设到上限值为最佳，否则，虽然在工作量上对每个平台都会减

26、轻，但是就经济和效率等角度上来说却造成不必要的浪费。对于检验平台增设的个数这个问题，引入一个“幸福感指数”的概念，所谓的幸福感指数即为交巡警在工作时的愉悦程度。本题中有两个决定因子分别是：管辖的范围和节点的案发率，而幸福感指数都与这两个因子呈负相关，并且在原则上“幸福感指数”需要满足：a) 每个交巡警平台的幸福感指数要尽可能的大。b) 其次每个交巡警平台的“幸福感指数”的方差要尽量的小，这样才能起到权衡各个交巡警服务平台的工作负荷度的功能。4.3.2模型的建立首先，通过“满意度”公式即，对剩余未建交巡警服务平台的交通路口节点进行群众的满意度计算，将得到的结果进行升序排列，根据满意度排名情况筛选

27、出前40个满意度较低的交通路口节点，如下表所示：未设交巡警服务平台路口的满意度（表 4-3）节点满意度节点满意度290.000125570.000669280.000162660.000679390.000194630.000693380.000245910.000695210.000264760.000708310.000304420.000725400.000307590.000731920.000347430.000735250.000349890.000753240.000381270.000761580.000395670.000772610.000398720.000778470.

28、000488220.000789540.000489550.00079480.000554710.000797320.000585300.000817530.00061600.000821870.000621230.000833640.000646410.00084450.000652820.000842在计算幸福感指数之前，需要先计算各交通路口节点的发案率平均值1.16，以及距离标准3000m（题设要求要尽可能在3min之内所能到达的最远距离）来定义幸福感指数： （4-3-1）增加交巡警服务平台各方案与幸福感的关系表（表4-4）增加平台数增加节点编号平均幸福感幸福感方差256 661.189

29、8890.609484339 56 661.3213690.563345429 58 66 921.4276550.497468530 39 56 66 731.4509420.487822由上表，我们得出增加2至5个交巡警服务平台的具体方案，与之对应的平均幸福感指数以及幸福感方差。表中得出的数据结果是：随着节点数的增加，平均幸福感指数增加，而幸福感方差减少，也是很符合实际情况的。根据最大边际效应的原理，当增加交巡警服务平台的个数由3个增加到4个时，平均幸福感指数增加为0.106286，幸福感方差减少0.065877，针对于平均幸福感指数而言他的增幅是最大的，幸福感方差的减幅也是最大的；但是当

30、平台数继续增加到第五个时，幸福感指数的增幅就仅仅0.023287，幸福感方差的减幅为0.009646，出于对增设平台需要耗费大量的资金、人力、物力的方面的考虑，认为无再增设第五个交巡警服务平台的必要。五全市范围交巡警服务平台设置、分配和调度5.1.分区优化模型5.1.1模型分析：研究该市交巡警服务平台的设置方案的合理性时，主要考虑的原则有：（1）每个交巡警服务平台的工作量要均衡；（2）每个交巡警服务平台的幸福感指数要尽可能的高，并且相差不要太大。由于考虑到全市范围内的交通网络的节点数有580多个，在数据处理的复杂度上的要求变的更高，不能够在选用复杂度为的Floyd算法，同时，除了节点数数目庞大

31、之外，交通网络的路径图也变的很复杂，在程序运行上的出错率高，因此，此处引入了SPFA算法来对各个区域进行合理性评价。全市有6个城区构成，通过分析6个城区中每个交巡警服务平台的平均服务人数、交巡警平台每天接案子的平均数量、每个平台平均服务的面积、城区每个交巡警服务平台的平均幸福感指数以及幸福感指数的方差，来比较6个城区各个指标的波动性，最后确定出交巡警服务平台配置不合理的城区，并对其进行优化。在本题中对于计算每个交巡警平台的工作量时，不在采用第一个模型中的Floyd算法，引入了SPFA算法。SPFA算法与Floyd算法相比，SPFA算法解决问题的复杂度为（其中，n为节点数目，m为边数，k为一个远

32、远小于n的常数），因此，对于像此题这样边数较少的稀疏图而言，SPFA算法可以表现出强大的优势，大大地减小在算法实现上的复杂度，特别是当图的规模大，用邻接矩阵存不下的时候，用SPFA则可以较方便地给出节点间的临接表。对于求最短路径的问题，有时候单单只求出其最短路径的长度的意义不大，只有知道具体的路径才能真正的解决问题，而SPFA同时也可以解决这个问题而Floyd算法却无法得出。SPFA是一种单源最短路径算法，所以以下所说的“某点的最短路径长度”，指的是“某点到源点的最短路径长度”。我们记源点为S，由源点到达点的“当前最短路径”为，开始时将所有初始化为无穷大，则初始化为0。算法所要做的，就是在运行

33、过程中，不断尝试减小b数组的元素，最终将其中每一个元素减小到实际的最短路径。过程中，我们要维护一个队列，开始时将源点置于队首，然后反复进行松弛操作，直到队列为空： (1)从队首取出一个结点u，扫描所有由u结点可以一步到达的结点，具体的扫描过程，随存储方式的不同而不同； (2)一旦发现有这样一个结点，记为v，满足，则将的值减小到和相等。其中，为图中的边u-v的长度，由于u-v必相邻，所以这个长度一定已知（不然我们得到的也不叫一个完整的图）；这种操作叫做松弛。5.1.2模型的建立 要分析该市现有交巡警服务平台设置方案的合理性，通过引入每个平台平均服务人数、交巡警平台每天接案子的平均数量、每个平台平

34、均服务的面积、城区每个交巡警服务平台的平均幸福感指数以及幸福感指数的方差这五个因子，对这五个因子的数值进行分析，并判断合理性。其中每个平台平均服务人数定义为，其中，m为平台平均服务人数，g为人口总数，q为交巡警服务平台数；交巡警平台每天接案子的平均数量,n为交巡警服务平台管辖区域内的所有节点总数；每个平台平均服务的面积，其中S为该区域内的区域总面积；城区每个交巡警服务平台的幸福感指数在上文已经给出, 幸福感指数的方差，通过对每个城区的计算，得到以下这张表格（表5-1）。各城区各项指标（表5-1）全市六个城区每个平台平均服务人数（万）交巡警平台每天接案子的平均数量每个平台平均服务的面积幸福指数幸

35、福指数的方差A36.251.10.870480.7303B2.6258.2512.8750.7232320.336815C2.88235294111130.42970.282633D8.1111111117.55555555642.555555560.5130120.179615E5.0666666677.93333333328.80.4203980.219176F4.8181818189.90909090924.909090910.3250830.0699从上表中，可以看出该市存在服务平台设置不合理的情形，从全市的各个城区的数据不难发现，发案率与交巡警平台数目基本上是呈正相关，这点符合常理（

36、除了A点）。从上表中也不难发现A区交巡警的幸福指数比较高，这是因为A区设置了比较多的交巡警服务平台，但从总的发案率来看A区其实并没有那么多的案件。C区由于区域面积比较大，而且犯案次数比较多，所以可以适当地增加交巡警服务平台。D、E、F三个区得情况类似，面积比较大，而服务平台相对较少。分析上表总结如下：1. A区的平台设置点过多，可以适当撤掉一些交巡警的平台，而且A区存在明显的分布不均匀，同一区不同地段的差异比较大，建议适当得减少平台，并调整几个平台的位置；2. B区得情况较理想，而C、D、E、F四区均可以适当增加平台数，从上表也可以发现，B、C、D、E、F的分布比A区更加合理，各个地段的工作量

37、相差不大。3. 如果B、C、D、E、F增加节点的话，建议B区设在靠西的区域，C区设在北偏东的区域，D区设在与C区的交接面，E区设在中部地区，F则设立在中下区域，优先考虑上述给的几个情况。上述建议主要是考虑到，各地交巡警的工作量不够均衡，以及处理事件的速度等因素。5.2快速封锁模型5.2.1模型分析：假设罪犯的车速为（定值），犯罪嫌疑人与交巡警均为理性人，信息完整对称。所谓理性人就是当在了解当地情形的条件下，不论是罪犯还是警察在任意2点之间都会选择最短路作为自己的行进路线，由于在案发后的三分钟之后交巡警才接到报案，那么在这3分钟之内罪犯可逃离的最远路程为3km，利用模型一中提到的算法，找出与P点

38、相距刚好能大于3的点集（既其上一点到P点的距离小于3 km）。要围堵罪犯，首先必须封锁路口，将罪犯包围在其中。由于它在不同的状态下（既各种路径，这里罪犯能走的路线很多），做下一步决定时都有很多种选择，为了更加快速得围住罪犯，也就是决策者要让罪犯能走的路越来越少，而且调度的警力也要尽量地少。5.2.2模型建立根据上述分析所提供的思想方法，本文构造了一个动态规划的方法最佳围堵方案算法描述：Step1：利用深度优先搜索（DFS）算法，给出3分钟内犯人可到达的最远路口，记作集合。Step2：针对第一步中每一个可能到达的路口，找出20分钟内能到达该点的所有交巡警服务平台。对每一个可能的交巡警服务平台，利

39、用SPFA算法，算出它们可以到达该点的最短路径。Step3：对，根据Step2可以得到到的最短路径，计算，寻找到某个中间节点的距离小于的点，若找的到，那么就求出最远的那个点，将的位置转移到这个点，找不到的话那么就原地待命。Step4：再根据Step1，确定出，由于上述处理过程中的某些平台的点已经转移，因此再利用Step2的过程确定，依此类推。5.2.3模型的求解为了说明上述问题，这里不妨设罪犯的行车速度与交巡警的行车速度一样，根据本文所提出的算法，可以得到如下的最佳围捕方案：表5-2调度方案被调度交巡警位置标号被调至的位置233554605566152916161692401702731712

40、31172243173238 比如第一行的含义就是，原来的交巡警所在的位置2，为了围堵犯人必须将其调度到3的位置，由于算法具有较好的可适应性，也能达到全局最优。根据上述算法可以得知，当犯人从P（32）点出发时，本文的算法选取了12个交巡警服务平台的人员，至多花费38.998分钟，便能将罪犯围捕成功（即将犯人困在某一区域之中），而且主要的时间花在C区，A区得调度比较简单，由于C区道路复杂，为了节约时间须调度5个人才能更快地将罪犯围住。六模型评价与优化 本文中我们引入了“幸福感指数”这一概念作为是否增设交巡警服务平台以及在哪增设交巡警服务平台的依据，就 “幸福感指数”这个指标作为增设平台的依据来说

41、，“幸福感指数”本身就是依据交巡警就自己的工作的评价构造出来的，我们采用“幸福感指数”，不仅在实际上符合衡量一个交巡警服务平台是否增设的必要性，同时“幸福感指数”也给人一种温暖、亲切的感觉。 此外，本文的另一个创新在于对于分析何如能够最迅速的搜捕嫌疑犯，由于犯罪嫌疑人是理性的，因此他每次都会选择走最短的路线，在最小的时间内逃逸，因此这个问题的随机性较大，用Floyd算法或者是其他算法显然是不能够解决此类的动态问题的，而且不管在时间还是空间上的复杂度都是巨大的。但是，我们采用的SPFA算法由于解决的是单源最短路问题，因此，当我们面对的数据总体是庞大的同时，我们只需根据我们的需求，选择两个节点作为

42、源点和目标节点进行求解，这样做的好处在于，我们无需花费大量的时间和空间的资源计算一些对于我们最终结果无用的数据，因此在时间和空间的分配问题的压力上又可以得到一定的释放。另外，因为我们可以更快速更精确的得到我们所需要的数据，因此，在计算机的模拟过程中，出错和由于栈溢出导致的系统崩溃概率大大减小。 由于时间的关系，在建立模型过程中的一些参数的设定中，我们考虑的影响因子不够多，导致参数可能出现偏差，还有待继续改进。每个模型都不是绝对的完美，既然在模型中存在着缺点，我们就现阶段发现的不足对模型进行理论上的优化。首先在增设交巡警服务平台时，通过提出一个“满意度”的概念进行筛选，之所以做这样的筛选，一则是

43、由于时间不够无法将“满意度”的影响因子考虑到最佳，同样地也无法将影响其的参数确定在准确的范围内，毕竟其中包括了些主观因数的存在。再者，我们还人为的筛选满意度比较低得前40名的交通路口节点作为增设交巡警服务平台的范围，在这其中也存在着偏差，需要优化，我们可以在考虑每个路口的路况和人口稠密度来进一步优化满意度因数，使得在筛选的过程中能够尽量的减小误差。七 模型推广 SPFA实际上是Bellman-Ford基础上的优化，是用来解决单源最短路问题的一种算法。显然，此算法在任何层次上都还可以代替BFS广度优先搜索，由于该算法也是在维护一个一维数列的基础上进行的。另外，如果对一个具有n个节点的稀疏图而言，

44、进行一次SPFA算法解决的是单源最短路问题，进行n次SPFA算法，也是可以解决两点间的最短路问题的，而且，显然，它的复杂度要比Floyd算法来的更加的简单，也更容易实现。 八、参考文献1赵静、但琦等，数学建模与数学实验，北京：高等教育出版社，2001.7.2维斯、冯舜玺，数据结构与算法，北京：机械工业出版社，2004.13李明哲、金俊、石端银，图论及其算法，北京：机械工业出版社，2010.104胡运权、郭耀煌，运筹学教程，北京：清华大学出版社，2007.45薛雪、孙伟、刘晓文，露天煤矿车辆的不确定调度模型与优化求解，长沙：中南大学学报，42（5）：58-96，2011.56王金敏、王世宇、王多

45、、李乃华，布局调度问题的聚合算法，天津：天津大学学报，35（4）：112-136，2002.77张保平，犯罪心理学，北京：中国人民公安大学出版社，2003年出版8严明、李文松、车磊，110警车配置及巡逻方案，,2011.99佚名，交巡警平台高科技装备揭秘重庆交通事故赔偿网， 附录一第一问的程序（包括用Floyd算法解决交巡警服务平台管辖范围等问题以及添设2-5个的交巡警服务台的程序）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>/using namespa

46、ce std;double x100,y100,d100100,b100,lv100,tot100,mind=10000,minave,copb100,myd100;int f100100,p150,q150,s100,kou14,n=20,pt26,minp6,cops100,dian100;void duzuobiao() int i; for (i=1;i<=92;i+) scanf("%lf %lf",&xi,&yi); void dulujing() int i,j; for (i=1;i<=92;i+) for (j=1;j<=

47、92;j+) dij=1000000; for (i=1;i<=92;i+) dii=0; for (i=1;i<=140;i+) scanf("%d %d",&pi,&qi); fpiqi=fqipi=1; dpiqi=dqipi=sqrt(xpi-xqi)*(xpi-xqi)+(ypi-yqi)*(ypi-yqi)*100; void floyd() int i,j,k; for (i=1;i<=92;i+) for (k=1;k<=92;k+) for (j=1;j<=92;j+) if (dij>dik+dkj)&

48、amp;&(i!=j)&&(j!=k)&&(k!=i) dij=dji=dik+dkj;void chuli1() int i,j; for(i=1;i<=n;i+) bpti=0; spti=pti; for (j=n+1;j<=92;j+) for (i=1;i<=n;i+) if (bj>dptij)|(bj=0) bj=dptij; sj=pti; void outp1() int i; for (i=21;i<=92;i+) /printf("(%.1lf,%.1lf)->(%.1lf,%.1lf)

49、:%lfn",xsi,ysi,xi,yi,bi); printf("%d->%d:%lfn",si,i,bi); void xunzhao() int i,j; double length,a,x2,y2; for (i=1;i<=91;i+) for (j=i+1;j<=92;j+) if (fij)&&(si!=sj) / printf("b%d=%lf,b%d=%lf;V%d(%.1lf,%.1lf)->",i,bi,j,bj,i,xi,yi); length=(bi+bj+dij)/2; if (

50、length<bi) x2=xj; y2=yj; else if (length<bj) x2=xi; y2=yi; else a=(length-bi)/dij; x2=(1-a)*xi+a*xj; y2=(1-a)*yi+a*yj; / printf("(%lf,%lf):%d;",x2,y2,si);/ printf("(%lf,%lf)->V%d(%.1lf,%.1lf):%d;n",x2,y2,j,xj,yj,sj); printf("%d %d (%lf,%lf) %d %dn",i,j,x2,y2,si

51、,sj); / printf("(%lf,%lf)n",x2,y2); void dukou() int i; for (i=1;i<=13;i+) scanf("%d",&koui); void outp2() int i,j; for (i=1;i<=20;i+) for (j=1;j<=12;j+) printf("%lf ",dikouj); printf("%lfn",dikou13); void jisuan(int k)int i;double ave=0,d=0,d1=0;

52、memset(tot,0,sizeof(tot);for (i=1;i<=92;i+)totsi+=bi;for (i=1;i<=n;i+)if (totpti!=0)totpti=4200/totpti;ave+=totpti;elsetotpti=3000*lvi;totpti=4200/totpti;ave+=totpti; /*void jisuan(int k) int i; double ave=0,d=0; memset(tot,0,sizeof(tot); for (i=1;i<=92;i+) totsi+=exp(lvi)*log(bi); for (i=1

53、;i<=n;i+) if (totpti!=0) totpti=exp(0.14)*log(300)/totpti; ave+=totpti; */ ave=ave/n; for (i=1;i<=n;i+) d+=(totpti-ave)*(totpti-ave); d=d/n; d=sqrt(d); d1=d/ave; if (d1<mind) mind=d1; minave=ave; for (i=21;i<=20+k;i+) minpi-20=pti; void chuli2(int k) int i,j; for (i=1;i<=k;i+) for (j=

54、21;j<=92;j+) if (bj>dpti+20j) bj=dpti+20j; sj=pti+20; void huanyuanb() int i; for (i=21;i<=92;i+) bi=copbi; si=copsi; void meiju1() int i; mind=10000; for (i=21;i<=92;i+) n+; ptn=i; chuli2(1); jisuan(1); n-; huanyuanb(); printf("mind=%lf; AVE=%lf; Point=%dn",mind,minave,minp1);

55、 void meiju2() int i,j; mind=10000; for (i=n+1;i<=91;i+) n+; ptn=i; for (j=i+1;j<=92;j+) n+; ptn=j; chuli2(2); jisuan(2); huanyuanb(); n-; n-; printf("mind=%lf; AVE=%lf; Point=%d %dn",mind,minave,minp1,minp2); void meiju3() int i,j,k; mind=10000; for (i=n+1;i<=90;i+) n+; ptn=i; for (j=i+1;j<=91;j+) n+; ptn=j; for (k=j+1;k<=92;k+) n+; ptn=k; chuli2(3); jisuan(3); huanyuanb(); n-; n-; n-; printf("mind=%lf; AVE=%lf; Point=%d %d %dn",mind,minave,minp1,minp2,minp3); /*void meiju4() int i,j,l,k; mind=10000; for (i=n+1;i<=89;i+) n+; ptn=i; for