淘豆网
下载此文档放大查看缩小查看   1/11
下载文档 文档分类:论文 > 自然科学论文

多约束条件车辆路径问题的二阶段遗传退火算法.doc


下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
多约束条件车辆路径问题的二阶段遗传退火算法.doc
文档介绍:
多约束条件车辆路径问题的二阶段遗传退火算法.doc多约束条件车辆路径问题的二阶段遗传退火算法
第39卷第12期
2005年12月
西安交通大学
JOURNALOFXIANJIAOTONGUNIVERSITY
Vo1.39№12
Dec.2005
多约束条件车辆路径问题的二阶段遗传退火算法
吕军,冯博琴,李波
(西安交通大学电子与信息工程学院,710049,西安)
摘要:针对多约束条件的多配送中心有时间窗车辆路径问题,提出了一种二阶段遗传退火算法.在第1阶
段,使用遗传算法对客户按供应量和路径长度进行模糊分区;在第2阶段,采用二维变长染色体编码及相应
的遗传算子进行混合遗传算法的全局优化.在初始种群生成和交叉,变异算子中采用了随机贪心算法以避免
无效解,并利用退火选择来提高种群的多样性.实验结果表明,二阶段遗传退火算法可加速收敛,提高搜索效
率,在模糊分区上的搜索速度较之标准遗传算法提高了3410倍.
关键词:车辆路径;遗传退火算法;贪心算法
中图分类号:TP18;Ul16文献标识码:A文章编号:0253—987X(2005)12—1299—04
Two-ic-AnnealingAlgorithmforVehicleRouting
ProblemwithMultipleConstraints
L//Jun,FengBoqin,LiBo
(SchoolofElectronicsandInformationEngineering,XianJiaotongUniversity,Xian710049,China)
Abstract:Anoveltwo—ic-annealingalgorithmisproposedtosolvethevehicleroutingproblem
withtimewindow(MDVRPTW)andmulti—constraintinmultipledispatchingcenters.Inthefirstphase,
ic
algorithm;icalgorithmwith
2Dvariable-icoperators.Therandomgreedyalgorithmis
usedingeneratingofinitialpopulationandcrossoverandmutationoperatortoavoidinvalidsolution.then
thesimulatedannealingalgorithmisemployedtoenhancethediversityofpopulation.Theexperimentalre—
icalgorithmthesearchspeedoftheproposedalgorithm
is3410timesfaster,theconvergenceisspeedup,andsearchefficiencyisincreased.
Keywords:vehiclerouting;gP以Pc口72以P口Z以galgorithm;greedyalgorithm
车辆路径问题(VehicleRoutingProblem,
VRP)是一类经典的NP难问题_1],目标函数通常为
车辆数和运输成本最小化.随着约束条件的不同,
VRP演化出许多模型,如非对称VRP(AVRP),带
时间窗的VRP(VRPTW)及多配送中心的VRP
(MDVRP)等,而现实环境中的问题往往是以上模
型的混合.
VRP的求解算法主要有精确算法和启发式算
法.对大规模的VRP问题,启发式算法能在较短的
时间内获得满意的近似最优解,这种算法主要指构
造型算法,改进型算法,导向邻域搜索算法l2],也有
许多研究是这些算法的某种混合算法.
对于复杂约束VRP问题的遗传算法,其简单
的编码必然损失解的大量信息,所以需要设计合适
的编码方案.另外,由于约束的增加,会造成整个搜
索空间不连续,使邻域搜索更加困难.一般的遗传算
子易导致大量的解因违背约束条件而成为无效解,
必须针对问题的特殊性设计相关的交叉,变异算子.
收稿日期:2005—04—08.作者简介:吕军(1968~),男,在职博士生,高工;冯博琴(联系人),男,教授,博士生导师.
基金项目:国家高技术研究发展计划资助项目(2003AA001048).
1300西安交通大学第39卷
本文提出的二阶段遗传退火算法采用二维变长
编码保存合法解的各种约束条件,并在初始种群生
成和交叉,变异算子中采用随机贪心算法以避免出
现无效解.为了缓解种群的多样性损失,在种群竞争
中还引入了模拟退火选择机制.算法在第1阶段对
客户按供应量和路径长度进行模糊分 内容来自淘豆网www.taodocs.com转载请标明出处.
更多>>相关文档
文档信息
最近更新
文档标签