现代物流学- 第47部分

｛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　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