交巡警服务平台的设置与调度

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

1、B题 交巡警服务平台的设置与调度目 录一 摘要二 问题重述三 问题分析与建模思路四 基本假设五 符号说明六 模型的建立与求解七 模型的评价与推广八 参考文献与附录九程序一摘要警察是现代社会不可或缺的角色，肩负着执法、治安、提供社会服务等重要职责。为了更好更有效的实现这些只能，必须设立交巡警服务平台。这些平台需要合理地分布在城市的各个地区和交通要道，这样不仅可以及时响应出警到达案发现场，在遇到重要的或者突发的事件时也能高效的通过联合调度行动起来。该论文就交巡警服务平台的设置与调度等实际问题，针对提出的5个问题分别给出具体的解决方案并给出结果。问题一：（1） 题目要求根据已知20个交巡警服务平台的

2、位置，为它们分别分配各自的管辖范围，使其能在3min内到达自己管辖区域内的事发地点。对于此问题本文建立最大集合覆盖模型，建立了A区街道结点连通性的邻接矩阵。通过对该邻接矩阵进行优化，建立了带权边邻接矩阵。借助floyd多源最短路算法并利用数学软件MATLAB进行分配求解，最后得到A区现有每个巡警服务台的管辖范围如表1。（2）题目要求对13条交通要道实现快速全封锁，我们以所用时间最少为目标，引入0-1变量，建立该问题的0-1规划模型，并借助数学软件LINGO进行求解，求解结果表明需要8.05分钟可以实现快速封锁。（3）题目要求以交巡警服务平台工作量尽量均衡以及出警时间尽量短为前提，确定增设平台（

3、25）的具体数目及位置。 由问题（1）的分配结果可知，在现有巡警服务台的设置下：还有6个路口在案发时巡警不能在3min之内到达，即某些地方出警时间过长；我们根据巡警服务台的工作量的方差定义工作量不均衡度，结果显示：此时服务台的工作量不均衡度为8.4314。为了解决上述出警时间过长与工作量不均衡的问题。我们建立集合覆盖的0-1规划模型，求解结果表明：在增加4个平台的情况下，可以解决出警时间过长的问题。在此基础上我们优化分配方案：在增加4个巡警服务台的情况下，使平台的工作量的不均衡度降为3.0742。增加的4个巡警服务台的路口标号见表8。问题二：（1）题目要求针对全市六个城区的具体情况，分析研究该

4、市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。这里本文设定了两条原则，原则一：警力必须在案发3分钟之内到达案发地点；原则二：交巡警服务台的工作量尽量均衡，出警速度尽量快。根据以上两个原则对该市现有交巡警服务台的设置方案的合理性 进行评价，评价结果显示 ：全市有138个路口，在案发时交巡警不能在3min之内到达；此时的不均衡度已达40.3。基于上述两点，现有的交巡警服务台设置不合理。由于我们认为现有的交巡警服务平台的设置略有不合理，所以我们你拟定以下两个调整部署的优化方案。方案一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；方案二：保持现有巡

5、警服务台的个数，但对其位置进行调整。 （2）题目假设市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。设计总体调度全市交巡警平台的最佳围堵方案，使其能够尽快地抓捕嫌疑人。 本问题实质是单目标规划问题，我们建立0-1规划模型，以交巡警围堵时间最短为目标，以成功围堵条件 。对于巡警的成功围堵，可以转化为二部图的完全匹配，求得最佳围堵方案完全匹配，原始方案和两种优化的求解结果见表15、表16和表17。 关键字：最大集合覆盖 0-1规划模型 FLOYD算法 MATLAB软件 LINGO软件 二问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法

6、、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车

7、的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在

8、案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。三问题分析与建模思路问题一：（1）题目要求为A区各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。本文引入经典离散定位理论中的最大集合覆盖模型进行求解。记I=1，2，3，,92为城区A的所有路口节点集合，J=1，2，20为城区A巡警服务台的节点集合，ij为i交巡警服务台到达j路口的最短距离。引入0-1 变量iI,jJ，当路口i分配给巡警服务台j管辖是为1，当路口i不分配给巡警服务台j 管辖是为0。即：由题目的要求可知，当ij3m

