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

1、交巡警服务平台的设置与调度一、 摘要随着社会的发展，城市化的步伐加快，交通管理问题也日益突出，为了更加有效解决交通管理问题、更好的服务群众，本文根据城市的实际情况与需要针对交巡警服务平台的设置与调度问题进行研究，建立模型分配A区交巡警服务台的管辖范围，制定了合理的交巡警服务台警力调度方案，根据服务台的工作量及出警时间增加了4个平台，最后分析全市的交巡警服务台的设置方案，并由此制定出最佳的围堵犯罪分子方案。问题一：(1)：利用最短路径法中的Dijkstra算法算出A区任意两个路口的最短距离，得出最短距离矩阵，根据就近分配原则将1到92个路口分配给20个交巡警服务台。最后得出分配方案，具体结果详见

2、表一，其中距离所有平台距离都大于3Km的路口节点为28、29、38、39、61、92，我们将其划分到就近的平台管辖区内。(2)：利用01规划问题中的指派算法计算，通过MATLAB计算出20个平台对13个路口的覆盖矩阵和到达这些路口所需最短时间，再通过Lingo计算出完成封锁13条交通要道所需的最短时间以及服务平台对路口的分配方案，得到封锁13条交通要道的最短时间为8.015分钟。(3)：由问题一的结果知路口28、29、38、39、61、92与20个平台的距离均超过3Km，再利用MATLAB计算出92个路口节点与这六个路口节点的距离和覆盖矩阵，得出需要再添置四个平台，有72种方案，其中的最优方案

3、为（28 39 48 87），此时24个平台的案发率的不均衡度最小为5.38，相较于原来的8,0大幅度下降。问题二：(1)：对于分析该市现有交巡警服务平台设置方案，采用两种评判标准：其一服务平台是否与其管辖区内的路口节点距离在3Km之内，其二每个工作平台的工作量不均衡度最小。通过MATLAB对全市582个路口节点进行处理，得出138个路口节点与现有的服务平台之间的距离均超过3Km，因此现有方案不满足条件一，再通过MATLAB计算出工作平台的不均衡度，结果为20.3481，可见，不均衡度较大，因此现有的方案不合理。对此制定了两个方案，方案一是新增加平台，使所有路口到交警平台的距离满足在3Km内，

4、得出需要再添置54个服务平台，增加新平台后的工作量不均衡度为9.8661，相较于原有的80个平台的不均衡度20.3481大幅度下降。方案二是不考虑现有交警平台，在582个路口中重新计算能够覆盖所有路口的交警平台位置，得出只要有96个平台就可使其与582个路口距离均在3公里内，总的不均衡度为29.7719。 (2)：时间为 t时罪犯的所有可能存在区域为一个图，也可以看做以p点为根节点的一个树，可知这个树是随着时间增长而扩大，只要警察可以在罪犯到达树的叶子节点之前封锁这些叶子节点，就可以将罪犯封堵从而逮捕罪犯。首先采用图和树的思想先找出罪犯位置的存在图，再把图的关键节点即图转化为树后树的叶子节点找

5、出。然后通过迭代找出满足条件的时间t ，在时间t内警察能够比罪犯更早到达所有叶子节点，经计算得出:t=10.589可以满足条件。 关键词 : Dijkstra算法 指派问题 集合覆盖 0-1规划 动态规划二、问题研究1、问题重述为了更有效地贯彻实施警察的各项职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。现在就某市设置交巡警服务平台的相关情况，需要做出以下研究：问题一：(1)：根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。(

6、2)：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，制定该区交巡警服务平台警力合理的调度方案。(3)：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。问题二(1)：分析研究该市现有交巡警服务平台设置方案的合理性，如果方案不合理制定合理的设置方案。(2)：该市地点P处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，制定调度全市交巡警服务平台警力资源的最佳围堵方案。2、问题分析2.1问题重要性分析交巡警的的宗旨是为人民

7、服务，全力维护社会稳定和治安大局平稳中发挥越来越重要的作用，他们肩负着刑事执法、治安管理、交通管理、服务群众四大职能。因此在交通要道和重要部位设置交巡警服务平台是相当重要的。这对于确保道路平安、畅通，预防和减少道交通事故，保证人民群众的生命财产安全，最终达到社会稳定、政治稳定的目的非常重要。2.2问题思路问题一(1)：给出了A区的交通网络和20个现有的交巡警服务平台，需要建立一个模型分配这20个交巡警服务平台管辖区，为此，我们建立了最短路径模型,采用Dijkstra算法，将92个路口按就近分配原则分配给20个服务平台。 (2)：可0-1规划指派问题来解决，根据每个路口必须由一个平台封锁，而每个

8、平台至多封锁一个路口的原则将20个平台分配到13个路口中，根据20个平台到13个路口的时间矩阵，用Lingo求得所需到达路口的最短时间。(3)：利用集合覆盖模型求解。先找出交警平台在3分钟之内不能到达的B类路口，建立集合覆盖，用MATLAB计算出72个节点与B类路口的覆盖矩阵,得出新增加的交警平台，使得新增加的交警平台可以覆盖原来3min内不能到达的路口，再利用MATLAB计算出增加后各个平台的案发率，选取案发率最低的作为最优方案。 问题二：(1)：此题可结合第一问与第三问，设置合理包含两个方面：一是在任一路口发生突发事件后，相应管辖区内的交警可在3min中之内抵达，二是考虑全市现有的80个交

9、巡警服务平台的工作量均衡，如果存在某一路口节点与现有的80个服务平台之间的距离均超过3Km或者是这80个服务平台的工作量的不均衡度过大3都证明现有方案的不合理，需要重新制定优化方案。(2)：我们考虑在交巡警追到犯罪嫌疑人之前的时间内，犯罪嫌疑人可能到达的路口节点，合理调度警力资源，使得交巡警在这段话时间内可以围堵所有路口。P点发生重大刑事案件，犯罪分子逃脱，而警方在3min后才接到报警，计算出t+3时间内犯罪分子可能达到的路口，在这些路口中挑选叶子节点，首先判断其是不是市区出口，再判断是不是出入各区的路口，如果是将这些点保存下来，如果交警能在t分钟之内到达叶子节点，即可对犯罪分子进行包围，从而

10、不让其逃脱。三、模型假设为了研究问题的方便，我们进行以下假设；1、每两个路口所连接的路径均为直线；2、该城市没有交通负担，交巡警到达突发事件的发生地过程中不会在路上耽搁时间 ；3、所有的交巡警服务平台均在各个路口节点设置；4、每个交巡警服务平台至多封锁一个路口；5.、每一条路径都是双行道；6、罪犯的速度与警车的速度相同；7、罪犯不走已经走过的路径。四、符号说明Individual(i).path：存储某一点到其余92个路口的最短路径；Individual(i).value：起始点到第i个点的最短路径长度；Distocorner：存储任意两个路口之间的最短距离；：表示第i个服务平台封锁第j个交通

11、要道Var:0-1变量；average1:20g个服务平台的平均案发率；average2:24个服务平台的平均案发率；swork1：20个服务平台的案发率方差；swork2：24个服务平台的案发率方差；wworkpnew：每一个服务平台的案发率t：犯罪份子达到某一路口所用时间五、模型建立与求解5.1.1模型一：基于最短路径算法的Dijkstra算法Dijkstra算法概述：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到找到起始点到所有点的最短路径为止。Dijkstra算法能得出到任意点的最短路径的最优值和最优路径。设G

12、(i，j)是一个包含A区所有顶点的距离矩阵，起始点p到其余92个点的最短路径储存在结构体数组individual(92)里面，其中individual(i).value保存的是起始点到第i个点的最短路径的长度，individual(i).path保存的是起始点到第i个点的最短路径，individual(i).istrue=1 表示起始点到第i个点的最短路径已经找到，否则=0表示未找到。程序每循环一次就要更新所有的individual(i).value值，选择individual(i).istrue为0的中间individual(i).value最小的individual(i).istrue=1

13、，然后对这一行进行遍历。根据Dijkstra算法，程序终止条件应该为所有的individual(i).istrue全部为1首先通过matlab计算出任意两个路口之间的最短距离，构造出92x92的邻接矩阵，将其存储到矩阵distocorner中，再计算出92个路口分别到20个服务平台的最短路径，将距离超过3Km的路口记录下来保存在b里面。通过计算将92个路口分为以下两类：A：此类路口与服务平台的距离在3Km之内；B：此类路口（28、29、38、39、61、92）与现有的20个服务平台的距离均超过3Km，我们将其称之为B类路口。分配方案：A：将此类路口与服务台距离在3Km之内，分配距离最近的服务平

14、台。B:此类路口与服务台距离超过3Km也分配给距离最近的服务平台。分配结果见下表： 表一：A区交通路口节点的分配服务平台A区交通路口节点167 68 69 71 73 74 75 76 78 1239 40 43 44 70 72 2354 55 65 66 3457 60 62 63 64 4549 50 51 52 53 56 58 59 566730 32 47 48 61 7833 46 8931 34 35 45 910101126 27 111225 121321 22 23 24 1314141528 29 151636 37 38 161741 42 171880 81 82

15、83 181977 79 192084 85 86 87 88 89 90 91 92 201126 27 111225 121321 22 23 24 1314141528 29 151636 37 38 161741 42 171880 81 82 83 181977 79 192084 85 86 87 88 89 90 91 92 201126 27 111225 121321 22 23 24 1314141528 29 151636 37 38 161741 42 171880 81 82 83 181977 79 192084 85 86 87 88 89 90 91 92 20

16、其中节点路口与服务平台距离超过3Km分配为表二：B类路口节点的分配 1528152916382397612092具体MATLAB代码详见附录5.1.2模型二：基于0-1规划问题的指派问题此题属于指派问题，可用Lingo解决。指派问题简介： 指派问题是在满足特定指派要求条件下，使指派方案总体效果最佳。如：有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包：有若干班级需要安排在若干教室里上课等。首先利用MATLAB得出13个路口与20个平台的0-1覆盖矩阵，再通过设置0-1变量var表示是否选择该平台,用表示第i个平台与第j个路口之间的最短时间。即模型为：: St

17、 var=0或1由此求得交警平台对路口的分配方法、封锁平台到达封锁路口的最短路径及到达所需的最短时间求出的结果如下：表三：封锁13条交通要道的路径及时间13条交通要道封锁的最短路径所用时间12121201416146.74216547893536166.228211322212.70822102611227.7082314212213236.473241125243.8052815284.75229730298.0153064748303.214381979781697024039387.63948847483.0996218807919777664634626.734根据上表可知封锁13条要

18、道的最短时间为8.015min.5.1.3.模型建立与求解通过MATLAB计算出的覆盖28、29、38、39、61、92的路口节点集合分别为28,2938,39,4048,6187 88 89 90 91 92（见下表）表四：覆盖B类路口节点的路口28293839619228,2928,2938,39,4038,39,4048,6187 88 89 90 91 92由上表可知：至少需要增加4个平台，共=72种方案，将72种方案中24个平台的案发率不均衡度，即案发率的平均值average2=;方差swork=结果为swork=5.38原来的20个服务平台的swork=8.0，经比较新增添4个平台

19、后，工作量的不均衡度明显减小。选出不均衡度最小的方案作为最优方案得到最佳方案为28 39 48 87 。72种方案为：表五：72种增加新平台的方案 28 38 48 87 28 40 61 92 28 38 48 88 29 38 48 87 28 38 48 89 29 38 48 88 28 38 48 90 29 38 48 89 28 38 48 91 29 38 48 90 28 38 48 92 29 38 48 91 28 38 61 87 29 38 48 92 28 38 61 88 29 38 61 87 28 38 61 89 29 38 61 88 28 38 61 9

20、0 29 38 61 89 28 38 61 91 29 38 61 90 28 38 61 92 29 38 61 91 28 39 48 87 29 38 61 92 28 39 48 88 29 39 48 87 28 39 48 89 29 39 48 88 28 39 48 90 29 39 48 89 28 39 48 91 29 39 48 90 28 39 48 92 29 39 48 91 28 39 61 87 29 39 48 92 28 39 61 88 29 39 61 87 28 39 61 89 29 39 61 88 28 39 61 90 29 39 61 8

