现代物流学-第51部分
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
调整，即
。xij
（k
） ＋ε当（vi；vj）是增广链上的正向弧
xij
（k
＋1） =
。。
xij
（k
） 。ε
当（vi；vj）为增广链上的反向弧
。x（k
） 当（vi；vj）不在增广链上
。
ij
ε=
min｛ε1；ε2 ｝
其中 ε1 =
min｛ij
。
xij
（k ）｜ 当（vi；vj）为正向弧 ｝
（k
）
ε2 =
min｛（c） xij
｜ 当（vi；vj）为反向弧 ｝
得到新的可行流x （k＋1） ；此可行流为同一流量中费用最小的可行流，若不存在最短路，
转第五步。
第四步 令k=k＋1，重复第二步至第三步。
第五步 退出计算，所得x （k）即为最小费用最大流。
例12…5 求图12…12所示网络的从v 1到v8的最小费用最大流，图中（vi；vj）上所标的三个数
字依次表示 bij、cij、xij。
解：首先对x（0）=0的初始可行流，根据式（12。13）、（12。14）构造赋权有向图w（x （0））
如图12…13，并找出v 1到v8的最短路径为：v1→v2→v5→v6→v8
12…16
V2 （2；4；0） V5 V2 2 V5
V1
V4 V7
V3 V6
（2；4；0）
（7；3；0）
（4；4；0）
（2；4；0）
（3；2；0）
（3；2；0）
（3；2；0）
（3；3；0）
（6；4；0）
（6；3；0） （8；3；0） （3；2；0）
V1
V8
V3 V6
2
7
4
2
3
3
3
8
3
6
6 3
V8
V4V4 V7 V7
（2；2；0） 2
图12…12图12…13
沿此增广链对x（0）进行调整，显然可增加的流量为2，得可行流x （1），如图12…14所示，对
x（1）根据式（12。13）、（12。14）构造赋权有向图w（x （1））如图12…15，找出v 1到v8的最短路径
为：v1→v3→v7→v8
V2 （2；4；2） V5 V2 2 V5
V1 V1
V8
V3 V6
（2；4；2）
（7；3；0）
（4；4；0）
（2；4；0）
（3；2；0）
（3；2；0）
（3；2；0）
（3；3；2）
（6；4；0）
（6；3；0） （8；3；0） （3；2；2）
V8
V3 V67
2 6 8
4
2
3
3
3
…2
…3
6
…2 …3
3
V4 （2；2；0） V7 V4 2 V7
图12…14 图12…15
沿此增广链对x （1）进行调整，可增加的流量为2，得可行流x （2），如图12…15所示，对x （2）
构造赋权有向图w（x（2））如图12…17，找出v 1到v8的最短路径为：v1→v2→v6→v8
V2 （2；4；2） V5 V2 2 V5
V1
V3 V6
（2；4；2）
（7；3；0）
（4；4；0）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；2）
（6；4；2）
（6；3；0） （8；3；0） （3；2；2）
V1
V8
3
V3 V6
2
72
4 3 6
…2
6
…3
3
…3
…2
…3
8…2
…6
V8
V4 （2；2；0） V7 2
V4 V7
图12…16图12…17
沿此增广链对x （2）进行调整，可增加的流量为1，得可行流x （3），如图12…18所示，对x （3）
构造赋权有向图w（x（3））如图12…19，找出v 1到v8的最短路径为：v1→v4→v7→v8
V2 （2；4；2） V5 V2 2 V5
V1
V8
V3 V6
（2；4；3）
（7；3；0）
（4；4；0）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；2）
（6；3；1） （8；3；0） （3；2；2）
V3 V6
2
4
…2
72
6
3
…3
3
8
…3
6
…2
…2
…3
…6
V1
…6
V8
V4 （2；2；0） V7 V4 2 V7
图12…18 图12…19
12…17
沿此增广链对x（3）进行调整，可增加流量2，得可行流x （4），如图12…20所示，对x （4）构造
赋权有向图w（x（4））如图12…21，找出v 1到v8的最短路径为：v1→v2→v5→v8
V2 （2；4；2） V5 V2 2 V5
V1
V3 V6
（2；4；3）
（7；3；0）
（4；4；2）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；1） （8；3；0） （3；2；2）
V8
V8
V1 V3 V6
2
4
72
…2
6
3
…3
3
8
…3
…6
…2
…2
…3
…6
…4
V4 （2；2；2） V7 V4 …2 V7
图12…20图12…21
沿此增广链对x（4）进行调整，可增加流量1，得可行流x （5），如图12…22所示，对x （5）构造
赋权有向图w（x（5））如图12…23，找出v 1到v8的最短路径为：v1→v3→v6→v2→v5→v8
V2 （2；4；3） V5 V2 2 V5
V1
V8
V3 V6
（2；4；4）
（7；3；0）
（4；4；2）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；1） （8；3；1） （3；2；2）
V3 V6
…2
4
…2
72
6
3
…3
3
8
…3
…6
…2
…3
…6
…4
V1
…8
V4 （2；2；2） V7 V4 …2 V7
图12 …22 图12 …23（5）（6）（6）
沿此增广链对x 进行调整，可增加流量1，得可行流x ，如图12…24所示，对x 构造
赋权有向图w（x（6））如图12…25，找出v 1到v8的最短路径为：v1→v3→v6→v5→v8
V5
V2 （2；4；4） V5
V3 V6
（2；4；4）
（7；3；1）
（4；4；2）
（2；4；3）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；0） （8；3；2） （3；2；2）
V2
V1
V1
V8
V8
V3 V6
…2
4
72
…2
6
3
…3
3
…3
…2
…3
…4
…7
8
…6
…8
（2；2；2）
V4 …2 V7
图12…24图12…25
沿此增广链对x（6）进行调整，可增加流量1，得可行流x （7），如图12…26所示，对x （7）构造
赋权有向图w（x（7））如图12…27，可以看到已无从v 1到v8的最短路径。可知x（7）即为最小费用最
大流，其网络图如图12…26。
V2 （2；4；4） V5 V2
V1
V3 V6
（2；4；4）
（7；3；2）
（4；4；2）
（2；4；4）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；0） （8；3；2） （3；2；1）
V8
V8
V5
V3 V6
…2
7 …2
4
6
3
…3
…6
3
…8
3
…2
…3
…4
…7
V1
…3
（2；2；2） V4 …2 V7
图12…26图12…27
12。3。4最短路径问题
12…18
对于包含n个顶点v 1；v2；。。。；vn的有向网络流；假设无负权；已知弧（vi；vj）的权为wij；求v1
到vn的最短路径；以Lij表示从vi到vj的最短距离；则对此问题有Dikstra算法如下：
第一步 给发点v 1以标号（1；0）；L11=0。
第二步 从已标号顶点出发，找出与这些顶点v i相信相邻所有顶点，若
L1 j
=min（L1i
＋
wij
） （12。15）
i； j
则对vj标号为（i；L1j）
第三步 重复第二步，直到所有的顶点都标号为止，每个顶点标号内的第二个数字即为
v1到该顶点的最短距离，运用反向追踪可找出此最短路径。
例12…6 在图12…28中，求v 1到v7的最短路线。 1
V2
V5
2
21 V4
V6
V1
43
2
3
V7
V3 1
图12…28
解：首先给出发点v 1以标号（1；0）；L11=0，从v 1出发，与v1相邻的顶点为v2、v3 、v4，由
式（12。15）得
L14=min｛0＋1；0＋2；0＋3｝=1 ； 故v 4标号为（1；1）。
从v 1 、v4出发，有相邻顶点v2、v3、v6，由式（12。15）得
L12=min｛0＋2；0＋3；1＋3｝=2；故v 2标号为（1；2）。
对与已标号点｛v 1 ；v2 ；v4｝相邻顶点v5、v6、v3，由式（12。15）得
L13=min｛0＋3；2＋1；1＋3｝=3； 故v 3标号为（1；3）。
对与已标号点｛v 1；v2；v3；v4｝相邻顶点v 5、v6、v7，由式（12。15）得
L15=min｛2＋1；1＋3；3＋1｝=3； 故v 5标号为（2；3）。
对与已标号点｛v 1；v2；v3；v4；v5｝相邻顶点v6、v7，由式（12。15）得
L16=min｛1＋3；3＋4；3＋1｝=4； 故v 6标号为（4；4）。
对于顶点v 7，有L17=min｛3＋1；4＋2｝=4；故v 7标号为（3，4）。
至此，所有顶点均已标号，得v 1到v7的最短距离为4，运用反向追踪法，得最短路径
为：v1→v3→v7
当网络图中存在负权弧时，对于顶点v i与 vj不存在弧时，令wij=∝；有如下的递推算
法：开始时，令L
wj1（1）
1=j
（
j
=1；2；。。。n）
，标号顶点j为 1； L（j（1）
1）。
对t=2；3；。。。；令
。1）
L
｛
｝（1）（（）
1。
ijtiijtiitjwLwL0011min＋=＋= （j=1；2；。。。；n）
（12。16）
标号顶点j为 （i0； L1（
tj））
若进行到第k步时，对所有j=1；2；。。。n；有：
（k
）（k。1）
=
L1 jL1 j
（）
则 L1k
为v1到各点的最短距离，对各点标号运用反向追踪法可找出相应的最短路径。
｛j｝
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
《
bk
（k
=
1；2；L； K） ，分仓库i到分仓库 j的运距为 cij。设nk为第k辆车所包含的分仓库数
（若nk=0 表示未启用第 k辆车），用集合Rk表示此第 k条路径（第k辆车的行车路线），其
中的元素rki表示分仓库rki在路径k中的顺序为 i（不包含中心仓库）。 rki为0到l中的一个整
数，令rk
0 =
rk
（nk
＋1） =
0 表示中心仓库，则有如下表示的送货模型：
K
nk
min imize
（ c
＋
c
。
sign（n
。1））
Σ∑
rrrr
k
k
（i。1） ki
knkk
（ nk
＋1）
（12。17）
k
=1 i=1
st。
bdknrk≤k
=
1；2；L； K
（12。18）
∑
ki
i=1
0 ≤
nk
≤
lk
=
1；2；L； K
（12。19）
Σ（K） nk
=
l
（12。20）
k
=1
R
=
｛r
｜ r
∈｛1；2；L；l｝；i
=
1；2；L； n
｝ （12。21）
k
kiki
k
R
∩
R
=φ
。k
≠
k
kk
12
12 （12。22）
其中； sign（n。1） =
。1 nk
≥
1
k
。。
0 其他
上式中；（12。17）为整个送货问题的最短路径目标，不等式 （12。18）保证每条路径上的各
分仓库的货物总需求量不超过这条路径的送货车容量，不等式（12。19）表明每条路径上分仓
库的数量不超过总分仓库数，等式 （12。20）要求每个分仓库都得到车辆的送货服务，等式
12…20
（12。21）表示每条路径所经历的分仓库组成，等式 （12。22）则限制每个分仓库的货物需求仅能
由一个车辆来完成。
上述模型只考虑了最短路径的目标以及车辆容量约束，没有考虑车辆的运行时间。若
对车辆达到分仓库的时刻进行限制，则上述问题变成有时间窗的VSP问题。
在有时间窗的VSP问题中，trki
为车辆k达到分仓库rki
的时刻，trkirkj
为车辆由分仓库rki
行驶到分仓库rkj
的时间，分仓库rki
要求到货的时间范围在＇etr
；ltr
＇之间，即车辆最早到
ki
ki
达分仓库rki
的时刻为etrki
，最迟不超过时刻lt
。 因此，在上述一般VSP模型中加入式
rki
（12。22）作为约束条件，即成为有时间窗的VSP模型。
et
≤t
≤
lt
（12。23）
rr
r
kiki
ki
无论是无时间窗要求还是有时间窗要求，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
300
300
400
100
300
200
200
100
200 200
200
200
中心仓库
200
300
300
400
100
300
200
200
100
200 200
200
200
线路3
800件
线路1
1000件
线路3
900件
（a）送货数据 （b）扫描法解
图 12…29 应用扫描法进行送货线路安排
12。4．3节约法求解
12…21
节约法最早是由Clarke…Wright所提出来的，能够对站点不多的VRP问题进行快速求
解，其结果与最优解比较接近，而且节约法的一个重要特点是其能够包含实际应用中许多
重要的约束条件，如时间窗口�
