《物流运筹学》第4章-物流运输路径规划

第4章物流运输路径规划4.1图与网络的基本概念4.2最短路径问题4.3运输流量问题4.4单回路运输路线问题4.5多回路运输路线第4章物流运输路径规划本章重点：图论是运筹学的一个分支，是建立和处理离散数学模型的一个重要工具。本章中学生要了解图论的基本概念，掌握最短路径问题的狄克斯屈标号法和运输流量问题的福特—富尔克逊标号法，了解单回路运输路线问题和多回路运输路径。返回4.1图与网络的基本概念图论（TheoryofGraphs或GraphTheory）是应用非常广泛的运筹学分支，是建立和处理离散数学模型的一个重要工具。图论的起源最早可追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。直到20世纪中叶，随着离散数学和计算机技术的发展，图和网络的研究更是得到了飞速发展。目前，网络分析的理论已经在工程设计、管理科学、交通规划、通信网络规划等众多领域中得到广泛应用，并取得了丰富的成果。下一页返回4.1图与网络的基本概念4.1.1图和图解1.图的基本结构首先看一个图的实例。图4-1是某地7个村镇之间的道路交通示意图，点①、②、③、④、⑤、⑥、⑦分别表示7个村镇，各村镇之间的连线称为道路。（1）结点用来表示物理实体或事物，一般用vi来表示。例如，图4-1中的结点就是各村镇。（2）边是结点间的连线，表示两结点之间的关系，一般表示为e=（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-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.环，多重边，简单图。若一条边的两个端点是同一结点，则称该边为环；若两个端点之间不止一条边，称为具有多重边；无环也无多重边的图称为简单图。以下讨论的图多指简单图。下一页返回上一页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图与网络的基本概念5.连通图。在一个图种，若任意两点之间至少存在一条链，则称该图为连通图，否则称为不连通图。图4-1和图4-2都是连通图，而图4-3不是连通图。6.网络，权。一个图连同定义在其边集上的实函数w（vi，vj）一起称为一个网络。网络一般是连通图。记wij=w（vi，vj），称为边（vi，vj）的权数。返回上一页4.2最短路径问题4.2.1狄克斯屈标号法该法是Dijkstra在1959年提出的，适用于所有权数均为非负（即一切wij≥0）的网络（对于负权网络，该法有时失效），能够求出网络的任一点到其他各点的最短路，使目前求这类网络最短路的最好算法。该法直接在网络上对每一个点标号，标号分为两种：临时标号T（vj）和固定标号P（vj）。在网络中，固定标号以带括号的数字表示，临时标号不带括号。网络中一个点的临时标号表示从始点到该点的最短路长的上界，固定标号表示最短路长。在标号过程中，临时标号不断被新的更小的临时标号所替代，直到不能再减小为止，就得到该点的固定标号。计算步骤如下：下一页返回4.2最短路径问题（1）给始点标固定标号（0）；（2）给与（0）点相邻的各点标上临时标号，标号数值为始点固定标号值加上始点到该点间边的权数；（3）从所有的临时标号里找最小的确定为固定标号，对该最小临时标号打上括号；（4）从新得到的固定标号出发，给相邻的没有固定标号的点打上临时标号。对于没有标号的点，标号数值为出发点的固定标号值加上两点间边的权数；对于已有临时标号的点，新的临时标号比原有临时标号小的，替换为新的临时标号，否则保持原有临时标号不变；（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）所示。从新得到的固定标号点②出发，检查与其相邻并且没有固定标号的点③、④、⑤，确定临时标号如下：下一页返回上一页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）所示。从新得到的固定标号点③出发，检查与其相邻并且没有固定标号的点⑤、⑥，确定临时标号如下：下一页返回上一页4.2最短路径问题点⑤：min{T（5），P（3）+w35}=min{7，4+5}=7，即T（5）=7点⑥：min{T（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最短路径问题点⑤：min{T（5），P（4）+w45}=min{7，5+2}=7，即T（5）=7点⑦：min{T（7），P（4）+w47}=min{∞，5+6}=11，即T（7）=11从所有的临时标号中选出点⑤的最小标号7，改为固定标号（7），此时，T（5）=7改为P（5）=（7），我们又得到了点①到点⑤的最短路长为7，如图4-4（d）所示。从新得到的固定标号点⑤出发，检查与其相邻并且没有固定标号的点⑥，⑦，确定临时标号如下：下一页返回上一页4.2最短路径问题点⑥：min{T（6），P（5）+w56}=min{11，7+1}=8，即T（6）=8点⑦：min{T（7），P（5）+w57}=min{11，7+4}=11，即T（7）=11从所有的临时标号中选出点⑥的最小标号8，改为固定标号（8），此时，T（6）=11改为P（6）=（8），我们又得到了点①到点⑥的最短路长为8，如图4-4（e）所示。从新得到的固定标号点⑥出发，检查与其相邻并且没有固定标号的点⑦，确定临时标号如下：下一页返回上一页4.2最短路径问题点⑦：min{T（7），P（6）+w67}=min{11，8+2}=10，即T（7）=10此时，只有一个临时标号10，将其改为固定标号，T（7）=11改为P（7）=（10），得到了点①到点⑦的最短路长为10，如图4-4（f）所示。至此，所有的点都已得到固定标号，问题求解结束。由此可以看出，点①到点⑦的最短路有两条：①→②→④→⑤→⑥→⑦①→②→⑤→⑥→⑦下一页返回上一页4.2最短路径问题4.2.2距离矩阵摹乘法该算法适用于求任何网络的最短路，它比狄克斯屈标号法要复杂些，但应用范围广，对于任何含负权的网络都适用。1.网络的距离矩阵设一个网络N中有n个结点，对于网络中相邻的点，两点间的距离即为边的权数；不相邻的两点，其距离设为∞。这样可以定义一个矩阵W=（wij）n×n称为网络N的直接距离矩阵，简称距离矩阵。如图4-1所示的网络的距离矩阵为：下一页返回上一页4.2最短路径问题2.求各点至某点的最短路（1）建立网络的直接距离矩阵，行表示“从”列表示“至”。下一页返回上一页4.2最短路径问题（2）找出到达的点所在的列，右摹乘距离矩阵，进行摹乘运算。所谓摹乘运算，顾名思义，是模仿矩阵相乘运算，在矩阵相乘中，对应元素相乘后求和，得到新矩阵对应元素，而在摹乘运算中，是对应元素相加后求最小值，得到新矩阵对应元素。（3）得到的列向量继续右摹乘距离矩阵，直到与前一个摹乘结果相同则得到最短路长。（4）在距离矩阵中寻找与列向量相加得到最短路长的元素，给该元素加标记。（5）按每行加标记数字对应的“从/至”关系，就得到各点到某点的最短路。下一页返回上一页4.2最短路径问题例4-2求图4-1中各点至点⑦的最短路。解：已知网络的直接距离矩阵，求各点到点⑦的最短路，从距离矩阵中找出v7的列向量d1，右摹乘距离矩阵W。中的元素计算式如下：min{0+∞,3+∞,4+∞,7+6,∞+4,∞+2,∞+0}=13min{3+∞,0+∞,3+∞,2+6,4+4,∞+2,∞+0}=8min{4+∞,3+∞,0+∞,∞+6,5+4,7+2,∞+0}=9min{7+∞,2+∞,∞+∞,0+6,2+4,∞+2,6+0}=6

以下依次类推。下一页返回上一页4.2最短路径问题要注意的是，给元素加标记时，除了v7至v7，对角线的其他0元素一律不予考虑。按照标记数字对应的从\至关系，得到各点到v7的最短路：v1→v2

v2→v5

v3→v5

v4→v5

v5→v6

v6→v7

v7→v7下一页返回上一页4.2最短路径问题下一页返回上一页4.2最短路径问题乍看似乎有些点未达到v7，但根据最短路的特性，有：下一页返回上一页4.2最短路径问题为了书写简便，上述迭代过程可简写如下：下一页返回上一页4.2最短路径问题3.求某点至各点的最短路（1）建立网络的距离矩阵，行表示“从”列表示“至”。（2）找出出发的点所在的行，左摹乘距离矩阵，进行摹乘运算。下一页返回上一页4.2最短路径问题（3）得到的行向量继续左摹乘距离矩阵，直到与前一个摹乘结果相同则得到最短路长。（4）在距离矩阵中寻找行向量与之相加得到最短路长的元素，给该元素加标记。（5）按每列加圈数字对应的“从/至”关系，就得到某点到各点的最短路。例4-3求图4-5中v1至各点的最短路解：写出网络的直接距离矩阵，从距离矩阵中找出v1的行向量l1，左摹乘距离矩阵W。同样要注意的是，给元素加标记时，除了v1至v1，对角线的其他0元素一律不予考虑。网络的直接距离矩阵W为：下一页返回上一页4.2最短路径问题具体计算过程可简写如下：下一页返回上一页4.2最短路径问题按照标记数字对应的从\至关系，得到v1到各点的最短路：v1→v1，v4→v2，v1→v3，v3→v4，v4→v5，v2→v6进而有：下一页返回上一页4.2最短路径问题4．求各点至各点的最短路（1）确定摹乘次数：根据公式p>lg（n-1）/lg2，p为整数，确定p为最后摹乘矩阵下标；（2）建立初始网络距离矩阵D1；（3）根据公式，其中1≤s≤n，求D2中的各个元素。（4）依次类推，直到求出Dp，即为各点至各点的最短距离矩阵。例4-4求图4-1各村间的最短距离。下一页返回上一页4.2最短路径问题解：先估算摹乘次数值：p>lg（n-1）/lg2=lg（7-1）/lg2=lg6/lg2=2.6故p=3，应计算到D3。已知网络的距离矩阵W，按上面的公式依次计算如下。其中，D2矩阵中的数字由D1矩阵中数字计算而来，例如，D2矩阵中第二行第五列的数字为4，是这样计算出来的：下一页返回上一页4.2最短路径问题返回上一页4.3运输流量问题在生产和经济生活中，许多系统都存在着各种各样的流。所谓最大流问题，就是在一定条件下，使网络系统中的某种流的流量达到最大的问题。4.3.1基本概念1.网络流所谓网络流，是指在一定条件下流过一个网络的某种流在各边上的流量的集合。这里的一定条件，一般指：下一页返回4.3运输流量问题（1）网络有一个始点vs和一个终点vt；（2）流过网络的流量具有一定的方向，各弧的方向就是流量通过的方向；（3）每一个弧都有一个容量，表示允许通过该弧的最大流量。2.可行流满足以下两个条件的流称为一个可行流：（1）弧流量限制条件，即每一弧上通过的流量非负且必须不大于该弧容量；（2）中间点平衡条件，所谓中间点是指除了始点与终点的网络中的其他点，这些点的流入量必须等于其流出量，二者必须平衡。下一页返回上一页4.3运输流量问题3.最大流在一个网络中，流量最大的可行流称为最大流。4.链的前向弧与后向弧网络中一条链上与链方向一致的弧称为前向弧，链上与链方向相反的弧称为后向弧。5.增广链所谓增广链是指某可行流上，沿着从始点到终点的某条链调整各弧上的流量，可以使网络的流量增大，得到一个比原可行流流量更大的可行流。增广链必须满足的条件如下：下一页返回上一页4.3运输流量问题（1）该链上前向弧流量小于容量，即流量可以增加；（2）该链上后向弧流量大于零，即流量可以减少。若网络中存在增广链，则当前可行流就不是最大流，调整方法如下：（1）沿着增广链观察，计算所有前向弧的最大可增加量（即每条前向弧容量与当前流量的差值），及所有后向弧的最大可减少量（即后项弧上的流量），其中的最小值即为调整量θ。（2）令当前可行流的该增广链上所有前向弧加上调整量，所有后向弧减去调整量。下一页返回上一页4.3运输流量问题6.截集与截量在一个网络中，把所有结点的集合V分为两个非空集合和，使，，且中各点不需经由中的点而均连通，则把始点在中而终点在中的一切弧所构成的集合，称为一个分离vs和vt的截集，记为（，）。某一个截集的所有弧的容量之和称为该截集的容量，简称截量，记为r（，）。例如，图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运输流量问题该法从某一可行流出发，按照前面介绍的增广链的条件找出一条增广链，并按规则确定调整量θ并进行调整，得到一个流量增大的新的可行流。重复上述做法，直到找不出增广链为止，这时就得到一个最大流，同时还得到一个最小截集。1.给始点标号（0,∞），则该点已标号待检查；2.取一个已标号待检查的点vi，对所有与vi相邻而未标号的点依次处理如下：（1）前向弧，流量可增时，标号（vi，b），b取值为通过vi的流量和该弧容量与流量之差的最小值。（2）后向弧，流量大于0时，标号（-vi，b），b取值为通过vi的流量和该弧流量的最小值。下一页返回上一页4.3运输流量问题3.当所有与vi相邻而未标号的点都处理完后，就给vi打√，表示对它已经检查完毕；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，可增加流量为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检查完毕，给v1打√。（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。对与其相邻而未标号的点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中的可行流就是最大流。最大流的流量可按始点的净流出量计算：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所示，弧旁的数字不断变化，其中划去的数字是各次调整前的流量。保留的就是最大流在各弧上的最终流量。结果可知：最大流量20，最小截集为{（vs，v1），（vs，v2）（vs，v3）}。4.3.3最小费用最大流在实际生活中，涉及“流”的问题时，人们考虑的不只是流量，而且还有“费用”的因素，要寻求一个能使输送流量的费用达到最小的最大流。这就是最小费用最大流问题。下一页返回上一页4.3运输流量问题首先来分析一下解决该问题的思路。在求网络的最大流时，从某个可行流出发，找到关于这个流的一条增广链，如此反复调整流量至最大，这个过程中，增广链的选择是没有优先顺序的。那么在最小费用最大流问题中，在寻找增广链以增加流量时，要找到当前网络可行流中费用最小的增广链，优先安排调运，即进行流量调整；调整后，得到新的可行流，需再寻找费用最小的增广链，再次进行调整，如此反复进行，直到找不到费用最小的增广链为止。这样得到的就是费用最小的最大流。具体步骤如下：下一页返回上一页4.3运输流量问题开始取为初始可行流，一般地，如果在第k-1步得到最小费用流，则构造赋权有向图，在中，寻求从vs到vt的最短路，若不存在最短路，则就是最小费用最大流；若存在最短路，则在原网络中得到相应的增广链，在增广链上对进行调整，调整规则参见最大流标号法。调整后得到新的可行流，再重复上述步骤。下面通过例题来具体说明。下一页返回上一页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）构造当前可行流的赋权有向图。构造规则遵循三个要点：对于流量为零的弧，即“空弧”，流向保持不变；对于流量等于容量的弧，即“满弧”，流向与初始方向相反；对于流量非零且不满的弧，构造两个方向的弧。在新构造的中，求出从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，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的最短路，所以为最小费用最大流。返回上一页4.4单回路运输路线问题本节所要研究的是从某点出发，经过若干个要到达的点，或者经过若干必须经过的路线，最后返回出发点的一类问题。4.4.1中国邮递员问题一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。这个问题是我国管梅谷同志在1962年首先提出的，因此在国际上通称为中国邮递员问题。这个问题，实际上就是一类物流配送的最短路问题。下一页返回4.4单回路运输路线问题若把邮递员问题抽象为图的语言，就是给定一个连通图，在每条边上赋予一个非负的权，要求一个圈（不一定是简单的），过每边至少一次，并使总权数最小。1.一笔画问题在哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，河上有七座桥，如图4-12（a）所示。当地居民热衷于这样一个问题：一个散布者能否走过七座桥，且每座桥只走过一次，最后回到出发点。下一页返回上一页4.4单回路运输路线问题1736年，欧拉将此问题归结为如图4-12（b）所示图形的一笔画问题，即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。欧拉证明了这是不可能的，因为图4-12（b）中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成，这是古典图论中的一个著名问题。给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这条链为欧拉链，若存在一个简单圈，过每边一次，称这个圈为欧拉圈。一个图若有欧拉圈，则成为欧拉图。下一页返回上一页4.4单回路运输路线问题定理连通多重图G是欧拉图，当且仅当G中无奇点。推论连通多重图G有欧拉链，当且仅当G恰有两个奇点。上述定理和推论为我们提供了一个识别一个图能否一笔画出的较为简单的办法。2.奇偶点图上作业法如果在某邮递员所负责的范围内，街道图中没有奇点，那么他就可以从邮局出发，走过每条街道一次且仅一次，最后回到邮局，这样他所走的路程也就是最短的路程。而对于有奇点的街道，就必须在某些街道上重复走一次或多次。下一页返回上一页4.4单回路运输路线问题如图4-13所示的街道中，若v1是邮局，邮递员可以按以下的路线投递信件：v1→v2→v4→v3→v2→v4→v6→v5→v4→v6→v5→v3→v1总权为12；也可以按以下的路线投递信件：v1→v2→v3→v2→v4→v5→v6→v4→v3→v5→v3→v1总权为11。可见，按第一条路线走，在边[v2,v4]，[v4,v6]，[v6,v5]上各重复走了一次，而按第二条路线走，在边[v3,v2]，[v3,v5]上各重复走了一次。下一页返回上一页4.4单回路运输路线问题如果在某条路线中，边[vi，vj]上重复走了几次，可以在图中vi，vj之间增加几条边，因每边的权和原来的权相等，并把新增加的边称为重复边。于是这条路线就是相应的新图中的欧拉圈。在图4-13中，上边两条路线分别是图4-14（a）和（b）中的欧拉圈。显然，两条邮递路线的总路程的差必等于相应的重复边总权的差。因而，原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。把使新图不含奇点而增加的重复边，简称为可行（重复边）方案。使总权最小的可行方案称为最优方案。下一页返回上一页4.4单回路运输路线问题现在的问题是第一个可行方案如何确定，在确定一个可行方案后，怎么判断这个方案是否为最优方案？若不是最优方案，如何调整这个方案?（1）第一个可行方案的确定方法我们知道，在任何一个图中，奇点个数必为偶数。所以如果图中有奇点，就可以把它们配成对。又因为图是连通的，故每一对奇点之间必有一条链，我们把这条链的所有边作为重复边加到图中去，则新图中必无奇点，这就给出了第一个可行方案。下一页返回上一页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]，[v2，v1]，[v1，v8]作为重复边加到图中去，得到图4-16。这个图没有奇点，是欧拉图。这是个可行方案，重复边的总权数可计算出为51。下一页返回上一页4.4单回路运输路线问题（2）调整可行方案，使重复边总长度下降从图4-16中可以看出，有一些边上有两条重复边，比如[v1，v8]，如果把它们都从图中去掉，图仍然无奇点，还是可行方案，但边的总长度却有所下降。一般情况下，如果边上有两条或两条以上的重复边时，我们从中去掉偶数条，就能得到一个总长度较小的可行方案。为了得到总长度最小的最优方案，我们需遵守以下两条原则：①在最优方案中，图的每一边上最多有一条重复边。②在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半。下一页返回上一页4.4单回路运输路线问题按照上面的原则，图4-16可以调整为图4-17，重复边总权下降到21。进一步地，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。如果新的重复边总权数比原先的重复边总权数小，将会得到一个总权下降的可行方案。事实上，较小权数的重复边，其总权数应当小于其所在圈的总权的一半。经过调整，得到图4-18，重复边总长度下降为17。下一页返回上一页4.4单回路运输路线问题（3）判断最优方案的标准从上面的分析可知，一个最优方案一定是满足上述（1）和（2）两个条件的可行方案。可以证明，一个可行方案若满足（1）和（2），这个可行方案一定是最优方案。根据这样一个判别标准，对给定的可行方案，检查它是否满足上述两个条件。若满足，所得方案即为最优方案；若不满足，则对方案进行调整，直至满足上述两个条件为止。下一页返回上一页4.4单回路运输路线问题检查图4-18中的圈（v1，v2，v9，v6，v7，v8，v1）中重复边总权数为13，而圈的权为24，不满足条件（2），经调整得4-19。重复边总长度下降为15。再检查，条件（1）和（2）都满足，于是得到了最优方案。图4-20中的任意一个欧拉圈就是邮递员的最优邮递路线。以上求最优邮递路线的方法，通常称为奇偶点图上作业法。该方法的主要困难在于检查条件（2），当图中点、边数较多时，圈的个数将会很多，比如“日”字形的图有3个圈，而“田”字形的图就有13个圈。下一页返回上一页4.4单回路运输路线问题4.4.2旅行商问题旅行商问题大意是说：一个旅行商从某一个村庄出发，到周围若干个村庄进行销售，每个村庄都要走到，而且只去一次，最后返回出发点，试问应按什么顺序走遍所有村庄，同时使所走路程最短。这个问题属于组合最优化问题，当村庄数量不太大时，利用动态规划方法求解是很方便的。下面通过一个具体的例子来说明如何应用动态规划方法求解简单的旅行商问题。下一页返回上一页4.4单回路运输路线问题例4-9求解四个城市旅行推销员问题，其距离矩阵如表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城的最短距离是d124=d12+d24=8+5=13当i=4时，经过3城的最短距离是d134=d13+d34=5+5=10第二阶段：从1城市开始，中间经过两个城市（顺序随便）到达某城市i的最短距离分别是：下一页返回上一页4.4单回路运输路线问题当i=2时，经过3、4城的最短距离是d1[34]2=min[d134+d42

，d143+d32]=[10+7，14+9]=17路线为1-3-4-2。当i=3时，经过2、4城的最短距离是d1[24]3=min[d124+d43，d142+d23]=[13+8，13+8]=21路线为1-2-4-3。下一页返回上一页4.4单回路运输路线问题当i=4时，经过2、3城的最短距离是d1[23]4=min[d123+d34，d132+d24]=[16+10，14+5]=19路线为1-3-2-4。第三阶段：从1城市开始，中间经过三个城市（顺序随便）回到1城市的最短距离为：d1[234]1=min[d1342+d21，d1243+d31，d1324+d41]=[17+6，21+7，19+9]=23由此可知，推销员的最短旅行路线是1-3-4-2-1，最短总距离为23。返回上一页4.5多回路运输路线随着社会经济的不断发展，作为“第三利润源”的物流越来越引起人们的关注，其中物流配送车辆优化调度问题是物流中关键的一环，对其进行优化调度，可以提高物流经济效益、实现物流科学化。物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出的，称之为VehicleRoutingProblem（简称VRP）。该问题一般定义为：对一系列给定的顾客（取货点或送货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少等）。下一页返回4.5多回路运输路线车辆路径问题（VRP问题）是组合优化领域中著名的NP难题。近二十年来，无论在国内外，VRP问题都是一个非常活跃的研究领域。目前解决该问题的现代数学方法主要分为以下几类：1.精确优化方法包括分枝定界算法、Ｋ度中心树及相关算法、动态规划、集合划分和列产生、三索引车辆流方式、二索引车辆流方式等。但精确算法的计算复杂度很高，随着运输系统的复杂化和对调度的多目标要求，获得整个系统的精确优化解越来越困难，花费的时间和费用太大，因此精确解法不能应用于规模较大的物流配送车路由问题的求解，仅用于运输调度的局部优化问题。下一页返回上一页4.5多回路运输路线2.启发式方法（Heuristics）指通过经验法则来求取运输过程满意解的数学方法。启发式方法能同时满足详细描绘问题和求解的需要，较精确优化方法更为简单实用，缺点是难于知道什么时候好的启发式解己经被求得。启发式方法中最具代表性的就是由Clarck和Wright提出的节约法（SavingMethod）。许多成功的车辆调度软件就是根据该方法或其改进方法开发的。下一页返回上一页4.5多回路运输路线典型启发式算法中还包括由Lin和Kemighan提出的，并由Chtistofidests和GilbertlaPorte等人所推广的分支交换探索法，该算法始终保持解的可行性而又力图向最优目标前进。在每一步，都改变一个可行解而减少总费用，直到这个过程继续到不再可能使费用减少为止。Gillet和Milled提出的扫描法（SweepMethod）先把节点或弧的需求进行分组或划群，然后对每一组按旅行商问题（TSP）求解，设计出一条经济的路线。此外，常用的启发式方法还有2-阶段法、不完全树搜索算法等。各种启发式方法的主要区别在于收敛的速度和程度不同。下一页返回上一页4.5多回路运输路线精确优化方法是以往广泛采用的方法，另外三种方法则代表了最近研究的方向。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现己成为解决配送问题的重要方法。启发式算法中最具有代表性的就是由克拉克（Clarke）和怀特（Wright）提出的节约法（SavingMethod）。下面说明节约法思考的基本方法。下一页返回上一页4.5多回路运输路线设有一个配送中心,两个配送点和,若配送中心向配送点分别单独送货，则运输路线为,