9、in时，路口可能分配给巡警服务台，也可能分配给其他可在3min 到达i 路口的其他巡警服务台，而不分配给平台j ，故此时s i j0。根据上述的分配原则及每个路口只由一个巡警服务台进行管辖、每个巡警服务台至少要管辖一个路口，可建立最大集合覆盖模型，并借助数学软件MATLAB进行求解。（2）该问题要求当发生突发事件时，要调度全区20 个交巡警服务平台的警力资源，对进出A 区的13 条交通要道进行快速全封锁，且每个平台的警力最多封锁一个路口。本文将问题转化为：从20个服务平台中选出13个对13条交通要道进行封锁，且这13个平台所用的时间要最小的规划问题。本文引入0-1 变量表示一个巡警服务台是否封

10、锁一条交通要道，从而建立这个问题的0-1 规划模型，并借助数学软件LINGO进行求解。（3）根据问题一（1）的分配方案可知：当标号为39、61、28、29、38、92 的路口有案件发生时，标号为2、7、15、16、20 的巡警服务台的出警时间将超过3min，即出警时间过长。此时每个巡警服务台的工作量分别为： 表1 20 个巡警服务台的工作量平台标号12345678910工作量10.38.35.66.69.72.5958.21.6平台标号11121314151617181920工作量4.648.52.52.13.85.36.13.410.7此时巡警服务台的工作量不均衡度为8.4314。由（1），

11、（2）可知现有巡警服务台的工作量极其不均衡且有些地方出警时间过长。针上述问题，题目要求再增加25个巡警服务台来解决上述问题。本文首先按照（1）、（2）中的方法建立集合覆盖的0-1规划模型，然后利用MATLAB 对模型进行求解，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加巡警服务台的数目与位置。问题二： （1）本文定义了两个评价原则： 原则一：巡警能在3min之内到达案发路口 原则二：巡警服务台的工作量均衡度尽量小。 根据以上两个原则对该城区现有巡警服务台的设置方案的合理性进行评价。 若现有巡警服务台的设置不合理，本文则提出三种方案对全城的巡警服务台设置进行优化： 方案

12、一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台； 方案二：保持现有巡警服务台的个数，但对其位置进行调整； 方案三：不考虑现有巡警服务台的设置情况，重新确定全城的最佳巡警服务台数目与位置。 2）当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台 警力围堵嫌疑犯。因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌 疑犯逃跑方向，所以此问题可转化为以下模型：对于任意时间t，嫌疑犯驾车跑的最大范围为：在t+3时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，记为Q将Q的边界点集记为。所谓最快围堵方案，

13、即寻找一个最短时间t,适当的调配巡警警力，使其在时间t内能够到达边界点，这样嫌疑犯就被控制在区域Q中了，此时嫌疑犯将无法逃脱。四基本假设1.假设每个巡警服务台的职能和警力配备基本相同；2.假设每个路口只由一个巡警服务台进行管辖；3.假设每个巡警服务台至少管辖一个路口；4.假设巡警都按最短路径到达各案发路口；5.假设犯罪案件都在路口上发生；6.假设在重大案件发生时，每个平台都有能够封锁一个路口的能力；7.工作量：每个巡警服务台所管辖范围内的所有路口案发率之和；8.出警时间：巡警到达案发路口所需时间；9.假设逃犯的逃跑速度等于警车的行驶速度；10.假设巡警在接到报案后并不知道逃犯的逃跑方向；五符号

14、说明1.Cij：为交巡警服务平台j到达路口i的最短距离，其中：i=1,292，j=1,220；2.uij：为路口i与路口j之间的最短距离，其中：i=1,292，j=1,292；3. ，其中：i=1,292，j=1,220； 4. ，其中：i=1,220，j=1,292；5. ，其中：i=1,220，j=1,292；6.Cj：j交巡警服务平台的工作量，其中：i=1,292；7. ：平均工作量；8.Ini：i路口的发案次数，其中：i=1,292；9.p：工作量不均衡度；1011.Iisolated：C类路口的集合；12.Qi+3：嫌疑犯在（t+3）min内行驶的最大区域；13. ：嫌疑犯在（t+3

15、）min内行驶的最大区域边界点集；六模型的建立与求解6.1问题一（1）：管辖区域的确定-最大集合覆盖模型6.1.1模型建立：最大覆盖函数：根据问题一（1）的分析确定最大覆盖函数为：满足条件：1）因为每个路口只由一个巡警服务台管辖，所以： 2）根据实际情况每个巡警服务台管辖的路口数至少等于1，所以。综上所述，得到最大集合覆盖模型为：满足： （1）6.1.2 模型求解：1.最短路径矩阵 U9292的建立本文选用floyd算法确定城区A任意两个路口之间的最短路径矩阵U9292。floyd 算法为：任意两点(i, j)之间的最短路径（记为Dij ）等于从i 出发到达j点的以任一点为中转点所有可能方案中

16、，距离最短的一个。即：Dij=min(Dij,Dik+Dkj,),1kn,n为节点总数。算法为：U(1)ii=0,U(1)ij=wijij,U(k+1)ij=minu（k）ij,u(k)ik+u(k)kj，i,j,k=1,.,n在上式中，临时标号u（k）ij是不通过k,k +1, ,n节点（i, j除外）时从节点i到节点j 的最短路径。通过上述算法，利用数学软件MATLAB 计算出各节点的最短路径，组成一个最短路径矩阵U9292。矩阵中，元素ui1j为从路口i1 到路口j的最短距离，其中i1=192,j=192。2.集合覆盖矩阵的建立K9292 以巡警服务台能否在3min内到达案发路口为分配标

17、准，将上述最短路矩阵转化为集合覆盖问题，即0-1覆盖问题。转化方法为： (2)此时将得到集合覆盖矩阵K9292。此时从矩阵中可以得到巡警服务台在只考虑能在规定时间内到达的初始分配情况。3.最终分配方案的确定由集合覆盖矩阵K9292将92 个路口分为A、B、C 三类：A 类：已只由一个巡警服务台进行管辖；（直接分配）B 类：可被多个巡警服务台进行管辖；(按就近原则分配)C类；还不能被任何巡警服务台进行管辖；（按就近原则分配）处理的时候按照A、B、C的顺序依次进行；可以看出在处理完B类之后仍有标号为28、29、38、39、61、92的6个任何巡警服务台都不能在规定时间内到达规定路口。最终分配方案如

18、下表所示：表2 最终分配方案服务台管辖路口服务台管辖路口11 67 68 69 71 73 74 75 76 781111 26 2722 40 43 44 70 72 391212 25354 55 3 65 661313 21 22 23 2444 57 60 62 63 641414549 53 5 50 51 52 56 58 591515 28 29661616 36 37 38730 7 32 47 48 611741 17 4288 33 461818 80 81 82 8399 31 34 35 451919 77 7910102086 20 84 85 87 88 89 90

19、 91 926.2 问题一（2）：警力合理调度方案0-1整数规划模型6.2.1模型建立：记20个巡警服务台分别为i=1.20，记13条交通要道分别为j=113。记巡警服务台i与要道j间的距离为cij。 决策变量：引入0-1变量xij，若选择巡警服务台i对要道j进行封锁，记xij=1,否则记xij=0，即: (3)此为问题的决策变量，共260个。目标函数：本题要求对13条要道进行快速封锁，即要求巡警服务台对13条交通要道进行全部封锁所需时间最短的调度方案。在假设警车行驶速度相同的条件下，可转化为求巡警服务台与要道最大距离最短的调度方案。则本题目标函数为f2=max(cijxij),其中i=120