21、9 28 39 61 91 29 39 61 90 28 39 61 92 29 39 61 91 28 40 48 87 29 39 61 92 28 40 48 88 29 40 48 87 28 40 48 89 29 40 48 88 28 40 48 90 29 40 48 89 28 40 48 91 29 40 48 90 28 40 48 92 29 40 48 91 28 40 61 87 29 40 48 92 28 40 61 88 29 40 61 87 28 40 61 89 29 40 61 88 28 40 61 90 29 40 61 89 28 40 61 9

22、1 29 40 61 90 29 40 61 92 29 40 61 915.2.1问题二模型建立：问题二可以说是综合了问题一中的第一问与第三问，全市共有582个路口节点，80个交巡警服务平台，先挑选出距离交警服务平台大于3Km的所有路口集合，经计算共有138个路口，也就是说现有的设置方案并不满足条件一。再利用MATLAB计算每个工作平台的工作量与不均衡度现有的80个工作平台的工作量计算出的不均衡度swork=20.3481表六：原有80个平台的工作量工作平台12345678910工作量10.39.75.66.69.72.59.658.21.6工作平台11121314151617181920工

23、作量4.645.73.64.86.25.36.13.411.5工作平台21222324252627282930工作量2.1139.512.75.612.14.96.66.313.5工作平台31323334353637383940工作量4.73.412.215.58.31510.1118.14.7工作平台41424344454647484950工作量11.318.426.18.510.511.413.24.45.47.9工作平台51525354555657585960工作量2.25.19.98.65.25.75.56.12.64.2工作平台61626364656667686970工作量3.713

24、.18.86.215.813.69.912.67.715.9工作平台71727374757677787980工作量13.618.315.69.97.28.65.54.45.33.3由上表可知10号工作台的工作量仅为1.6，而42号工作台的工作量却达到18.4，而且这80个工作平台的工作量不均衡度达到20.3481，由此可见现有的交巡警平台设置方案不合理。而且根据题目所给数据E区的面积最大，城区的人口也最多，全区的路口节点也最多，但是E区的交巡警平台却只有15个，由此可得出结论，该市的交巡警平台设置方案很不合理。优化方案方案一：不考虑现有80个交警平台，只考虑B类路口，新增加40个平台由上面计算

25、知存在138个路口节点我们暂且称之为B类路口，而且现有的80个工作平台的工作量不均衡度过大，因此制定了一下优化方案：需要新增加若干平台。设置一个0-1变量var表示是否选择该路口，isin(i，j)第i个路口与第j个B类路口间的覆盖矩阵，模型为：.s.t 经计算总共需要新平台54个新平台的位置如下表：表七：新增54个平台的位置新增平台12345678910平台位置394887105149183199202203205新增平台11121314151617181920平台位置214235239240248251263268286301新增平台21222324252627282930平台位置3193

26、29332333337340344362370387新增平台31323334353637383940平台位置388391407416417418420440454459新增平台41424344454647484950平台位置471489488499509525540541549567新增平台51525354平台位置573574575582新增54个服务平台后134个平台的工作量见下表：表八：134个平台的工作量平台位置178179180181182320321322323324工作量1.714.711.549.68.7124.44.27.9 平台位置3253263273283723733743

27、75376377工作量2.25.17.62.63.84.15.56.12.62.6 平台位置378379380381382383384385386475工作量2.65.74.76.28.75.456.24.712 平台位置476477478479480481482483484485工作量11.89.16.34.93.95.22.93.32.42.1 平台位置394887105149183199202203205工作量5.73.678.73.12.62.12.24.11.5 平台位置214235239240248251263268286301工作量2.14.13.33.22.41.93.35.8

