现代物流学-第55章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
素个数相同。本例中为：
。
。
。
。。
。。。
。
。0 Ф 7
2 1 0
8 7 Ф
（2）在直线不穿过的所有元素中找出最小元素。
（3）在没有水平线的各行减去此最小元素；有垂直线的各列加上此最小元素；得新的效率
矩阵。
本例中，所求最小元素为1，计算过程为：
。。。
。
。
。。。
。
。0 Ф 7
2 1 0
8 7 0
。
008
。
…1 →
…1
。
。
。。
100
760
。
。
。。
＋1
第四步 回第二步；直到求出最优分配方案。
本例中，对修改后的效率矩阵重复第二步得：
Ф 8
1 0 Ф
7 6 0
。
0
。
。
。
。。
。
。
。。
已经得3个0元素，故得最优分配方案为：
Σ
A1→B1，A2→B2，A3→B3
根据原效率矩阵，3叉车总搬运作业费为：
25＋20＋17=62元
12。2。3 巡回运输问题（旅行商问题）
在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1；2； …；n），货
车载重量为Q，若满足bi
≤
Q
，则该网点只需一辆货车巡回送货即可。显然，在这种情
况下使费用最省的方案就是合理安排货车访问各用户的顺序，使货车的巡回线路的总距离
最短，这也就是旅行商问题。
12…8
例12…3已知5用户间距离如表12…13，其中d（i；j）=∝表示从第i个用户到第j个用户是
没有意义的； 用户1为物流网点所在位置，如果只考虑将每个用户都当作一个出发用户；每
个用户都当作一个到达用户；则对每个出发用户都要选择一个到达用户；而每个到达用户只
能有一个出发用户到达该地；将问题变成了一个分配问题；可用匈牙利法求解。
表12…13 用户间距表
到达
出发
1 2 3 4 5
1 ∝ 1 7 4 3
2 2 ∝ 6 3 43 1 6 ∝ 2 1
4 1 5 4 ∝ 6
5 7 5 4 5 ∝
以例12…13说明求解步骤
第一步 令d（i；i）=∝；不存在通路的也记为∝；得距离阵；通常d（i；j）与d（j；i）不一定
相同；即矩阵不一定对称。
第二步 对距离矩阵用匈牙利法求解；若得到无环路的路线；则就是最优路线；若路线有
环路；就不是最优路线；但所走总距离给出了旅行商问题总距离的下界。
在本例中，匈牙利法求解过程为：
∞
1743
∞
0632
∞
622
。
。
。
。
。
。
…1
0
。
。
。
。
。
。。
。。。。。
。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
→
。
。
。
。
。
。。
φ
2
∞
634
0
∞
412
∞
4
2
…2
0
…1
φ
φ
16
∞
21
05
∞
10
5
∞
→
0
…1
154
∞
6
043
∞
5
43
∞
φ
5
0
…4
7545
∞
3101
∞
31
∞
0
。
。1
得不考虑环路下的最优方案：
1→2，2→4，4→1，3→5，5→3
所走总距离为：
1＋3＋1＋1＋4=10
可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。
第三步 出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的
各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。
本例中，出现两个环路，1→2→4→1和3→5→3，打开节点数少的环路，分别令
d（3；5）=∝和d（5；3）=∝求解。
（1）当d（3；5）=∝时；用匈牙利法求解
0
φ
∞
1743
∞
0632
∞
62
。
。
。
。
。
。
…1
…2
…1
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
。
。
。
。
。
。。
→
。
。
。
。
。
。。
φ
φ
2
∞
634
0
∞
412
∞
4
0
φ
16
∞
2
∞
05
∞
1
∞
5
∞
∞
→
0
…1
…4
154
∞
6
043
∞
5
43
∞
φ
5
∞
0
7545
∞
3101
∞
31
0
。1 。
2
可得无环路的最优方案： 5→3→4→1→2→5
12…9
所走总距离为： 1＋4＋2＋1＋4=12
（2）当d（5；3）=∝时；用匈牙利法求解
。
∞17 4 3
2∞6 3 4
1 6∞2 1
1 5 4∞6
7 5∞5∞
。
…1
。
∞0 6 3 2
0∞4 1 2
0 5∞1 0
0 4 3∞5
2 0∞0∞
。
。
0
332
。
∞
。。。。。
。。。。。
。。。。。
。。。。。
112
∞
0
…2
…1 →
…1
41
∞
0
→
4
0
5
∞
…5
。。。。。0。
。
3
得路线： 1→2；2→1；3→5；4→3；5→4
总距离： 1＋2＋1＋4＋5=13
可以看到：
20
∞
∞
上述方案出现环路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函数），跨导T ij模拟神经元之间互连的
突触特性，电容c i 及电阻R i用来模拟生物神经元的输出时间常数。设有n个神经元互连，则
可用下述非线性微分方程描述：
（a）Hopfield神经元
。。。。。
。。。。。
φ
φ
12…10
（b）Hopfield神经网络
图12…1 连续时间神经网络模型
n
。
dui
（t） ui
（t）
。ci
=ΣTijv
j
（t） 。＋
Ii
。 dt =1 Ri
（12。3）
。v
（t） =
g（u ）（i）
。 ii
对式（12。3）可以定义系统的能量函数为：
11 v
E =。Σ（n） Σ（n） Σ（n） Σ（n） i
（v）dv
（12。4）
2 i
j
iiR11111i
∫
==
。
==
＋。iijiijgvITvv0
可以证明，对于该能量函数，恒有
dE≤
0 ，即当t→∞，网络达到稳态。显然应用网
dt
络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成
（12。4）式的形式，然后应用式（12。3）运算到网络收敛即可。通常在用Hopfield神经网络求
解实际问题时，一般忽略能量式中的积分项，将能量函数简化为下式（12。5），以便目标函
数的映射。
E =。 1 ΣΣn（n） Tijviv
j
。Σ（n） viIi
（12。5）
2 i=1 j=1 i=1
2。神经网络求解旅行商问题
对于n个用户的TSP问题，任何一个用户在最终访问路径上的访问次序可用一个n维向量
表示，因此每一个用户可用n个神经元表示。下面仍以例12…3为例说明，如果用户1第3个被
访问，则表示为00100，即第三个神经元输出为1，其余为0。为了表示n个用户，可简单地
用n╳n换位矩阵表示，如表12…14所示。
表 12…14 换位矩阵
用户
次序 1 2 3 4 5
1 0 0 1 0 0
2 0 1 0 0 0
3 1 0 0 0 0
4 0 0 0 1 0
5 0 0 0 0 1
上述换位矩阵表示巡回线路为：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）所构造的函数的极小值对应。 ΣΣΣΣΣΣΣΣE（。）＋＋vvvvvn=（n） （n） （n） （n） xixjxiyixi2221i1jii111i1≠≠x===x=yxx==（n） nΣΣΣd（）（）＋＋xyvvv；i1＋y；；式（12。5）中第1、2、3项对应于换位矩阵的条件（1）、（2）、（3），第4项对应于条件（4），即使路径最短的目标要求。A、B、C、D为4个正常系数，将式（12。6）写成如IT（12。5）所表示的Hopfield能量函数标准形式，得的表达式和的值如下：xiyixi；。。。由（12。6） 得Hopfiled网络运行方程式如式（12。8）： （n） （n）
用n╳n=25个神经元的输出 vxi
（1 ≤x
≤
n；1 ≤
i
≤
n） 表示换位矩阵中的某一元素（取值
为“0”或“1”），其中x表示用户，i表示访问次序，则可以写出与本问题对应的计算能
量函数为：
n
nn
A
BC
2
（12。6）
D
xi
1 yi。
2 x=1 y≠
xi=1
Txi； yi
=。Aδxy
（1。δij
） 。
Bδij
（1。δ
xy
） 。
C
。
Dd（x； y）（δ
j；i＋1 ＋δ
j；i。1）（1。δ
xy
）
（12。7）
I
xi
=
CN
其中δxy
=
1 if
x
=
y
0
。。
。
nn
nnn
xi
xi
du
=。
u
。
C（ΣΣvxj
。
n） 。
AΣvxj
。
BΣvyi
。
DΣd（x； y）（vy；i＋1 ＋
vy；i。1）
（12。8）
dt
τx=1 j=1 j≠iy≠xy≠x
v
。。
。
。。
=
g（uxi
） x
1；2；L；n； i
=；2；L；n；
=
xi
作用函数 g选用sigmoid函数 g（uxi
） =12
（1＋
th（uxi
/ u0 ）） ；网络初始值可置为
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 V2
V2
V3
V4 V3
V4
VB5
VB6
VB5
VB6
图12…2 回路 图12…3树
12…12
10（5）
3（2）
5（1）
10（5）
3（2）
5（1）
在实际问题中，对于一个图，总要考虑它们代表的各城市间道路的交通流量、流动方
向，因此需在各顶点弧上标明流动方向和流量限制，这种表示流动方向和流量限制的图称
为网络或网络流，如图12…4。
V1 V2
V3
V4
V5
V6
图12…4
在网络流中有些点只有发出，称不发点或源点，如图12…4中的V 1；有些点只有收入，
无发出，称为收点或汇点，如图12…4中的V 6，还有些顶点既有收入又有发出，称为中间
点。
12。3。2 网络最大流问题
1。问题的提出
已知连接产地V1与销地Vn的交通网，每一弧（Vi；Vj）代表从Vi到Vj的运输线，产品经由
Vi输送到Vj，弧旁括号外的数字Cij为弧的容量，括号内的数字Xij为Vi到Vj的货运量，要求合
理安排Xij，使V1到V n的货运量最大。这种问题称为最大流问题，如图12…5所示。
V4
V2 6（3）
11（6）
10（5）
2（3）
V1
V6
17（2）
8（3）
6（3）
图12…5
2。寻求最大流的标号法
对于包含n个顶点V1，V2。。。；Vn的网络流，V 1为发点，Vn为收点，各段弧（V i；Vj）上容量为
Cij，设｛Xij｝是一个可行流，如果存�
