第4章 物流运输路径规划.ppt

1、第4章 物流运输路径规划,4.1 图与网络的基本概念 4.2 最短路径问题 4.3 运输流量问题 4.4 单回路运输路线问题 4.5 多回路运输路线,第4章 物流运输路径规划,本章重点： 图论是运筹学的一个分支，是建立和处理离散数学模型的一个重要工具。本章中学生要了解图论的基本概念，掌握最短路径问题的狄克斯屈标号法和运输流量问题的福特富尔克逊标号法，了解单回路运输路线问题和多回路运输路径。,返回,4.1 图与网络的基本概念,图论（Theory of Graphs或Graph Theory）是应用非常广泛的运筹学分支，是建立和处理离散数学模型的一个重要工具。图论的起源最早可追溯到1736年欧拉所

2、发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。直到20世纪中叶，随着离散数学和计算机技术的发展，图和网络的研究更是得到了飞速发展。目前，网络分析的理论已经在工程设计、管理科学、交通规划、通信网络规划等众多领域中得到广泛应用，并取得了丰富的成果。,下一页,返回,4.1 图与网络的基本概念,4.1.1 图和图解 1. 图的基本结构 首先看一个图的实例。图4-1是某地7个村镇之间的道路交通示意图，点、分别表示7个村镇，各村镇之间的连线称为道路。 （1）结点用来表示物理实体或事物，一般用vi来表示。例如，图4-1中的结点就是各村镇。 （2）边是结点间的连线，表示两结点之间的关系，一般表示为e =

3、（vi，vj）。,下一页,返回,上一页,4.1 图与网络的基本概念,2. 无向图和有向图 若某一图中所有边之间都没有方向，则称该图为无向图。无向图一般用G=（V，E）表示，其中，V = v1，v2，vn表示点的集合，E = eij 表示边的集合。 若某一图中所有边都有方向，则称该图为有向图。在有向图中，有方向的边又称为弧。有向图用D=（V，A）表示，A = aij 表示弧的集合，其中a = （vi，vj）。,下一页,返回,上一页,4.1 图与网络的基本概念,3. 图解 若用平面上的点表示图G的结点，用连接相应的结点而不经过其他结点的线表示图G的边，所画出的图形称为图G的平面图解，简称图解。由于

4、对结点的位置和边的形状的选取具有随意性，因此一个图可以有几种形状迥异的图解。图4-2（a）和（b）为同一个无向图的图解，图4-2（c）和（d）为同一个有向图的图解。,下一页,返回,上一页,4.1 图与网络的基本概念,4.1.2 几个基本概念 1. 端点，关联边，相邻。若有e = （vi，vj），则称vi，vj是e的端点，称e是vi，vj的关联边。若点vi与vj跟同一条边相关联，则称点vi与vj相邻，若边ei与ej有一个公共端点，则称边ei与ej相邻。 2. 环，多重边，简单图。若一条边的两个端点是同一结点，则称该边为环；若两个端点之间不止一条边，称为具有多重边；无环也无多重边的图称为简单图。以

5、下讨论的图多指简单图。,下一页,返回,上一页,4.1 图与网络的基本概念,3. 次，奇点，偶点。点v的关联边的数目称为点v的次。次为奇数的点称为奇点，次为偶数的点称为偶点。图4-2（a）中v1的次为3，所以是奇点；图4-2（c）中v1的次为2，所以是偶点。 4. 链，圈，路。一个图中相邻结点与相邻边的序列v1，e1，v2，e2，en-1，vn称为一条从v1到vn的链。若v1与vn重合，则该链为闭链，在一个闭链中，若任意两点均不同，且所有的边也均不相同，则称为一个圈。若交替序列是有向图D =（V，A）的一条链，则称是图D的一条从v1到vn的路。,下一页,返回,上一页,4.1 图与网络的基本概念,

6、5. 连通图。在一个图种，若任意两点之间至少存在一条链，则称该图为连通图，否则称为不连通图。图4-1和图4-2都是连通图，而图4-3不是连通图。 6. 网络，权。一个图连同定义在其边集上的实函数w（vi，vj）一起称为一个网络。网络一般是连通图。记wij=w （vi，vj），称为边（vi，vj）的权数。,返回,上一页,4.2 最短路径问题,4.2.1 狄克斯屈标号法 该法是Dijkstra在1959年提出的，适用于所有权数均为非负（即一切wij0）的网络（对于负权网络，该法有时失效），能够求出网络的任一点到其他各点的最短路，使目前求这类网络最短路的最好算法。 该法直接在网络上对每一个点标号，标

7、号分为两种：临时标号T（vj）和固定标号P（vj）。在网络中，固定标号以带括号的数字表示，临时标号不带括号。网络中一个点的临时标号表示从始点到该点的最短路长的上界，固定标号表示最短路长。在标号过程中，临时标号不断被新的更小的临时标号所替代，直到不能再减小为止，就得到该点的固定标号。计算步骤如下：,下一页,返回,4.2 最短路径问题,（1）给始点标固定标号（0）； （2）给与（0）点相邻的各点标上临时标号，标号数值为始点固定标号值加上始点到该点间边的权数； （3）从所有的临时标号里找最小的确定为固定标号，对该最小临时标号打上括号； （4）从新得到的固定标号出发，给相邻的没有固定标号的点打上临时标

8、号。对于没有标号的点，标号数值为出发点的固定标号值加上两点间边的权数；对于已有临时标号的点，新的临时标号比原有临时标号小的，替换为新的临时标号，否则保持原有临时标号不变； （5）回到3，重复上述步骤，直到所有的点都被标上固定标号为止。,下一页,返回,上一页,4.2 最短路径问题,例4-1 求图4-1中点1到点7的最短路。 解：在图4-1所示网络中，先给出始点的三条关联边的终点、的临时标号，分别为T（2）= 0+3=3，T（3）= 0+4=4，T（4）= 0+7= 7；从中选出最小标号3，改为固定标号（3），此时，T（2）=3改为P（2）=（3），实际上得到了点到点的最短路长为3，如图4-4（a

9、）所示。从新得到的固定标号点出发，检查与其相邻并且没有固定标号的点、，确定临时标号如下：,下一页,返回,上一页,4.2 最短路径问题,点：min T（3），P（2）+w23 =min 4，3+3= 4，即T（3）=4 点：min T（4），P（2）+w24 =min 7，3+2= 5，即T（4）=5 点：min T（5），P（2）+w25 = min，3+4=7，即T（5）=7 从所有的临时标号中选出点的最小标号4，改为固定标号（4），此时，T（3）=4改为P（3）=（4），又得到了点到点的最短路长为4，如图4-4（b）所示。从新得到的固定标号点出发，检查与其相邻并且没有固定标号的点、，确定临

10、时标号如下：,下一页,返回,上一页,4.2 最短路径问题,点：minT（5），P（3）+w35 = min7，4+5= 7，即T（5）=7 点：minT（6），P（3）+w36 = min，4+7= 11，即T（6）=11 从所有的临时标号中选出点的最小标号5，改为固定标号（5），此时，T（4）= 5改为P（4）=（5），又得到了点到点的最短路长为5，如图4-4（c）所示。从新得到的固定标号点出发，检查与其相邻并且没有固定标号的点，确定临时标号如下：,下一页,返回,上一页,4.2 最短路径问题,点：minT（5），P（4）+w45 = min7，5+2= 7，即T（5）=7 点：minT（7）

11、，P（4）+w47 = min，5+6= 11，即T（7）=11 从所有的临时标号中选出点的最小标号7，改为固定标号（7），此时，T（5）= 7改为P（5）=（7），我们又得到了点到点的最短路长为7，如图4-4（d）所示。从新得到的固定标号点出发，检查与其相邻并且没有固定标号的点，确定临时标号如下：,下一页,返回,上一页,4.2 最短路径问题,点：minT（6），P（5）+w56 = min11，7+1= 8，即T（6）=8 点：minT（7），P（5）+w57 = min11，7+4= 11，即T（7）=11 从所有的临时标号中选出点的最小标号8，改为固定标号（8），此时，T（6）= 11改

12、为P（6）=（8），我们又得到了点到点的最短路长为8，如图4-4（e）所示。从新得到的固定标号点出发，检查与其相邻并且没有固定标号的点，确定临时标号如下：,下一页,返回,上一页,4.2 最短路径问题,点：minT（7），P（6）+w67 = min11，8+2= 10，即T（7）=10 此时，只有一个临时标号10，将其改为固定标号，T（7）=11改为P（7）=（10），得到了点到点的最短路长为10，如图4-4（f）所示。至此，所有的点都已得到固定标号，问题求解结束。 由此可以看出，点到点的最短路有两条： ,下一页,返回,上一页,4.2 最短路径问题,4.2.2 距离矩阵摹乘法 该算法适用于求任

13、何网络的最短路，它比狄克斯屈标号法要复杂些，但应用范围广，对于任何含负权的网络都适用。 1. 网络的距离矩阵 设一个网络N中有n个结点，对于网络中相邻的点，两点间的距离即为边的权数；不相邻的两点，其距离设为。这样可以定义一个矩阵W=（wij）nn称为网络N的直接距离矩阵，简称距离矩阵。如图4-1所示的网络的距离矩阵为：,下一页,返回,上一页,4.2 最短路径问题,2. 求各点至某点的最短路 （1）建立网络的直接距离矩阵，行表示“从”列表示“至”。,下一页,返回,上一页,4.2 最短路径问题,（2）找出到达的点所在的列，右摹乘距离矩阵，进行摹乘运算。所谓摹乘运算，顾名思义，是模仿矩阵相乘运算，在

14、矩阵相乘中，对应元素相乘后求和，得到新矩阵对应元素，而在摹乘运算中，是对应元素相加后求最小值，得到新矩阵对应元素。 （3）得到的列向量继续右摹乘距离矩阵，直到与前一个摹乘结果相同则得到最短路长。 （4）在距离矩阵中寻找与列向量相加得到最短路长的元素，给该元素加标记。 （5）按每行加标记数字对应的“从/至”关系，就得到各点到某点的最短路。,下一页,返回,上一页,4.2 最短路径问题,例4-2 求图4-1中各点至点的最短路。 解：已知网络的直接距离矩阵，求各点到点的最短路，从距离矩阵中找出v7的列向量d1，右摹乘距离矩阵W。中的元素计算式如下： min0+,3+,4+,7+6,+4,+2,+0=1

15、3 min3+,0+,3+,2+6,4+4,+2,+0=8 min4+,3+,0+,+6,5+4,7+2,+0=9 min7+,2+,+,0+6,2+4,+2,6+0=6 以下依次类推。,下一页,返回,上一页,4.2 最短路径问题,要注意的是，给元素加标记时，除了v7至v7，对角线的其他0元素一律不予考虑。 按照标记数字对应的从至关系，得到各点到v7的最短路： v1v2 v2v5 v3v5 v4v5 v5v6 v6v7 v7v7,下一页,返回,上一页,4.2 最短路径问题,下一页,返回,上一页,4.2 最短路径问题,乍看似乎有些点未达到v7，但根据最短路的特性，有：,下一页,返回,上一页,4.

16、2 最短路径问题,为了书写简便，上述迭代过程可简写如下：,下一页,返回,上一页,4.2 最短路径问题,3. 求某点至各点的最短路 （1）建立网络的距离矩阵，行表示“从”列表示“至”。 （2）找出出发的点所在的行，左摹乘距离矩阵，进行摹乘运算。,下一页,返回,上一页,4.2 最短路径问题,（3）得到的行向量继续左摹乘距离矩阵，直到与前一个摹乘结果相同则得到最短路长。 （4）在距离矩阵中寻找行向量与之相加得到最短路长的元素，给该元素加标记。 （5）按每列加圈数字对应的“从/至”关系，就得到某点到各点的最短路。 例4-3 求图4-5中v1至各点的最短路 解：写出网络的直接距离矩阵，从距离矩阵中找出v

17、1的行向量l1，左摹乘距离矩阵W。同样要注意的是，给元素加标记时，除了v1至v1，对角线的其他0元素一律不予考虑。网络的直接距离矩阵W为：,下一页,返回,上一页,4.2 最短路径问题,具体计算过程可简写如下：,下一页,返回,上一页,4.2 最短路径问题,按照标记数字对应的从至关系，得到v1到各点的最短路：v1v1，v4v2， v1v3，v3v4，v4v5，v2v6进而有：,下一页,返回,上一页,4.2 最短路径问题,4求各点至各点的最短路 （1）确定摹乘次数：根据公式 plg（n-1）/lg2 ，p为整数，确定p为最后摹乘矩阵下标； （2）建立初始网络距离矩阵D1； （3）根据公式 ，其中1s

18、n，求D2中的各个元素。 （4）依次类推，直到求出Dp，即为各点至各点的最短距离矩阵。 例4-4 求图4-1各村间的最短距离。,下一页,返回,上一页,4.2 最短路径问题,解：先估算摹乘次数值： plg（n-1）/lg2= lg（7-1）/lg2= lg6/lg2=2.6 故p = 3，应计算到D3。 已知网络的距离矩阵W，按上面的公式依次计算如下。 其中，D2矩阵中的数字由D1矩阵中数字计算而来，例如，D2矩阵中第二行第五列的数字为4，是这样计算出来的：,下一页,返回,上一页,4.2 最短路径问题,返回,上一页,4.3 运输流量问题,在生产和经济生活中，许多系统都存在着各种各样的流。所谓最大

19、流问题，就是在一定条件下，使网络系统中的某种流的流量达到最大的问题。 4.3.1 基本概念 1. 网络流 所谓网络流，是指在一定条件下流过一个网络的某种流在各边上的流量的集合。这里的一定条件，一般指：,下一页,返回,4.3 运输流量问题,（1）网络有一个始点vs和一个终点vt； （2）流过网络的流量具有一定的方向，各弧的方向就是流量通过的方向； （3）每一个弧都有一个容量，表示允许通过该弧的最大流量。 2. 可行流 满足以下两个条件的流称为一个可行流： （1）弧流量限制条件，即每一弧上通过的流量非负且必须不大于该弧容量； （2）中间点平衡条件，所谓中间点是指除了始点与终点的网络中的其他点，这些

20、点的流入量必须等于其流出量，二者必须平衡。,下一页,返回,上一页,4.3 运输流量问题,3. 最大流 在一个网络中，流量最大的可行流称为最大流。 4. 链的前向弧与后向弧 网络中一条链上与链方向一致的弧称为前向弧，链上与链方向相反的弧称为后向弧。 5. 增广链 所谓增广链是指某可行流上，沿着从始点到终点的某条链调整各弧上的流量，可以使网络的流量增大，得到一个比原可行流流量更大的可行流。 增广链必须满足的条件如下：,下一页,返回,上一页,4.3 运输流量问题,（1）该链上前向弧流量小于容量，即流量可以增加； （2）该链上后向弧流量大于零，即流量可以减少。 若网络中存在增广链，则当前可行流就不是最

21、大流，调整方法如下： （1）沿着增广链观察，计算所有前向弧的最大可增加量（即每条前向弧容量与当前流量的差值），及所有后向弧的最大可减少量（即后项弧上的流量），其中的最小值即为调整量。 （2）令当前可行流的该增广链上所有前向弧加上调整量，所有后向弧减去调整量。,下一页,返回,上一页,4.3 运输流量问题,6. 截集与截量 在一个网络中，把所有结点的集合V分为两个非空集合 和 ，使 ， ，且 中各点不需经由 中的点而均连通，则把始点在中而终点在中的一切弧所构成的集合，称为一个分离vs和vt的截集，记为（ ， ）。某一个截集的所有弧的容量之和称为该截集的容量，简称截量，记为 r（ ， ）。 例如，图

22、4-6的所有不同的截集及其截量见表4-1。可见，一个很简单的网络也有较多不同的截集。,下一页,返回,上一页,4.3 运输流量问题,在一个网络中，截量最小的截集称为最小截集。由表4-1可知，图4-6的最小截量为11，最小截集为（1,3）,（4,t）。 网络中从vs到vt的最大流的流量等于分离vs和vt的最小截集的截量。这就是最大流量最小截量定理。依此原理来求网络的最大流。 4.3.2 求网络最大流的标号法 这种标号法由福特（Ford）和富尔克逊（Fulkerson）于1956年提出，故称为福特富尔克逊标号法。,下一页,返回,上一页,4.3 运输流量问题,该法从某一可行流出发，按照前面介绍的增广链