28、6.69.7 平台位置319329332333337340344362370387工作量4.52.70.260.71.10.12.71.11 平台位置388391407416417418420440454459工作量55.33.32.51.64.212.83.64.93.4 平台位置471489488499509525540541549567工作量02.52.74.53.16.46.20.17.15.3 平台位置573574575582工作量4.40.60.60.4由上表可知：在134个平台中工作量最大的为14.7，不均衡度也降为9.8661，因此较为合理。方案2：不考虑现有的80个平台，重新

29、分配，将路口均采取就近分配方案，建立平台，通过Lingo计算出需要96个平台，位置见下表：平台数12345678910平台位置10142124252731424648平台数11121314151617181920平台位置49577090959698104150167平台数21222324252627282930平台位置169174175177181185190201204208平台数31323334353637383940平台位置210216236239240250261263271276平台数41424344454647484950平台位置28829831231533033233333834

30、4352平台数51525354555657585960平台位置361362363369370373374378381382平台数61626364656667686970平台位置386387388393397407416418420421平台数71727374757677787980平台位置423440449454472474483485486488平台数81828384858687888990平台位置500509527529539541549555561567平台数919293949596平台位置570573574575581582此时96个平台的工作量average=7.0260,不均衡度s

31、work= 29.7719此方案满足条件一，即各个路口与工作平台的距离均在3公里内，而且这是根据距离设置路口，因此也避免了因城区与人口造成的影响。5.2.2此问涉及Lingo中的指派问题及多目标规划问题。P处发生了重大刑事案件，犯罪分子沿任意路径逃脱，而警方在3分钟之后才接到报警电话，t表示犯罪分子达到某一路口所用时间，建立模型如下：第一步：计算t时间内犯罪分子所能达到的所有可能路口；第二步：通过MATLAB在这些所有可能路口中挑选叶子节点，即判断其是不是全是出入口以及各区的出入口；第三步：画出t时间内犯罪分子所有可能到达路口路线；第四步：将所得的叶子节点数代入Lingo中计算包围的最短时间

32、经Lingo算出t= 10.58890时警方可包围犯罪分子，此时叶子节点有四十个见表九：表九：40个叶子节点47137213249285882091213179182186194175212221178248252254278283280293370371458565568487491501518520522528535544567犯罪分子所有可能从P点到达这40个叶子节点的路线，见下图：星号“*”表示交警所需封锁的全部路口；圆圈“”表示市内路口；“”代表犯罪分子所有可能逃跑路径。“”犯罪分子最远可能到达的路径。通过Lingo计算得出这40个节点分别由40个平台进行封锁，见下表：表1140个节

33、点47137213249285882091213封锁平台1110374384320192417140个节点179182186194175212221178248252封锁平台181178176147917317017216616740个节点254278283280293370371458565568封锁平台16917417918218032032137647547840个节点487491501518520522528535544567封锁平台378372482477481476483484480485其中封锁路径及封锁时间用MATLAB计算，结果见下表：表12：从平台到达节点的路径所用时间11

34、1251247110.1912102611123728.424337445737223136.9164384467466468469470247.7453442434217419210.184620850.447719798018838489883.9278243727318838485207.083946285848988918.087101712162152142136.838111813083071803062972961798.344121782842822812911792922931829.376131761881861.964141757664634621901891921931

35、9410.35154704795805811831961758.7971617323223117121621521421321210.208171702252232222214.807181712262242232221787.692191662652622612602592488.709201672502523.81321169 2542.22221742242232251702762752786.985231792912812822833.643241822932921792912812805.32251802702712721822935.754263203493713707.80827

36、3213553503203493718.98283763754294323744574589.16294755651.382304785665675695688.586313784584864877.593237245745848649110.057334824894904815315305017.293344775015205215183.544354815315305015203.913364765445435365285275225.763748351151252652552752810.589384845395385285365358.7353948056756656554254354

37、48.486404855715695675.095由上表可知：封锁的最短时间为10.589分钟。模型结果分析六、模型评价与推广1、模型优点：本模型在评价交警平台是否合理时采用多目标规划的思想，先满足交警能够在3分钟内到达所有路口，然后考虑使各个交警平台的不均衡度最低。在需要封锁某一些路口时，然后求出交警平台对这些路口的覆盖矩阵转化为0-1规划问题然后用Lingo求得花费时间最短的分配方案，大大简化了问题，缩短了计算时间。在追捕罪犯时，采用图和树的思想先找出罪犯的存在图，再把图的关键节点即图转化为树后树的叶子节点。然后找出满足条件的时间t ，在时间t内警察能够比罪犯更早到达所有叶子节点即可。2、

38、模型缺点：本模型主要考虑了出警时间和各个交巡警平台的工作量，并未考虑对于不同区来说，人口密度不同对于交巡警平台设置的影响。3、模型推广：本模型不仅适用于交巡警服务平台的设置与调度，还适用于市区垃圾箱的合理分配、救火战、医院的位置选择等等各种最优位置选择问题。七、参考文献【1】高一凡，数据结构算法分析，清华大学出版社，第1版 ，2008年2月1日。【2】谢金星，优化模型与LINDO/LINGO软件，北京：清华大学出版社，2006年【3】卓金武，MATLAB在数学建模中的应用，北京航空航天大学出版社，第1版，2011年4月【4】运筹学教材编写组，运筹学，清华大学出版社，第三版，2006年3月.【5

39、】 ，LINGO在多目标规划和最大最小化模型中的应用【6】陈仁爱，刘婷，冯贤财，吕云凯，基于优化模型的街面逃逸犯罪嫌疑人的围堵方案探讨，SCIENCE & TECHNOLOGY INFORMATION，2012年第3期附录问题一(1)：分配各交巡警服务平台的管辖范围MATLAB程序代码%计算A区路口之间的邻接矩阵Dmatrix=zeros(92,92);load line line;n=size(line,1);for i=1:n; if(line(i,1)93&line(i,2)93) Dmatrix(line(i,1),line(i,2)=ppd(line(i,1),line(i,2);

40、Dmatrix(line(i,2),line(i,1)=Dmatrix(line(i,1),line(i,2); end;end;save Dmatrix1 Dmatrix%计算A区任意两个路口之间的距离function val=LestdisMtrix(v)load Dmatrix1 Dmatrix;G=Dmatrix; %邻接矩阵 N=size(G,1); %顶点数for i=1:N for j=1:N if G(i,j)=0 G(i,j)=inf; end endend%定义一个结构体individual(N)=struct(value,ones(1,1),path,ones(1,1),

41、istrue,ones(1,1);%结构体初始化for i=1:N individual(i).value=inf; individual(i).path=v i; individual(i).istrue=0;end; individual(v).value=0;individual(v).istrue=1; p=v;for ij=1:91for i=1:N if (individual(i).istrue=0)&isinf(G(p,i)=0&(individual(p).value+Dmatrix(p,i)individual(i).value); individual(i).value=

42、individual(p).value+Dmatrix(p,i); individual(i).path=individual(p).path i; end; endmin=inf;for i=1:N; if (individual(i).istrue=0)&(individual(i).value30) b=b,i; end;end;assign=struct(son,ones(1,1);for i=1:20 assign(i).son=;end;%路口采取就近分配方案数据保存在assign里面load caseoccuer casepercen;workp=zeros(1,20); %每个

43、平台的工作量for i=1:92; a=distocorner(i,1:20); listvalue id=min(a); workp(1,id)=workp(1,id)+casepercen(i); assign(id).son=assign(id).son i;end;save assign1 assignexit=12 14 16 21 22 23 24 28 29 30 38 48 62;for i=1:20 for j=1:13 distoexit(i,j)=distocorner(i,exit(j); %每个交警服务平台到出城A区路口距离矩阵 end;end;eachavailab

44、le=zeros(72,6);for i=21:92; for j=1:6; if(distocorner(i,b(j)30) eachavailable(i,j)=1; end; end;end;%不均衡度 swork=0;average=sum(workp)/20;for i=1:20; swork=swork+(workp(i)-average)2;end;swork=swork/20 distovjbkbvjkjbvkjb=round(distoexit); %计算最短路径 v=15; load Dmatrix1 Dmatrix;G=Dmatrix; %邻接矩阵N=size(G,1); %顶点数for i=1:N