20、,j=113。约束条件：根据问题的要求，每个交通要道必须有一个巡警服务台对其进行封锁，即对于j=113, 应有： ，对于i=120, 应有： 。综上所述，此问题的优化模型为6.2.2模型的求解：本文利用MATLAB和Lingo进行编程求解，程序见附录，具体步骤如下：1.求解cij。整理附件2中的数据，根据Floyd算法，利用MATLAB编程，得到20个巡警服务台距离13条交通要道的最短距离cij。 2.按照附件2中20个巡警服务台和13条交通要道的顺序进行编号，引入决策变量xij，根据已经建立的模型中的约束条件和目标函数，利用Lingo9.0求得全局最优解。 3.求解结果显示，目标函数的最小值

21、为8.0155，即封锁13条交通要道的最少时间为8.0155分钟。下表列出了A区交巡警服务平台警力合理的调度方案。表3 A区交巡警服务平台警力合理的调度方案A区路口12141621222324282930384862平台位置1016611121413157819420到路口时间7.56886.74176.2595.07236.88256.47332.38544.75188.01553.06087.63937.39596.44896.3问题一（3）确定增加平台的个数与位置集合覆盖模型6.3.1模型建立与问题求解：1.初步分配方案的确定同样运用问题一（1）中的方法可得到：距离C类各个路口小于3km

22、的路口集合，如下表：表4 距离C类各个路口小于3km的路口集合C类路口标号282938394892集合28,2928,2938,39,4038,39,4048,6187,88,89,90,91,92对上表中的6个集合求并，得到需要增加巡警服务台的路口的候选集Q=28,29,38,39,61,92。本文将在候选集Q中选择25个路口设置服务台，使需求集Iisolated=28,29,38,39,61,92中所有路口在案发时均有巡警在3min之内赶到。集合覆盖模型的建立首先，建立覆盖矩阵T613，其元素： （5）i=1,26,j=1,213。其次，建立集合覆盖模型： 满足：其中，最后，利用MATLA

23、B运用搜索法得到：至少从候选集Q中选出4个路口来设置巡警服务台，才能解决出警时间过长的问题。此时共有48种可能的分配方案。分别如下表所示：表5 72种分配方案28384887283848872939618829396188284048892840488929386190293861902839489128394891294061922940619228384887283848872939618829396188284048892840488929386190293861902839489128394891294061922940619228384887283848872939618829396

24、188284048892840488929386190293861902839489128394891294061922940619228384887283848872939618829396188284048892840488929386190293861902839489128394891294061922940619228384887283848872939618829396188284048892840488929386190293861902839489128394891294061922940619228384887283848872939618829396188284048892

25、84048892938619029386190283948912839489129406192294061922.最终分配方案的确定1）为每种方案中的24个巡警服务台分配管辖范围。步骤一：同样按照问题一（1）中的求解过程1和2可得到有24个巡警服务台的集合覆盖矩阵K9224。 步骤二：此时由上述集合覆盖矩阵可将城区A的92个路口分为A、B两类：A类：已只由一个巡警服务台进行管辖；B类：可被多个巡警服务台进行管辖；将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。对于B类的路口，在综合距离最近与工作量平均的情况下来进行分配。即：首先选择距离路口i最近的巡警服务台j(j=1,224),然后利

26、用公式 ,计算巡警服务台j的工作量cj，若cj ,则将路口i分配给巡警服务台j管，否则选择次短距离的服务台进行同样考虑。最后得到每种分配方案中24服务平台的管辖范围。步骤三：根据平局工作量公式 与工作量不均衡度公式 利用MATLAB分别对48种分配方案中服务台的工作量不均衡度计算得：表6 72种分配方案的工作量不均衡度3.4889673913.4889673913.4889673913.4889673913.4889673913.3389673914.4117210144.4117210144.4117210144.4117210144.4117210144.2556340583.074184

27、7833.0741847833.0741847833.0741847833.0741847833.0767934783.9969384063.9969384063.9969384063.9969384063.9969384063.9995471013.0741847833.0741847833.0741847833.0741847833.0741847833.0767934783.9969384063.9969384063.9969384063.9969384063.9969384063.9995471013.4889673913.4889673913.4889673913.488967391

