第9章 配送线路规划.ppt

&1线路优化模型第9章配送线路规划点点间运输多点间运输单回路运输多回路运输&------最短路径求解方法最短路径问题的应用:各种管道铺设,线路安排,厂区布局,旅游,道路修筑,道路选择等最短路径问题常分为两类:(1)从起点到其它各点的最短路径;(2)求任意两点间的最短路径。连通图:任何两点间至少有一条链连接。连通图的最短路径问题:求两个顶点间长度最短的路程。如费用、(Vn,Em),图中每条弧(i,j)都有一个权重Cij,则最短路径问题为:在G(Vn,Em)中找到一条从节点V1到节点Vn总权重最小的路径。(Vn,Em),权重C=(Cij),目标函数:其中,A为从V1到Vn的一条路径。.(1)两点之间的弧线距离为整数(在现有算法下,已经不需要考虑);(2)在连通图中,从任意端点到其他所有的端点都有直接的路程,如存在不直接相连的端点,则可设。(3),(4)连通图是有方向性的。即我们讨论的问题为:有向且的连通图的最短路问题。并设::主要算法:Dijkstra算法、逐次逼近算法、Floyd算法。Dijkstra算法基本思路在G(Vn,Em)中,求解从V1到Vn的最短路径时,先求出从V1出发的一条最短路径,再参照它求出一条次短的路径,依次类推,直到从V1到Vn的最短路径求出为止。Dijkstra算法的依据定理:如果序列是从V1到Vn的最短路径,则子序列也必然是从V1到Vn-1的最短路径。Dijkstra算法中的标号标号:在Dijkstra算法中用来标记各节点的属性的符号。对于每一个节点Vj,都赋予一个标号,标号分为T标号和S标号两种:(多数教材永久标号记为P。Permanent)T标号:表示从V1到Vj的最短路径的上界,称为临时标号;TemporaryS标号:指V1到Vj的最短路径,称为固定标号。注:得到S标号的点不再改变。算法的每一步把某一点的T标号改变为S标号,直至Vn变为S标号。根据标记确定节点Vj的标号属性和标记过程的不同,有两种不同的Dijkstra算法:①标号设定算法(Label-SettingAlgorithm)思路:在每一步迭代中用试探性标号标记所有的试探点,通过一系列的试探寻找该步中的最短路径。并将每一次迭代中得到的满意的试探标号设置为永久标号。适用:只适用于求解非负网络中的最短路径问题。