23、的条件找出一条增广链，并按规则确定调整量并进行调整，得到一个流量增大的新的可行流。重复上述做法，直到找不出增广链为止，这时就得到一个最大流，同时还得到一个最小截集。 1. 给始点标号（0,），则该点已标号待检查； 2. 取一个已标号待检查的点vi，对所有与vi相邻而未标号的点依次处理如下： （1）前向弧，流量可增时，标号（vi，b），b取值为通过vi的流量和该弧容量与流量之差的最小值。 （2）后向弧，流量大于0时，标号（-vi，b），b取值为通过vi的流量和该弧流量的最小值。,下一页,返回,上一页,4.3 运输流量问题,3. 当所有与vi相邻而未标号的点都处理完后，就给vi打，表示对它已经检查

24、完毕； 4. 重复2，可能出现两种结果： （1）终点vt得到标号。则依据第一个标号回溯，就能找到一条增广链，转5。 （2）所有标号点均已打，而vt未得到标号，说明不存在增广链，而当前的可行流即最大流，算出其流量，终止。 5. 取终点的第二个标号为调整量，沿第一个标号回溯的增广链进行调整：前向弧加上；后向弧减去。 6. 删除所有标号，返回1。,下一页,返回,上一页,4.3 运输流量问题,例4-5 用标号法求图4-6所示网络的最大流与最小截集。 解：（1）先给vs标号（0,）。现在已标号待检查的点只有s点，对其相邻点v1和v2分析如下： 对v1，因与vs相关联的弧（vs，v1）上流量为7，容量为9

25、，可增加流量为2，故给v1标号（vs，2）。 对v2，因与vs相关联的弧（vs，v2）上流量为3，容量为5，可增加流量为2，故给v2标号（vs，2）。 至此对vs检查完毕，给vs打。,下一页,返回,上一页,4.3 运输流量问题,（2）现在已标号待检查的点有v1、v2。取v1检查，对与其相邻而未标号的点v3、v4分析如下： 对v3，因弧（v1，v3）上容量与流量相等，不能增加流量，故不给v3标号。 对v4，因与v1相关联的弧（v1，v4）上流量为1，容量为3，可增加流量为2，该可增流量与来源点v1的后一标号比较取最小值，已知v1点后标号也为2，故给v4标号（v1,2）。 至此对v1检查完毕，给v

26、1打。 （3）现在已标号待检查的点有v2、v4。取v2检查，因与其相邻的点都已标号，故给v2打。,下一页,返回,上一页,4.3 运输流量问题,（4）现在已标号待检查的点仅有v4。对与其相邻而未标号的点v3，vt分析如下： 对v3，因弧（v3,v4）流量为1，我们是从v4出发去v3，（v4,v3）是后向弧，该弧上可减少的流量为1，比较来源点v4的后一标号2，得到最小值1，故给v3标号（-v4,1）。 对vt，因弧（v4，vt）上容量与流量相等，不能增加流量，故不给vt标号。 至此对v4检查完毕，给v4打。,下一页,返回,上一页,4.3 运输流量问题,（5）现在已标号待检查的点仅有v3。对与其相邻

27、而未标号的点vt分析如下： 对vt，因与v3相关联的弧（v3，vt）上流量为3，容量为6，可增加流量为3，该可增流量与来源点v3的后一标号比较取最小值，已知v3点后标号为1，故给vt标号（v3，1）。 至此对v3检查完毕，给v4打。 （6）因终点vt已得标号，故从vt依次回溯各点的第一个标号，就得到一条增广链。如图4-7粗箭头线所示。 （7）取调整量=1，调整增广链上各弧的流量，其中，前向弧增加，后向弧减少，得到一个新的可行流，如 图4-8所示。,下一页,返回,上一页,4.3 运输流量问题,在图4-8中重复上述标号步骤,依次给vs，v1，v2，v4标号并检查后,由于标号过程依法停止，故图4-8

28、中的可行流就是最大流。 最大流的流量可按始点的净流出量计算：8+3=11；也可按终点的净流入量计算：4+7=11。这时的标号点集为vs，v1，v2，v4，未标号点集为v3，vt，故最小截集为（v1，v3）,（v4，vt），最小截量为11，与最大流相等。 下面再举例来说明手工计算最大流标号法的简单表示。,下一页,返回,上一页,4.3 运输流量问题,例4-6 求图4-9所示网络的最大流与最小截集。图中每条弧旁边的数字为容量，当前网络流量为零。 解：从零流开始，依次选取增广链进行调整，具体调整步骤如下：,下一页,返回,上一页,4.3 运输流量问题,调整过程如图4-10所示，弧旁的数字不断变化，其中划

29、去的数字是各次调整前的流量。保留的就是最大流在各弧上的最终流量。结果可知：最大流量20，最小截集为 （vs，v1），（vs，v2）（vs，v3）。 4.3.3 最小费用最大流 在实际生活中，涉及“流”的问题时，人们考虑的不只是流量，而且还有“费用”的因素，要寻求一个能使输送流量的费用达到最小的最大流。这就是最小费用最大流问题。,下一页,返回,上一页,4.3 运输流量问题,首先来分析一下解决该问题的思路。在求网络的最大流时，从某个可行流出发，找到关于这个流的一条增广链，如此反复调整流量至最大，这个过程中，增广链的选择是没有优先顺序的。那么在最小费用最大流问题中，在寻找增广链以增加流量时，要找到当

