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

交巡警服务平台的设置与调度【摘要】警察是现代社会中不可或缺的社会角色，肩负着执法、治安与服务群众等重要职能。为了更好地履行这些职能，交巡警服务平台要合理地分布在城市的各个地区，这样不仅可以及时响应出警到达案发现场，在遇到突发事件时也可以通过联合调度高效地行动起来。该论文就交巡警服务平台的设置与调度等实际问题，针对所提出的5个问题分别给出具体的解决并给出结果：对于问题1要给A区的每个服务平台分配管辖范围，即分配其管辖的节点。我们根据“就近原则”来分配管辖的节点，保证尽量在3分钟内有交巡警到达事发地。对此，借助MATLAB编程采用“Floyd最短路径算法”确定距离每个节点最近的服务平台，从而得到每个服务平台的管辖范围。对于问题2的合理的调度方案的确定，我们在“快速封锁”的原则下，通过调度警力使得A区在最短时间内被全封锁。20个服务平台对13个路口进行全封锁，而且每个服务平台最多封锁一个路口，这可划归于一个0-1规划问题，因此可用LINGO编程求得各种可选调度方案中13个路口封锁时间的最大值取值最小时的调度情况。对于问题3增加平台的个数与位置的确定，我们的目的是使各个服务平台的工作量达到均衡状态而且出警时间过长的问题得到有效解决。为此，我们在出警时间过长的节点或附近尝试增加新的服务平台，然后计算方差来衡量工作量的均衡程度，比较增加2至5个服务平台时的方差，以此确定方差最小的情况为最后的可选方案。这个过程仍然借助MATLAB程序来完成，采用“模拟退火法”来确定工作量达到均衡时新增平台的个数与位置。对于问题4对全市服务平台设置方案的合理性的讨论，我们借助问题1和问题3的解决方法来确定各区服务平台的管辖范围与新增服务平台的个数与位置。同时对模型进行优化，考虑到有些服务平台的工作量过少的情况，撤消一些现有的服务平台。借助MATLAB程序，可以给出一个较合理的解决方案，即给出各个分区的服务平台的调整方案。对于问题5围堵方案的确定，可将全市的交通网看作一张图，各个节点看作顶点。同时根据必要的假设：嫌疑犯一直朝远离事发点P点的方向逃跑，而且不走回路。这时，将P点看作树根，嫌疑犯的可能的逃跑路线便成为一个树，有可能经过的节点便是枝和叶。这样，就能根据图论的知识，通过MATLAB与LINGO程序，利用“追捕算法”来对各个分支道路进行有序的封锁排查，进而求得最佳的围堵方案。关键词：Floyd最短路径算法、0-1规划、模拟退火法、平台的设置与调度、图论、追捕1、问题背景现代社会中，要保证社会的良性运行，人民警察扮演着重要的角色。他们肩负着刑事执法、治安管理、交通管理、服务群众的重要职能，在保障人民财产安全面前起着举足轻重的作用。为了更有效地实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。这些交巡警服务平台的职能和警力配备基本相同，共同维护着社会的治安，保证城市的安全。在交巡警服务平台的设置中我们要充分考虑到警察所担负的社会职责：刑事执法、治安管理、交通管理、服务群众。在保证人民群众人身与财产安全的前提下还要尽量把服务工作做好做到位，让人民群众满意，因此，交巡警服务平台的设置是关键还要考虑到调度上的方面与快捷。而现实中由于警务资源的限制，同时考虑到社会资源的高效分配，不可能在每个交通要到和重要部位都设置这些交巡警服务平台。因而，如何根据城市的实际情况和需求合理的配置有限的交巡警服务平台、分配平台的管辖范围、调度警务资源是警务部门面临的一个实际而重要的问题。2、问题重述就某市设置交巡警服务平台的相关情况，建立数学模型研究下面的问题：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。全市（主城六区A，B，C，D，E，F）的交巡警服务平台的设置的具体情况与其他这些城市的情况见附件2。问题1：请为A区各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。问题2：对于重大突发事件，需要调度A区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口。请给出遇到重大突发事件时的警力合理的调度方案。问题3：根据A区现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题4：针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。问题5：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。3、基本假设现针对问题做必要的假设：1、发生突发事件后，警察在接到报警时能立刻出警，时间上的消耗主要考虑到在路上所花的时间。2、警察出警时，在去案发现场的路上道路通畅（不发生堵车等现象），警车行驶正常。3、交巡警服务平台的工作量主要由于出警所引起，而在现场或服务平台处理案件的工作量忽略。4、任何事故都发生在市区道路的节点上。5、警察出警到达事发地点走最短距离，而且警车始终保持匀速行驶。6、犯罪嫌疑人驾驶车辆出逃时，只能通过联通市区与外界的节点逃出市区。7、交巡警服务平台一般不能跨区管理，除非是一些重大事故。8、一般地，驾车逃跑的嫌疑犯不会走回路，而且想尽量离出事地点越远越好。9、嫌疑犯逃跑的车速是恒定的。4、符号说明表1 符号 数学解释 路口（节点）的发案率 两节点之间的距离 节点处交巡警服务平台的工作量 节点处的出警时间 标准差 警车的行驶速度 嫌疑犯逃跑车速5、问题分析5.1问题1的分析分配交巡警服务平台管辖范围的目的是当其所管辖的范围内发生突发事件时，尽量能在3分钟之内有交巡警到达事发地。根据实际生活中的经验，人们当然也希望突发事件发生时交巡警能够能尽快到达事发地处理事件。因而，在确定每个服务平台的管辖范围时，应根据“就近原则”——节点距离某个服务平台最近就属于那个服务平台管辖。可以考虑借助“Floyd-Warshall最短路径算法”解决这个问题。5.2问题2的分析当发生重大突发事件时要调度全区20个交巡警服务平台的警力资源对13条进出该区的交通要道实现全面快速的封锁。其中时间是关键因素，我们希望封锁完成得越快越好，而全封锁的最终完成以最后一个交通要道的封锁实现为标志。从而只须要求封锁最慢的那个交通要道的封锁时间最短即可。5.3问题3的分析之所以要增加2至5个平台，是为了解决现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际问题。由于管辖范围的划分是依据出警时间来确定的，因此在这里我们首先应该考虑工作量均衡问题，然后再以出警时间作为辅助来检验增加的服务平台的合理性。而一般说来，出警时间与工作量具有一定的正相关性，因此在出警时间较长的节点或其附近增加交巡警服务平台可以在一定程度上协调解决这两个问题。由于工作量既与出警路程有关，又与案件发生频率有关，所以可用案件发生频率与路程的积来表征工作量的大小，于是对每一个服务平台都有一个相应的工作量；同时又可用方差来表征工作均衡的程度。因此，通过添加服务平台，可以调整管辖范围，从而不但可以确保出警时间，也能调整工作量大小，以方差大小来衡量其均衡程度，最终可得一个添加方案。整个过程主要采用模拟退火算法，由于此题距离较远的节点出警时间不一定能保证，且工作量相对较大，故可从距离入手来添加服务平台。依据该算法原理，采用逐步寻优的手段，以工作量方差为检验标准，温度下降时工作量以较大概率趋于均衡，最终将得到一个较为合理的平台设置方案。5.4问题4的分析根据设置交巡警服务平台的原则与任务——刑事执法、治安管理、交通管理与服务群众，同时结合题目的要求可知平台设置的效果：第一是保证接到报警后出警时间不能过长；第二是各个服务平台的工作量大致均衡。接下来主要依据这两个方面对服务平台的设置进行优化。对于第一点，依据题意，不管在哪个区，出现突发事件时，尽量在相对短的时间内有巡警到达，基于这一点，我们可以对各个区内巡警服务平台的管辖范围进行划分。这就是说，范围的划分是为了保证出警时间不是太长。但考虑到现实中交巡警一般不能跨区管理，并且每个区的面积、人口密度、服务平台数目也不相同，因此要对不同区分开考虑，故不同区的出警最长时间的设定标准是不同的。对于第二条，由上面划分的管辖范围，依据问题3中的方法算出各个服务平台的工作量，通过比较，我们可以直观的发现其中的不合理的地方——一些服务平台之间的工作量相差太大，有些节点的出警时间的相对较长，可以分如下情况进行优化：（1）某个服务平台的工作量很大，若将其中某些节点划给其它服务平台管理则可达相对均衡状态，但划出的这些节点归为其他服务平台则会导致出警时间过长，也即该服务平台附近没有其他工作量较小的服务平台，两种矛盾无法调和，此时应该考虑添加一个服务平台。（2）某几个服务平台较为集中，且各自工作量相对较小，而将这些平台管辖区域外的节点调给它时又会导致出警时间过长，此时可以考虑撤消（或转移）某一个或几个服务平台来平衡工作量。通过以上两方面的调整，采用模拟退火算法思想，通过添加和撤消服务平台，最终工作量的方差达到最小且基本不变，而且每个节点的出警时间均不会有太大差异，这样就得到一个相对较为合理的设置方案。5.5问题5的分析当发生重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点。我们根据假设，嫌疑犯希望里出事地点P节点越来越远，而且嫌疑犯所走的路线不会出线回路。这时，我们将P点当作根，嫌疑犯可能的逃跑路线构成一个树。交巡警便可以根据逃跑路线所构成的树对嫌疑犯进行围堵。根据图论的知识，借助MATLAB与LINGO编程便可以得到一个围堵方案。6、模型的建立与分析6.1问题1的求解6.1.1模型的建立与求解根据“就近原则”的要求只需要确定距离每个节点最近的交巡警服务平台是哪个，从而就可以确定每个交巡警服务平台的管辖范围。这里我们用到“Floyd-Warshall最短路径算法[1]”。这个算法通过不停地加入中间点进行矩阵的迭代，从而解决有向图中每对顶点的最短路径问题，当我们把每个节点看作顶点时，我们便可以求得每个服务平台的管辖范围——管辖的节点。由MATLAB编程（见附录1），利用Floyd-Warshall最短路径算法可以得到A区20个服务平台的管辖范围，即每个服务平台所管辖的节点编号。A区服务平台的工作量见表2，结果见表3：表2 A区交巡警平台编号 A区交巡警平台的位置编号 A区交巡警平台的工作量 A1 1 84.7033 A2 2 128.7231 A3 3 58.4864 … … … A18 18 97.9036 A19 19 92.9778 A20 20 38.7462表3 A区交巡警平台编号 A区交巡警平台位置编号 每个交巡警平台所管辖节点编号 A1 1 1、67、68、69、71、73、74、75、76、78 A2 2 2、39、40、43、44、70、72 A3 3 3、54、55、65、66 A4 4 4、57、60、62、63、64 A5 5 5、49、50、51、52、53、56、58、59 A6 6 6 A7 7 7、30、32、47、48、61 A8 8 8、33、46 A9 9 9、31、34、35、45 A10 10 10 A11 11 11、26、27 A12 12 12、25 A13 13 13、21、22、23、24 A14 14 14 A15 15 15、28、29 A16 16 16、36、37、38 A17 17 17、41、42 A18 18 18、80、81、82、83 A19 19 19、77、79 A20 20 20、84、85、86、87、88、89、90、91、92A区各个交巡警平台的相应的管辖范围如图1所示（MATLAB程序见附录2）:图1（不同管辖范围用不同的颜色标识）6.1.2模型的分析从结果中可以很直观地看到不同交巡警平台所管辖的周围的节点个数是不同的，从而管辖范围不同，他们的工作量当然也不相同。例如平台A20要管辖10个节点，而平台A6仅管辖1个节点，这显然是不合理的——利用最短路径的思想划分的管辖范围会使得服务平台的工作量的不均衡。6.2问题2的求解6.2.1模型的建立与求解当遇到突发事件需要对A区进行全封锁时，合理的调度方案应该是使出警时间最长的节点处的出警时间达到最小值，其余的节点处出警时间尽量减小。又由于警车匀速行驶，所以路程的长短反映出出警时间的长短，故可用距离来代替时间考虑。由于20个服务平台的交巡警封锁13个路口，每个路口要有一个平台的交巡警负责，每个交巡警平台最多只能封锁一个路口，可以考虑用0-1规划来解决。目标函数为13个路口到各个服务平台的距离的集合，求解目标函数就是对这些距离进行搜索，找出达到13个一一对应时的最小距离，也就是说对所有可选的调度方案，找出每个方案的最大距离，然后从这些最大距离中取出最小值。对于取出的方案，由于前12个对应距离均比这个距离小，所以这个对应就表示完成封锁所需时间的最小值。借助计算机编程可得结果。其LINGO程序见附录3，运行结果如下：以A7服务平台封锁29号出口节点即可找到符合题意的一种封锁方案，并且这个方案中的最大距离是所有可行方案中最小的，所以说这个结果是最佳的。而其余的封锁时间均比完成该封锁用时短，故只用保证第29号出口节点由A7服务平台负责封锁，其余的节点处可有不止一种选择，这里我们给出一种相对较佳的方案作参考，见表4：表4 路口号 12 14 16 21 22 23 24 28 29 30 38 48 62 平台号 A10 A16 A9 A14 A11 A13 A12 A15 A7 A6 A2 A5 A46.2.2模型分析LINGO程序的最终结果显示只需要将29号路口由A7来封锁，其余路口在保证选择与他们距离短于A7-29之间的距离的平台的情况下，尽量选较短距离。即便如此，调度方案也不唯一，这里仅给出一个相对较佳的可行方案。6.3问题3的求解6.3.1模型建立与求解为解决服务平台工作量的不均衡和有些地方的出警时间过长的实际问题，可以考虑添加新的服务平台来分摊工作量较大的服务平台的工作量，又由于工作量大小和出警时间在一定程度上有正相关性，故一般也可同时减少出警时间过长节点的出警时间。每个服务平台都有一定的工作量，我们定义工作量函数其表示标号为的服务平台的工作量，为其管辖的节点处的发案率。节点处的出警时间为由于不变，仅与成正相关关系，距离长的地方出警时间相应会长。为节点与管辖其的服务平台之间的距离。各个服务平台的工作量的均衡程度由各个服务平台的工作量之间的方差来决定。当我们计划增加2至5个服务平台时，我们最终要使得方差达到最小值时的工作量达到最均衡的状态。这时便可以确定所增加的服务平台的个数与位置。对此，我们运用“模拟退火算法[2]”对其进行求解。该算法是寻求各个状态点之间的一个均衡的状态。而我们正是要通过增加服务平台的个数使得更个服务平台的工作量达到基本均衡，同时使得出警时间过长的节点的出警时间得到有效缩短。MATLAB程序见附录4，运行结果表5：表5 新增服务平台个数 新增服务平台所在节点标号 5 21、24、28、38、92 5 21、24、28、39、92新增平台如图2：图2（其中青色加号表示新增平台）6.3.2模型分析根据程序运行的结果，可知在38或39号节点处增加新的服务平台所得结果差异不大，因此都可以当作供选方案。由于退火模型存在普遍的缺陷，根据所选的“退火系数”t的不同，得到的结果可以有一定的差异，但对问题没有本质上的影响。如t取不同值时，92这个节点也可不添加服务平台，但也符合时间限制，对工作量均衡也无显著影响，只是上面的添加方案可以更加有效，工作量也相对较小，即这是一个较佳方案，故选之。6.4问题4的求解6.4.1模型的建立与求解对现有交巡警服务平台设置的合理性的讨论主要有两个指标来确定——各服务平台的工作量的差异与各个节点的出警时间的长短。现实生活中不同区的警力管辖范围仅限于该区，只有发生特殊事件时才有跨区合作的机会，因此我们将全市六区分开考虑，每个区的服务平台的管辖范围仅限于该区，那么问题的解决思路与问题3有很多类似的地方。问题的解决过程如下：（1）计算各区的服务平台的工作量，及它们的方差大小。计算各个节点处的出警时间。（2）根据问题三的方法对每个区的服务平台进行优化。（3）对于服务平台集中且各个服务平台的工作量都不大的情况考虑撤销一个服务平台节约警力资源。根据求解以上问题的思路，我们把全市划分为6各区，各个区由Floyd-Warshall最短路径算法求得各个服务平台的管辖范围，先通过直观地观察撤销一些明显的工作量过少的的平台，然后由模拟退火算法通过增加服务平台的个数来均衡各个平台的工作量。由MATLAB编程运行得到各个服务平台的工作量如表6,得到结果如表7：表6 交巡警平台编号 交巡警平台的位置标号 交巡警平台的工作量 A1 1 84.7033 A2 2 128.7231 A3 3 58.4864 … … … F9 483 97.9036 F10 484 92.9778 F11 485 38.7462表7 区号 新增平台所在节点的标号 撤销平台所在节点的标号 A 21、24、28、38或39、92 B 120、147 97、99 C 205、240、261、281、301、313 166、169、179、178 D 333、362 322、325 E 391、409、417、452 372、376、377 F 493、515 484增加与撤销平台如图3所示：（其中蓝色表示原服务平台，青色加号表添加新平台，红色叉号表撤消平台）图36.4.2模型的分析原方案的设计从时间和工作量上来讲绝大部分是合理的，只是有些地方设置不太科学。事实上，考虑时间因素和工作量因素占不同比重时优化方案也会不同。此处先考虑的是时间因素，对各个区域的服务平台管辖范围进行划分，然后采用问题3中方法给出工作量并得出撤消和添加的服务平台，然后再以时间限制进行优化检验。当然，采取不同的均衡标准与时间限制也可以有不同的优化方案。6.5问题5的求解6.5.1模型的建立与求解当发生重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点。根据假设，嫌疑犯希望离出事地点P节点越远越好，而且嫌疑犯所走的路线不会出现回路。因此，与同一个顶点相连的任意两个顶点不会连通（即无圈），这样可以将P点当作树根，而嫌疑犯可能的逃跑路线则构成一个树，这个树采用广度优先搜索BFS的方法得到的(附录5)。下面我们用图论的知识对这个围堵问题进行求解[3]：假设嫌疑犯可能的逃跑路线所构成的树为，我们的算法如下：（1）把的全部叶删除，得到子树；若是一个顶点组成的，算法终止；否则转（2）。（2）用替换，转（1）。（3）反复执行（1）和（2）。对于示意图如下图3的树，我们先从点出发，分别向围堵，然后删除点。接着从点出发，分别向围堵，依据这样的思路进行下去便可以对嫌疑犯进行围堵。图3SHAPE\*MERGEFORMAT由于嫌疑犯逃跑路径具有一定的随机性，而且其车速又是恒定的。从该假设出发，利用上述算法，不妨定义度数相同的顶点构成的集合为圈，这样可分不同的圈对其进行围堵。根据嫌疑犯车速来确定在哪个圈进行围堵，然后可用上述算法不断去掉“叶子”（外围顶点）最后把嫌疑犯包围。确定在给定圈内围堵疑犯可否成功方法如下：用问题2的模型计算出警察最快封锁该圈的时间（），比较嫌疑犯在恒定速度下到达该圈的时间（），以此来判断：当时，围堵成功；时，围堵失败。由MATLAB编程（见附录6）和LINGO编程（见附录7）得到第三圈下的一个结果：MATLAB运行结果(疑犯逃跑路程)：>>arealock(D,a,b)ans=184.6233LINGO运行结果（围堵过程中的最大距离）：Localoptimalsolutionfound.Objectivevalue:216.3435Objectivebound:216.3435Infeasibilities:0.000000Extendedsolversteps:42Totalsolveriterations:5457；当时，选择该围堵方案；时，不选择此方案。6.5.2模型的分析由于车速的不确定性，并且嫌疑犯逃跑路径也有一定的随机性，因此围堵方案也有不确定性。而且在假设中忽略了一些联通的道路，这也对结果造成了一定程度的影响。7、模型评价基于本问题有大量数据的前提，而且问题比较复杂，我们主要借助于计算机编程的思想，运用各种算法（如Floyd-Warshall最短路径算法、模拟退火算法）解决各个实际问题，最后得到一些合理的答案。当寻求遇到突发事件时各区警力资源的合理调度问题时，我们要求尽量快速地实现封锁与围堵，这时根据图论的知识，采用BFS算法并结合假设可得到围堵方案设计的一些准则，依据这些准则可选出围堵方案。但由于不确定的因素太多，无法保证结果的唯一性与准确性，因此只给出一种结果，它还是能够在一定程度上说明问题的。8、参考文献[1]ThomasH.CormenCharlesE.Leiserson,RonaldL.RivestCliffordStein,IntroductiontoAlgorithms[M],American:ChinaMachinePress,2009,386-388[2]Cabbage,Dan,Zfj3000等.模拟退火算法[EB/OL].http://wiki.mbalib.com/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95[3]王树禾,图论[M],北京：科学出版社，2004，,45-479、附录附录1——Floyed-Warshall最短路径算法MATLAB程序Floyed-Warshall算法程序代码如下：%这个算法采用的是floyd-warshall最短路径方法求解%%W表示初始时每个点与点之间联通的距离的矩阵化%%i表示起点，j表示终点%%D(i,j)表示中间点集合为{1,...,k}时的i点到j点的最短路径，其中k=0时D(i,j)=W(i,j)%%path表示最短路的路径矩阵%functionD=floydwarshall(W)n=size(W,1);D=W;path=zeros(n,n);[ab]=ind2sub([n,n],find(W~=inf));fork=1:npath(a(k),b(k))=b(k);endfork=1:nfori=1:nforj=1:nifD(i,j)>D(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend生成最短路径的函数程序代码如下：functionD=setshortestpathA=xlsread('fujian',1);B=xlsread('fujian',2);W=inf(92,92);l=triu(W,1);u=tril(W,-1);tmp=zeros([92,92]);W=l+u+tmp;nB=size(B,1);fori=1:nBifall([B(i,1)<=92,B(i,2)<=92])W(B(i,1),B(i,2))=sqrt((A(B(i,1),2)-A(B(i,2),2))^2+...(A(B(i,1),3)-A(B(i,2),3))^2);W(B(i,2),B(i,1))=W(B(i,1),B(i,2));endendW;D=floydwarshall(W);附录2——生成A区服务平台的设置的示意图的程序代码如下：functiondraw1(D)A=xlsread('fujian',1);B=xlsread('fujian',2);c=linspace(0.33,1,3);[xyz]=meshgrid(c);fori=1:20holdon[abc]=ind2sub([333],i+6);plot(A(i,2),A(i,3),'*','color',[x(a,b,c)y(a,b,c)z(a,b,c)]);endfori=21:92[tmp,position]=min(D(i,1:20));%iftmp>30%i%position%endholdon[abc]=ind2sub([333],position+6);plot(A(i,2),A(i,3),'*','color',[x(a,b,c)y(a,b,c)z(a,b,c)]);endn=size(B,1);fori=1:nifall([B(i,1)<=92,B(i,2)<=92])holdonline([A(B(i,1),2),A(B(i,2),2)],[A(B(i,1),3),A(B(i,2),3)],'color','k');endendxlabel('A区交通网络与平台设置的分配管辖范围初步示意图');附录3——求解问题2的程序代码LINGO程序代码如下：model:sets:cordon/c1..c13/;police/p1..p20/;forme/1..13/:f;links(police,cordon):distance,volume;endsetsmin=@smax(f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8),f(9),f(10),f(11),f(12),f(13));@for(cordon(J):@sum(police(I):volume(I,J))=1;);@for(police(I):@sum(cordon(J):volume(I,J))<=1;);@for(police(I):@sum(cordon(J):volume(I,J))>=0;);@for(links:@bin(volume););@for(cordon(J):f(J)=@sum(police(I):volume(I,J)*distance(I,J)););data:distance=222.3615273160.284737292.86812205192.9343927210.962149225.0175342228.932028190.0116023195.1580619120.834445258.80934932118.501147648.85216716204.6392212141.297247173.88063198173.9469026191.974659206.0300441211.2097218172.2892962177.4357558103.112139139.82185925103.095372160.35067549183.5226849127.672272860.25565768160.3219283178.3496847192.4050698190.0931855151.1727599156.319219581.995602860.9383955881.9788357643.93385175219.9738302150.085145682.66853046182.7348011200.7625574214.8179426226.5443309162.2690872155.353378681.0297618648.6097577373.958694053.5176.281911129.69628662.27967084162.3459414177.4952363191.5506215182.8524116113.0686519106.152943331.8293266294.2111911124.7582588152.55074784176.58776130.00213562.58551981162.6517904177.8010853191.8564704183.1582606113.3745009106.458792332.1351755994.5170400825.0641077753.37332351149.1493579109.012209941.5955947141.6618653150.3626833164.4180684155.719858685.7021836780.15456865.83095189573.5271149712.9020197179.91721609140.925056994.3394318826.92281672126.9890873142.1383822156.1937673147.4955575102.2802537104.93181530.6081983458.8543369930.9946733786.77282849130.10714982.7420183815.32540322115.3916738131.3204744145.3758595136.677649797.75722402107.24405734.9230364547.2569234941.9941042693.3666812275.86585214127.756589369.566700195.1069338577.0791774791.1345626182.4363528141.9486453151.435478379.1144577101.498220486.18552552147.607978137.9135282183.37297726113.950312150.7233218332.6955654546.7509505938.05274077186.3322573195.8190903123.4980697145.8818324130.5691375191.99159010119.502818145.432552286.853162668.8254062264.7700210835.9163002217.8144974227.3013304154.9803098177.3640725162.0513777223.473830259.7700210859.73279695127.149412127.083141529.055385138523.85372088228.0832079237.5700409165.2490203161.2081848172.3200881213.3179426119.502818067.4166151632.6496554350.6774118164.7327969583.58651783180.4992424189.1667785114.8431618101.4753879121.9142296153.5851456170.2960799132.980824965.56420975165.6304804171.5094053185.5647904176.866580647.5184174857.0052504644.0147180897.4957300251.08578589118.1009823145.432552267.416615160100.0662706118.094027132.1494121151.003133113.0826272121.750163347.4265465934.0587727354.497614486.16853046218.9211021149.032417581.61580237181.682073199.7098293213.7652145225.4916028186.5711771195.2387132120.915096547.55702964127.986164378.20524634242.471781185.1448456117.7282304217.794501235.8222574249.8776425249.0422817210.121856215.2683157140.94469983.66945767136.992599567.34361906225.4652514169.6148394102.1982242202.2644948220.2922512234.3476363232.035752193.1153264198.261786123.938169376.39281345119.986069850.3370894269.4580495212.131114144.7144989244.7807695262.8085258276.863911276.0285502230.1082001223.1924915148.8688748110.6557261141.79780764.48880031;enddataend附录4——模拟退火算法MATLAB程序代码如下：functionsa2addpoliceA=xlsread('fujian');rand('seed',sum(clock));D=setshortestpath;pposition=1:20;form=1:5%计算管辖区域的归属dist=[];p2p=[];p1p=[];i=21;whilei<=92ifisempty(find(i==pposition))[tmp1,tmp2]=min(D(i,pposition));dist=[disttmp1];p2p=[p2ptmp2];p1p=[p1pi];i=i+1;elsei=i+1;continue;endend[dist,tmp3]=sort(dist);p2p=p2p(tmp3);p1p=p1p(tmp3);%计算初始方差worksum=zeros(1,20+m-1);i=1;whilei<=92ifisempty(find(i==pposition))worksum(find((p2p(find(i==p1p))==pposition)==1))=...worksum(find((p2p(find(i==p1p))==pposition)==1))+dist(find(i==p1p))*A(i,5);i=i+1;elsei=i+1;continue;endendworksumvariance=var(worksum);%SA模型t=1;fo=variance;j=1;loop=0;%SA循环开始whilej<=72ifloop==20break;end%加入新解，构造新的管辖区pposition(1,20+m)=p1p(end-j+1);distin=[];p2pin=[];p1pin=[];i=21;whilei<=92ifisempty(find(i==pposition))[tmp1,tmp2]=min(D(i,pposition));distin=[distintmp1];p2pin=[p2pintmp2];p1pin=[p1pini];i=i+1;elsei=i+1;continue;endend[distin,tmp3]=sort(distin);p2pin=p2pin(tmp3);p1pin=p1pin(tmp3);worksum=zeros(1,20+m);i=1;whilei<=92ifisempty(find(i==pposition))worksum(find(p2pin(find(i==p1pin))==pposition))=...worksum(find(p2pin(find(i==p1pin))==pposition))+distin(find(i==p1pin))*A(i,5);i=i+1;elsei=i+1;continue;endendvariance=var(worksum);fe=variance;iffo-fe>0&&rand<exp(-1/t)j=j+1;t=t/2;fo=fe;elseloop=loop+1;endendendpposition附录5--广度优先搜索BFS的方法function[dTpar]=BFSB=xlsread('fujian',2);nB=size(B);numsum=1;par=zeros(1,582);clr=zeros(1,582);dT=zeros(1,582);Q=32;dT(32)=0;while~isempty(Q)u=Q(1);Q(1)=[];[ab]=ind2sub(nB,find(B==u));b=3-b;v=B(sub2ind(nB,a,b));v=v(find(clr(v)==0));if~isempty(v)clr(v)=clr(v)+1;dT(v)=dT(u)+1;par(v)=u;Q=[Qrot90(v)];endclr(u)=clr(u)+1;end附录6——问题5的程序代码functionarealock(D,dT,par,v)rand('seed',sum(clock));fori=1:max(dT)circle=find(dT==i);iv=rand*(min(D(32,circle))+max(D(32,circle)))/2end附录7---问题5的程序代码model:sets:cordon/c1..c20/;police/p1..p20/;forme/1..20/:f;links(police,cordon):distance,volume;endsetsmin=@max(f);@for(cordon(J):@sum(police(I):volume(I,J))=1;);@for(police(I):@sum(cordon(J):volume(I,J))<=1;);@for(police(I):@sum(cordon(J):volume(I,J))>=0;);@for(links:@bin(volume););@for(cordon(J):f(J)=@sum(police(I):volume(I,J)*distance(I,J)););data:distance=@ole(‘input.xls’,’data’);enddataend�EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4����EMBEDEquation.DSMT4���第2页，共20页PAGE1_1377282653.unknown_1377303854.unknown_1377304267.unknown_1377308552.unknown_1377308740.unknown_1377308777.unknown_1377307355.unknown_1377307443.unknown_1377307487.unknown_1377307393.unknown_1377304400.unknown_1377303962.unknown_1377304213.unknown_1377303946.unknown_1377303195.unknown_1377303199.unknown_1377303203.unknown_1377303802.unknown_1377303841.unknown_1377303205.unknown_1377303207.unknown_1377303208.unknown_1377303206.unknown_1377303204.unknown_1377303201.unknown_1377303202.unknown_1377303200.unknown_1377303197.unknown_1377303198.unknown_1377303196.unknown_1377282657.unknown_1377303193.unknown_1377303194.unknown_1377299474.unknown_1377282655.unknown_1377282656.unknown_1377282654.unknown_1377282645.unknown_1377282649.unknown_1377282651.unknown_1377282652.unknown_1377282650.unknown_1377282647.unknown_1377282648.unknown_1377282646.unknown_1377282641.unknown_1377282643.unknown_1377282644.unknown_1377282642.unknown_1377282639.unknown_1377282640.unknown_1377282638.unknown