第9章配送线路规划.ppt

第9章配送线路规划
点点间运输
多点间运输
单回路运输
多回路运输
&1线路优化模型
点点间运输------最短路径求解方法
最短路径问题的应用：各种管道铺设，线路安排，厂区布局，旅游，道路修筑，道路选择等
最短路径问题常分为两类：
〔1〕从起点到其它各点的最短路径；
〔2〕求任意两点间的最短路径。
连通图：任何两点间至少有一条链连接。
连通图的最短路径问题：
求两个顶点间长度最短的路程。
如费用、影响等
路径上各边的权值之和
1. 最短路径问题的描述
设有一n个节点和m条弧的连通图G(Vn,Em)，
图中每条弧(i , j)都有一个权重Cij,那么最短路径
问题为：在G(Vn,Em)中找到一条从节点V1到
节点Vn总权重最小的路径。
2. 建模
设连通图G(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的最短路径的上界，称为
临时标号；Temporary
S标号：指V1到Vj的最短路径，称为固定标号。
注：得到S标号的点不再改变。算法的每一步把
某一点的T标号改变为S标号，直至Vn变为S标号。
根据标记确定节点Vj的标号属性和标记过程的不
同，有两种不同的Dijkstra算法：
①标号设定算法〔Label-Setting Algorithm〕
思路：在每一步迭代中用试探性标号标记所有的
试探点，通过一系列的试探寻找该步中的最短路
径。并将每一次迭代中得到的满意的试探标号设
置为永久标号。
适用：只适用于求解非负网络中的最短路径问题。