现代物流学-第35部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！


解，其结果与最优解比较接近，而且节约法的一个重要特点是其能够包含实际应用中许多
重要的约束条件，如时间窗口条件、最长驾驶时间条件、司机休息时间条件等，因此一直
以来是求解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　12　20　24　21　
1　9　0　9　19　29　33　30　
2　12　9　0　10　32　29　33　
3　12　19　10　0　25　19　25　
4　20　29　32　25　0　6　1　
5　24　33　29　19　6　0　6　
6　21　30　33　25　1　6　0　

解：首先计算各点对间节约里程ΔDij　
=　
ci0＋　
c0　j　
。　
cij　
，例如点1和点2，有　
ΔD12　=　
c10　＋　
c02　。　
c12　=　
9　＋12　。　
9　=　
12　，类似地，可得到其他点对的节约里程，按从大
到小的顺序示于表12…17中。　

　表　12…17　节约里程表　

序号　（i；j）　ΔDij序号　（i；j）　ΔDij序号　（i；j）　ΔDij　
1　（4；　6）　40　6　（1；　2）　12　11　（1；　4）　0　
2　（5；　6）　39　7　（3；　6）　8　12　（1；　5）　0　
3　（4；　5）　38　8　（2；　5）　7　13　（1；　6）　0　
4　（3；　5）　17　9　（3；　4）　7　14　（2；　4）　0　
5　（2；　3）　14　10　（1；　3）　2　15　（2；　6）　0　

然后，　根据表12…17所示的节约里程顺序，逐项考察对应的（i；j）；进行点对间的连
接，过程如表12…18所示：　

　表　12…18　点对间连接过程　

i…j　两点位置　Q=Σdi连接否　
4…6　非线路上点　Q=d4＋d6=2。94　×　
2…3　非线路上点　Q=d2＋d3=1。74　×　

表中第一列表示根据表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　遗传算法求解　
遗传算法（Geic　Algorithm；GA）是由J。H。Holland等于70年代发展起来的。它是一
种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机
信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交
叉重组、自然选择等算子，进行并行迭代，求得优化解。由于它采用随机运算，对搜索空
间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，因此近年来有很快的发
展，并在组合优化、自适应控制、机器学习等许多领域获得应用，有着广泛的应用前景。
应用遗传算法可方便地对式（12…16）到式（12…21）所表示的VSP模型进行求解。　
从上述模型可知，求解的关键是合理确定车辆与各分仓库的关系；在满足车辆载重量和
分仓库需求约束条件的情况下使得总里程最小；因此可以构造遗传算法如下：　

1。　构造染色体；产生初始种群　
用矢量（S1　；S2　；。。。；Sl　）表示染色体G，其中元素（基因）S　j　为＇1；Kl＇之间的一个互不
重复的自然数，它表示了第j个确定第　m　
=　
（sj　
。＇sj　
。1　＇。　l）　个分库与路径　k=＇sj　。1　＇＋1的关系　
（。。表示取整数；　下同。），即确定分库m是否由车辆（l）　k配送及确定分库　m在路径（l）　k中的顺序的
次序为j。随机产生一组染色体G　h　（h=1；2；。。。；n）（其中n为一代种群中的个体数），G　h　各
不相同，此为第一代种群。　

2。　可行化过程　
将染色体的编码向量映射为满足全部约束条件的可行解称为可行化，其过程如下：　
a。　令分库需求条件满足的标志变量dz　m=0　（m=1；2；　…；l）。　
b。　令路径k中的分库数目n　k=0　（k=1；2；。。。；K），令　bk　
'　=　
bk　
；Rk=φ　（k=1；2；。。。；K），路径
k中除去中心仓库后第i个位置的分库号为r　ki=0　（i=1；2；…；l）；即此时所有路径皆未形成。　
j　


c。　j=1。　
d。　第j次确定分库m与路径k间的关系，其中；m　
=　
（s＇sj。l　
。1　＇。　
l）　；　k=＇lsj＇。1　＋1。　

　e。　判断dz　m是否等于0，若等于0，表明分库m的需求尚未满足，转e继续判断路径m的情
况；否则转g。　
f。　判断bz　k是否为0？　
①若为0：判断d　
≤　
bk　
'　成立否？　若成立；令dzm　
=　
1；　bk　
'　=　
bk　
'　。　
dm　
，
nk　
=nk　
＋1；　rkn　
=　
m；　Rk　
=　
Rk　
｛m｝　；若不成立，转g。∪（m）　
k　


　②　若不为0：转g。　
g。　j=j＋1；转d重复上述过程，直到j=K　l＋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　

s1=1，首先确定路径　k=＇s1　
l　
。1＇＋1　=＇1。1＇＋1　=　1　与分库　m　=　s　。＇1ls＇。1　。l　=　1。　0　=　1　关系，此时dz1=0，d1=1