关于洒水车路线设计-基于中国地质大学.docVIP

关于洒水车路线设计-基于中国地质大学 摘要：本文提出中国地质大学洒水车的路线问题，结合中国地质大学路面的实际情况将其进行抽象,建立了图论模型。并引进了“中国邮路问题”的理论与算法对问题进行求解。 关键词：中国邮路问题 佛罗莱算法 奇偶点作业法 图论模型 一、问题提出 中国地质大学的洒水车要给主要路面洒水，该如何确定行车路线？ 二、问题分析 我们首先根据中国地质大学的实际情况确定需要洒水的路段。由校园的平面图，并进行的细化，绘制出在尺度上大致准确的示意图。洒水车要给主要路面洒水，也就意味着行车路线必需经过图示所有的路面至少一次。这类似于图论中一个典型的问题：中国邮路问题。中国邮路问题说的是：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么该如何选择投递路线，使所走的路程最短。 图1 三、假设与符号约定 假设： 洒水车行驶过一次即能满足路面的洒水要求； 洒水车一次加水，即有足够水量给图示所有路面洒水,或者用完水后能在可以忽略路程内加水； 符号约定： ：图的第个节点； ：图中连接第个顶点与第个节点的边； ：边上的权； ：以为节点集，以为边集的图； :以为起点为终点的路； ：图的第个节点的度数； ：图的一个附加边子集； ：边集的总权； ：经过边的次数； ：最短路矩阵 四、一些基本概念、算法和定理 下面是本文将要用到的一些基本概念、算法和定理： 欧拉回路：设G(V,E)为一个图,若存在一条回路,使它经过图中的每条边且只经过一次又回到起始节点,就称这种回路为欧拉回路,并称图G为欧拉图。 节点的度数：连接节点的边数为此节点的度数。当为奇数时，称为奇节点；否则，称为偶节点。 附加边子集：将图的奇节点配对，每对节点之间在图中有相应的最短路，连接这些最短路即构成一个附加边子集。 佛罗莱算法（Fleury Algorithm）： Step 1：任取起始节点，取连接这起始节点的任一边 为初始路，即； Step 2：设路已经选出，则从中选出边，使与相连，除非没有其他选择。不应为的断边，即仍为连通图； Step 3：重复Step 2直到不能进行下去为止。 确定邮路问题最优路线的定理（证明从略）: 设为一个连通的赋权图，则使附加边子集的权数为最小的充要条件是（1）中任意边至多重复一次；（2）中的任意回路中重复边的权数之和不大于该回路总和的一半。 上面定理的证明给我们提供了一般情况下寻求最优投递路线的方法,即奇偶点作业法: Step 1：任给初始方案，使图的各节点的度数为偶数，图成为边权的欧拉图； Step 2：检查每一回路中重复边的长度和是否超过回路长度的一半，如是，则现行方案即为最优解，否则进行下一步； Step 3：调整重复边，即将回路中重复的边改为不重复，不重复的边改为重复，返回Step 2。 五、模型的建立与求解 根据前面的假设与示意图,我们建立如下的图论模型: Min S.T. 图注:为使图看起来简洁，节点和边的编号未在图上标出，只是标出边上的权（单位为m），即边上的长度。 进行求解即在图中寻找最优的“邮递员路线”: 图2 Step 1:找具有奇度数的节点并进行标号，依次为：A1，B1，A2，B2，A3，B3。不妨按A1与A2，B1与B2，A3与B3进行配对，如图 3。求其最短路，添加重复边，如图 3上的曲线。 图3 Step 2:在图 3中可以找到一个包含A1，B1，A2回路使得其不满足邮路问题的最优解的充要条件即A1到A2的最短路长(130+90)=220 m加上A2到B1的路长130为350 m大于包含A1，B1，A2的最小回路的路长130+130+90+90=440 m的一半220 m。于是按奇偶点作业法调整重复边如图 4 图4 Step 3:对图 5进行检查,发现已经满足定理的充要条件。 按佛罗莱算法在图 5寻找得到一条欧拉回路为如图 5示。 图5 这条路线的总长度为：2900 m，其中重复走的路长为280 m。由前面的定理即可验证这是一条最优路线。 参考文献： [1] 《运筹学》教材编写组，运筹学，清华大学出版社，2005 [2] 肖位枢,图论及其算法,航空工业出版社,1993 [3] /maps?hl=zh-cntab=wl 350 350 250 130 90 130 90 90 260 90 130 60 200 100 50 250 250 50 100 200 60 90 90 260 90 130 130