30、前网络可行流中费用最小的增广链，优先安排调运，即进行流量调整；调整后，得到新的可行流，需再寻找费用最小的增广链，再次进行调整，如此反复进行，直到找不到费用最小的增广链为止。这样得到的就是费用最小的最大流。具体步骤如下：,下一页,返回,上一页,4.3 运输流量问题,开始取 为初始可行流，一般地，如果在第k-1步得到最小费用流 ，则构造赋权有向图 ，在 中，寻求从vs到vt的最短路，若不存在最短路，则 就是最小费用最大流；若存在最短路，则在原网络中得到相应的增广链，在增广链上对 进行调整，调整规则参见最大流标号法。调整后得到新的可行流 ，再重复上述步骤。 下面通过例题来具体说明。,下一页,返回,上

31、一页,4.3 运输流量问题,例4-7 求图4-11（a）的最小费用最大流。弧旁数字为（bij,cij），其中，bij表示费用，cij表示容量，当前流量为零。 解：（1）取 为初始可行流。 （2）构造赋权有向图 ，并求出从vs到vt的最短路（vs，v2，v1，vt），费用为4，如图4-11（b）所示。 （3）在原网络中对与这条最短路相应的增广链（vs，v2， v1，vt）上进行调整，根据求网络最大流的增广链调整规则，=5，得到新的可行流 ，如图4-11（c）所示。,下一页,返回,上一页,4.3 运输流量问题,（4）构造当前可行流的赋权有向图 。构造规则遵循三个要点：对于流量为零的弧，即“空弧”，

32、流向保持不变；对于流量等于容量的弧，即“满弧”，流向与初始方向相反；对于流量非零且不满的弧，构造两个方向的弧。在新构造的 中，求出从vs到vt的最短路（vs，v1，vt），费用为5，如图4-11（d）所示。 （5）在原网络中对与这条最短路相应的增广链（vs，v1，vt）上进行调整，根据求网络最大流的增广链调整规则，=2，得到新的可行流 ，如图4-11（e）所示。,下一页,返回,上一页,4.3 运输流量问题,（6）构造当前可行流的赋权有向图 。在新构造的 中，求出从vs到vt的最短路（vs，v2，v3，vt），费用为6，如图4-11（f）所示。 （7）在原网络中对与这条最短路相应的增广链（vs，

33、v2，v3，vt）上进行调整，根据求网络最大流的增广链调整规则，=3，得到新的可行流，如图4-11（g）所示。 （8）构造当前可行流的赋权有向图 。在新构造的 中，求出从vs到vt的最短路（vs，v1，v2，v3，vt），费用为7，如图4-11（h）所示。,下一页,返回,上一页,4.3 运输流量问题,（9）在原网络中对与这条最短路相应的增广链（vs，v1，v2，v3，vt）上进行调整，根据求网络最大流的增广链调整规则，=1，得到新的可行流 ，如图4-11（i）所示。 （10）构造当前可行流的赋权有向图 ，如图4-11（j）所示。在新构造的 中，不存在从vs到vt的最短路，所以 为最小费用最大流

34、。,返回,上一页,4.4 单回路运输路线问题,本节所要研究的是从某点出发，经过若干个要到达的点，或者经过若干必须经过的路线，最后返回出发点的一类问题。 4.4.1 中国邮递员问题 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。这个问题是我国管梅谷同志在1962年首先提出的，因此在国际上通称为中国邮递员问题。这个问题，实际上就是一类物流配送的最短路问题。,下一页,返回,4.4 单回路运输路线问题,若把邮递员问题抽象为图的语言，就是给定一个连通图，在每条边上赋予一个非负的权，要求一个圈（不一定是简单的），过每边至少一次，并使总权数最小。 1.

35、 一笔画问题 在哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，河上有七座桥，如图4-12（a）所示。当地居民热衷于这样一个问题：一个散布者能否走过七座桥，且每座桥只走过一次，最后回到出发点。,下一页,返回,上一页,4.4 单回路运输路线问题,1736年，欧拉将此问题归结为如图4-12（b）所示图形的一笔画问题，即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。欧拉证明了这是不可能的，因为图4-12（b）中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成，这是古典图论中的一个著名问题。 给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这条链为欧拉链，若存在一

36、个简单圈，过每边一次，称这个圈为欧拉圈。一个图若有欧拉圈，则成为欧拉图。,下一页,返回,上一页,4.4 单回路运输路线问题,定理 连通多重图G是欧拉图，当且仅当G中无奇点。 推论 连通多重图G有欧拉链，当且仅当G恰有两个奇点。 上述定理和推论为我们提供了一个识别一个图能否一笔画出的较为简单的办法。 2. 奇偶点图上作业法 如果在某邮递员所负责的范围内，街道图中没有奇点，那么他就可以从邮局出发，走过每条街道一次且仅一次，最后回到邮局，这样他所走的路程也就是最短的路程。而对于有奇点的街道，就必须在某些街道上重复走一次或多次。,下一页,返回,上一页,4.4 单回路运输路线问题,如图4-13所示的街道