28、3.4889673913.3389673914.4117210144.4117210144.4117210144.4117210144.4117210144.2556340583.0741847833.0741847833.0741847833.0741847833.0741847833.0767934783.9969384063.9969384063.9969384063.9969384063.9969384063.9995471013.0741847833.0741847833.0741847833.0741847833.0741847833.0767934783.9969384063.9

29、969384063.9969384063.9969384063.9969384063.999547101由表中数据可得，最小不均衡度为3.0742，有8种不同分配方案，如下表：表7 满足题目一（3）要求的4个巡警服务台的路口标号2838488728384887293961882939618828404889284048892938619029386190283948912839489128384887283848872939618829396188284048892840488929386190293861902839489128394891对应的城区A的24个巡警服务台的管辖范围与每个巡警服

30、务台对应的工作量，如下表：表8 24个交警服务台的管辖范围服务台管辖范围服务台管辖范围11 67 68 69 71 731313 21 22 23 2422 43 44 70 721414354 55 3 65 66151544 57 60 62 63 641616 36 37553 5 49 50 511741 17 4266 52 56 58 591818 74 80 81 8277 30 321919 75 76 77 78 7988 33 45 462020 85 86 90 9199 31 34 352128 2910102238 39 401111 26 272361 47 481

31、212 252492 83 84 87 88 89表9 每个交巡警服务台对应的平均工作量服务台工作量服务台工作量服务台工作量16.596.8175.326.6101.6186.335.6114.6196.146.6124206.356.6138.5212.765.6142.5224.376152.1233.686.4163.8246.16.4问题二（1）6.4.1现有巡警服务台设置的合理性的讨论本文定义了两个评价原则：原则一：巡警能在3min之内到达案发路口原则二：巡警服务台的工作量均衡度尽量小。依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。讨论现有设置方案是否满足原则

32、一全城六区A，B，C，D，E，F现有个80巡警服务台、582个路口，运用问题一（1）中的算法，得到全城C类路口的数目与位置，如下表：表10 C类路口的位置标号28 29 38 39 61 92 122 123 124 151 152 153 183 199 200 201 202 203 205 206 207 208 209 210 215 238 239 240 247 248 251 252 253 257 259 261 262 263 264 268 269 285 286 287 288 299 300 301 302 303 304 312 313 314 315 316 317

33、 318 319 329 330 331 332 336 337 339 344 362 369 370 371 387 388 389 390 391 392 393 395 407 408 409 411 412 413 417 418 419 420 438 439 443 445 446 451 452 455 458 459 464 469 471 474 486 487 505 506 507 508 509 510 512 513 514 515 516 517 518 519 522 523 524 525 526 527 529 533 540 541 559 5605615

34、66569574575578580计算结果表明：582个路口中共有138个C类路口，即在案发时巡警不能在3min到达此路口，约占全城总路口数的1/4。讨论现有设置方案是否满足原则二运用问题一（3）中的方法，为每个巡警服务台分配管辖范围，并计算工作量及巡警服务台的工作不均衡度。结果如下：表11 现有配置下每个服务台的工作量1服务台工作量服务台工作量 服务台工作量服务台工作量1 10.3932.11784.53782.62 9.7 94 11.3 179 13 379 7.4 3 5.6 95 9.5 180 13 380 2.5 4 17.1 96 11.5 181 6.2 381 6.2 5

35、9.7 97 5.6 182 12.2 382 10.3 6 2.5 98 12.1 320 8.7 383 10 7 40.4 99 4.3 321 12 384 8.3 8 5 100 4.5 322 4.4 385 9.1 9 8.2 166 3.8 323 4.2 386 6.3 10 1.6 167 8.3 324 7.9 475 13.1 11 4.6 168 4.7 325 2.2 476 13 12 10.3 169 3.4 326 5.1 477 10.7 13 39.6 170 12.9 327 7.6 478 9.5 14 7.2 171 12.4 328 6.7 479

