按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
（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问题进行快速求
解，其结果与最优解比较接近，而且节约法的一个重要特点是其能够包含实际应用中许多
重要的约束条件，如时间窗口条件、最长驾驶时间条件、司机休息时间条件等，因此一直
以来是求解VRP问题的一个有效的方法。
假设中心仓库0用两辆车分别向分仓库i和j送货，随后返回，如图12…30（a）所示，这
时的路线里程为：
D
=c
＋
c
＋
c
＋
c
（12。24）
10ii00 jj0
但如果使用一辆车辆由0…i…j…0进行一次巡回送货； 如图12…30（b）所示，；其总行驶
线路里程将变为：
D
=c
＋
c
＋
c
（12。25）
20 iij
j
0
显然，后一种送货方案比前一种可减少行驶里程为：
ΔDij
=
ci0＋
c0 j
。
cij
（12。26）
这一减少的行驶里程ΔDij
就称为节约里程。
中心仓库0
i
中心仓库0
j
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），各任务的货运量d i（单位为
吨）如表12…15，这些任务由中心仓库0发出的容量为4吨和2。5吨的车辆来完成，中心仓库
12…22
及各分仓库点对间距离（单位为公里）由表12…16给出。试选择、构造合理车辆线路，完成
上述送货任务。
表 12…15 货运需求量
分仓库 1 2 3 4 5 6
Di（吨） 0。8 0。7 1。0 1。75 1。10 1。15
表 12…16 点对间距
i
j
0 1 2 3 4 5 6
0 0 9 12