-1-
带时间窗和货物权重的车辆路径问题的遗传算法
朱才华，何渝
北京工商大学计算机与信息工程学院，北京 (100037)
摘 要：本文提出了带货物权重及时间窗的车辆路径问题(vehicle routing problem with time
window and weight，VRPTWW)在车辆数不确定条件下的一个新的求解算法。通过利用轮盘
赌选择策略，既能使最优个体进入下一代, 又避免了个体之间因为适应度不同而被选择进入
下一代的机会相差很大,从而保证了下一代的多样性并提高了算法的收敛速度。选用 cx交叉
算子有效避开遗传算法的“早熟收敛”,同时对路径划分算法进行优化，从而达到 VRPTWW车
辆数与路径双重优化。数值实验结果表明 ,此算法可以有效求得车辆路径问题的优化解或近
似优化解 ,是求解车辆路径问题的一个较好的方案。
关键词：车辆路径问题；货物权重；时间窗；遗传算法
中图分类号：O224
1．引言
车辆路径问题 ( vehicle routing problem ,VRP)最早是由 Dantzig 和 Ramser 于 1959 年
首次提出的, 在公路交通运输、 水运、 航空和通讯等领域有着广泛的应用。遗传算法
（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是
一种通过模拟自然进化过程搜索最优解的方法，它是由美国 Michigan 大学 教授于
1975 年首先提出来的， 教授所提出的 GA 通常为简单遗传算法（SGA）。有时间
窗并且带货物权重的车辆路径问题(vehicle routing problem with time window and weight，
VRPTWW )是在基本 VRP 中对每个客户的开始服务时间范围和车辆容量加以约束, 与实际
情况更加吻合, 因此有很强的实用背景。
目前对该问题的研究主要集中在各种启发式算法上, 其中遗传算法是研究得较多的一
种方法[1-3,8]。] 目前, 国内外对 VRPTW 的研究多以针对带时间窗[5-6]或带货物权重[7]来求解,
而对两者进行综合的问题涉及较少[4]。本文采用遗传算法, 对不确定车辆数的有时间窗和带
货物权重车辆路径问题的求解进行研究, 通过引入CX 交叉算子, 提出了一种改进路径划分
算法, 使遗传算法在 VRPTWW 问题的计算过程中能自动寻找满足要求的最少费用的路径
划分, 能有效克服遗传算法的“早熟性收敛” , 得到的优化结果也更接近最优解。
2．问题的描述及模型建立
问题描述
一个分销中心(记为节点 0)，拥有 K 辆容量为 V 的车辆，负责对 N 个零售商进行货物
分送工作(记为节点 I=1，2，…，n)，每个零售商的需求量为 iQ (i=1，2…，n)假设 iQ <V。
分销中心与零售商两两之间的距离记为 jid , (i，j 的取值从 0 到 n)，并假设任意三点间的距离
满足三角不等式。同时车辆必须在一定时间范围[ ia ， ib ]内到达。求如何安排分销路线和车
辆，使整个分销过程的费用最小。
数学模型
设每辆车的载重量为 v，行驶单位距离的费用为 rc ,所花费的时间为 T，运送单位重量
-2-
货物行驶单位距离的费用为 gc ，每租用一辆费用为 fc 。
数学模型表示如下：
∑ ∑
= =
++×= ++
R
k
N
m
ssrf
k
kNmkmk
dcRcMinFee
1 0
, )1)%(1,(,
∑ ∑
= = ++++
××
R
k
N
m
ssssg
k
kNmkmkkNmkmk
Qdc
1 0
,, )1)%(1,(,)1)%(1,(, （1）
R,1,k .
1
,
"=∀≤∑
=
VQ
k
mk
N
m
s （2）
∑
=
++ ++=
k
kNikkmk
N
mi
SNmk QsQs )1)%(1(,, )1)%(1(,, （3）
∑
= +
×= k
kNmkmk
N
m
ssmk dTt
0
,, )%1(,, （4）
imki bta << , （5）
其中:R 表示线路的条数， kN 表示第 k 条路线节点的个数， mkt , 表示第 k 条路线,从分
销中心到达 m 节点所需要的时间， mks , 表示第 k 条路线第 m 个节点, 1,, , +mkmk ssd 表示第 k 条
路线上节点 m 到节点 m+1 的距离。
1,, , +mkmk ssQ 表示第 k 条路线上从节点 m 到节点 m+1 车
辆的载重。
3．算法设计
染色体表示、划分
本文采用基于车辆行驶路径的顺序编码，与以往的大多数求解 VRP 问题的遗传算法编
码不同的是，路径划分算法不以分销中心作为路径的划分点（即连续两个分销中心点之间所
有节点构成一条路线），而是采用划分算法将染色体划分成多条路径。
对于已经确定的染色体，该染色体的最优划分满足动态规划，即：去掉染色体最后一部
分节点，剩下节点的划分仍满足最优划分。因此可以在满足车辆载重和时间窗限制的条件下，
针对当前节点 i 和后继节点 i+1 之间的开销与和先经过分销中心再到后继节点 i+1 的开销做
比较，选择开销小的为最优路径。如下图：
-3-
图 1 染色体的划分
Fig1 Partition of chromosome
适值计算
由遗传算法得到的每条染色体，MinFee 为当前染色体在路径划分算法下得到的可行解
的运输费用，即：MinFee 越小，得到的染色体就越好。
自然选择
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗
传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作
的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。本文选择算子采用
轮盘赌选择方法。
轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函
数值大小成正比。设群体大小为 n ，个体 i 的适应度为 Fi，则个体 i 被选中遗传到下一代
群体的概率为 ：
∑
=
=
n
i
iii FFP
1
/
交叉
在每代种群中, 以一定的交叉概率对染色体进行交叉重组, 本文采用一种新的CX 交叉
算子, 其最大特点是当两父串相同时, 仍能产生新的个体, 这就减弱了对群体多样性的要求,
能有效地避免传统遗传算法 “早熟收敛” 的缺点, 这是以往交叉算子所不具备的, 实验结果
说明这样做有更好的的结果。 具体的交叉过程为:
任意给定两个互不相同的染色体 A 和 B , 随机产生两个交叉点, 将不同的染色体 A 和
B , 随机产生两个交叉点, 将每一个染色体的交叉段移到对方染色体的首部得到染色体 A1
和 B1, 消去相同项得到两个新个体 A 2 和 B2。
表 1 染色体 A 和 B
Chromosome A and B
A 1 2 |3 4 5 6 7| 8 9 0
B 0 9 |8 7 6 5 4| 3 2 1
将 B(A)中间的一段染色体移到 A(B)的最前面，得到表 2。
-4-
表 2 交叉
Crossing
A1 8 7 6 5 4 1 2 3 4 5 6 7 8 9 0
B1 3 4 5 6 7 0 9 8 7 6 5 4 3 2 1
消去染色体中相同的部分，得到表 3。
表 3 消去相同的部分
Delete the same part
A2 8 7 6 5 4 1 2| 3 9 0
B2 3 4 5 6 7 0 9| 8 2 1
任意给定两个相同的染色体 A’,B’ , 经过 CX 交叉算子, 仍然可以产生不同于父体的新
个体, 即, 由于新颖交叉算子的引入, 当个体都相同时, 仍然能进行迭代进化, 继续寻找问
题的优化解,跳出了局部最优解, 克服了 “早熟收敛” 的缺点。 而以往的交叉算子, 当个体
都相同时无法继续迭代进化, 只能寻找到问题的局部最优解，如下表 4，5。
表 4 两个相同的染色体
Two same chromosome
A’ 1 2 |3 4 5 6 7| 8 9 0
B’ 1 2 |3 4 5 6 7| 8 9 0
最后得到表 5。
表 5 使用 CX 算子交叉后的情况
The new chromosome after using CX operator
A1’ 3 4 5 6 7 1 2 8 9 0
B1’ 3 4 5 6 7 1 2 8 9 0
变异
物种变异的可能性较小, 所以在遗传算法中变异操作只起辅助作用。对每代种群以变异
概率进行染色体变异。在此, 对自然数编码的染色体采用交换两点基因值的变异策略。
表 6 变异前的染色体
The primal chromosome
1 |2 3 4 5| 6 7
将 5 移动到 2 的前面，其他顺次往后移，得到表 7。
表 7 变异后的染色体
The new chromosome after variation
1 5 2 3 4 6 7
4．计算实例
测试平台：Visual Studio 2005
随即生产 15 个零售商的数据，其坐标和需求量如下：
-5-
表 8 零售商位置
The position of retail merchant
零售商编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
X 坐标 -12 -7 -7 -5 -4 -1 0 0 4 7 9 10 12 14 14
Y 坐标 10 2 -3 -6 -5 -9 -11 13 -14 -12 -1 1 5 15 -10
表 9 零售商需求量
The demand of retail merchant
零售商编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
需求量 15 15 12 17 13 16 15 6 17 16 16 12 10 7 17
表 10 时间窗限制
The constraint of time window
零售商编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
时间范围 1 5 1 3 9 4 5 2 7 3 5 4 2 1 3
注：考虑到针对某零售商在某一时间之前到达可能没有可行解，本文此处将时间的下限设置
为 0，即：不能迟到，能提前到达。
本文针对当前算法的实际情况，交叉概率取 ，变异概率取 ，种群为 120，遗传
代数 500，在 v=40， rc =15， gc =5， fc =200 下，重复运行 30 次得出：
表 11 重复运行 30 次,结果比较
Rerun 30 times and compare the results
VRP 算法 最优解 平均解
简单遗传算法
改进遗传算法
5．结论
本文探讨了一种带有时间窗和货物权重的车辆路径遗传算法。根据遗传算法的特点, 通
过分析车辆运输的实际情况, 将影响配送车辆调度的多项指标和约束条件转化为新的 CX
交叉算子,, 能有效地避免 “早熟收敛”现象, 同时通过路径划分算法能减少遗传代数，能得
到更接近最优解的优化结果。
-6-
参考文献
[1] Beasley J E. Route first cluster second methods for vehicle routing[J ] . Omega , 1983 , 11(4) : 403-408.
[2] Tan K, Lee T ,O u K, et al . A messy genetic algorithm for the vehicle routing problem with time window
constraints . proceedings of IEEE Congress on Evolutionary Computation, 2001 (1) : 6792686.
[3] Baker B,A yechew M. A genetic algorithm for the vehicle routing problem. Computers &Operations Research,
2003, 30 (2) : 7872800.
[4] 郭辉煌,李军.车辆优化调度问题的研究现状评述[J].西南交通大学学报,1995,30(4):376-382.
[5] 李大卫, 王莉, 王梦光. 遗传算法在有时间窗车辆路径问题上的应用. 系统工程理论与实践, 1999,19 (8) :
65269.
[6] 谢秉磊, 李 军, 刘建新. 有时间约束旅行商问题的启发式遗传算法. 西南交通大学学报, 2001, 36
(2) :2112213.
[7] 潘震东, 唐加福, 韩 毅. 带货物权重的车辆路径问题及遗传算法. 管理科学学报,2007,10(3):24-27.
[8] 李 军, 郭耀煌. 物流配送车辆优化调度理论与方法. 北京: 中国物资出版社, 2001: 1302156.
Vehicle Routing Problem Optimization with Time
Windows and Weight
Zhu Caihua，He Yu
Department of Computer Science and Information, Beijing Technology and Business University,
Beijing, PRC (100037)
Abstract
This paper proposed a new genetic algorithm for solving vehicle routing problem with time window
and weight(VRPTWW) under the uncertain vehicle number. Using the roulette wheel strategy the
optimal individual can be selected into next generation. The phenomenon, which is there are significant
differences between the opportunity to individuals selected into next generation according to their
fitness, is also escaped. As a result, the next generation is more diversity and convergence rate is
improved. The premature convergence is avoided successfully by introducing CX crossover operator.
Improvement in rout partition algorithm lead vehicle number and vehicle rout to optimal solution.
Finally, the computational results show our algorithm can solve VRPTWW effectively.
Keywords: Vehicle Routing Problem; Weight; Time Window; Genetic Algorithm
作者简介：朱才华，男，1979 年生，硕士研究生，主要研究方向是最优化方向，遗传算法。
