第12章 货物运输的优化求解
本章学习目的：了解常见货物运输问题，如产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，并掌握对这些问题进行系统分析、数学模型建立和优化求解的一些方法，以提高货物运输的科学管理水平。
降低物流成本、提高物流效率，要求对货物运输进行优化组织，即要运用掌握的资源（人力、物力、财力）合理安排运输任务，消灭对流、迂回、重复等不合理现象，尽量以最少的资源来完成最多的任务。这就需要对货物运输问题进行系统分析，建立模型，并应用各种数学方法进行求解，以实现货物运输的科学管理。常见的货物运输问题有产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，下面就这些问题的优化求解进行介绍。
12.1 产销运输问题
销售商在组织某一产品销售时，需要从多个厂家或产地采购，运输到其不同的销售门店，而每个厂家或产地可提供的产品数量和运价各不相同，如何组织运输才能使总运费最低？或生产厂家从多个地方采购原料时，各地原料可供数量和运价不同，如何确定各地原料调拨量，才能使运输费用最省？这就是产销运输问题，根据供求双方的物资数量关系，可分为产销平衡的运输问题和产销不平衡的运输问题。
12.1.1 产销平衡的运输问题
12.1.1.1 模型分析
产销平衡的运输问题一般可表述为：某种物资有m个产地A1，A2,...,Am，其供应量分为a1,a2,...,am;有n 个销地B1,B2,...,Bn,其销量分为b1,b2,...,bn;产地物资供应量总合等于销地物资销量（需求量）总合；从产地Ai到销地Bj的物资量和单位物资运价为分为xij,cij,求此时调运物资最佳方案。
对此问题可有下述线性规划模型：
minz=∑∑cijxij
i=1j=1
mn
s.t.
∑x
j=1m
n
ij
=ai=bj
m
i
(i=1,...,m)
（12.1）
∑x
i=1nj=1
ij
(j=1,...,n)
∑b=∑a
j
i=1
xij≥0
12.1.1.2 表上作业法求解
(i=1,...,m;j=1,...,n)
12-1
上述模型是一种线性规划模型，自然可以用单纯形法求解，但是根据其特殊结构而建立的表上作业法比起用单纯形法要简单得多。其思路为：由初始运输方案开始，通过检验、改进，最后获得最优运输方案。
下面结合例12-1具体说明表上作业法的步骤和方法：
例12-1 设有两个煤矿供应三个城市用煤，煤矿A1和A2的日产量分别为a1=200吨;a2=250吨。三城市（B1,B2,B3）的日销量分别为b1=100吨，b2=150吨，b3=200吨。假定每吨货物的社会运输费与出行公里线性有关，取cij代表煤矿I至城市j的最短距离。已知c11=90公里，c12=70公里，c13=100公里，c21=80公里，c22=65 公里，c23=80公里。问如何安排运输使运输费用最省？
解：设xij为煤矿I运往j的煤量，根据每个煤矿产煤总量和城市的用煤总量，xij(I=1,2;j=1,2,3)必须满足下列条件：
x11+x12+x13=200 x21+x22+x23=250 x11+x21=100 x12+x22=150
x13+x23=200
目标函数为：minz=90x11+70x12+100x13+80x21+65x22+80x23
1.列运输平衡表
列表时要求表内供销平衡，并将运费标入表内空格，如下表12-1所示：
表 12-1 运输平衡表 需 供 B190 A1X11X12B270 X13B3供应量 100200 80 A2需求量 X21100 X22150 65 X23 200 80 250 450 2.建立初始调运方案
鉴于最好运输方案是使总运费最小，采用最小元素法，即在平衡表中挑取运价最小或较小的供需点格子尽量优先分配的调运方法。一行（或一列）满足了，就划去一行（或一列），如果运费相等时可任选一个，直到全部分配完为止。分配时注意一个问题，即分配数字的格数要为“行数+列数-1”，若分配完时出现规定数时，应在适当的空格补零，这个补零的格子在数量上是零，但要当成非零数字格对待。如表12-2所示： 表 12-2 初始调运方案表 需 供 B190 A10 B270 200 B3供应量 100200 80 65 80 12-2
A2需求量
100 100
150 150
200
250 450
表12-2先从A2,B2（c22最小）开始，确定c22=150,划去余下的B2 列，然后确定x21=100(c21
为剩下方格中最小运价)，划去余下的B1列，A2的供应量也同时得到满足，故此时余下的A2也被划去，最后确定x12为200，形成初始调运方案。
3.方案的检验和调整
（1）闭回路
从调运方案的任意空格出发，沿水平方向或垂直方向前进，而遇到填有数字的方格，折转90度前进，当然可以直接穿过数字格和空格，但只能遇有数字的格才能折转，只能水平、垂直方向前进，不能对角线移动，这样经过多次折转直到回到原来出发的空格，形成一条闭回路。
（2）位势法检验
①由方案表列出检验表。表中行列数与方案表一样，运价在每个格的右上角，原方案表中的空格填写检验数，原方案表中的数字格为检验表中的空格，原方案表中的供应量、需求量格填写行与列的位势，称为行或列位势格。
②求位势。记第i行位势为ui ，第j列位势为vj，可任选一个位势格填任意数，通常取0作为该格的位势。其它位势格的位势由下列法则求出：每个空格右上角的运价cij等于该行位势与该列位势之和，即cij=ui+vj. 例如在表12-2中，任取左下端的位势格为0，由上述法则求出其它4个位势格的位势,如表12-3。
表12-3 位势表 需 供 B190 A10 B270 200 B3Vj10090 80 A2Ui
100 0 150 -15 65 10 80 80 ③求检验数。若空格位于第i行第j列，则其检验数σij按下式求出：
σij=cij−ui−vj
例如由表12-3可求出1行2列空格的检验数σ12=70+15-90=-5，其它如检验数表12-4所示。
表12-4 检验数表 供 需 B190 A1 -5 B270 B3vj10090 80 65 12-3 80 A2ui
0
-15
-10 10
80
由表12-4知，有负的检验数存在，这表明12-2所给的运输方案不是最优的，需要进行调整。
（3）调整运输方案。当运输表对应的检验表中有负的检验数时，需在运输方案表上对运输方案进行调整。
①确定闭回路。在需调整的运输方案表上选取对应的检验数为负的格作为调整格， 若有两个以上格的检验数为负，选其中检验数绝对值最大的格为检验格，从检验格出发在运输方案表上作闭回路。
例如在表12-4中，A2B3格的检验数是-10，为绝对值最大的负检验格，故选取此格为调整格，并用虚线在运输方案表上作闭回路，如表 12-5所示。
表12-5 闭回路表 需 B2B3 B1供 90 70 65 150 150 200 450 200 80 250 100供应量 200 A10 80 A2需求量
100 100 ②在闭回路上作运输量最大的调整,得出新的运输方案。从空格开始，沿闭回路在各偶数格中挑选运量最小的作为调整量，调整闭回路各点的运输量。
例如在表12-5中，闭回路上偶数格最小运输量为min(200,100)=100,调整闭回路各点运输量，得表12-6.
表12-6 新运输方案1表 需 供 B190 A1100 B270 100 250 B3供应量 200 10080 A2需求量
100 150 150 65 100 200 80 450 （4）返回（2），对新运输方案进行位势法检验。若无负检验数，则此方案为最优方案，否则继续进行调整。 例如对于表12-6，得检验表12-7。
12-4
表12-7 新运输方案1检验表 供 需 B190 A1 10 80 A2ui
表12-7中有负得检验数，继续进行调整，得新运输方案表12-8.
表12-8 新运输方案2表 需 供 B190 A1100 100 B270 B3供应量 100B270 -15 B3vj10090 65 10 80 70 0 -5 200 80 A2需求量 100 50 150 65 200 200 80 250 450 对表12-8进行检验，得检验表12-9
表12-9 新运输方案2检验表 供 需 B190 A1 B270 15 B3Vj10090 80 A2ui-5 0 -20 65 -5 80 85 表中有负检验数，继续进行调整，得新运输方案表12-10
表12-10 新运输方案3表 供 需 B190 A150 150 B270 B3供应量 100200 80 65 12-5 80 A2需求量
50 100
150
200 200
250 450
对此运输方案进行检验，得检验表12-11
表12-11 新运输方案3检验表 需 供 B190 A1 B270 10 B3Vj10090 80 A2Ui 0 5 -20 65 0 80 80 从表12-11中可以看到，检验数全是正数，因此表12-10中的运输方案为最优方案，即应确定A1向B1、B2调运煤数量分别为50、150;A2向B1、B3调运数量分别为50、200。
二.产销不平衡时的运输问题 （一）产大于销的运输问题
对于产量大于销量即
∑b<∑a
jj=1
i=1
nm
i
的运输问题，必然有些产地的产品不能安排运输，
此时引入虚拟需求点，令其需量等于总供量与总需量之差，并设其相应运价为0。这样，就可以用上面介绍的表上作业法求解产大于销的运输问题。 （一） 销大于产的运输问题
对于销量大于产量即
∑b>∑a
jj=1
i=1
nm
i
的运输问题，必然有一些销地不能得到满足，发生
缺货，此时引入虚拟供应点，并设其相应运价为0。这样，就可以用产销平衡的表上作业法求解销大于产的运输问题。
12.2 分配运输问题
在运输过程中经常遇到这样的问题，需完成几条运输线路的任务，恰好有几个运输单位可承担这些任务。由于每个单位的情况各不相同，其完成各项任务的效率（或效益）也不同，如何安排这些运输单位去完成任务，使效率（或效益）也最高，这一类问题统称为分配问题。
12.1.1 模型分析
例12-2 某材料厂有B1、B2、B3三台叉车可分配给A1、A2、A3三个仓库进行搬运作业，其中任一叉车都可以在任一仓库中进行搬运工作，只是搬运作业费不同，各台叉车相应作业费Cij如表12-12所示，要求一台叉车只分配给一个仓库使用，试求搬运作业费用最小的分配方案。
12-6
叉车 cij表12-12 效率矩阵表 仓库 B1 25 31 35 B2 15 20 24 B3 22 19 17 A1 A2 A3对应于每个分配问题， 都有类似于表 12-12 的数字表，称之为效率矩阵，其元素 cij
＞0(i,j=1,2,...,n)表示分配第i个单位去完成第j项任务时的效率(或时间、成本等)。根
据问题引入变量xij，并按以下规定取值：
⎧1第i个单位被分配去完成第j项任务
xij=⎨
第i个单位不去完成第j项任务0⎩
其中i=1,2,...,n; j=1,2,...,n
当问题要求极小时,有数学模型: minz=∑∑cijxij
i=1j=1n
n
st.
n⎧∑x=1,j=1,2,...,n⎪i=1ij
⎨n (12.2)
⎪∑xij=1,i=1,2,...,n⎩j=1
上述模型中,约束条件1表明第j项任务只能由1个单位去完成；约束条件2则说明第i个单位只能完成1项任务。对于求极大问题时，可转化cij为c’ij,即令c’ij=cij-max{cij},将原maxz=∑∑cijxij转化为minz’= c’ijxij求解。
12.2.2 匈牙利算法
可以看到，分配问题是0-1规划问题，对于几个单位分配几项任务的分配问题，总共有n！种可能的分配方案，若用隐枚举法求解，当n较大时，计算量是很大的。由匈牙利数学家考尼格给出的匈牙利算法，是一种求解分配问题最简单、最有效的方法。
匈牙利法的主要依据是，在效率矩阵的任何行或列中，加上或减去同一常数，并不改变最优分配。利用此性质，可使原效率矩阵变换为含有很多0元素的新效率矩阵，找出在其中的位于不同行、不同列的n个独立的0元素，将其取值为1，其它元素取值为0，即得原分配问题的最优解。
以下通过求解例12-2的分配问题，介绍匈牙利算法 已知其效率矩阵为：
⎡251522⎤
⎥⎢ 312019 ⎥⎢
⎢⎦⎣352417⎥
第一步 变换效率矩阵，使其每一行和每一列都至少有一个0元素，具体通过减去每行、每
列的最小元素，如下：
⎡1007⎤⎡007⎤⎡251522⎤-15
⎥⎥⎢⎢⎥⎢ 312019 -19 →⎢1210⎥ →⎢210⎥
⎥⎢
⎢⎢⎢⎦⎦⎣1870⎥⎣870⎥⎦-17 ⎣352417⎥
−10
12-7
第二步 试求最优分配方案。
（1）从1行开始，依次检查各行，找出只有一个未标记的0元素的行，并将该元素用“0”表示，与该元素同行同列的其它0元素用“Ф”表示，其含义为，0元素对应的任务仅由所对应的单位去完成，此单位不再去完成其它任务，这项任务也不再由其它单位完成。0和Ф称为已标记的0元素。重复此过程，直到每一行没有一个尚未标记的0元素，或至少有两个未标记的0元素。
（2）依次检查各列，找出只有一个未标记的0元素的列，将该元素标以0，并与该元素同行同列的其它未标记0元素标以Ф，直到每列没有一个尚未标记的0元素，或至少有两个未标记的0元素。
（3）重复上述步骤，直到效率矩阵中没有未标记的0元素为止，若n行n列效率矩阵中恰有n个0元素，就得到最优分配方案，否则，仍需进行效率矩阵调整，本例中为： ⎡0 Ф 7 ⎤
⎥⎢ 2 1 0 ⎥⎢
⎢⎣8 7 Ф ⎥⎦
第三步 继续调整效率矩阵
（1）对每个0元素划一条水平线或垂直线，使这些线覆盖所有0元素。直线个数与0元素个数相同。本例中为： ⎡0 Ф 7 ⎤⎥⎢ 2 1 0 ⎥⎢⎢⎦⎣8 7 Ф ⎥(2)在直线不穿过的所有元素中找出最小元素。
(3)在没有水平线的各行减去此最小元素,有垂直线的各列加上此最小元素,得新的效率
矩阵。
本例中，所求最小元素为1，计算过程为： ⎡0 Ф 7 ⎤⎡008⎤
⎥ →⎢100⎥ ⎢ 2 1 0 -1 ⎥⎥⎢⎢
8 7 0 ⎥-1 ⎢⎢⎦⎣⎣760⎥+1 ⎦第四步 回第二步,直到求出最优分配方案。 本例中，对修改后的效率矩阵重复第二步得：
⎡0 Ф 8 ⎢ 1 0 Ф ⎢⎢⎣7 6 0 ⎤
⎥ ⎥⎥⎦
已经得3个0元素，故得最优分配方案为： A1→B1，A2→B2，A3→B3
根据原效率矩阵，3叉车总搬运作业费为： 25+20+17=62元
12.2.3 巡回运输问题（旅行商问题）
在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1,2,…,n），货车载重量为Q，若满足
∑b
i
≤Q，则该网点只需一辆货车巡回送货即可。显然，在这种情
况下使费用最省的方案就是合理安排货车访问各用户的顺序，使货车的巡回线路的总距离最短，这也就是旅行商问题。
12-8
例12-3 已知5用户间距离如表12-13，其中d(i,j)=∝表示从第i个用户到第j个用户是没有意义的, 用户1为物流网点所在位置，如果只考虑将每个用户都当作一个出发用户,每个用户都当作一个到达用户,则对每个出发用户都要选择一个到达用户,而每个到达用户只能有一个出发用户到达该地,将问题变成了一个分配问题,可用匈牙利法求解。
表12-13 用户间距表 出发 1 2 3 4 5 到达 1 2 3 4 5 ∝ 1 7 4 3 2 ∝ 6 3 4 1 6 ∝ 2 1 1 5 4 ∝ 6 7 5 4 5 ∝ 以例12-13说明求解步骤
第一步 令d(i,i)=∝,不存在通路的也记为∝,得距离阵,通常d(i,j)与d(j,i)不一定相同,即矩阵不一定对称。
第二步 对距离矩阵用匈牙利法求解,若得到无环路的路线,则就是最优路线;若路线有环路,就不是最优路线,但所走总距离给出了旅行商问题总距离的下界。
在本例中，匈牙利法求解过程为：
⎡∞1743⎤-1 ⎡∞0632⎤⎡∞⎢2∞634⎥-2 ⎢0∞412⎥⎢φ⎢⎥⎢⎥⎢
-1 ⎢16∞21⎥ →⎢05∞10⎥→⎢φ⎥-1 ⎥⎢⎢⎢
154∞6043∞5⎢⎥-4 ⎢⎥⎢0 ⎢⎢⎣7545∞⎥⎦⎣3101∞⎥⎦⎢⎣3 −1
得不考虑环路下的最优方案： 1→2，2→4，4→1，3→5，5→3
所走总距离为：
2⎤
∞40 2⎥⎥
⎥ 5∞φ0 ⎥
43∞5⎥10 φ∞⎥⎦
0 62
1+3+1+1+4=10
可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。 第三步 出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。
本例中，出现两个环路，1→2→4→1和3→5→3，打开节点数少的环路，分别令d(3,5)=∝和d(5,3)=∝求解。
32⎤⎡∞
⎢2∞634⎥-2 ⎢0∞412⎥⎢φ⎢⎥⎢⎥⎢
-1 ⎢16∞2∞⎥ →⎢05∞1∞⎥→⎢φ⎢⎥-1 ⎢⎥⎢154∞6043∞5⎥-4 ⎢⎥⎢0 ⎢⎢⎢⎦⎦⎢⎣7545∞⎥⎣3101∞⎥⎣3 −1 −2
可得无环路的最优方案: 5→3→4→1→2→5
（1）当d(3,5)=∝时,用匈牙利法求解 ⎡∞1743⎤-1 ⎡∞06
⎥∞4φ0 ⎥
5∞0 ∞⎥
⎥
43∞5⎥10 φ∞⎥⎦
0 6
2φ⎤
12-9
所走总距离为: 1+4+2+1+4=12
（2）当d(5,3)=∝时,用匈牙利法求解
⎡∞1743⎤-1 ⎡∞0632⎤⎡∞⎢2∞634⎥⎢0∞412⎥⎢0 -2 ⎢⎥⎢⎥⎢
⎢16∞21⎥-1 →⎢05∞10⎥→⎢φ⎢⎥-1 ⎢⎥⎢154∞6043∞5⎢⎥⎢⎥⎢φ-5 ⎢⎢⎣75∞5∞⎥⎦⎣20∞0∞⎥⎦⎢⎣2
−3
得路线: 1→2,2→1,3→5,4→3,5→4 总距离: 1+2+1+4+5=13
3
∞114∞140 ∞0∞0 0 3
2⎤2⎥⎥⎥ 0 ⎥5⎥∞⎥⎦
可以看到:
上述方案出现环路1→2→1和3→5→4→3,如果打开环路求解,其总距离一定不小于13,而已经得到总距离为12的路线,故不必再作计算；
因此得上述旅行商的最优路线为:5→3→4→1→2→5,总距离为12。
12.2.4 旅行商问题的神经网络求解
虽然可以应用匈牙利算法求解旅行商问题，但是该方法需要进行多次试探，只适用于小规模的问题，而随着距离矩阵维数的增加，求解的时间将大量增长，求解的复杂度也急剧增加，该方法变得不再适用，此时可采用人工智能的方法——神经网络方法进行求解。
1.连续Hopfield神经网络模型
连续Hopfield神经网络模型如图12-1所示。第i个神经元的输入为ui ，输出状态为vi；运算放大器模拟神经元的转移函数g(其中g为sigmoid函数)，跨导Tij模拟神经元之间互连的突触特性，电容ci 及电阻Ri用来模拟生物神经元的输出时间常数。设有n个神经元互连，则可用下述非线性微分方程描述：
（a）Hopfield神经元
12-10
（b）Hopfield神经网络 图12-1 连续时间神经网络模型
n
u(t)⎧dui(t)
=∑Tijvj(t)−i+Ii⎪ci
(12.3) dtRi⎨i=1
⎪⎩vi(t)=g(ui)
对式(12.3)可以定义系统的能量函数为：
nn
1nn1vi−1
E=−∑∑Tijvivj−∑viIi+∑∫g(v)dv (12.4)
02i=1j=1i=1Rii=1
dE
可以证明，对于该能量函数，恒有≤0，即当t→∞，网络达到稳态。显然应用网
dt
络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成(12.4)式的形式，然后应用式(12.3)运算到网络收敛即可。通常在用Hopfield神经网络求解实际问题时，一般忽略能量式中的积分项，将能量函数简化为下式(12.5)，以便目标函数的映射。
n
1nn
E=−∑∑Tijvivj−∑viIi (12.5)
2i=1j=1i=1
2.神经网络求解旅行商问题
对于n个用户的TSP问题，任何一个用户在最终访问路径上的访问次序可用一个n维向量表示，因此每一个用户可用n个神经元表示。下面仍以例12-3为例说明，如果用户1第3个被访问，则表示为00100，即第三个神经元输出为1，其余为0。为了表示n个用户，可简单地用n╳n换位矩阵表示，如表12-14所示。 表 12-14 换位矩阵 次序 1 2 3 用户 1 2 3 4 5 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 4 5 上述换位矩阵表示巡回线路为：3→2→1→4→5
巡回距离为：distance=d(3,2)+d(2,1)+d(1,4)+d(4,5)
12-11
显然，一条换位距阵可表示一条有效路径，如果要构成一条有效的最短巡回路线，必然要求满足下列条件：
（1）换位矩阵中每行只能有一个为“1”； （2）换位矩阵中每列只能有一个为“1”； （3）换位矩阵中元素“1”之和应为n；
（4）所构造的函数的极小值对应。
用n╳n=25个神经元的输出vxi(1≤x≤n,1≤i≤n)表示换位矩阵中的某一元素（取值为“0”或“1”），其中x表示用户，i表示访问次序，则可以写出与本问题对应的计算能量函数为：
AnnnBnnnCnn
E=∑∑∑vxivxj+∑∑∑vxivyi+(∑∑vxi−n)2
2x=1i=1j≠i2i=1x=1y≠x2x=1i=1
+
D
∑∑∑d(x,y)vxi(vy,i+1+vy,i−1)2x=1y≠xi=1
n
n
n
(12.6)
式(12.5)中第1、2、3项对应于换位矩阵的条件（1）、（2）、（3），第4项对应于条件（4），即使路径最短的目标要求。A、B、C、D为4个正常系数，将式（12.6）写成如（12.5）所表示的Hopfield能量函数标准形式，得Txi,yi的表达式和Ixi的值如下：
⎧Txi,yi=−Aδxy(1−δij)−Bδij(1−δxy)−C−Dd(x,y)(δj,i+1+δj,i−1)(1−δxy)
(12.7) ⎨
=ICN⎩xi
其中δxy
⎧1=⎨⎩0
ifx=y
由(12.6) 得Hopfiled网络运行方程式如式（12.8）:
nnnnn
uxi⎧duxi
=−−C(∑∑vxj−n)−A∑vxj−B∑vyi−D∑d(x,y)(vy,i+1+vy,i−1)⎪
(12.8) τ⎨dtx=1j=1j≠iy≠xy≠x
⎪⎩vxi=g(uxi)x=1,2,L,n;i=,2,L,n;
1
作用函数g选用sigmoid函数g(uxi)=(1+th(uxi/u0)),网络初始值可置为
2
uxi=1/n,在选择适当的系数A,B,C,D, τ,进行迭代运算，得网络收敛稳定输出vxi，即可
获得巡回配送的最短路径。
12.3 网络流问题
12.3.1 图的基本概念
考虑6个城市间的交通路线图,如图12-12所示,图中的点V1、V2、V3、V4、V5、V6代表6个城市，又称为顶点，连接各顶点的弧记作（V1、V2）、（V2、V3）、...等。这种表明各点之间连接关系的图形，通常称为图。
从一个顶点沿着弧、顶点、弧、顶点的顺序，回到出发点的路线称为回路，如图12-2中，V1→V2→V4→V3→V1、V4→V5→V6→V4都是回路，不含回路、各顶点又相互连通的图称为树，如图12-3就是一个树。
V1
V3 V5
V2
V2
V4 V3 V4
V6 12-12
V5
V6
图12-2 回路 图12-3 树
在实际问题中，对于一个图，总要考虑它们代表的各城市间道路的交通流量、流动方向，因此需在各顶点弧上标明流动方向和流量限制，这种表示流动方向和流量限制的图称为网络或网络流，如图12-4。
V3 V5 V4
V1 V2
V6
图12-4
在网络流中有些点只有发出，称不发点或源点，如图12-4中的V1；有些点只有收入，无发出，称为收点或汇点，如图12-4中的V6，还有些顶点既有收入又有发出，称为中间点。
12.3.2 网络最大流问题
1.问题的提出
已知连接产地V1与销地Vn的交通网，每一弧（Vi,Vj）代表从Vi到Vj的运输线，产品经由Vi输送到Vj，弧旁括号外的数字Cij为弧的容量，括号内的数字Xij为Vi到Vj的货运量，要求合理安排Xij，使V1到Vn的货运量最大。这种问题称为最大流问题，如图12-5所示。
V4
V2 6(3)
11(6)
10(5) 5(1) 2(3) 10(5) V1 3(2) V6
17(2) 8(3)
V3 V5
6(3)
图12-5
2.寻求最大流的标号法
对于包含n个顶点V1，V2...,Vn的网络流，V1为发点，Vn为收点，各段弧(Vi,Vj)上容量为Cij，设{Xij}是一个可行流，如果存在一条从V1到Vn的路线，这条路线具有以下特点：
（1）所有正向弧（弧的方向与流向一致）上 Xij 则称此条路线为可行流{Xij}的一个增广链，记 ε1=min{cij-xij| 当（vi,vj）为正向弧} （12.8） ε2=min{xij| 当 (vi,vj)为反向弧} (12.10) ε=min{ε1, ε2} (12.11) 由增广链的特点可知ε>0,按如下公式调整可行流{xij}为{x’ij}: 当(vi,vj)是增广链的正向弧 当(vi,vj)是增广链的反向弧 (12.12) 12-13 当(vi,vj)不在增广链上 ⎧xij+ε⎪ x'ij=⎨xij−ε ⎪x⎩ij 显然,此时{x’ij}仍为可行流,且它的值比{xij}增加了ε。 由此不难看出,对于可行流{xij},判断它是否最大流及对它进行调整,关键在于求出其增广链,标号法就是基于此来寻求最大流的,其具体步骤如下: 第1步 给发点以标号(0,+) 第2步 设vi已经有了标号,与vi相邻的点vj尚未标号。若在弧(vi,vj)上, xij 第3步 利用“反向追踪”，找出v1到vn的增广链，例如设vn的标号为(k,+)，则在增广链上vn前面的一点为vk,且弧(vk,vn)是正向弧，接下来检查vk，若其标号为(i,+)，则找出正向弧(vi,vk)；若标号为(i,-),则找出反向弧(vk,vi)，依此下去，一直追踪至具有标号(0,+)的发点v1，得到由v1到vn的一个增广链。 第4步 调整过程，由式（12.9）至(12.11)得出增广链的调整量ε,根据式(12.12)得出新的可行流{x’ij},令可行流{xij}={x’ij},去掉所有标号,重新上述标号、寻找增广链及调整过程，如果标号过程进行不下去，而vn尚未标号，则说明再也找不出增广链，当前可行流即为最大流。 例12-4 求出图12-5的最大流 解： 第1步 首先给v1标上（0,+） 第2步 检查v2，在弧(v1,v2)上，x12=5 第4步 因为增广链上的弧(v1,v2)、(v2,v4)、(v4,v6)都是正向弧，由式（12.9）、（12.11）得： ε=ε1=min(10-5,5-2,11-6)=3 根据式(12.12)调整增广链上每段弧的流量,经调整后可行流如图12-7所示。 V1 (0,+) V2 (1,+) V4 (2,+) V2 10(5) 6(3) 5(1) V4 11(6)2(3) V6 17(2)V5 V6 5 V V1 4(1) 3(2) V 3 (4,+) 8(3) V3 6(3) 图12-6 图12-7 重新执行1-4步，v1标上(0,+)，依次给v2标上(1,+)，给v3标上(2,+)，给v5标上(3,+),给v6标上(5,+)，得增广链v1→v2→v3→v5→v6，因为此增广链上的弧都是正向弧，由式(12.9)、(12.11)得： ε=ε1=min{10-8,4-1,6-3,17-2}=2 12-14 根据式(12.9)调整流量,得新的可行流如图12-8 V1 V2 10(10) 5(1) 4(3) 3(3) 3(2) 17(4) V3 6(5) V5 V6 5(5) V4 11(9) 8(3) 图12-8 对图12-8,重新标号、调整，v1标上(0,+),V3标上(1,+),v5标上(3,+),v6标上(5,+)，得 增广链v1→v3→v5→v6，此增广链上的弧皆为正向弧，由式(12.9)、(12.11)得 ε=ε1=min{8-3,6-5,17-4}=1 根据（12.9）调整流量,得新可行流如图12-9 V1 V2 10(10) 5(1) 4(3) 8(4) V3 图12-9 对图12-9,重新标号、调整，v1标上(0,+),V3标上(1,+),v4标上(3,+),v6标上(4,+)，得增广链v1→v3→v4→v6，此增广链上的弧皆为正向弧，由式(12.9)、(12.11)得 ε=ε1=min{8-4,5-1,11-9}=2 根据（12.9）调整流量,得新可行流如图12-10 V4 V2 5(5) 11(11) 10(10) 5(3) 3(3) V1 4(3) 3(2) V6 17(5)8(6) VV5 6(6) 图12-10 对图12-10,重新标号、调整，v1标上(0,+),V3标上(1,+),v4标上(3,+),v5标上（4,-），v6标上(5,+)，得增广链v1→v3→v4→v5→v6，其中(v1,v3)(v3,v4)(v5,v6)为为正向弧，由式(12.9)得 ε1=min{8-6,5-3,17-5}=2 (v4,v5)为反向弧，由式（12.10）得ε2=3 由式(12.11)得ε=min{ε1,ε2}=2,因此在此增广链的正向弧上流量增加2,反向弧上流量减少2,得可行流如图12-11. V2 10(10) V14(3) 5(5) V4 11(9)3(3) 17(5)V6 3(2) 6(6) V5 5(5) 5(5) V4 11(11) 3(1) 17(7)V5 3(2) 12-15 V6 8(8) V3 6(6) 图12-11 对图12-11显然用标号法再也不能得到一个增广链,故其所给的可行流即为最大流,最大流量=x12+x13=x46+x56=18 12.3.3 最小费用最大流问题 在实际运输工作中，人们除了考虑运量外，还需考虑成本问题，从而产生了最小费用最大流问题，即对于某个网络D=(V,A,C)，每个弧(vi,vj)上除了容量cij外，还给出了单位流量的费用bij，要求找出一个最大流x，使流的总输送费用b(x)=Σbijxij 最小。 解最小费用最大流问题的基本思想是，通过已知的由v1到收点vn的最小费用流x，寻找其对应的最小费用增广链，沿此增广链去调整x，实现最大流。 对于网络D=(V,A,C)，构造赋权有向图W（X），其顶点为原网络D的顶点，而把D中的每一条弧(vi,vj)变成两个相反方向的弧(vi,vj)和(vj,vi)，定义W（X）中弧的权wij为（其中长度为+∝的弧可从W（X）中略去）： 若xij wij=⎨ +∞ xij=cij (12.13) (12.14) ⎩⎧−bij若xij>0 wij=⎨ ⎩+∞ xij=0 在w(x)中寻找到的v1 到vn 的最短路即为关于可行流x的最小费用增广链。 最小费用最大流算法如下： 第一步：取x(o)=0为初始可行流，即流量为0的最小费用流，k=0 第二步：对于可行流x(k)，根据式(12.12)、(12.13)构造赋权有向图w(x)，并在此有向图中找出v1到vn的最短路。 第三步：若存在最短路，则此最短路为x的最小费用增广链，在增广链上对x进行调整，即 xij (k+1) (k)⎧xij+ε⎪(k)=⎨xij−ε ⎪x(k)⎩ij (k) (k) (k) 当(vi,vj)是增广链上的正向弧 当(vi,vj)为增广链上的反向弧 当(vi,vj)不在增广链上 其中 ε=min{ε1,ε2}(k) ε1=min{cij−xij| 当(vi,vj)为正向弧} (k) ε2=min{xij|当(vi,vj)为反向弧} (k+1) 得到新的可行流x 转第五步。 ,此可行流为同一流量中费用最小的可行流，若不存在最短路， 第四步 令k=k+1，重复第二步至第三步。 第五步 退出计算，所得x(k)即为最小费用最大流。 例12-5 求图12-12所示网络的从v1到v8的最小费用最大流，图中(vi,vj)上所标的三个数字依次表示 bij、cij、xij。 解：首先对x=0的初始可行流，根据式（12.13）、（12.14）构造赋权有向图w(x)如图12-13，并找出v1到v8的最短路径为：v1→v2→v5→v6→v8 (0) (0) 12-16 V1 V2 (2,4,0) (2,4,0) V5 (8,3,0) 2 V2 2 6 V5 3 8 (6,3,0) (3,2,0) V3 (7,3,0) (2,4,0) (4,4,0) (3,2,0) (3,2,0) (3,2,0) V6 (3,3,0) V1 V8 2 4 V3 7 3 3 3 V6 3 6 V8 V4 V7 V7 (6,4,0) 图12-12 图12-13 (0) (1) V4 (2,2,0) V4 2 V7 沿此增广链对x进行调整，显然可增加的流量为2，得可行流x，如图12-14所示，对(1)(1) x根据式（12.13）、（12.14）构造赋权有向图w(x)如图12-15，找出v1到v8的最短路径为：v1→v3→v7→v8 V2 V5 V2 (2,4,2) (2,4,2) (6,3,0) (3,2,2) (8,3,0) 2 -2 VVV V1 3 2 6 7 3 -2 V5 -3 8(7,3,0) 6 V1 3 V6 3 3 -36 (2,4,0) (4,4,0) (3,2,0) (3,2,0) (3,3,2) (3,2,0) V8 2 4 3 V8 (6,4,0) V4 (2,2,0) V7 V4 2 V7 图12-14 图12-15 沿此增广链对x进行调整，可增加的流量为2，得可行流x，如图12-15所示，对x (2) 构造赋权有向图w(x)如图12-17，找出v1到v8的最短路径为：v1→v2→v6→v8 V1 V2 (2,4,2) (2,4,2) (1) (2) (2) V5 (8,3,0) 2 V2 -2 2 -2 (6,4,2) 4 3 2 6 -2 V5 -3 83 6 (6,3,0) (3,2,2) V3 (7,3,0) (2,4,2) (4,4,0) (3,2,0) (3,2,2) (3,2,0) V6 V1 (3,3,2) V8 V3 7 -3 3 V6 -3 V8 -6 V4 (2,2,0) V7 V4 2 V7 图12-16 图12-17 (2)(3)(3) 沿此增广链对x进行调整，可增加的流量为1，得可行流x，如图12-18所示，对x构造赋权有向图w(x)如图12-19，找出v1到v8的最短路径为：v1→v4→v7→v8 V1 V2 (2,4,3) (2,4,2) (3) V5 (8,3,0) 2 V2 -2 2 2 -6 6-2 V5 -3 8(6,3,1) (3,2,2) V3 (7,3,0) (2,4,2) (4,4,0) (3,2,0) (3,2,2) (3,2,0) V6 (3,3,3) V3 7 -3 3 3 V6 -3 6 -6 V8 V1 4 -2V8 (6,4,2) V4 (2,2,0) V7 V4 2V7 图12-18 图12-19 12-17 沿此增广链对x进行调整，可增加流量2，得可行流x，如图12-20所示，对x构造赋权有向图w(x)如图12-21，找出v1到v8的最短路径为：v1→v2→v5→v8 V2 2 V2 V5 (2,4,2) (2,4,3) V1 (2,4,2) (4,4,2) (3,2,0) (6,3,1) (3,2,2) (8,3,0) 2 -2 2 -24-4 3 (4) (3)(4)(4) V5 -2 -3 8V3 (7,3,0) (3,2,2) (3,2,0) V6 (3,3,3) V1 V8 -6 6V3 7 -3 3 V6 -3 -6 V8 (6,4,4) V4 (2,2,2) V7 V4 -2 V7 图12-20 图12-21 沿此增广链对x进行调整，可增加流量1，得可行流x，如图12-22所示，对x构造 (5) 赋权有向图w(x)如图12-23，找出v1到v8的最短路径为：v1→v3→v6→v2→v5→v8 V1 V2 (2,4,4) (2,4,3) (4) (5) (5) V5 (8,3,1) -2 V2 2 -24-4 3 2 -6 6 -2 V5 -3 8-8 (6,3,1) (3,2,2) V3 (7,3,0) (2,4,2) (4,4,2) (3,2,0) (3,2,2) (3,2,0) V6 (3,3,3) V1 V8 V3 7 -3 3 V6 -3 -6 (6,4,4) V4 V7 V4 (2,2,2) -2 图12-22 图12-23 (5) (6) (6) V7 沿此增广链对x进行调整，可增加流量1，得可行流x，如图12-24所示，对x构造 (6) 赋权有向图w(x)如图12-25，找出v1到v8的最短路径为：v1→v3→v6→v5→v8 V1 V2 (2,4,4) (2,4,4) V5 (8,3,2) -2 2 -2(6,4,4) -4 4 V2 6-2 V5 8-8 (6,3,0) (3,2,2) V3 (7,3,1) (2,4,3) (4,4,2) (3,2,0) (2,2,2) (3,2,2) (3,2,0) V6 (3,3,3) V1 V8 -3 V3 7 -3 3 -7 3 V6 -3 -6 V8 V4 -2 图12-24 图12-25 (6) (7) V7 (7) 沿此增广链对x进行调整，可增加流量1，得可行流x，如图12-26所示，对x构造 (7)(7) 赋权有向图w(x)如图12-27，可以看到已无从v1到v8的最短路径。可知x即为最小费用最大流，其网络图如图12-26。 V2 (2,4,4) (2,4,4) V1 (2,4,4) (4,4,2) (3,2,0) (2,2,2) V5 (8,3,2) -2 -2 V2 6-2 -3 V5 3 -8 (6,3,0) (3,2,1) V3 (7,3,2) (3,2,2) (3,2,0) V6 (3,3,3) V1 V8 V3 7 -3 -7 3 V6 -3 -6 V8 (6,4,4) 4-4 3 V4 -2 V7 图12-26 图12-27 12.3.4 最短路径问题 12-18 对于包含n个顶点v1,v2,...,vn的有向网络流,假设无负权,已知弧(vi,vj)的权为wij,求v1到vn的最短路径,以Lij表示从vi到vj的最短距离,则对此问题有Dikstra算法如下: 第一步 给发点v1以标号(1,0),L11=0。 第二步 从已标号顶点出发，找出与这些顶点vi相信相邻所有顶点，若 L1j=min(L1i+wij) (12.15) i,j 则对vj标号为(i,L1j) 第三步 重复第二步，直到所有的顶点都标号为止，每个顶点标号内的第二个数字即为v1到该顶点的最短距离，运用反向追踪可找出此最短路径。 例12-6 在图12-28中，求v1到v7的最短路线。 V2 1 V1 3V3 1 214V4 3V5 2V6 2V7 图12-28 解：首先给出发点v1以标号(1,0),L11=0，从v1出发，与v1相邻的顶点为v2、v3 、v4，由式（12.15）得 L14=min{0+1,0+2,0+3}=1 , 故v4标号为(1,1). 从v1 、v4出发，有相邻顶点v2、v3、v6，由式（12.15）得 L12=min{0+2,0+3,1+3}=2,故v2标号为(1,2). 对与已标号点{v1 ,v2 ,v4}相邻顶点v5、v6、v3，由式（12.15）得 L13=min{0+3,2+1,1+3}=3, 故v3标号为(1,3). 对与已标号点{v1,v2,v3,v4}相邻顶点v5、v6、v7，由式（12.15）得 L15=min{2+1,1+3,3+1}=3, 故v5标号为(2,3). 对与已标号点{v1,v2,v3,v4,v5}相邻顶点v6、v7，由式（12.15）得 L16=min{1+3,3+4,3+1}=4, 故v6标号为(4,4). 对于顶点v7，有L17=min{3+1,4+2}=4,故v7标号为（3，4）。 至此，所有顶点均已标号，得v1到v7的最短距离为4，运用反向追踪法，得最短路径为：v1→v3→v7 当网络图中存在负权弧时，对于顶点vi与 vj不存在弧时，令wij=∝,有如下的递推算法：开始时，令 (1)L1j=w1j (j=1,2,...n) ，标号顶点j为(1,L +wij=L1i (1)1j ). 对t=2,3,..., 令 L (t) 1j =min i {L (t−1) 1i }(t−1) 0 +wi0j (j=1,2,...,n) （12.16） (t) 标号顶点j为(i0,L1j) 若进行到第k步时，对所有j=1,2,...n,有： (k)(k−1) L1 j=L1j (k)则L1j为v1到各点的最短距离，对各点标号运用反向追踪法可找出相应的最短路径。 {} 12．4 送货集货问题 12.4.1 模型分析 12-19 送货问题是指在中心仓库中，需要向几个分仓库送货，每个分仓库对货物有一定的需求，运送货物的车辆在中心仓库装满货后发出，把货送到各分仓库卸载，完成任务后返回中心仓库，求满足货运需求的费用最小的车辆行驶路线。这里的送货问题指每个分仓库的任务仅由一辆车完成，如图12-29所示就是一个3个车辆、10个分仓库的送货问题，其中一个小圆圈表示的是分仓库，图中3个闭回路就是3条送货路线。集货问题与此类似，只是车辆在各分仓库的任务由卸货变为装货，装满后返回中心仓库。送货或集货问题又称车辆调度问题，简称VRP问题。 中心仓库 图 12-29 送货问题 假定中心仓库最多可用K辆车对l个分仓库进行送货，每个车辆载重为bk(k=1,2,L,K)，每个分仓库的需求为di(i=1,2,L,l)，且di k=1 i=1 Knk rkk(nk+1) ⋅sign(nk−1)) (12.17) st. ∑d i=1 nk rki ≤bk k=1,2,L,Kk=1,2,L,K (12.18) (12.19) (12.20) (12.21) (12.22) 0≤nk≤l ∑n k=1 K k =l Rk={rki|rki∈{1,2,L,l},i=1,2,L,nk}Rk1∩Rk2=φ∀k1≠k2 ⎧1nk≥1 其中,sign(nk−1)=⎨ ⎩0其他 上式中,（12.17）为整个送货问题的最短路径目标，不等式(12.18)保证每条路径上的各分仓库的货物总需求量不超过这条路径的送货车容量，不等式(12.19)表明每条路径上分仓库的数量不超过总分仓库数，等式(12.20)要求每个分仓库都得到车辆的送货服务，等式 12-20 (12.21)表示每条路径所经历的分仓库组成，等式(12.22)则限制每个分仓库的货物需求仅能由一个车辆来完成。 上述模型只考虑了最短路径的目标以及车辆容量约束，没有考虑车辆的运行时间。若对车辆达到分仓库的时刻进行限制，则上述问题变成有时间窗的VSP问题。 在有时间窗的VSP问题中，trki为车辆k达到分仓库rki的时刻，trkirkj为车辆由分仓库rki行驶到分仓库rkj的时间，分仓库rki要求到货的时间范围在[etrki,ltrki]之间，即车辆最早到达分仓库rki的时刻为etrki，最迟不超过时刻ltrki。 因此，在上述一般VSP模型中加入式(12.22)作为约束条件，即成为有时间窗的VSP模型。 etrki≤trki≤ltrki (12.23) 无论是无时间窗要求还是有时间窗要求，VSP问题都是NP完全问题，不可能用多项式算法获得最优解，因此可构造启发式算法求解满意解，下面就介绍其中的几种。 12.4.2 扫描法求解 扫描法是 Gillett和Miller提出的，其基本步骤如下： 1． 在地图或方格图中确定所有分仓库的位置。 2． 自中心仓库始沿任一方向向外划一条直线。 3． 沿顺时针或逆时针方向旋转该直线直到与某分仓库相交，相交时考虑在线路上增 加该分仓库运货任务时，是否会超过车辆的载货容量（先使用容量最大的车辆），如果不会，线路增加该分仓库，并继续旋转直线到下一分仓库。否则执行步骤4。 4． 构成一条送货线路。 5． 从不包含在上一条线路中的分仓库开始，继续旋转直线，继续步骤3，直到所有的 分仓库的送货任务都已安排在不同线路中。 6． 应用TSP问题的求解算法，排定各线路中分仓库的先后顺序，使各线路的路径最 短。 例 12-7 已知某运输公司的送货点如图12-29（a）所示，图中圆圈旁边的数字表示该分仓库所需送货量，运输公司的送货车辆载货容量为1000件。问：如何安排送货线路比较合理？ 解：扫描法进行上述问题的求解。首先，向北画一条直线，进行逆时针方向“扫描”。逆时针旋转该直线，直到装载的货物能装上一辆载重1000件货物的车辆，同时由不超重。一旦所有的分仓库都已分配了线路，用TSP的算法安排各分仓库在各线路中的先后位置，形成最后的送货线路如图12-29（a）所示。 200 200 （a）送货数据 （b）扫描法解 图 12-29 应用扫描法进行送货线路安排 12.4．3 节约法求解 200 100 200 200 100 300 400 300 300 200 线路1 1000件100 300 200 400 300 线路3 200 800件 300 中心仓库 200 中心仓库 100 200 200 线路3 200 900件 200 200 12-21 节约法最早是由Clarke-Wright所提出来的，能够对站点不多的VRP问题进行快速求解，其结果与最优解比较接近，而且节约法的一个重要特点是其能够包含实际应用中许多重要的约束条件，如时间窗口条件、最长驾驶时间条件、司机休息时间条件等，因此一直以来是求解VRP问题的一个有效的方法。 假设中心仓库0用两辆车分别向分仓库i和j送货，随后返回，如图12-30（a）所示，这时的路线里程为: D1=c0i+ci0+c0j+cj0 (12.24) 但如果使用一辆车辆由0-i-j-0进行一次巡回送货, 如图12-30（b）所示，,其总行驶线路里程将变为: D2=c0i+cij+cj0 (12.25) 显然，后一种送货方案比前一种可减少行驶里程为: ΔDij=ci0+c0j−cij （12.26） 这一减少的行驶里程ΔDij就称为节约里程。 i i 中心仓库0 中心仓库0j j （a）分别进行送货的线路 （b）合并后的送货线路 图 12-30 通过合并线路节约行驶里程 在对多个分仓库进行送货时，将其中能取得最大“节约里程”的两个分仓库合并在一条线路上，进行巡回送货，能够获得最大的里程节约。同时，在不超过运输车辆载货容量的条件下，设法使这条选定的巡回路线，尽可能将其他分仓库按其所能取得“节约里程”的大小纳入这条线路中，则能获得更大的里程节约效果。这就是节约法的基本原理。 一般VSP问题的节约法求解步骤如下： 1. 计算收货点i,j的节约里程ΔDij,令M={ΔDij|ΔDij>0}; 2. 在M内按ΔDij从大到小的顺序进行排列； 3. 若M=Φ，则终止，否则对第一项ΔDij,考察对应的(i,j),若满足下述条件之一： （1） 点i和点j均不在已构成的线路上； （2） 点i或点j在已构成的线路上，但不是线路的内点（即不与中心仓库相连）； （3） 点i或点j位于已构成的不同线路上，均不是内点，且一个是起点，一个是终 点。 则转下步，否则转步骤6。 4. 计算点i和点j连接后的线路上总货运量Q，若Q≤bk（bk为车辆k的容量，可按容量从 大到小的原则采纳车辆），则转下一步，否则转步骤6。 5. 连接点i和点j。 6. 令M：=M−ΔDij,转步骤3。 例12-8 有6个分仓库的货运任务（编号为1,2,3,4,5,6），各任务的货运量di（单位为吨）如表12-15，这些任务由中心仓库0发出的容量为4吨和2.5吨的车辆来完成，中心仓库 12-22 及各分仓库点对间距离（单位为公里）由表12-16给出。试选择、构造合理车辆线路，完成上述送货任务。 表 12-15 货运需求量 分仓库 Di(吨) 1 0.8 2 0.7 3 1.0 4 1.75 5 1.10 6 1.15 表 12-16 点对间距 i j 0 1 2 3 4 5 6 0 9 12 12 20 24 21 9 0 9 19 29 33 30 12 9 0 10 32 29 33 12 19 10 0 25 19 25 20 29 32 25 0 6 1 24 33 29 19 6 0 6 21 30 33 25 1 6 0 0 1 2 3 4 5 6 解：首先计算各点对间节约里程ΔDij=ci0+c0j−cij，例如点1和点2，有 ΔD12=c10+c02−c12=9+12−9=12，类似地，可得到其他点对的节约里程，按从大 到小的顺序示于表12-17中。 表 12-17 节约里程表 ΔDij ΔDij 序号 (i,j) 序号 (i,j) 1 2 3 4 5 （4,6） 40 （5,6） 39 （4,5） 38 （3,5） 17 （2,3） 14 6 7 8 9 10 （1,2）（3,6）（2,5）（3,4）（1,3） 12 8 7 7 2 序号 11 12 13 14 15 (i,j) ΔDij （1,4） 0 （1,5） 0 （1,6） 0 （2,4） 0 （2,6） 0 然后， 根据表12-17所示的节约里程顺序，逐项考察对应的(i,j),进行点对间的连接，过程如表12-18所示： 表 12-18 点对间连接过程 i-j 4-6 6→5 5→3 2-3 1→2 3-6 2-5 3→4 两点位置 非线路上点 非线路上点，外点 非线路上点，外点 非线路上点 非线路上点，外点 一点为内点 一点为内点 不同线路上点 一个终点，一个起点 Q= ∑d i 连接否 4→6 4→6→5 × 2→3 1→2→3 × × × Q=d4+d6=2.9<4 Q=d4+d6+d5=4 Q>4 Q=d2+d3=1.7<2.5 Q=d2+d3+d1=2.5 Q>4 表中第一列表示根据表12-17的顺序考察的i-j,若两点均不在线路上，则考察i→j和j→i；若一点不在线路上，一点为外点，则考察i→j（i不在线路上、j是线路的起点，或i 12-23 是线路的终点、j不在线路上）或者j→i（j不在线路上、i是线路的起点，或j是线路的终点、i不在线路上）；若两点都是不同线路上的外点，则根据点的位置关系，构造终点（一条线路）→起点（另一条线路）的顺序。第二列表示考察的两点的位置，若不满足位置条件，显然不能连接，不再考察其它各项，在第四列划×，转其他点对。第三列表示连接后线路的总货运量，若大于车辆容量，则在第四列中划×。 当一个点i不在线路上时，认为点i与中心仓库单独构成线路0→i→0。 由表12-18，得到最终送货线路分别为： 4吨货车： 0→4→6→5→0，其送货里程=20+1+6+24=51公里 2.5吨货车： 0→1→2→3→0，其送货里程=9+9+10+12=40公里 这样，完成上述送货任务需安排4吨和2.5吨货车各一辆，总送货里程为91公里。 12.4.4 遗传算法求解 遗传算法（Genetic Algorithm,GA）是由J.H.Holland等于70年代发展起来的。它是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。由于它采用随机运算，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，因此近年来有很快的发展，并在组合优化、自适应控制、机器学习等许多领域获得应用，有着广泛的应用前景。应用遗传算法可方便地对式（12-16）到式（12-21）所表示的VSP模型进行求解。 从上述模型可知，求解的关键是合理确定车辆与各分仓库的关系,在满足车辆载重量和分仓库需求约束条件的情况下使得总里程最小,因此可以构造遗传算法如下: 1. 构造染色体,产生初始种群 用矢量(S1 ,S2 ,...,Sl )表示染色体G，其中元素(基因)Sj 为[1,Kl]之间的一个互不 s−1s−1 重复的自然数，它表示了第j个确定第m=(sj−jl⋅l)个分库与路径k=jl+1的关系(⎣⎦表示取整数, 下同。)，即确定分库m是否由车辆k配送及确定分库m在路径k中的顺序的次序为j。随机产生一组染色体Gh (h=1,2,...,n)（其中n为一代种群中的个体数），Gh 各不相同，此为第一代种群。 2. 可行化过程 将染色体的编码向量映射为满足全部约束条件的可行解称为可行化，其过程如下: a. 令分库需求条件满足的标志变量dzm=0 （m=1,2,…,l）。 ' b. 令路径k中的分库数目nk=0 (k=1,2,...,K)，令bk=bk,Rk=φ (k=1,2,...,K)，路径k中除去中心仓库后第i个位置的分库号为rki=0 (i=1,2,…,l),即此时所有路径皆未形成。 c. j=1。 s−1s−1 d. 第j次确定分库m与路径k间的关系，其中,m=(sj−jl⋅l), k=jl+1。 e. 判断dzm是否等于0，若等于0，表明分库m的需求尚未满足，转e继续判断路径m的情况；否则转g。 f. 判断bzk是否为0？ '' ① 若为0: 判断dm≤bk成立否? 若成立,令dzm=1,bk=bk'−dm，nk=nk+1,rknk=m,Rk=Rk∪{m}；若不成立，转g。 ② 若不为0：转g。 g. j=j+1,转d重复上述过程，直到j=Kl+1。此时检查是否所有dzm=1,(m=1,2,L,l)成立，若成立，说明在满足各约束条件的情况下，所有的分库均分配了一个路径，构成路径集合RT={R1,R2,…,Rk},即为染色体所相应的原车辆路径问题的一个可行解；若不成立，说明此染色体表示的路径分配方案不满足约束，为原VRP问题的一个不可行解。 以例12-9的数据为例说明上述过程，假设一染色体编码为： [][][][]12-24 1 2 4 7 8 16 15 9 10 13 12 5 6 14 3 11 s−1s1−11 ⋅l=1−0=1关s1=1，首先确定路径k=1l+1=1−8+1=1与分库m=s1−l 系，此时dz1=0，d1=1 dz1=1；s2=2，第2次确定路径k=2l+1=1与分库m=s2−2l⋅l=2的关系，此时dz2=0，d2=1 [][][][][][]2 r12 []分库 路1 径 2 1 r11╳ 3 r15╳ 1 4 r13╳ 2 5 ╳ r221 6 ╳ r234 7 r14╳ 2 8 ╳ r212 ╳ 2 需求量 1 表中╳格表示对应的路径无需安排分库，染色体所代表的路径安排为： 0→1→2→4→7→3→0与0→8→5→6→0 3. 性能估计 对一代种群中的每一个染色体G(h=1,2,...,l)应用步骤2,求得对应可行解 Knh k RTh(h=1,2,…,n),代入目标函数Zh=∑(∑crk(i−1)rki+crknrk(n+1)⋅sign(nk−1));若染色体对应 kk k=1i=1 的为非可行解，则赋予其目标函数一个很大的整数zh=M。令Gh的适应性函数fh =1/Zh ,fh 是个体Gh 在生存竞争中生存能力的表现,fh 越大表明其性能越好,即其对应的解越接近最优解。 4. 判断停止进化条件 * 判断迭代的代数是否为要求代数N,若是,停止进化,选性能最好的染色体Gh所对应的路径集合RTh*作为原VRP问题的优化解输出。反之,继续执行步骤5。 5. 自然选择 将每代种群共L个染色体按适应值fh 由大到小排列(h=1,2,...,n)，排在最前一位的个体性能最优，将它其复制一个，直接进入下一代种群。下一代种群的另L-1个染色体则从前代种群的n个染色体中按概率ph =q'(1-q)h-1 (h=1,2,...,n)用轮转法选择个体Gh ，产生后代形成。这样既可保证最优者生存至下一代，又可避免个体间因适应值大小不同而使被选择进入下一代的机会相差悬殊，保持了下代种群个体的多样性，从而可有效提高整个算法的收敛速度。其中q'=q/(1-(1-q)n )，q=0.08。种群代数增１。 6. 染色体交叉重组 对步骤5 所产生的新种群，按选择概率pc 选择个体对进行交叉重组，共进行n/2次。文献表明交换率pc =0.6～0.8之间时，进化性能较好，本文取pc =0.7，交叉规则采用PMX法，下面举例说明。设父代的两个染色体为 A=9 8 4 5 6 7 1 3 2 10，B=8 7 1 2 3 10 9 5 4 6,按照PMX法，交叉重组过程如下: k1 k2 k1 k2 A =9 8 4 5 6 7 1 3 2 10 A’ =9 8 4 2 3 10 1 6 5 7 B =8 7 1 2 3 10 9 5 4 6 B’ =8 10 1 5 6 7 9 2 4 3 其中交叉交换点1≤k1 ＜k2 ≤l是随机选取的。对交叉成功所获得的子代应用步骤2, 3求得其对应的适应值，并与其父代进行比较，选择四者中性能最好的２个进入种群。 7. 染色体变异 12-25 在每代种群中，以变异率pm =0.02对进行变异，变异策略是随机交换选中染色体内两个基因的值。对变异成功所获染色体应用步骤2,3求得其适应值，并与其父染色体比较，择性能优者进入种群。 8. 返回步骤4，循环。 例 12-9 有八个分仓库和一个中心仓库的配送系统，各分仓库的对中心仓库的需求为di（i=1，2,…,8）(单位为吨)，中心仓库只有两辆车用于配送，每辆车的容量皆为8吨，已知中心仓库与各分仓库间的距离如下表(其中0表示中心仓库)，要求合理安排车辆的行驶路线，使总运输里程最短。 表 12-20 分库间距离及各分库需求量表 cij0 1 2 3 4 5 6 7 8 0 0 4 6 7.5 9 20 10 16 8 1 4 0 6.5 4 10 5 7.5 11 10 1 2 6 6.5 0 7.5 10 10 7.5 7.5 7.5 2 3 7.5 4 7.5 0 10 5 9 9 15 1 4 9 10 10 10 0 10 7.5 7.5 10 2 5 20 5 10 5 10 0 7 9 7.5 1 6 10 7.5 7.5 9 7.5 7 0 7 10 4 7 16 11 7.5 9 7.5 9 7 0 10 2 8 8 10 7.5 15 10 7.5 10 10 0 2 需求量 解：运用遗传算法对上述问题进行求解，用2×8个互不重复的１到16的自然数构成一个染色体码链，表示一种车辆路径安排方案，随机产生10个这样的染色体构成初始种群,预定进化代数为50，以0.7和0.02分别作为染色体的交叉率和变异率对染色体进行交叉和变异操作，经过上机运算,得最终的线路为： 0→4→7→6→0 0→1→3→5→8→2→0 运输总距离为：67.5 显然，此方案既满足车辆容辆约束又满足了各分仓库的需求，是一个上述车辆路径问题的一个可行解。而用节约法对同一问题进行求解，得线路安排为： 0→6→5→7→3→0 0→4→8→2→1→0 相应的运输距离为：79.5 从上可见，遗传算法不失为VRP问题一个较优的满意解。而对上述算例的遗传算法过程进行跟踪,发现每代最优个体的适应度变化如图5-31所示,说明所构造的遗传算法在较小的种群规模下可以较快的速度进化，向最优解逼近。同时遗传算法也适用于规模较大的VRP问题，对于具有如时间窗口、行驶里程限制等约束条件的VRP问题，通过实验证明，遗传算法的求解性能也非常好，可以较快地找到问题的优化解或近似优化解。 适应度0.0150.01480.01460.01440.01420.0140.01380.01360.01340.01320.013 12-26 15101520253035404550代数 图12-31 GA寻优过程图 本章小结 本章对产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题常见运输问题进行了分析，建立了这些问题的数学模型，并就求解这些问题的基本方法如表上作业法、匈牙利法、标号法、Dikstra法等进行了介绍，同时也就一些启发式算法、人工智能方法进行了分析和构造，如扫描法、节约法、遗传算法、神经网络算法等等，这些对于掌握运输优化方法，提高运输管理水平具有重要的意义。 思考题 1.下图为W仓库，A,B,C,D为4个需要配送的站点，图上每边上的数字为点对间的距离，请安排从W出发，巡回配送每个站点的最短路线。 31 D C 23 34 26 34 A W 47 48 34 B 2.已知一个运输公司有两辆货车，一辆载重量为12吨，另一辆为10吨。该公司在A,B,C,D,E,F6个城市装载货物，然后运回到货场o。货场和6城市间的距离以及A,B,C,D,E,F6个城市需要装载的货物量均列在下表中，问如何安排车辆及运输线路比较合理？ 点对间距及载货需求表 间距 0 A B C D E F 3.设有某企业在a,b,c,d4个不同地区设有生产工厂生产同一种产品，每月产量分别为40，30，45和20（单位为吨），按计划调运到设在e,f,g的3个分配中心，分别为50，55和30（单位为吨）。已知各产地到各销地的单位产品运费（单位为元）如下表，请作出调运计划，使调运费用最少。 单位运费表 销地 产地 e f g O 0 2 3 4 2 3 5 A 3 0 9 3 6 5 7 6 B 4 3 0 4 5 3 2 5 C 2 1 5 0 3 4 6 8 D 6 4 2 6 0 2 3 5 E 3 5 6 3 4 0 1 6 F 5 3 8 4 2 4 0 7 载货需求 12-27 a b c d 17 11 15 12 16 14 11 11 14 13 14 10 4.请构造出带时间窗的VSP节约法算法，并进行说明。 12-28 因篇幅问题不能全部显示，请点此查看更多更全内容