0→1→2→4→7→3→0与0→8→5→6→0
3。性能估计
对一代种群中的每一个染色体G h （h=1；2；。。。；l）应用步骤2；求得对应可行解
RTh（h=1；2；…；n）；代入目标函数Z =
K
（ （ 。rrrrknkkikicc＋
1） （ ＋1）
。
sign（n
。1）） ；若染色体对应
ΣΣ（n）
h k
knk
k
k=1 i=1
的为非可行解，则赋予其目标函数一个很大的整数 zh=M。令G 的适应性函数f h =1/Zh ；fh
h
是个体G h 在生存竞争中生存能力的表现；f h 越大表明其性能越好；即其对应的解越接近最
优解。
4。 判断停止进化条件
判断迭代的代数是否为要求代数N；若是；停止进化；选性能最好的染色体Gh
* 所对应的路
径集合RTh* 作为原VRP问题的优化解输出。反之；继续执行步骤5。
5。 自然选择
将每代种群共L个染色体按适应值f h 由大到小排列（h=1；2；。。。；n），排在最前一位的个
体性能最优，将它其复制一个，直接进入下一代种群。下一代种群的另L…1个染色体则从前
代种群的n个染色体中按概率p h =q'（1…q）h…1 （h=1；2；。。。；n）用轮转法选择个体G h ，产生
后代形成。这样既可保证最优者生存至下一代，又可避免个体间因适应值大小不同而使被
选择进入下一代的机会相差悬殊，保持了下代种群个体的多样性，从而可有效提高整个算
法的收敛速度。其中q'=q/（1…（1…q）n ），q=0。08。种群代数增１。
6。 染色体交叉重组
对步骤5 所产生的新种群，按选择概率p c 选择个体对进行交叉重组，共进行n/2次。
文献表明交换率pc =0。6～0。8之间时，进化性能较好，本文取p c =0。7，交叉规则采用PMX
法，下面举例说明。设父代的两个染色体为 A=9 8 4 5 6 7 1 3 2 10，B=8 7 1 2 3 10
9 5 4 6；按照PMX法，交叉重组过程如下：
k2
k1
k2 k1
A =9 8 4
5 6 7
1 3 2 10 A’ =9 8 4
2 3 10
1 6 5 7
B =8 7 1
2 3 10
9 5 4 6 B’ =8 10 1
5 6 7
9 2 4 3
其中交叉交换点1≤k 1 ＜k2 ≤l是随机选取的。对交叉成功所获得的子代应用步骤2；
3求得其对应的适应值，并与其父代进行比较，选择四者中性能最好的２个进入种群。
7。 染色体变异
12…25
在每代种群中，以变异率p m =0。02对进行变异，变异策略是随机交换选中染色体内两
个基因的值。对变异成功所获染色体应用步骤2；3求得其适应值，并与其父染色体比较，择
性能优者进入种群。
8。 返回步骤4，循环。
例 12…9有八个分仓库和一个中心仓库的配送系统，各分仓库的对中心仓库的需求为
di（i=1，2； …；8）（单位为吨），中心仓库只有两辆车用于配送，每辆车的容量皆为8吨，
已知中心仓库与各分仓库间的距离如下表（其中0表示中心仓库），要求合理安排车辆的行驶
路线，使总运输里程最短。
表 12…20 分库间距离及各分库需求量表
cij 0 1 2 3 4 5 6 7 8
0 0 4 6 7。5 9 20 10 16 8
1 4 0 6。5 4 10 5 7。5 11 10
2 6 6。5 0 7。5 10 10 7。5 7。5 7。5
3 7。5 4 7。5 0 10 5 9 9 15
4 9 10 10 10 0 10 7。5 7。5 10
5 20 5 10 5 10 0 7 9 7。5
6 10 7。5 7。5 9 7。5 7 0 7 10
7 16 11 7。5 9 7。5 9 7 0 10
8 8 10 7。5 15 10 7。5 10 10 0
需求量 1 2 1 2 1 4 2 2
解：运用遗传算法对上述问题进行求解，用2 ×8个互不重复的１到16的自然数构成一
个染色体码链，表示一种车辆路径安排方案，随机产生10个这样的染色体构成初始种群；预
定进化代数为50，以0。7和0。02分别作为染色体的交叉率和变异率对染色体进行交叉和变异
操作，经过上机运算；得最终的线路为：
0→4→7→6→0
0→1→3→5→8→2→0
运输总距离为：67。5
显然，此方案既满足车辆容辆约束又满足了各分仓库的需求，是一个上述车辆路径问
题的一个可行解。而用节约法对同一问题进行求解，得线路安排为：
0→6→5→7→3→0
0→4→8→2→1→0
相应的运输距离为：79。5
从上可见，遗传算法不失为VRP问题一个较优的满意解。而对上述算例的遗传算法过程
进行跟踪；发现每代最优个体的适应度变化如图5…31所示；说明所构造的遗传算法在较小的
种群规模下可以较快的速度进化，向最优解逼近。同时遗传算法也适用于规模较大的VRP问
题，对于具有如时间窗口、行驶里程限制等约束条件的VRP问题，通过实验证明，遗传算法
的求解性能也非常好，可以较快地找到问题的优化解或近似优化解。
0。015
0。0148
0。0146
0。0144
0。0142
0。014
0。0138
0。0136
0。0134
0。0132
0。013
图12…31GA寻优过程图
12…26
1 5 101520253035404550代数
适应度
本章小结
本章对产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题常见
运输问题进行了分析，建立了这些问题的数学模型，并就求解这些问题的基本方法如表上作业法、匈牙利
法、标号法、Dikstra法等进行了介绍，同时也就一些启发式算法、人工智能方法进行了分析和构造，如
扫描法、节约法、遗传算法、神经网络算法等等，这些对于掌握运输优化方法，提高运输管理水平具有重
要的意义。
思考题
1。下图为W仓库，A；B；C；D为4个需要配送的站点，图上每边上的数字为点对间的距离，请安
排从W出发，巡回配送每个站点的最短路线。
D
C
B
A
48
31
34
34
26
34
47
23
W
2。已知一个运输公司有两辆货车，一辆载重量为12吨，另一辆为10吨。该公司在
A；B；C；D；E；F6个城市装载货物，然后运回到货场o。货场和6城市间的距离以及
A；B；C；D；E；F6个城市需要装载的货物量均列在下表中，问如何安排车辆及运输线路比较合
理？
点对间距及载货需求表
间距 O A B C D E F
0 0 3 4 2 6 3 5
A 2 0 3 1 4 5 3
B 3 9 0 5 2 6 8
C 4 3 4 0 6 3 4
D 2 6 5 3 0 4 2
E 3 5 3 4 2 0 4
F 5 7 2 6 3 1 0
载货需求 6 5 8 5 6 7
3。设有某企业在a；b；c；d4个不同地区设有生产工厂生产同一种产品，每月产量分别为40，30，45和20（单位为吨），按计划调运到设在e；f；g的3个分配中心，分别为50，55和30（单位为吨）。已知各产地到各销地的单位产品运费（单位为元）如下表，请作出调运计
划，使调运费用最少。
单位运费表
产地
销地 e f g
12…27
a 17 16 14
b 11 14 13
c 15 11 14
d 12 11 10
4。请构造出带时间窗的VSP节约法算法，并进行说明。
12…28