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

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 黔南民族师范学院 参赛队员 (打印并签名) ：1 龚 浪 2 刘可馨 3 李文文 指导教师或指导教师组负责人（打印并签名）： 谢治州 日期： 2011 年 09 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘 要本文研究了城区交巡警服务平台的设置与调度问题。我们将全市的交叉路口作为图的顶点、道路作为图的边来构建交通网络图G。将图G的每边起点和终点的直线距离作为边权，根据已知的数据构建图G的权矩阵W，在此基础上采用Dijstra算法求出图G的每个顶点到达其他各点的最短路及路长，并构造了最短路长矩阵D，建立了服务平台管辖范围最优分配方案的条件模型；依据最短路长矩阵D构造服务平台管辖范围分配的覆盖算法，用此算法求出A区服务平台较为均衡的管辖范围，给出了增加服务平台的较优方案。对于封锁A区的问题，我们建立了指派模型，并求出了全局最优解，给出了最优的调度方案。另外，我们采用简单的圆覆盖原理，分析全市区现有服务平台设置的不合理性，根据服务平台负载情况来均衡各服务平台的工作量以及出警时间的原则和任务，将服务平台管辖范围内的发案率和到其所辖顶点的最短路作为服务平台设置的评价指标，采用模糊目标函数均值聚类法中的目标函数采用极小化类别方法建立了服务平台设置评价模型并得了较好的结果。最后对围堵重大刑事案件嫌疑犯的最佳方案问题，转化为在图G的边集中求始点在中而终点不在中的边的终点和终点在中而始点不在中的边的始点构成的集合所包含的元素个数和具体元素，即集合的元素个数即为需要封锁的路口个数，集合所包含的元素对应需要封锁的路口。本文提出的算法模型解决了服务平台的管辖范围，均衡了服务平台的工作量，并且几乎没有“越界”的情况。同时针对任意地区发生重大刑事案件，可以得出非常好的围堵方案。本文提出的服务平台选址模型，同样还适用于物流网点、超市、垃圾转运站的设立，有较好的推广价值。关键词：交巡警；Dijstra算法；最短路长矩阵；均值聚类; 极小化类别法18一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。如果假设每个交巡警服务平台的职能和警力配备基本相同，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度有限的警务资源是警务部门面临的一个实际课题。某市的交通网络与交巡警服务平台的设置如图1所示。图1 全市六区交通网络与交巡警服务平台设置示意图说明：1) 图中实线表示市区道路，红色线表示连接两个区之间的道路；2) 实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；3) 星号“*”表示出入城区的路口节点；4) 圆圈“”表示现有交巡警服务平台的设置点；5) 圆圈加星号“* ”表示在出入城区的路口处设置了交巡警服务平台；6) 图中的不同颜色表示不同的区。建立数学模型分析研究下面的问题：问题1 图2给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个服务平台，确定需要增加平台的具体个数和位置。图2 A区的交通网络与交巡警服务平台设置示意图问题2 针对全市(主城六区A，B，C，D，E，F)的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，给出解决方案。如果该市地点P(如图1的P点)处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析问题的研究是在将全市的交叉路口作为图的顶点、道路作为图的边所构成的图G上来进行。设图G的顶点集为V，共有582个顶点，依次标为1，2，582，图G的边集为E，每边起点和终点的标号已知。在图G上建立平面直角坐标系，给出了每个顶点对应位置的坐标和平均每天发生报警案件的数量(即发案率)。在目前的交巡警服务平台设置方案中，服务平台建在图G的一些顶点上，服务平台设置方案由服务平台与顶点标号的对应关系确定。各服务平台依据它所在的城区依次标为：A1，A2，；B1，B2，；。另外，还明确了出入市区的路口标号和出入A区的路口标号(详见“附件2_全市六区交通网路和平台设置的数据表”)。若整个市区各点的海拔高度相差不大，相邻两个交叉路口间的道路近似为直线段，我们可将图G的每边起点和终点的直线距离作为它的权值，根据已知的数据可得图G的权矩阵，其中，若标号为的顶点坐标分别为和，则 (2.1)不难看出，图G是一个连通图，由图G的权矩阵W，采用求最短路的Dijstra算法(详见文献1)，按附录中的程序1可求出图G的每个顶点到达其他各点的最短路及路长，记为从点到达的最短路长，可构造最短路长矩阵(其中，当时，)，最短路长矩阵的数据见“附件3_最短路长矩阵数据”。2.1 问题1的分析对于问题1，要为A区的各交巡警服务平台Ak(k=1,2,，20)分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地，需制定合理的分配方案，满足：纳入服务平台Ak的管辖范围的顶点，尽量不超过3km；各服务平台的工作量相对均衡。对于重大突发事件，若一个平台的警力只能封锁一个路口，调度全区20个服务平台的警力资源将进出该区的13条交通要道快速全封锁。可以将其看着一个指派问题，求出它的全局最优解即可。对于具体的服务平台管辖范围的分配方案，得出的服务平台工作量可能不均衡，有些地方出警时间甚至会超过3分钟。若允许增加2至5个平台，可根据操作分配方案中遇到的问题和分配结果，确定增加平台的具体个数和位置。2.2 问题2的分析问题2的规模较问题1大得多，但可将解决问题1所制定的服务平台管辖范围的分配方案分别应用于各个分区或整个市区，通过对比所得结果是否符合服务平台的设置原则和完成任务的情况来分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显的不合理，再给出有效的解决方案。如果该市地点P(如图1的P点)处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。根据犯罪嫌疑人逃跑速度和调度全市交巡警服务平台警力资源围堵嫌疑犯所需的时间，得出嫌疑犯在案发后的分钟内逃跑的路程。在图G中，对于以P点为始点的所有出逃道路，无论沿哪条道路，嫌疑犯在分钟内到过的顶点应满足，由此建立包含嫌疑犯的最佳区域(区域所包含的顶点和进出该区域的路口尽可能的少)，快速全封锁该区域的方案即为最佳围堵方案。三、问题假设1整个市区各点的海拔高度相差不大，相邻两个交叉路口间的道路近似为直线段；2图1所示的交通网络对应的道路皆为双向车道；3每个路口节点，平均每天发生的报案数包含它附近发生的案件；4警员到达出事地块边缘即为到达出事地点；5出警时道路恒畅通(无交通事故、交通堵塞等发生)，警车行驶正常；6出警时总是沿最短路到达出事点。四、符号说明： 图1所示的交通网络图，其中为顶点集，为边集；： 图的顶点标号；：图的权矩阵，其中为图的边的权，取值见(2.1)；：最短路长矩阵，其中为从点到达的最短路长；： 顶点的发案率；： 服务平台工作量的度量，为服务平台管辖的所有顶点的发案率之和；： 各服务平台工作量数据的标准差；: 表示嫌犯逃跑时的平均车速: 表示分钟内嫌犯逃跑的最大半径: 表示分钟内嫌犯逃跑的最大范围五、模型建立与求解5.1 服务平台管辖范围的最优分配方案的条件模型对于A区，设各服务平台Ak(k=1,2,，20)的管辖范围为顶点集，其中为A区交通网络图的顶点集的子集，并且两两不相交，(A区交通网络图的顶点个数为92)。用表示顶点的发案率，用作为服务平台Ak(k=1,2,，20)的每天工作量的度量，为各服务平台工作量数据的标准差，那么，A区服务平台管辖范围的最优分配方案应满足： (5.1)5.2 分配服务平台管辖范围的算法及计算结果分配服平台管辖范围，我们采用覆盖的方法确定管辖范围。具体地，对于A区，一共有20个服务平台，对应的最短路长矩阵为。为确保出现突发事件时，尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地，在上构造覆盖矩阵，其中为服务平台Ak(k=1,2,，20)对应的顶点，且 (5.2)若第行的第个元素的值为，那么顶点可纳入服平台Ak的管辖范围。由于该区的服务平台分布不均衡，一方面，存在3分钟内不能到达事发地的顶点；另一方面，在顶点密集区，存在同属于两个以上服务平台管辖范围顶点(称为重复顶点)。对于在3分钟内不能到达的顶点，则将它纳入距它最近的服务平台的管辖范围；对于同属于两个以上服务平台的顶点(不含服务平台所在的顶点)，我们考虑均衡A区各服务平台的工作量以及出警时间的原则综合考虑采用发案率与出警时间，将它们均衡分配给其中的某一个服务平台，具体算法如下：Step1：将非重复顶点直接分配给各服务平台；Step2：将发案率和出警时间归一化，分别尝试给发案率和出警时间赋权值，根据各服务平台管辖顶点的总发案率和出警时间，令 (5.3)算出每个服务平台的得分。Step3：定义矩阵用于表示重复顶点和它所属服务平台的情况，具体地，的每行的第一个元素为重复顶点的标号，后面的元素依次为该顶点所属的服务平台对应顶点的标号(不只一个)，为了运算上的方便，将矩阵设置为选择方案数最多的维数，不满个选择的顶点，先存储可选择服务平台标号，余下的元素用21补位）Step4：选择矩阵的任意一行(原则上，可以从第一行取到最后一行)，得到该行所表示顶点可选择的服务平台，将该路口分配给其中得分最少的服务平台，并将该路口与服务平台的得分加到该服务平台的得分中。Step5：选择下一行。重复Step4，直到矩阵中每一行元素都有且只有一次被分配。实现上述算法的程序见附录的文件夹1_3，运行程序算出A区各顶点在不同权重下服务平台管辖范围的分配方案和各服务平台工作量的标准差见表1。表1权重（0.4,0.6）(0.3,0.7)(0.2,0.8)标准差2.24992.28512.2718当出警时间和发案率的权重为0.4:0.6时，得出各服务平台工作量的标准差最小，分配效果最好。但在这一方案下，分布最密集的1号服务平台所管辖的范围，其中顶点80，82，43，67，70出现“越界”情况。也就是说，如果1号服务平台要到顶点80，82，43，67，70，必须途经18号服务平台所辖的78号顶点，2号服务平台所辖的69号顶点，19号服务平台所辖的68号顶点。这样和实际生活中大相径庭。为了尽量避免“越界”情况的发生，则对上述分配方案进行改进。具体方法如下：先确定每个服务平台以内的所有不重复的顶点，并将其分配给对应的交巡警平台，保证在每个服务平台的内不会出现“越界”情况。对于没被分配的顶点，按照原先的算法得出分配结果。考虑到实际管辖的合理性。我们考虑每个服务平台被分配的管辖范围是否有“越界”情况。用改进的算法给出重新分配的方案，我们同样寻找1号服务平台所辖范围的“越界”情况。在重新分配后，1号服务平台只有两个出现“越界”的顶点。即顶点65，67，必须经过19号服务平台的68号顶点。由此说明，改进后的分配方案要比为改进的方案更合理。这样的改进务必会使服务平台发案率的标准差有所增加(从2.2249增加到2.3702)，但是联系实际，本文启用改进后的分配方案，确定每个服务服务平台的管辖范围(见表2)。增加服务平台保证A区发生突发事故时，都有交巡警在3分钟内到达事发地，现在A区服务平台工作量的标准差为1.9906，比未增加前减少了0.3796，说明现在设置的服务平台，工作量比未添加服务平台前更均衡，更具合理性，但需要更多的警力资源。表2 各服务平台的管辖范围表服务平台服务范围A11 65 67 69 71 74 75 78A22 39 40 43 44 70 72A33 54 55 64A44 57 60 62 63A55 48 49 50 52 53 56 59A66 47 51 58A77 30 61A88 32 33 45 46A99 31 34 35 37A1010A1111 26 27A1212 25A1313 21 22 23 24A1414A1515 28 29A1616 36 38A1717 41 42A1818 73 80 81 83 88 91A1919 66 68 76 77 79A2020 82 84 85 86 87 89 905.3 快速全封锁A区的模型与方案对A区的交通网络图，用表示服务平台集，表示进出A区的路口集, 调度全区20个服务平台的警力资源将进出该区的13个路口快速全封锁，可将其看着一个指派问题，指派模型如下2： (5.4)式中：是到的最短路长。用lingo软件进行求解(代码见附录代码3)，得全局最优解，最优调度方案如表3。表3：调度方案表服务平台标号进出口标号服务平台标号进出口标号A1A1122A238A1212A3A1323A462A1421A548A1528A6A1616A730A17A829A18A914A19A1024A205.4 增加A区服务平台的方案对于A区现有服务平台的设置，按我们所提出的管辖范围分配方案，依然存在交巡警服务平台的工作量不均衡和有些地方出警时间过长的情况(见表4)。.表4：交巡警工作量（发案率）一览表服务平台标号发案率服务平台标号发案率A18.1A114.6A29.7A124.0A34.9A138.5A45.8A142,5A59.2A154.8A66.0A164.9A75.1A175.3A87.9A187.7A96.9A196.2A101.6A2010.8为了均衡各服务平台的工作量和缩短出警时间，我们给出以下方案：首先，找出工作量繁重的服务平台，服务平台A20号的所管辖路口的发案率总和最大，距A20号服务平台最近的A18号服务平台的发案率总和为7.7，高于A区所有服务平台管辖路口发案率的平均值6.225。所以在A20号和A18号服务平台附近增加一个服务平台是十分必要的。经过对服务平台和各街道路口的分布图的分析，选定在标号为91号的路口添加服务平台。其次，A13号服务平台的管辖范围为21，22，23，24号路口，工作量也较大，且处在A区的出入口；23号路口的发案率又高达2.4，为了降低23号路口的发案率，由于13号路口是进入23号路口的必经之路，所以考虑在13号路口临近的22号路口增设服务平台。最后，在3分钟内没有到达交巡警到达的路口(28，29，38，39，61，92)增加交巡警服务平台。其中28，29号路口可以被同一个交巡警服务平台管辖，由于29号路口的发案率为1.3，29号路口的发案率为1.4，则任取一个路口设置交巡警服务平台即可，这里我们选取28号路口；38，39号路口也可以被同一个交巡警服务平台管辖，由于38号路口为 A区的出口，则选择在38号路口设置服务平台；61号路口距其他路口距离稍远，独立设置一个交巡警服务平台；由于先设置了91号交巡警服务平台，可以在3分钟内到达92号路口，于是不考虑再为92号路口设置服务平台。最终得出A区增加的服务平台为5个，分别位于22，29，38，61，91号路口。采用5.2分配服务平台管辖范围的算法，对A区增加服务平台后的新服务平台设置，再次划分各服务平台的管辖范围(管辖分配情况见表5)。表5 新服务平台设置下的管辖范围分配表服务平台服务范围A11 67 68 71 72 74 75 78A22 40 43 44 70A33 54 55 65 66A44 57 60 62 63 64A55 49 50 52 53 56 59 A66 47 51 58A77 30 31 48A88 33 45 46A99 32 34 35A1010A1111 26 27A1212 25A1313 23 23 24A1414A1515A1616 36 37A1717 41 42A1818 73 81 82 83A1919 76 77 79 80A2020 84 85 86 89A2929 28A2222 21A3838 39A6161A9191 87 88 90表6 新服务平台设置下的服务工作量表服务平台标号发案率服务平台标号发案率A17.3A142.5A27.4A152.1A34.9A165.1A45.8A175.3A57.8A187.3A66.0A195.3A77.5A206.6A86.5A212.7A95.3A222.8A101.6A234.3A114.6A240.6A124.0A254.6A135.75.5 市区现有服务平台设置方案的合理性分析图3 现有服务平台服务范围覆盖图类似5.2节，对各个分区应用其算法得到一个全市区各服务平台管辖范围分配方案，对整个市区我们也求得另一个分配方案，这个方案比分区处理要好得多，但仍不能否符合服务平台的设置原则和任务(数据详见附件)，说明该市现有交巡警服务平台设置方案很不合理。实事上，运用Matlab画图函数画出各个路口的散点图，以每个交巡警服务平台为圆心，为半径画圆。圆内的顶点表示被其所属的服务平台。事实上，图中的管辖范围管辖的路口到对应的服务平台可能大于，因为实际道路是各个道路相连的折线段，而图中用直线代替服务半径，由直线距离小于折线距离可知，没有被分配管辖范围的路口到任意交巡警服务平台一定大于，即3分钟内一定没有交巡警到达事发地，由图3可知，这样不合理的路口多达167个，显然现在全市交巡警服务平台的分布是不合理的。5.6 市区服务平台设置评价模型根据服务平台负载情况来均衡各服务平台的工作量以及出警时间的原则和任务，将服务平台管辖范围内的发案率和到其所辖顶点的最短路作为服务平台设置的评价指标。模糊目标函数均值聚类法中的目标函数采用极小化类别方法3，假如可供选择的服务平台有个，则，按照个指标来划分，即，将其分为个子集()，其对应的模型为： (5.5) (5.6)其中：为加权指数，一般情况下为大于等于1的定值；为元素属于类别的隶属度；为模糊分类矩阵；是类别的聚类中心；。新的服务平台对应的顶点编号为：156 398 354 36 17 183 449 428 437 135 14 219 432 212 47 471 442 306 450 2 405 394 10 78 208 227 509 568 318 238 334 5 581 463 58 512 106 224 197 460 222 263 408 388 344 144 28 278 54 577 186 142 110 162 528 400 366 331 554 572 82 192 200 25 303 23 520 66 483 514 413 298 89 289 253 269 343 338 545 293 252 448 493 71 564 499 582 124 311 201 379 459 348 502 203 454 300 259 62 482。图4 重置服务平台后服务范围详细数据见“附件4_重置方案后的结果”。5.7 围堵重大刑事案件嫌疑犯的最佳方案方案如果该市地点P(如图1的P点)处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。设嫌疑犯逃跑平均车速为，据此可以算出分钟内嫌疑犯逃跑的最大半径。以点为圆心，为半径画圆，可以得出分钟内嫌犯逃跑的最大范围，从而可以确定在这段时间内嫌犯可能经过的路口，设以这些路口构成的集合为，对需要封锁路口的个数及具体位置的确定问题，转化为在图G的边集中求始点在中而终点不在中的边的终点和终点在中而始点不在中的边的始点构成的集合所包含的元素个数和具体元素，即集合的元素个数即为需要封锁的路口个数，集合所包含的元素对应需要封锁的路口。算法步骤为：Step1：输入嫌犯逃跑速度；Step2：计算3分钟内嫌犯逃跑的最大范围，并找出属于这一范围内的顶点，并以这些顶点的编号为元素做成集合；Step3：以全市交通网络图路线表中的数据作边集其中m表示边集所包含的元素个数，为整数，且。Step4： 求在图G的边集中求始点在中而终点不在中的边的终点和终点在中而始点不在中的边的始点构成的集合所包含的元素个数和具体元素。由于服务平台在案发后3分钟才接到报警，假设嫌犯逃跑车速为，服务平台接到报警电话后，马上开始组织搜捕工作，且在3分钟内封锁所有出口，此时嫌犯已驾车逃跑时间，逃跑的最大半径，以点(32号路口)为圆心，为半径画圆，可以得出6分钟内嫌犯逃跑的最大范围即为该圆的面积。由最短路长矩阵进行分析可知，此时嫌犯最远可能在距离点的道路上的具体位置分别是以下37个路口(如表1所示)以外，相邻的下一个以外的站点之内。表7：与之间的最短路小于等于的顶点567891516303132333435363745464748495051525355565961173232233234235236237245247据此，以这37个路口的编号作为元素构成集合用“附件2_全市六区交通网路和平台设置的数据表”所给出的全市交通路线的路线表中的数据作边集求在图G的边集中求始点在中而终点不在中的边的终点和终点在中而始点不在中的边的始点构成的集合所包含的元素个数和具体元素。具体求解过程见附录的MATLAB程序luokouqueding.m，通过求解可知需要对17个路口进行封锁，这些路口的编号分别如表8所示：表8：需要封锁的顶点31014282938395457 860168231238244246560然而结合下面给出的点到各个顶点路口的有向赋权图5进行分析：图5 点到各个顶点路口的有向赋权图发现存在两个问题，一是有些服务平台位于待封锁点的前一个位置，同时满足距离点的距离在以外以内，对于满足此类条件的服务平台，考虑直接将该路口进行封锁，即可节省部分用于封锁该点以外路口的警力，比如16号服务平台，距离点的距离为，此时考虑将该服务平台直接进行封锁，即可节省原本需要用于封锁路口14号、38号以及560号的警力；二是对于无法实现3分钟到达的路口，将封锁地点向外移动，直到能够实现最短时间封锁，比如60号路口，不存在三分钟内可以到达的服务平台，此时考虑将待封锁地点向外移动到62号路口，并用1号服务平台对其进行封锁，即可实现最短时间封锁。在已确定17个待封锁路口的基础上综合以上两点，可得具体可行的最短时间封锁方案如表9所示：表9：最短时间封锁方案待封锁点编号用于进行封锁工作的服务平台所对顶点的编号所需封锁时间(min)322.11101001616040172.695432.275741.876214.8916816802311722.782401714.92441732.252461712.952481673.68由此可知，总共需要封锁13个路口，计算得封锁所需时间为4.9分钟。六、模型的优缺点及推广优点：1得出了服务平台的管辖范围，均衡了服务平台的工作量，并且几乎没有“越界”的情况。2在任意地区发生重大刑事案件，都可以得出最短时间内的围堵方案。缺点：1对于大型数据量，确定服务平台的管辖范围比较繁琐。2没有考虑在同一个服务平台同时发生两起案件的情况。推广：服务平台选址的模型，同样适用于物流网点、超市、垃圾转运站的设立。参考文献1 代西武, Dijkstra矩阵算法J, 北京建筑工程学院学报, 第23卷 第2期: 65-66,2007年6月.2 谢金星, 优化建模与lindo/lingo软件, 清华大学出版社.3 张兆民, 模糊C-均值在内陆无水港选址中的应用J, 上海海事大学学报, 第29卷第4期,3437,2008年12月.附录：1最短路代码，D.mn=582;A=ones(n)+inf;for i=1:n A(i,i)=0;endB=xlsread(点位置.xls,B2:C583);C=xlsread(可达点.xls,A2:B929);for i=1:928 A(C(i,1),C(i,2)=sqrt(B(C(i,1),1)-B(C(i,2),1)2+(B(C(i,1),2)-B(C(i,2),2)2);endfor i=1:582 for j=1:582 if A(i,j)=inf&A(i,j)=0 A(j,i)=A(i,j); end endenda=Dijstra(A);a=a/10;Dijstra.mfunction a=Dijstra(a)n=length(a);for i=2:n for j=1:(i-1) a(i,j)=a(j,i); endendfor k=1:(n-1) b=1:(k-1),(k+1):n; kk=length(b); a_id=k; b1=(k+1):n; kk1=length(b1); while kk0 for j=1:kk1 te=a(k,a_id)+a(a_id,b1(j); if tea(k,b1(j) a(k,b1(j)=te; end end miid=1; for j=2:kk if a(k,b(j)k miid1=find(b1=a_id); b1=b1(1:(miid1-1),b1(miid1+1):kk1); kk1=length(b1); end end for j=(k+1):n a(j,k)=a(k,j); endend2lingo代码：model:!17个警力平台，10出口;sets: jingli/1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20/; chuko /12 14 16 21 22 23 24 28 29 30 38 48 62/; Assign(jingli,chuko):c,x;endsets! 加权矩阵;data: c =22.24 16.03 9.29 19.29 21.10 22.50 22.89 19.00 19.52 12.08 5.88 11.85 4.89 20.46 14.13 7.39 17.39 19.20 20.60 21.12 17.23 17.74 10.31 3.98 10.31 6.04 18.35 12.77 6.03 16.03 17.83 19.24 19.01 15.12 15.63 8.20 6.09 8.20 4.39 22.00 15.01 8.27 18.27 20.08 21.48 22.65 16.23 15.54 8.10 4.86 7.40 0.35 17.63 12.97 6.23 16.23 17.75 19.16 18.29 11.31 10.62 3.18 9.42 2.48 5.26 17.66 13.00 6.26 16.27 17.78 19.19 18.32 11.34 10.65 3.21 9.45 2.51 5.4 14.91 10.90 4.16 14.17 15.04 16.44 15.57 8.57 8.02 0.58 7.35 1.29 7.99 14.09 9.43 2.69 12.70 14.21 15.62 14.75 10.23 10.49 3.06 5.89 3.10 8.68 13.01 8.27 1.53 11.54 13.13 14.54 13.67 9.78 10.72 3.49 4.73 4.20 9.34 7.59 1