36、 8.7 15 12.9 172 8.3 372 5.2 480 4.7 16 28.4 173 11.5 373 4.1 481 7.2 17 5.3 174 10.1 374 5.5 482 4.4 18 6.1 175 8.7 375 6.1 483 3.3 19 3.4 176 8.1 376 2.6 484 3.8 20 11.5 177 2.2 377 4.2 485 3.3 结果分析：由表中数据可得：在现有配置下，其中有个7巡警服务台的工作量已达到40.4，而其中还有10巡警服务平台的工作量仅为1.6，所有巡警服务台的工作量不均衡度为40.3。可见，此时巡警服务平台的工作量极其不

37、均衡。根据上述1、2的讨论可知：现有巡警服务台的设置极其不合理。6.4.2巡警服务台设置的优化由现有巡警服务台的分配不合理的情况，我们提出两种优化方案。方案一“静态增加”优化方案此方案的优化思想为：在不改变现有巡警服务台的位置的情况下，适当增加巡警服务台的数目，从而使城区A中无C类路口且每个巡警服务台的工作量尽量均衡。由上题6.4.1中的计算结果可知，全城共有138个C类路口。将其组成需求点的集合，同样利用求解问题一（3）中的方法与步骤，得到新增加的最小巡警服务台数目与位置、此种方案下巡警服务台的工作量和工作量的不均衡度。方案二“动态”优化方案此方案的优化思想为：在不改变现有巡警服务台数目的情

38、况下，对80个巡警服务台的位置进行重新定位，从而使城区A中的C类路口数目尽量少且巡警服务台的工作量尽量均衡。模型的建立根据此方案的优化思想，首先确定候选集为：J=1,2,582,需求点集为：I=1,2,582。然后，建立最大集合覆盖模型，从候选集中选出80个点以满足使城区A中的C类路口数目尽量少且巡警服务台工作量尽量均衡。模型如下：满足： （7）其中：6.5问题二（2）：围堵方案的确定6.5.1模型建立按照问题分析，本文定义相关概念如下：Qt+3:嫌疑犯在（t+3）min内行驶的最大区域;:嫌疑犯在（t+3）min内行驶的最大区域边界点集；P：现有所有服务台集合本文以时间t为目标，建立优化模型

39、如下：Min t模型的限制条件中，对于是否可以适当分配P 中的警力，可以在t 时间内到达中所有点。可以抽象为图论中二部图的完全匹配问题，如果可以分配警力使其和中的边界点一一匹配，则。七模型的评价与推广1.优点：1.本文把具体的实际问题抽象成函数模型、集合模型、规划与优化模型、图论与表格模型，有效的解决了实际问题吗，有助于交巡警服务平台的设置以及案发时候对案发现场及周边道路的封锁。2.本文采用离散的定位模型对城区交巡警服务平台进行优化布局，较为全面地考虑了一些影响因素，如案发率、出警速度、交巡警服务平台的工作量等，采用的算法也是精度高、效率高，较为形象，使处理实际问题时能够如鱼得水、方便快捷。3

40、.整个模型的建立思路清晰，遵循可操作性原则，可比性原则及科学性原则，该模型建立了在较为理想状态下交巡警平台的最优设置，缩短了出警时间，提高了效率。2.缺点：1.本文还未对案发的时间段进行综合考虑。由于各个时间段案发几率不同，尤其是夜晚突发事件会较多，警力的部署和工作量的均衡方面还有待优化，例如在夜晚加强对路口地点的工作量分配。2.本文还未对人口密度进行综合考虑。在城区，人口密度有较大差异也是一个实际情况，在设置交巡警服务平台时还应该对居民区及其附近重点布置，以保证城市居民的安全，使交巡警能在最快的时间内赶到现场处理问题。3.考虑到交接班不能同时，以防交接班的时候有突发事件发生，这点上应该根据每