37、中，若v1是邮局，邮递员可以按以下的路线投递信件：v1v2v4v3v2v4v6v5v4v6v5v3v1总权为12；也可以按以下的路线投递信件：v1v2v3v2v4v5v6v4v3v5v3v1总权为11。 可见，按第一条路线走，在边v2,v4，v4,v6，v6,v5上各重复走了一次，而按第二条路线走，在边v3,v2，v3,v5上各重复走了一次。,下一页,返回,上一页,4.4 单回路运输路线问题,如果在某条路线中，边vi，vj上重复走了几次，可以在图中vi，vj之间增加几条边，因每边的权和原来的权相等，并把新增加的边称为重复边。于是这条路线就是相应的新图中的欧拉圈。在图4-13中，上边两条路线分别

38、是图4-14（a）和（b）中的欧拉圈。 显然，两条邮递路线的总路程的差必等于相应的重复边总权的差。因而，原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。 把使新图不含奇点而增加的重复边，简称为可行（重复边）方案。使总权最小的可行方案称为最优方案。,下一页,返回,上一页,4.4 单回路运输路线问题,现在的问题是第一个可行方案如何确定，在确定一个可行方案后，怎么判断这个方案是否为最优方案？若不是最优方案，如何调整这个方案? （1）第一个可行方案的确定方法 我们知道，在任何一个图中，奇点个数必为偶数。所以如果图中有奇点，就可以把它们配成对。又因为图

39、是连通的，故每一对奇点之间必有一条链，我们把这条链的所有边作为重复边加到图中去，则新图中必无奇点，这就给出了第一个可行方案。,下一页,返回,上一页,4.4 单回路运输路线问题,例4-8 图4-15中的街道图，有四个奇点，v2，v4，v6，v8，把v2与v4分为一对，v6与v8为一对。在图4-15中，连接v2与v4的链有好几条，任取一条（v2，v1，v8，v7，v6，v5，v4），把v2，v1，v1，v8，v8，v7，v7，v6，v6，v5，v5，v4作为重复边加到图中去，同样地取连接v6与v8的链（v6，v5，v4，v3，v2，v1，v8），把v6，v5，v5，v4，v4，v3，v3，v2，v

40、2，v1，v1，v8作为重复边加到图中去，得到 图4-16。这个图没有奇点，是欧拉图。这是个可行方案，重复边的总权数可计算出为51。,下一页,返回,上一页,4.4 单回路运输路线问题,（2）调整可行方案，使重复边总长度下降 从图4-16中可以看出，有一些边上有两条重复边，比如v1，v8，如果把它们都从图中去掉，图仍然无奇点，还是可行方案，但边的总长度却有所下降。一般情况下，如果边上有两条或两条以上的重复边时，我们从中去掉偶数条，就能得到一个总长度较小的可行方案。为了得到总长度最小的最优方案，我们需遵守以下两条原则： 在最优方案中，图的每一边上最多有一条重复边。 在最优方案中，图中每个圈上的重复

41、边的总权不大于该圈总权的一半。,下一页,返回,上一页,4.4 单回路运输路线问题,按照上面的原则，图4-16可以调整为图4-17，重复边总权下降到21。进一步地，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。如果新的重复边总权数比原先的重复边总权数小，将会得到一个总权下降的可行方案。事实上，较小权数的重复边，其总权数应当小于其所在圈的总权的一半。经过调整，得到图4-18，重复边总长度下降为17。,下一页,返回,上一页,4.4 单回路运输路线问题,（3）判断最优方案的标准 从上面的分析可知，一个最优方案一定是满足上述（1）和（2）两个条件的可行方案。可以证

42、明，一个可行方案若满足（1）和（2），这个可行方案一定是最优方案。根据这样一个判别标准，对给定的可行方案，检查它是否满足上述两个条件。若满足，所得方案即为最优方案；若不满足，则对方案进行调整，直至满足上述两个条件为止。,下一页,返回,上一页,4.4 单回路运输路线问题,检查图4-18中的圈（v1，v2，v9，v6，v7，v8，v1）中重复边总权数为13，而圈的权为24，不满足条件（2），经调整得4-19。重复边总长度下降为15。再检查，条件（1）和（2）都满足，于是得到了最优方案。图4-20中的任意一个欧拉圈就是邮递员的最优邮递路线。 以上求最优邮递路线的方法，通常称为奇偶点图上作业法。该方法

43、的主要困难在于检查条件（2），当图中点、边数较多时，圈的个数将会很多，比如“日”字形的图有3个圈，而“田”字形的图就有13个圈。,下一页,返回,上一页,4.4 单回路运输路线问题,4.4.2 旅行商问题 旅行商问题大意是说：一个旅行商从某一个村庄出发，到周围若干个村庄进行销售，每个村庄都要走到，而且只去一次，最后返回出发点，试问应按什么顺序走遍所有村庄，同时使所走路程最短。这个问题属于组合最优化问题，当村庄数量不太大时，利用动态规划方法求解是很方便的。下面通过一个具体的例子来说明如何应用动态规划方法求解简单的旅行商问题。,下一页,返回,上一页,4.4 单回路运输路线问题,例4-9 求解四个城市

44、旅行推销员问题，其距离矩阵如表4-2所示，当推销员从1城市出发，经过每个城市一次且仅一次，最后回到1城市，问按怎样的路线走，能使总的行程距离最短。 解：按顺序解法的思路： 第一阶段：从1城市开始，中间经过一个城市到达某城市i的最短距离分别是： 当i=2时，经过3城的最短距离是d132=d13+d32=5+9=14 当i=2时，经过4城的最短距离是d142=d14+d42=6+7=13,下一页,返回,上一页,4.4 单回路运输路线问题,当i=3时，经过2城的最短距离是d123=d12+d23=8+8=16 当i=3时，经过4城的最短距离是d143=d14+d43=6+8=14 当i=4时，经过2

