大学毕业设计---交巡警服务平台的设置与调度数学建模.doc

交巡警服务平台的设置与调度摘要本文研究的是交巡警服务平台的设置与调度问题，所研究问题均以量化分析为基础，建立数学模型、求解与优化。针对所述问题的不同要求和约束条件，分别建立了“最短路径模型”、“整数规划模型”以及“多目标决策模型”。针对问题一，根据题目中所给的简单路线图，运用图论的相关理论，建立了“最短路径模型”。利用Floyd算法，通过LINGO和Matlab软件编程，得出区域划分方案。针对问题二，令已知的13个道路交通要点和20个交巡警服务平台为顶点，设立无向图G=(V,E,W)，建立“整数规划模型”，从题中提取出3个约束条件，求解得到城区A的20个交巡警服务平台到每一个交叉路口的最短路径矩阵，在快速封堵的原则下画出城区A的13条交通要道的封锁图。针对问题三，在问题一、二所得数据的基础上，增设新的交巡警服务平台，优化城区A交巡警服务平台的设置与调度。根据所求各道路交叉口实际距离和报案率建立“综合因素评价指标”，得出新增4个交巡警平台的具体位置，分别设在第60号、第24号、第28号、第87号道路交叉点上。针对问题四，综合利用P - 中值模型、P - 中心模型、覆盖模型的优点,建立“多目标决策模型”,采用“线性加权和法”求解该模型,得出应急设施的最优选址点。关键字：最短路径；Floyd算法；多目标决策；综合因素分析法；线性加权和法1 问题提出警察的职责是：刑事执法、治安管理、交通管理、服务群众。为了有效地贯彻实施这些职能，需要在一些交通要道等部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。若使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地， 如何为各交巡警服务平台分配管辖范围？（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。而实际中一个平台的警力最多封锁一个路口，请问怎样对交巡警服务平台警力合理的调度？ （3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请给出需要增加平台的具体个数和位置。.（4）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。2 问题分析2.1问题一的分析分析可知当城区A中某交巡警服务平台所管辖的范围内出现突发事件时，要求交巡警尽量在3分钟内以60km/h到达事发地,所以本着高效服务快速出警的理念,要求交巡警通过最短路径以最快速度到达指定位置。绘制出92个道路之间的交叉点的地理位置图，如下图1所示，问题一就转化为求解A城区中第号交巡警服务平台与其他第号交叉路口两点之间的最短路径d问题。 建立最短路径模型利用Floyd算法求解，结果可能会有道路之间的交叉点到交巡警服务平台的距离都大于3km，此时需要计算该店到各交巡警服务平台的最短路径。即最快时间交巡警出警到达该道路交叉点。图1 城区A内的道路之间的交叉点图2.2问题二的分析 分析问题，可知需要调度全区交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。利用Floyd算法，求出上面图1中20个交巡警服务平台到13条交通要道最短路径。各服务平台必须快速完全地进行出警，即是需要各个交巡警服务平台出警所用的总时间最少和将所有交通要道全封锁，所以对问题的求解可以转化为对目标函数的整数规划问题。2.3问题三的分析 根据问题一交巡警服务平台所管辖的范围，可以分析出各交巡警服务平台的工作量不均衡和有些地方出警时间过长，需要增设交巡警服务平台。有问题一结果可知各交巡警服务平台到道路交叉口的路径，各道路交叉口的报案率一直，可以算出交巡警每天实际走的路径，利用综合因素分析法，继而求出20个交巡警服务平台对各自管辖区的实际路径，即工作量。可以对工作量较大进行增设交巡警服务平台。2.4问题四的分析问题四要求分析评价该市现有交巡警服务平台设置方案的合理性，在不合理的情况下,对全市六城区合理设置交巡警服务平台并分配各平台的管辖范围。若仅以最短时间到达指定位置作为系统的优化指标，容易导致某城区局部区域警力资源的冗余，因此在满足时间最短的前提下, 需要综合考虑全市各个道路交叉口的发案率,各城区的人口数量和各交巡警服务平台快速封堵重要路口及围捕罪犯等多方面因素才会使设置方案更具合理性。因此需要综合考虑各方面因素合理设置交巡警服务平台。本文利用突发事件应急救援设施选址相关理论(参见表1)否定了该市现有交巡警服务平台设置方案.建立了一个多目标决策模型,采用线性加权和法求解该模型,得出全市交巡警服务平台的设置方案。表1 突发事件应急救援设施选址理论公共设施选址模型特点和适用范围选址模型目标适用设施p-中值模型寻求设施与需求点间总加权距离的最小化，进而求解出预设设施数目与最适合选址位置非紧急设施（公园邮局，加油站学校等）p-中心模型寻求设施与需求点间最大距离最小化，以求取设施数及选址点，目标是最小化需求点与其最近设施的最大距离紧急设施（紧急避难所，消防站医院，警察局）集合覆盖模型以最小化设施配置成本，寻求最少设施数的最适合位置，是所有需求点都在设施服务范围内，不考虑需求点在需求量上的的差别，且各需求点均被包含在特定的设施服务距离范围内非紧急设施，紧急设施最大覆盖模型目的在于求取设施最大化服务范围内的需求数量，并满足已知配置数量的设施非紧急设施，紧急设施 该市第32 道路交叉点处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。可知已逃出该交叉点所属A7交巡警服务平台所管辖区域，但还在城区A。而后安排全市交巡警对该罪犯进行围堵3 模型假设1.假设所供参考的数据真实可靠,各城区分类等信息真实合理；2.交巡警在出境路途中不会因意外事故而影响正常行驶；3.假设各交巡警服务平台所管范围内不会同时发生多次事故；4.假设交巡警在3min时间内到交叉点就认为到达报案地；5.假设交巡警接到报案和任务后无反应时间，即立即行动；6.假设交巡警出警必须沿图中已给路径行驶7.一个道路交叉点不会同时发生两个或两个以上报案时间；8.假设重大突发事件发生时，城区A内无其他报警事件；9.交巡警在出警时必须按图中所给线路行驶，不能另行行驶于图中各道路之间的空白处；4.符号说明本文对于交巡警服务平台的设置与调度的问题建立模型求解 ，所用到的符号及所表示的含义如下表2：表2 符号说明符号含义第个交巡警服务平台第个出入城区的路口节点第道路之间的交叉点邻接矩阵中的元素巡警服务点至道路交叉点的距离各道路交叉口报案率矩阵中的元素矩阵中的元素 实际路程矩阵的元素 道路交叉点的横坐标道路交叉点的纵坐标封锁调度矩阵的元素第个交叉点交巡警服务平台个数各服务平台到各交叉口的实际路程各交巡警服务点到各道路交叉点的风险度城区的权重各交巡警服务点管辖各城区为全市已有的交巡警数为道路交叉点最少交巡警服务平台数 5 模型的建立与求解5.1 交巡警服务平台管辖范围的分配方案5.1.1 最短路径模型的建立当城区A中某交巡警服务平台所管辖的范围内出现突发事件时，要求交巡警尽量在3分钟内以60km/h到达事发地,所以本着高效服务快速出警的理念,要求交巡警通过最短路径以最快速度到达指定位置,于是问题一就转化为求解A城区中第号交巡警服务平台与该区域内任一交叉路口两点之间的最短路径d的问题。最短路经模型流程图如右图2，下面建立最短路径模型。以交巡警服务平台，出入城区的路口节点和道路与道路之间的交叉点为顶点，构成赋权无向图 图2 模型流程图 。无向图的邻接矩阵为, 为矩阵中的元素。该无向图的邻接矩阵表示如下： 其中， 5.1.2 Floyd 算法求解Floyd 算法的基本思想。对于任何一个顶点（是公路之间的交汇点），顶点到顶点的最短路经过顶点或者不经过顶点。连接两点的边长，比较与的值。若，则令，保持是当前搜索的顶点到的最短距离。重复这一搜索过程，最后搜索完所有的顶点时，就是顶点到的最短距离。 用Floyd 算法，其算法程序见附件1.3首先递推产生一个矩阵序列，令，表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：其中，是迭代次数最后，当时， 即是各顶点之间的最短通路值。部分相邻交叉点有公路直接相连贯 ,其公路里程可由Matlab软件求解，计算结果见附件。根据所求相邻交叉路口间的距离结合问题一中警力配置要求可以得出每个交巡警服务平台的所管辖的具体范围，见下表1。表3 A1-A20号交巡警服务平台所辖交叉路口交巡警平台编号各平台所辖交通路口编号1，43,64,65,66,67,68,69,70,71，72,73,74,75,76,77,78,792,40,42,43,44,46,66,67,68,69,70,71,72,73,743，44,54,55,63,64,65,66,67,684，55,57,58,60,62,63,64,65,665，47,48,49,50,51,52,53,56,58,596，47,48,50,51,52,58,597，30,31,32,33,34,47,488，31,32,33,34,35,37,45,46,479，31,32,33,34,35,36,37,45,461011，25,26,271213，21,22,23,241415，3116，33,34,35,36,37,45,4617，40,41,42,43,70,7218，72,73,74,78,79,80,81,82,83,84,85,89,9019,65,66,68,69,71,74,75,76,77,78,79,80,81,8320，82,83,84,85,86,87,88,89,90,91从上表中，可知道路之间的交叉点没有交巡警平台服务的有：、。由问题分析可知在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地，而在三分钟内到达不了的道路之间的交叉点需要计算出能最快到达事发地交巡警服务平台。结合附件1.1（各相邻交叉点有道路直接相连的距离）可算出交巡警服务平台管辖范围的分配，结果如下表2：表4 未被交巡警平台服务的交叉点信息未及时到达的交点交巡警服务平台编号A15A15A16A16A4A20出警距离(km)4.755.703.414.115.313.85出警时间(min)4.755.703.414.115.313.85从上表1、表2中，可知同一个交叉路口可同时被多个交巡警服务平台所管辖，为达到高效服务，快速到达事发地的标准，不考虑同一事发地可同时被两处交巡警接警，当有交巡警服务平台的路口可不另安排其他警力，就可将上面交巡警服务平台所辖范围进一步得以优化，使案发时其所属的交巡警服务平台能在最短的时间内到达，优化后所管辖的范围如图2。图3 A1-A20号交巡警服务平台所管辖范围5.2 交巡警服务平台警力的调度方案5.2.1 整数规划模型的准备由 A区的已有的20个交巡警服务平台知道，要在接到处理重大突发事件的通知后，能快速完全地完成对A城区的13个交通要道进行封锁，既要满足每个交通要道的警力要求，又要满足最短的时间要求，所以该问题可以转化为20个交巡警平台与13个交通要道的优化配置的问题.以交巡警平台和交通要道为顶点，构成无向图,该无向图的邻接矩阵为，为矩阵中的元素该无向图的邻接矩阵表示如下：矩阵中各元素可以采用0-1表示，即 由题目给出的各个交巡警平台及交通要道的点的坐标，我们可以利用解析几何中计算任意两坐标点之间的直线距离公式：，用MatLab软件计算求出任一交巡警平台到每一个交通要道的直线距离，（程序见附见2.1）并得到关于的矩阵。距离矩阵表示如下： 通过邻接矩阵与距离矩阵的点乘来计算得到相邻接点间的距离和来求得该实际路程。实际路程矩阵为,即： 利用Floyd算法, 通过LINGO编程求出任意交巡警服务平台到交通路口两点间最短距离，得到最短距离矩阵（具体程序参考附件1.3）； 由于各个交巡警服务平台出警的目的地不尽相同，所以引入0-1变量模型： ，（）建立出警封锁调度矩阵：5.2.2整数规划模型的建立由于到第个交通路口出警的交巡警服务平台个数为，根据题目要求可知，各服务平台必须快速完全地进行出警，即是需要各个交巡警服务平台出警所用的总时间最少，所以对问题的求解可以转化为对目标函数的整数规划问题。目标函数为：由题意知，一个交巡警服务平台最多能封锁一个路口，即每个交通路口至少有一个交巡警平台，即。在A城区内交巡警服务平台的数量一定，即。综合以上分析，约束条件为：5.2.3整数规划模型的求解 对以上整数规划模型，运用Lingo软件求解得如下结果如图3（程序见附件2.2）。 图4 交巡警服务平台警力的封锁调度图5.3交巡警服务平台的优化 根据问题一分析出各交巡警服务平台的工作量不均衡和有些地方出警时间过长，需要增设交巡警服务平台。利用综合分析法，分析交巡警服务平台到道路交叉口的距离和各道路交叉口的报案率二个因素指标。建立二个因素之间的关系模型，可以算出交巡警每天实际走的路径，继而求出20个交巡警服务平台对各自管辖区的实际路径，即工作量。可以对工作量较大进行增设交巡警服务平台。取问题一中已有的20个交巡警服务平台的代表性较强一个交巡警平台管辖区分析。由图2交巡警服务平台所管辖范围图选出A5，如下图4分析交巡警服务平台A5到所管辖区内的道路及道路交叉口的报案率。图5 A5服务平台的路径与报案率由图5 A5服务平台的路径与报案率的数据，计算出A5服务平台分别到所管辖的道路交叉点的距离和报案率。依据综合因素分析法，建立距离和报案率的二个指标因素的关系模型。各道路交叉口报案率为，分析可知综合指标因素就是交巡警服务平台在所管辖区域要走的实际路程为，距离和报案率的二个指标因素的关系模型为：由距离和报案率的二个指标因素的关系模型计算的综合因素指标（交巡警服务平台在所管辖区域要走的实际路程）如下表5。表5 综合因素指标交叉路口5474951525356路程和服务距离（km）0.001.460.501.231.651.172.07交叉口报案率2.101.601.200.800.601.400.50各路口综合指标0.002.340.600.740.991.641.047.35同理，建立综合因素分析模型其他19各交巡警服务平台所管辖区分析交巡警服务平台在所管辖区域要走的实际路程。计算结果如下表6。表6 各服务管辖区综合因素指标服务平台管辖区A1A2A3A4A5A6A7综合因素指标6.285.957.2410.867.355.466.75服务平台管辖区A8A9A10A11A12A13A14综合因素指标3.854.2908.91011.230服务平台管辖区A15A16A17A18A19A20综合因素指标12.78.494.835.124.5912.14从上面表6中，交巡警服务平台A4、A13、A15、A20四个管辖区的综合因素指标，即交巡警服务平台在所管辖区域要走的实际路程大于10km。由综合因素分析法的经验值，可得城区A需要在这四个管辖区个增设一个交巡警服务平台，具体位置如下表7。表7 需增设交巡警服务平台的具体信息需增设的交巡警服务平台A21A22A23A24交巡警平台的横坐标（x）369212246448交巡警平台的纵坐标（y）380290337381服务平台位于的道路交叉口602428875.4 市区现有交巡警服务平台的评价和优化 5.4.1 现有交巡警服务平台的分析评价 根据问题一建立模型求解，在城区A,可知20个交巡警服务平台为道路交叉口服务不能完全使其在所管辖的范围内出现突发事件时， 在3分钟内有交巡警车 到达事发地。所以城区A中的交巡警服务平台的设置不合理。推而广之，市区中的交巡警服务平台的设置不合理。5.4.2多目标规划交巡警服务平台根据题目的要求，本文建立一个多目标决策模型。要求每个道路交叉路口都在其所属的交巡警服务平台管辖范围内，可用下式表达： （1）上式中，i,j分别表示交巡警服务点和道路交叉点，如果i , j 之间的距大于约束距离,表示在道路交叉点i处不建立交巡警服务平台，否则为1 ,表示此处可建立交巡警服务平台。因此通过此条标准利用MATLAB7.0软件可初步地排除如下候选点，这里得求解排除点为。建立具体的设置全市交巡警服务平台的多目标规划模型如下: （2） （3） s.t. （4） （5） （6） （7） （8）上式中,为城区的权重；为交巡警服务点至道路交叉点的距离；为交巡警服务点管辖城区；为全市已有的交巡警数;为道路交点所属的最少交巡警服务平台数。模型的说明,上式(1) 和约束式(5) 表示不同交巡警服务平台候选点至各个交叉路口节点点的最大距离最小化；式(2) 表示不同交巡警服务平台至各个交叉路口节点的加权距离和最小化；约束式(3)和约束式(4)表示全市现有交巡警服务平台总数不超过p 个。 上述模型是设置全市交巡警服务平台设置的多目标规划模型。常见求解多目标规划的方法有功效系数法、评价函数法、约束法、分成序列法等。结合该模型的特点,采用线性加权和法,这种方法计算起来比较简单,也应用较多,即将多目标化为单目标决策问题来求解,这样处理的好处是能在各目标权重选择时体现决策者对于不同目标的偏好,通过对权重赋值的不同,直观地体现不同目标倾向对于选址决策的影响,从而综合各方面要求最优化设施选址。对于上述多目标问题,根据各目标重要程度给出权1 ,2 ,3 ,其中:令评价函数为:上述多目标规划可以转化成如下形式:5.4.3 优化交巡警服务平台的实施该市地点P，即第32 道路交叉点处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。可知已逃出该交叉点所属A7交巡警服务平台所管辖区域，但还在城区A。在上述多目标规划模型中，已经给出交巡警服务平台的设置和位置，利用该市的五个区的所有交巡警对其围堵。由问题分析可知，先要对城区A的13各交通要点实施全方位封锁，然后对罪犯实施抓捕。具体实施方案如右图6。 图6 最佳围堵方案6.模型评价问题一所建最短路径模型，先假设各交巡警平台接警后赶赴事发现场的途中无障碍，即是能按原速度到达。结合图论知识，以个各交巡警平台及各公路的交点为顶点，构建了赋权无向图。并以此建立最短路径模型，运用Floyd算法求解出相邻两点之的最短距离，使得整个问题得以简化求解，并最终为各个交巡警平台管辖范围的确定给出最优分配方案。但用此模型解决的问题较为理想，忽略了实际生活中的道路阻塞等不可预知的因素的影响，所以用此最短路径模型解决局部问题的效果很好，若解决全局问题，可能会得到不太完美的结果。问题二所建的整数规划模型，采取同问题一相同的方法进行问题假设，以该区域里的13个交通要道及20个交巡警平台为顶点，构成无向图，运用Floyd算法求解出各个交巡警平台到个交通要道的最短距离，引入0-1变量，再建立整数规划模型，对原问题一步步地进行简化求解，最终得到最合理的警力调度方案。由于实际中两点之间的道路并非平直，并且忽略了各个交巡警平台接警后的反应时间，导致计算结果会出现一些偏差，所以解决实际问题时，还需要对模型做进一步的完善处理。问题三的综合因素分析法，依据综合因素分析法对每个交巡警服务平台管辖区的综合指标分析与求解，考虑了交巡警服务平台到道路交叉口的距离和各道路交叉口的报案率二个因素指标。建立二个因素之间的关系模型，可以算出交巡警每天实际走的路径，即综合因素指标。对于本问题考虑的因素稍有片面，可以再加上案件的处理时间。 问题四所建的多目标决策模型，把交巡警服务平台设置问题转化多目标规划问题，建立多目标决策模型所给出的算法却不适用于所有的图。尤其对重复路线的考虑不够完全。模型的求解对软件编程依赖性太强。7.模型改进与推广在本文模型一、二中，交巡警服务平台管辖区的划分可以归结为数学规划模型 ,模型以最小化平均反应时间为优化目标 ,综合考虑服务时间、道路网、消防站和需求节点的空间分布、工作量约束等因素，因此，在进行区域化方案的确定的时候，建立最短距离模型由于受范围的影响较大，使得计算结果不能很准确地得到应用，并且该模型也受到范围大小的影响，适用性不大。可以考虑采用综合风险分析法对整个区域进行类别的划分，再建立p-中心模型进行定点的最大覆盖范围求解，最终得到的规划方案会更符合实际。在综合因素分析法中，对问题三利用综合因素分析法考虑的因素稍有片面，可以再加上案件的处理时间等因素。而后，对各因素求相应权值，建立模型; 。表示处理各案件时间，表示各因素指标的权值。本题中的综合因素分析法可以在其他类似于影响因素问题。在本文模型四中，所给出的算法却不适用于所有的图。尤其对重复路线的考虑不够完全。可以进行适当的改进和补充，使之满足一般图的情况。在给出的全市交通图中，每个行政区域是由众多道路交叉口组成的，如果将他们看成网络中的顶点，每个道路口的发案率作为顶点的权重，连接它们的道路看成网络中的顶点，每个道路口的发案率作为顶点的权重，连接它们的道路看成网络中的弧，那么整个应急系统可以看成一个无向赋权网络图，此问题的数学模型可看作是顶点赋权并附加约束条件的绝对单重心问题，从而扩展了模型的应用范围。8.参考文献1 孙祥，MATLAB 7.0基础教程,北京：清华大学出版社，2005。2 赵静，但琦，数学建模与数学实验M,北京：高等教育出版社，2003。3 姜启源.谢金星.叶俊.数学建模M,北京:高等教育出版社,2003。4 许洪范，数学建模教程，北京：国防工业出版社，2007。5 陈培森, 道路交通应急调度策略研究, 漳州师范学院学报, 2009.46 魏汝营，杨立兵，突发事件应急救援设施选址决策模型，长沙：中南大学资源与安全工程学院,410083。 7 王海英，黄强等，图论算法及其MATLAB实现，北京：北京航空航天大学出版社，2010。8 Frank R. Giordano、Steven B.Horton等：A First Course in Mathematical Modelng.(Fourth Edition) 机械工业出版社 2009年8月。附录附件1.1 道路距离MATLAB运算程序clear,clc c=xlsread(data.xls,sheet1,A1:E582);b=xlsread(data.xls,sheet2,A1:B143);a=c(1:92,:);m,n=size(a);x=a(:,2);xx=x(1:20,:);y=a(:,3);yy=y(1:20,:);plot(xx,yy,r.)hold onplot(x(21:end,:),y(21:end,:),b.)for i=1:m text(x(i),y(i),num2str(i);endp=b(:,1);q=b(:,2);zb=c(p,2) c(p,3) c(q,2) c(q,3);t=sqrt(zb(:,1)-zb(:,3).2+(zb(:,2)-zb(:,4).2);xlswrite(data.xls,t,sheet2,C1)附件1.2 各相邻交叉点有道路直接相连的路径 路线起点(节点）标号1 1 2 3 3 4 4 5 5 6 路线终点(节点）标号75 78 44 45 65 39 63 49 50 59 终起点的距离（km）0.9 0.6 0.9 4.2 1.5 4.6 1.0 0.5 0.8 1.6 路线起点(节点）标号7 7 8 8 9 10 11 11 12 14 路线终点(节点）标号32 47 9 47 35 34 22 26 25 21 终起点的距离（km）1.1 1.3 1.2 2.1 0.4 4.9 3.3 0.9 1.8 3.3 路线起点(节点）标号15 15 16 16 17 17 17 18 18 19 路线终点(节点）标号7 31 14 38 40 42 81 81 83 79 终起点的距离（km）3.8 3.0 6.7 3.4 2.7 1.0 4.0 0.7 0.5 0.4 路线起点(节点）标号20 21 22 23 24 24 25 26 26 27 路线终点(节点）标号86 22 13 13 13.0 25 11 27 10 12 终起点的距离（km）0.4 1.8 0.9 0.5 2.4 1.8 2.0 0.7 3.5 3.3 路线起点(节点）标号28 28 29 30 30 31 31 32 33 33 路线终点(节点）标号29 15 30 7 48 32 34 33 34 8 终起点的距离（km）0.9 4.8 7.4 0.6 0.7 1.2 1.6 0.5 0.8 0.8 路线起点(节点）标号34 35 36 36 36 36 37 38 38 39 路线终点(节点）标号9 45 35 37 16 39 7 39 41 40 终起点的距离（km）0.5 0.7 0.5 0.5 0.6 3.5 3.0 0.3 4.0 1.8 路线起点(节点）标号40 41 41 42 43 43 44 45 46 46 路线终点(节点）标号2 17 92 43 2 72 3 46 8 55 终起点的距离（km）1.9 0.9 4.6 0.8 0.8 0.8 1.2 0.6 0.9 2.9 路线起点(节点）标号47 47 47 48 49 49 50 51 51 52 路线终点(节点）标号48 6 5 61 50 53 51 52 59 56 终起点的距离（km）1.0 1.5 1.5 2.9 1.0 0.7 0.4 0.4 0.3 0.4 路线起点(节点）标号53 53 54 54 55 56 57 57 57 58 路线终点(节点）标号52 54 55 63 3 57 58 60 4 59 终起点的距离（km）0.9 2.3 1.0 2.4 1.3 1.2 0.8 0.8 1.9 0.8 路线起点(节点）标号60616262636464656666路线终点(节点）标号6260485646576666776终起点的距离（km）1.4 3.5 0.4 6.0 0.9 0.6 1.3 0.3 0.4 0.9 路线起点(节点）标号67676868696969707071路线终点(节点）标号446869757071124372终起点的距离（km）1.5 0.4 0.7 0.5 0.5 0.6 0.5 0.9 0.8 0.5 路线起点(节点）标号717273737474 75767777路线终点(节点）标号7473741818076777819终起点的距离（km）0.6 0.8 0.4 2.0 0.6 1.7 0.4 0.4 1.0 1.0 路线起点(节点）标号78798081828283848586路线终点(节点）标号79801882839084852087终起点的距离（km）0.7 0.4 0.8 0.5 0.5 0.9 1.0 0.7 0.4 1.1 路线起点(节点）标号86878788888989899091路线终点(节点）标号88889289912084909192终起点的距离（km）0.9 0.4 2.1 0.4 0.3 0.9 0.3 0.4 0.5 2.0 附件1.3Floyd 算法程序model: sets: !nodes; nodes /A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18,A19 A20F21,F22,F23,F24,F25,F26,F27,F28,F29,F30,F31,F32,F33,F34,F35,F36,F37,F38,F39,F40, F41,F42,F43,F44,F45,F46,F47,F48,F49,F50,F51,F52,F53,F54,F55,F56,F57,F58,F59,F60, F61,F62,F63,F64,F65,F66,F67,F68,F69,F70,F71,F72,F73,F74,F75,F76,F77,F78,F79,F70, F71,F72,F73,F74,F75,F76,F77,F78,F79,F80,F81,F82,F83,F84,F85,F86,F87,F88,F89,F90, F91,F92 /; !dmin(i,j) i j path1 ;link(nodes, nodes): w, path1; supply/A1.A20/; need/F21.F92/; linkf(supply, need):dmin; endsets data: path1=0; w=0; a=file(c:data5.txt) enddata calc: !; w(a(:,1),a(:,2)=a(:,3);for(link(i,j): w(i,j) = w(i, j)+w(j,i) ); !; for(link(i,j)|i#ne#j: w(i,j)=if(w(i,j) #eq#20000,w(i,j); ! ; !Floyd-Warshall ; for(nodes(k):for(nodes(i):for(nodes(j):tm=smin(w(i,j),w(i,k)+w(k,j); path1(i,j)=if(w(i,j)#gt# tm,k,path1(i,j);w(i,j)=tm); for(link(i,j)|i #le# 10 #and# j#ge#18 #and# j#le# 35:dmin(i,j-17)=w(i,j); ! 10!18;