车辆路径问题的改进遗传算法.pdf

!""!年#月系统工程理论与实践第#期
#################################################################
文章编号$%"""&’(##)!""!*"#&""(+&"’

车辆路径问题的改进遗传算法

张丽萍,柴跃廷
)清华大学自动化系-./0中心,北京%"""#1*

摘要$通过引入新颖交叉算子,构造了一种改进遗传算法,此算法摆脱了对群体多样性的要求,不存在传
统遗传算法常见的2早熟收敛3问题4将该算法用于解决车辆路径问题,实验结果表明,此算法可以有效求
得车辆路径问题的优化解,是求解车辆路径问题的一个较好方案4
关键词$遗传算法5车辆路径问题5交叉算子5群体多样性5早熟收敛
中图分类号$6!!1文献标识码$78

.9:;<=>?@>A>BCD7EF<;CBG9H<;I>GCDE>J<KBCAFL;<ME>9

NO7P@QC&:CAF,-O7.RK>&BCAF
)7KB<9SBC<AT>:S;B9>AB,UVCAFGKSWAC=>;VCBX,Y>CZCAF%"""#1,-GCAS*

[\]^_‘a^$.ABGCV:S:>;,SC9:;<=>?F>A>BCDSEF<;CBG9).@7*CV:;<:<V>?MSV>?<ABG>A<=>ED;<VV<=>;
<:>;SB<;b.@7S=<C?V>HH>DBC=>EXBG>D<99<A?>H>DBV<H>S;EXD<A=>;F>AD>SA?BG>?C=>;VCBX<H:<:KESBC<A
CAB;S?CBC<ASEF>A>BCDSEF<;CBG9bUGCVSEF<;CBG9DSAHCA?BG><:BC9SE<;A>S;EX<:BC9SEV<EKBC<AB<BG>=>&
GCDE>;<KBCAF:;<ME>9>HH>DBC=>EX,cGCDGCV:;<=>?MXSAK9M>;<H>d:>;C9>ABV:;<=C?>?MXBGCV:S:>;b
efghi_j]$F>A>BCDSEF<;CBG95=>GCDE>;<KBCAF:;<ME>95D;<VV<=>;<:>;SB<;5:<:KESBC<A?C=>;VCBX5>S;EX
D<A=>;F>AD>

k引言
车辆调度问题)I>GCDE>J<KBCAFL;<ME>9简称为IJL*是一个极具魅力的优化问题,吸引着全世界无
数的科学家l工程师和管理者为之探索4这不仅是因为它是一类求解较难的组合优化问题,是对人类智慧
的考验,而主要是因为它有很强的使用背景,可产生极其可观的经济效益4该问题是一个PL完全问题,只
有在需点数和路段数较少时才有可能寻求其精确解4因此,如何针对车辆路径问题的特点,构造运算简单l
寻优性能优异的启发式算法,这不仅对于配送系统而且对于许多可转化为车辆路径问题求解的组合优化
问题都具有十分重要的意义4先后涌现出一大批启发式算法,如-ES;m和n;CFGB提出的节约法,@CEE>BB和
/CEE>;提出的扫描法,Y;S9>EB和0C9DGC&Q>=C提出的基于选址问题转换的QYO法,oCVG>;和pSCmK9S;建
立的一般分派算法,-G;CVB<HC?>V和/CAFF<qqC等建立的不完全树搜索算法等4这些算法为求解车辆路径
问题提供了有效的方法,但也存在一系列问题,如节约法存在未组合点零乱l边缘点难于组合的问题5扫描
法为非渐进优化5QYO法则存在问题转化麻烦且选址问题本身难解等等4近年来,遗传算法l神经网络l禁
忌搜索和模拟退火等智能化启发式算法的出现为求解IJL问题提供了新的工具,并且在理论上也取得
了一些较好的效果4

r问题的描述及数学模型
车辆路径问题可以这样描述$假定配送中心最多可用s辆车对t个商店进行运输配送,每个车辆载
重为每个商店的需求为商店到商店的物耗值为商店到商
uv)vw%,!,x,s*,yz)zw%,!,x,t*,z{|z{,z
店的时耗值为设为第辆车所包含的商店数若表示未启用第辆车用集合表示第
{}z{~!vv)!vw"v*,"v

8收稿日期$!""%&"%&"$
作者简介$张丽萍)%+’+%*,女,硕士研究生b研究领域为管理与决策5柴跃廷)%+’1%*,男,副教授b研究领域为-./0分析与设计l管
理与决策l供需链lYJL等方面的研究l开发与应用b
e(系统工程理论与实践@((@年e月

条路径其中的元素表示商店在路径中的顺序为不包含配送中心令表示配
!"#!$#!$!$%&’#!()#!%*!+,&)(
送中心"则有如下表示的车辆路径问题的数学模型-
./0
**
3!3!
14##+4##6/70%*!5,&+%,51&:##+:##6/70%*!5,&%(&
22!%$5,&!$!*!!%*!5,&22!%$5,