45、城的最短距离是d124=d12+d24=8+5=13 当i=4时，经过3城的最短距离是d134=d13+d34=5+5=10 第二阶段：从1城市开始，中间经过两个城市（顺序随便）到达某城市i的最短距离分别是：,下一页,返回,上一页,4.4 单回路运输路线问题,当i=2时，经过3、4城的最短距离是d1342=mind134+d42 ，d143+d32=10+7，14+9=17 路线为1-3-4-2。 当i=3时，经过2、4城的最短距离是d1243=mind124+d43， d142+d23=13+8，13+8=21 路线为1-2-4-3。,下一页,返回,上一页,4.4 单回路运输路线问题,当i=

46、4时，经过2、3城的最短距离是d1234=mind123+d34， d132+d24=16+10，14+5=19 路线为1-3-2-4。 第三阶段：从1城市开始，中间经过三个城市（顺序随便）回到1城市的最短距离为： d12341=mind1342+d21，d1243+d31，d1324+d41=17+6，21+7，19+9=23 由此可知，推销员的最短旅行路线是1-3-4-2-1，最短总距离为23。,返回,上一页,4.5 多回路运输路线,随着社会经济的不断发展，作为“第三利润源”的物流越来越引起人们的关注，其中物流配送车辆优化调度问题是物流中关键的一环，对其进行优化调度，可以提高物流经济效益、

47、实现物流科学化。物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出的，称之为Vehicle Routing Problem（简称VRP）。该问题一般定义为：对一系列给定的顾客（取货点或送货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少等）。,下一页,返回,4.5 多回路运输路线,车辆路径问题（VRP问题）是组合优化领域中著名的NP难题。近二十年来，无论在国内外，VRP问题都是一个非常活跃的研究领域。目前解决该问题的现代

48、数学方法主要分为以下几类： 1. 精确优化方法 包括分枝定界算法、度中心树及相关算法、动态规划、集合划分和列产生、三索引车辆流方式、二索引车辆流方式等。但精确算法的计算复杂度很高，随着运输系统的复杂化和对调度的多目标要求，获得整个系统的精确优化解越来越困难，花费的时间和费用太大，因此精确解法不能应用于规模较大的物流配送车路由问题的求解，仅用于运输调度的局部优化问题。,下一页,返回,上一页,4.5 多回路运输路线,2. 启发式方法（Heuristics） 指通过经验法则来求取运输过程满意解的数学方法。启发式方法能同时满足详细描绘问题和求解的需要，较精确优化方法更为简单实用，缺点是难于知道什么时候

49、好的启发式解己经被求得。启发式方法中最具代表性的就是由Clarck和Wright提出的节约法（Saving Method）。许多成功的车辆调度软件就是根据该方法或其改进方法开发的。,下一页,返回,上一页,4.5 多回路运输路线,典型启发式算法中还包括由Lin和Kemighan提出的，并由Chtistofidests和Gilbertla Porte等人所推广的分支交换探索法，该算法始终保持解的可行性而又力图向最优目标前进。在每一步，都改变一个可行解而减少总费用， 直到这个过程继续到不再可能使费用减少为止。Gillet和Milled提出的扫描法（Sweep Method）先把节点或弧的需求进行分组

50、或划群，然后对每一组按旅行商问题（TSP）求解，设计出一条经济的路线。此外，常用的启发式方法还有2-阶段法、不完全树搜索算法等。各种启发式方法的主要区别在于收敛的速度和程度不同。,下一页,返回,上一页,4.5 多回路运输路线,精确优化方法是以往广泛采用的方法，另外三种方法则代表了最近研究的方向。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现己成为解决配送问题的重要方法。 启发式算法中最具有代表性的就是由克拉克（Clarke）和怀特（Wright）提出的节约法（Saving Method）。下面说明节约法

51、思考的基本方法。,下一页,返回,上一页,4.5 多回路运输路线,设有一个配送中心 ,两个配送点 和 ,若配送中心向配送点分别单独送货，则运输路线为 , 运输距离为 ，若采取回路送货，运输路线为 ，运输距离为 。如图4-19所示。路线改动后运输路线的节约量是： 这就是有名的节约量公式。,下一页,返回,上一页,4.5 多回路运输路线,4.5.1 单配送中心配送规划 1. 配送路线与车辆调度前提条件 实际的配送路线优化问题，存在各种约束条件，非常复杂。为了简化问题，我们首先提出一些假设条件。 （1）被配送的是已知的一种或者几种物资； （2）各个用户的所在地和需求量已知； （3）从配送中心到各个用户之

52、间的运输距离已知； （4）各种类型的车辆数目一定，能满足运输要求； （5）每一辆发送车辆的装载量有一定的限制，不能超载运行。,下一页,返回,上一页,4.5 多回路运输路线,2. 配送路线优化节约法 一般地，配送中心向用户配送物资，使用的车辆的装载量不可能完全相同（主要是由于车型不同），假设向每个用户都派一辆车，各个用户的需要量都小于最大发送车的装载量，同时装载量最小的车子台数足以安排货运。下面通过一个实际例子来说明节约法的求解思路。,下一页,返回,上一页,4.5 多回路运输路线,例4-10 已知配送中心P0向7个用户Pj配送货物，其配送路线网络、配送中心与用户的距离、用户之间的距离如 图4-2