41、片交巡警服务平台设置的均衡性，分配不同的交接班时间，保证相邻的两个交巡警服务平台不会同时交接班。4.本文在服务台设置优化的步骤中没有涉及在不考虑现有巡警服务台的设置情况下，重新确定全城的最佳巡警服务台数目与位置的优化方案。5.在实际应用中，还应考虑道路是否通畅，交通工具是否能够通过等诸多现实问题，才能真正运用于实际的生活中。3.模型推广：本题模型较好的解决了交巡警的出警问题，追捕逃犯的封堵路口的分配问题，本模型除此之外，还可用于消防救援的最优安排问题，安全事故的应急救援问题，出租车省油的最佳路径问题以及加油站的点位设置问题等现实生活中。总的来说，在实际生活中有很大的利用价值，一定程度上可作为参

42、考。八参考文献与附录1 谢金星，优化模型与LINDO/LINGO软件，北京：清华大学出版社，2006年。2 王沫然，MATLAB与科学，北京：电子工业出版社，2008年。3 方世昌，离散数学，西安：西安电子科技大学出版社，2009年 附录见附件九程序问题一(1):管辖区域的分配：求解最大结合覆盖模型function dyt1.1disp(sprintf(正在载入相关数据.);Node_data=xlsread(F:数学建模第二期培训第一题B2.xls,1,b2:c93); %载入A区路口节点的左边数据Routine_data=xlsread(F:数学建模第二期培训第一题B2.xls,2,a2:

43、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_inde

44、x); 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 =

45、 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; endend%根据邻接矩阵数据创建图论的稀疏矩阵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,

46、j)=inf; if i=j DG(i,j)=0; end end endendfor k=1:92 for i=1:92 for j=1:92 if DG(i,k)+DG(k,j)DG(i,j) DG(i,j)=DG(i,k)+DG(k,j); end end endendPatrol_range=cell(20,1);for i=1:20 for j=1:92 if(DG(i,j)1) %如果大于1，说明有交集，先去除，不分配 Cover=Cover,i; Patrol_coveri=c; %保存交集 for k=1:m find(Patrol_distributionc(k)=i); P

47、atrol_distributionc(k)=Patrol_distributionc(k)(find(Patrol_distributionc(k)=i);%预分配只属于自己的交通节点 end end if(m=0) Isolated=Isolated,i; endendPatrol_xin=Patrol_distribution; %进行B类节点的的分配for i=1:92 m=length(Patrol_coveri); Distance_linshi=; if(m=1) for j=1:m Distance_linshi(j)=DG(i,Patrol_coveri(j); end m0

48、=min(Distance_linshi); for k=1:20 if DG(i,k)=m0 f=k; end end Patrol_xinf=Patrol_xinf,i; endendm=length(Isolated); %对孤立点进行分配for i=1:m for j=1:20 dist(j)=DG(Isolated(i),j); end m0,m1=min(dist); Patrol_xinm1=Patrol_xinm1,Isolated(i);endsave Patrol_xin.mat;问题一（2）：求解围堵13条要道的方案程序1：！求围堵的方案与最快时间sets: AA/1.2

49、0/; cross/1.13/; links(AA,cross): dis, x; Endsets !数据的定义部分; data:dis=22236.1516028.479286.81219293.4421096.2122501.7522893.219001.1619515.8112083.445880.93511850.114885.21720463.9214129.727388.06317394.6919197.472060321120.9717228.9317743.5810311.213982.18610309.546035.06818352.2712767.236025.566160

50、32.1917834.9719240.5119009.3215117.2815631.928199.566093.848197.8844393.38521997.3815008.518266.85318273.4820076.2621481.7922654.4316226.9115535.348102.9764860.9767395.86935017628.1912969.636227.96716234.5917749.5219155.0618285.2411306.8710615.293182.9339421.1192475.8265255.07517658.7813000.216258.5

51、5216265.1817780.1119185.6518315.8311337.4510645.883213.5189451.7042506.4115337.33214914.9410901.224159.55914166.1915036.2716441.8115571.998570.2188015.457583.09527352.7111290.2027991.72214092.519433.9432692.28212698.9114213.8415619.3814749.5610228.0310493.183060.825885.4343099.4678677.28313010.718274.2021532.5411539.1713