12.2 物流运输线路优化模型在线视频

同学们

今天我们来学习

物流运输线路优化方法

物流运输线路规划

通常采用最短路线

即从运输起点到终点的最短路

最短路度量单位可能是时间

也可能是成本费用最省

常见的最短路优化问题

包括点到点运输

多点间运输以及回路运输问题

这里我们着重讲解

点到点运输的最短路问题

对于分离的单个起点

和终点的点到点运输线路选择问题

最简单和最直观的方法

就是最短路径法

解决最短路径法有以下几种算法

Dijkstra算法

Bellman-Ford算法

Floyd算法和SPFA算法等

Dijkstra算法是由

荷兰计算机科学家狄克斯特拉

于1959 年提出来的

因此又叫狄克斯特拉算法

是从一个顶点到其余各顶点的

最短路径算法

解决的是有向图中最短路径问题

该算法的基本思路是

在一个连通图中

G(Vn.Em) 中求解

从V0到Vn的最短路径时

首先找出从V0出发的一条最短路径

再参照它求出一条次短路径

由此类推

直到从顶点V0到Vn顶点的

最短路径为止

Dijkstra算法

可采用标号法来求解

标号是用来标记各个节点的属性

的一套符号

标号法中可用两种标号

T标号和P标号

T标号为试探性标号

P标号为永久性标号

算法是每步

都把某一点的T标号改为P标号

当终点得到P标号时

则计算结束

标号法的计算步骤如PPT所示

下面我用一例题来具体讲解

标号法求解点到点的最短路径问题

如图所示

该图为单行线交通网络图

用Dijkstra算法

求v1到v6的最短路

第一步首先给v1以P标号

Pv1＝0

给其余所有点T标号

Tvj＝＋∞

第二步我们观察到与永久标号点

V1

直接相连的有V2 v3 点

v2 v3为T标号

所以修改这两个点的标号

Tv2=Tv2与Pv2+L12

取小值及无穷大

与0+3取小的数等于3

Tv3=Tv3与Pv3+L13

取小值及无穷大

与0+5取小的数等于5

比较所有T标号

Tv2最小所以令Pv2=3

记录路径v1 v2

对V2进行永久标号

第三步观察与已经永久标号的

点V1 v2直接相连

而且为T标号的点为V3 V4

考察v2 v3

v2 v4的端点v3 v4

Tv3=Tv3与Pv2+L23

取小值

及5与3+1取小的数等于4

Tv4=Tv4与Pv2+L24

取小值

及无穷大与3+6取小的数等于9

比较所有T标号

Tv3最小

所以令Pv3=4

记录路径v2v3

V3进入永久标号

第四步观察与已经永久标

的点V1v2V3直接相连

而且为T标号的点为v4 v5

Tv4=Tv4与Pv3+L34

取小值

及9与4+4取小的数等于8

Tv5=Tv5与Pv3+L35

取小值

及无穷大与4+1取小的数等于5

比较所有T标号

Tv5最小

所以令Pv5=5

记录路径v3 v5

V5进入永久标号

第五步观察与已经永久标号

的点V 1v2 V3 V5直接相连

而且为T标号的点为v4 V6

Tv6=Tv6与Pv5+L56

取小值

及无穷大与5+6取小的数等于11

Tv4=Tv4与Pv5+L45

取小值

及8与4+1取小的数等于7

及8与4+1取小的数等于7

比较所有T标号

Tv4最小

所以令Pv4= 7

记录路径v5 v4

V4进入永久标号

第六步观察与已经永久标号的

点V1 v2 V3 V5

V4直接相连而且

为T标号的点为V6

Tv6=Tv6与Pv4+L46

取小值

及11与7+3取小的数等于10

终点V6进入P标号

全部点均为P标号则停止计算

v1到v6的最短路可从v6开始

根据永久性标号数值回溯得到

其最短路径为

v1到v2到v3

到v5到v4到v6

路长为10

好的

今天就讲到这

感谢聆听