53、0所示，图中括号内的数字表示客户的需求量Qi（单位：t），线路上的数字表示两结点之间的距离（单位：km），现配送中心有8台4t卡车和3台6t两种车辆可供使用。试利用节约里程法制定最优的配送方案？ 解：首先做出配送中心与各用户间的运输里程表4-3。 根据节约量公式，求出用户连接的费用节约值，见表4-4。 初始方案为：配送中心向每个用户单独送货，需要7台4t的车，总里程为：,下一页,返回,上一页,4.5 多回路运输路线,车辆分配方案为：4t车辆使用7台，6t车辆使用0台。 在初始解的基础上，选出具有最大节约值的格子，该格子应满足下列条件： （1）用户Pi和用户Pj不在同一条线路上； （2）原计划分

54、别运送用户Pi和用户Pj的货物可用装载量大于 的车进行运送。 表4-4中最大节约量为 ，把用户P6和用户P7进行连接，进行第一次路线修改。第一次修改后得到表4-5的配送方案。其中，将用户P6和用户P7的需要量分别改为 的总载运量。,下一页,返回,上一页,4.5 多回路运输路线,注：表4-5中，1表示连接这两个用户，0表示不连接，2表示由配送中心单独送货。 车辆分配方案为：4t车辆使用6台，6t车辆使用0台。 由节约量公式可知，总里程减少了23，此时总里程为 ,进一步优化,选取次大节约值 ， 把用户P3和用户P4进行连接，进行第二次路线修改。修改后得到表4-6的配送方案。其中，将用户P3和用户P

55、4的需要量分别改为 的总载运量。,下一页,返回,上一页,4.5 多回路运输路线,车辆分配方案为：4t车辆使用5台，6t车辆使用0台。 由节约量公式可知，总里程又减少了16，此时总里程为 ，再进一步优化，比16小的节约值 和 ，任选一个进行优化，把用户P2和用户P3进行连接，进行第三次路线修改。我们将用户P2、用户P3和用户P4的需要量分别改为 的总载运量。因为用户P3两端分别和用户P4、用户P2相连，不可能再与其它点相连，故表4-4中P3行整行节约值删除，不再考虑。修改后得到表4-7的配送方案。,下一页,返回,上一页,4.5 多回路运输路线,车辆分配方案为：4t车辆使用4台，6t车辆使用0台。

56、 由节约量公式可知，总里程又减少了11，此时总里程为 ，下一步选 进行优化，把用户P5和用户P6进行连接，进行第四次路线修改。将用户P5、用户P6和用户P7的需要量分别改为 的总载运量。因为用户P6两端分别和用户P7、用户P5相连，不可能再与其它点相连，故表4-4中P6行整行节约值删除，不再考虑。修改后得到表4-8的配送方案。,下一页,返回,上一页,4.5 多回路运输路线,车辆分配方案为：4t车辆使用2台，6t车辆使用1台。 由节约量公式可知，总里程又减少了11，此时总里程为 ，下面看到比11小的节约值10和8因为处于P3和P6行，因此不予考虑 和 ，若选 进行优化，则现有车辆吨位不够。因此用

57、户P4和用户P5所在线路不能相连。选 进行优化，把用户P1和用户P2、P3、P4进行连接，进行第五次路线修改。我们将用户P1、P2、P3、P4的需要量分别改为 的总载运量。因为用户P2两端分别和用户P1、用户P3相连，不可能再与其它点相连，故表4-4中P2行整行节约值删除，不再考虑。修改后得到表4-9的配送方案。,下一页,返回,上一页,4.5 多回路运输路线,车辆分配方案为：4t车辆使用0台，6t车辆使用2台。 由节约量公式可知，总里程又减少了7，此时总里程为 。现在，有两条线路进行配送，就现有的车辆吨位状况，每条线路上载运量都不可能再增加，因此，第五次修改后的方案就是最优调运方案。 3. 节

58、约法的改进 前面已经讲到，启发式算法并不能保证得到问题的最优解。节约法求解配送路线优化问题，有时就会出现仅得满意解的情况，这时就需要结合其他的方法来求最优解。,下一页,返回,上一页,4.5 多回路运输路线,例4-11 同样是一个配送中心，7个用户的问题，改变一下上例的部分参数。表4-10给出了配送中心与用户的距离、用户之间的距离以及客户的需求量Qi（单位：t） 解：根据节约量公式，求出用户连接的费用节约值，见表4-11。 配送路线优化的过程简写如下： 初始方案：对每个用户单独送货，需7台4t的车，总里程为：,下一页,返回,上一页,4.5 多回路运输路线,改进1：最大节约量Smax=S34=16

59、,Q34=Q3+Q4=2.9t，需要6台4t的车，总里程S1=124-16=108km。 改进2：Smax=S67=11，Q67=Q6+Q7=3.9t，需要5台4t的车，总里程S2=108-11=97km。 改进3：Smax=S17=11,Q167=Q1+Q67=7.1t，不可行。 Smax=S45=9，Q345=Q5+Q34=5.3t，需要3台4t的车，1台6t车，总里程S3=97-9=88km。,下一页,返回,上一页,4.5 多回路运输路线,改进4：Smax=S23=9，Q2345=Q2+Q345=6.9t，不可行。同理，Smax=S56=8，Smax=S13=8均不可行。 Smax=S12=7，Q12=Q1+Q2=4.8t，需要1台4t的车，2台6t车，总里程 S3=88