运输距离为，若采取回路送货，运输路线为，运输距离为。如图4-19所示。路线改动后运输路线的节约量是：这就是有名的节约量公式。

下一页返回上一页4.5多回路运输路线4.5.1单配送中心配送规划1.配送路线与车辆调度前提条件实际的配送路线优化问题，存在各种约束条件，非常复杂。为了简化问题，我们首先提出一些假设条件。（1）被配送的是已知的一种或者几种物资；（2）各个用户的所在地和需求量已知；（3）从配送中心到各个用户之间的运输距离已知；（4）各种类型的车辆数目一定，能满足运输要求；（5）每一辆发送车辆的装载量有一定的限制，不能超载运行。下一页返回上一页4.5多回路运输路线2.配送路线优化节约法一般地，配送中心向用户配送物资，使用的车辆的装载量不可能完全相同（主要是由于车型不同），假设向每个用户都派一辆车，各个用户的需要量都小于最大发送车的装载量，同时装载量最小的车子台数足以安排货运。下面通过一个实际例子来说明节约法的求解思路。下一页返回上一页4.5多回路运输路线例4-10已知配送中心P0向7个用户Pj配送货物，其配送路线网络、配送中心与用户的距离、用户之间的距离如图4-20所示，图中括号内的数字表示客户的需求量Qi（单位：t），线路上的数字表示两结点之间的距离（单位：km），现配送中心有8台4t卡车和3台6t两种车辆可供使用。试利用节约里程法制定最优的配送方案？解：首先做出配送中心与各用户间的运输里程表4-3。根据节约量公式，求出用户连接的费用节约值，见表4-4。初始方案为：配送中心向每个用户单独送货，需要7台4t的车，总里程为：下一页返回上一页4.5多回路运输路线车辆分配方案为：4t车辆使用7台，6t车辆使用0台。在初始解的基础上，选出具有最大节约值的格子，该格子应满足下列条件：（1）用户Pi和用户Pj不在同一条线路上；（2）原计划分别运送用户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和用户P4的需要量分别改为的总载运量。下一页返回上一页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台。由节约量公式可知，总里程又减少了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行，因此不予考虑和，若选进行优化，则现有车辆吨位不够。因此用户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.节约法的改进前面已经讲到，启发式算法并不能保证得到问题的最优解。节约法求解配送路线优化问题，有时就会出现仅得满意解的情况，这时就需要结合其他的方法来求最优解。下一页返回上一页4.5多回路运输路线例4-11同样是一个配送中心，7个用户的问题，改变一下上例的部分参数。表4-10给出了配送中心与用户的距离、用户之间的距离以及客户的需求量Qi（单位：t）解：根据节约量公式，求出用户连接的费用节约值，见表4-11。配送路线优化的过程简写如下：初始方案：对每个用户单独送货，需7台4t的车，总里程为：下一页返回上一页4.5多回路运输路线改进1：最大节约量Smax=S34=16,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-7=81km。最优方案为：1、2商店共同送货，货物量4.8t，6t车；3、4、5商店共同送货，货物量5.3t，6t车；6、7商店共同送货，货物量3.9t，4t车。总里程81km。如果在遇到相同节约值的时候做出不同的选择，会有如下另一种方案。下一页返回上一页4.5多回路运输路线初始方案：对每个用户单独送货,需7台4t的车,总里程为：改进1：最大节约量Smax=S34=16,Q34=Q3+Q4=2.9t。需要6台4t的车，总里程S1=124-16=108km。改进2：Smax=S17=11，Q17=Q1+Q7=4.9t。需要4台4t的车，1台6t的车，总里程S2=108-11=97km。改进3：Smax=S67=11，Q176=Q17+Q6=7.1t，不可行。Smax=S23=9，Q234=Q2+Q34=4.5t。需要2台4t的车，2台6t车，总里程S3=97-9=88km。下一页返回上一页4.5多回路运输路线改进4：Smax=S45=9，Q2345=Q234+Q5=6.9t，不可行。Smax=S56=8，Q56=Q5+Q6=4.6t。Smax=S12=7，Q12=Q1+Q2=4.8t，需要3台6t车，总里程S4=88-8=80km。最优方案为：1、7商店共同送货，货物量4.9t，6t车；2、3、4商店共同送货，货物量4.5t，6t车；5、6商店共同送货，货物量4.8t。总里程80km。进一步地，如果用分支的形式将各种路线组合优化的方案对比，可以得到如下分支图，如图4-21所示。通过分支法，对此类问题的求解过程进行改进，可以更精确地得到最优解、次优解，以便做出更好的选择。下一页返回上一页4.5多回路运输路线4.5.2多配送中心配送规划现实生活中，为提高经济效益，有时候需要使用多个配送中心来进行配送，即利用多个配送中心为用户服务。此类问题可以看作是由几个封闭循环线路的旅行商问题，是组合优化问题的一种，调度的目标是寻求在完成用户的货运任务前提下，使用最少的车辆数并且安排各车的行驶路线。对此类问题有两类基本的算法。下一页返回上一页4.5多回路运输路线一类先对用户分组后安排路线，即把用户按一定调度规则划分为不同的组，每一组对应一个配送中心，然后对每一个配送中心求解。如果任何一个配送中心的车辆不足以安排任务，就修正原来的分组，并对新的单配送中心问题进行求解。这一过程按照分组规则一直进行下去，直到得到满意的解为止。对用户进行划分的规则可以是“就地就近发送”等实际经验调度（目前一般采用这种方式），也可以是一些对局优化有贡献的启发式规则。下一页返回上一页4.5多回路运输路线另一类则先安排线路后分组，即先对所有用户求解线路安排，而不管配送中心在哪，这样就构建了一条大的路线（通常不可行），它包含了所有的用户。然后，对每一辆车的路线，指定一个配送中心。其目的是在满足配货中心的车辆限制下使得总的运输距离最小。当车辆进出配送中心的距离远小于它消耗在运输货物的行驶距离时，这种方法就比较合理，求解的满意度也很高。下一页返回上一页4.5多回路运输路线现在采用先分组后安排路线的方法，对此类问题的求解进行讨论。设di（t）表示用户i和配送中心t之间的距离，记为集合Di={di（t），t=1，…，p}，p是配送中心的个数。计算r（i）=minDi/subminDi，minDi和subminDi分别表示集合Di中的最小值和次小值，取适当的δ，比较r（i）和δ的大小，当r（i）＜δ，把用户i分配给minDi对应的配送中心，如果r（i）≥δ，这时用户i为边界点，对边界点的分配如下：下一页返回上一页4.5多回路运输路线当r（i）≠1时，利用节约法进行分派。首先考虑由最近的配送中心发出配送车服务每一个点，构成初始解。各点对最近配送中心的分派都是暂时的，一旦两个或者多个点已被分派给一个配送中心发出的线路，这些点就不再分派给其他的配送中心。当点i和j都不与配送中心相连时，进行连接，连接的节约量按上述节约量公式计算。根据节约值，连接用户i和j。在这种情况下，点i被分配离它最近的配送中心。下一页返回上一页4.5多回路运输路线第二种情况，当r（i）=1时，如果点j和点k已分派给某配送中心t，插入点i，对配送中心t而言产生的附加费用是dijk（t）=dik+dji-djk，并且将用户i分派给使得dijk（t）最小的配送中心。通过改变δ的大小，可以控制边界点的个数。当δ=0时，所有的用户都是边界点，当δ=1时，所有的用户均分派给最近的配送中心。对用户的分组完毕后，就可以分别对每组的用户进行单配送中心的车辆调度安排，得到各组的路线安排。下一页返回上一页4.5多回路运输路线例4-11现有三个配送中心（标号1，2，3）给10个用户（标号4，5，…，13）进行配送。配送中心与用户之间，以及用户之间的距离如表4-12所示。对各用户进行分组，以便求单配送中心的车辆路线安排。解：计算r（i），得表4-13。取δ=0.7，所有r（i）＜δ的用户被分配给最近的中心，如表4-14所示。对r（i）≥δ且r（i）≠1的点8，10和12，两两相连，计算节约量sij（t）（i，j=8，10，12；t=1，2，3），并且按照从大到小的顺序排列，得表4-15。下一页返回上一页4.5多回路运输路线根据表4-15，把用户8和用户10分配给配送中心1，得到永久分配。把用户12分配给最近的配送中心3。对于r（i）=1的用户13，分配给不同的配送中心时，需插入到已分配给该配送中心的各用户点之间，根据插入点产生附加费用的公式dijk（t）=dik+dji-djk，计算节约值：对配送中心1，其现已安排的用户为4，5，8，10。d13,4,5=101+43-44=100d13,4,8=101+121-63=159d13,4,10=101+55-65=91下一页返回上一页4.5多回路运输路线d13,5,8=101+43-44=100d13,5,10=43+55-69=29d13,8,10=121+55-35=141对配送中心2，其现已安排的用户为11。d13,11=37+48-32=53对配送中心3，其现已安排的用户为6，7，9，12。d13,6,7=89+98-75=112d13,6,9=89+73-40=122d13,6,12=89+64-67=86下一页返回上一页4.5多回路运输路线d13,7,9=98+73-53=118d13,7,12=98+64-46=116d13,9,12=73+64-28=109从上述节约值中取最小值29，故把