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

多约束条件车辆路径问题的二阶段遗传退火算法.doc多约束条件车辆路径问题的二阶段遗传退火算法
第39卷第12期
2005年12月
西安交通大学
JOURNALOFXIANJIAOTONGUNIVERSITY
№12

多约束条件车辆路径问题的二阶段遗传退火算法
吕军,冯博琴,李波
(西安交通大学电子与信息工程学院,710049,西安)
摘要:针对多约束条件的多配送中心有时间窗车辆路径问题,
段,使用遗传算法对客户按供应量和路径长度进行模糊分区;在第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—,
ic
algorithm;icalgorithmwith
2Dvariable-

—
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的求解算法主要有精确算法和启发式算
,启发式算法能在较短的
时间内获得满意的近似最优解,这种算法主要指构
造型算法,改进型算法,导向邻域搜索算法l2],也有
许多研究是这些算法的某种混合算法.
对于复杂约束VRP问题的遗传算法,其简单
的编码必然损失解的大量信息,所以需要设计合适
,由于约束的增加,会造成整个搜
索空间不连续,
子易导致大量的解因违背约束条件而成为无效解,
必须针对问题的特殊性设计相关的交叉,变异算子.
收稿日期:2005—04—:吕军(1968~),男,在职博士生,高工;冯博琴(联系人),男,教授,博士生导师.
基金项目:国家高技术研究发展计划资助项目(2003AA001048).
1300西安交通大学第39卷
本文提出的二阶段遗传退火算法采用二维变长
编码保存合法解的各种约束条件,并在初始种群生
成和交叉,变异算子中采用随机贪心算法以避免出
,在种群竞争

客户按供应量和路径长度进行模糊分区,以减少多
配送中心的搜索空间.
1问题描述