退火单亲遗传算法求解随机需求VRP问题  

Simulated Annealing Partheno Genetic Algorithm for VRP with Stochastic Demand

作　　者：张启义[1] 朱杰[1] 

机构地区：[1]汽车管理学院运输指挥系,安徽蚌埠233011

出　　处：《江南大学学报（自然科学版）》2010年第2期196-200,共5页Joural of Jiangnan University (Natural Science Edition)　

摘　　要：为了有效求解随机需求的车辆路径问题,在单亲遗传算法中加入模拟退火选择操作,构建了退火单亲遗传算法;并实现了以虚拟自然数代表中心点,可直接利用求解随机需求VRP问题的有效遗传算子。在选择操作中,采用三复本锦标选择的方式,保持了种群的多样性。计算结果表明,该方法可有效求解随机需求车辆路径问题,算法的搜索效率、收敛概率均得到大幅度提高,取得了比一般遗传算法更优的结果。In order to solve the vehicle routing problem with stochastic demand,a kind of Partheno Genetic Algorithms combined with Simulated Annealing was proposed in the paper.Central point was replaced by the dummy natural number.It is easy to make use of the available methods used by VRP with stochastic demand.A selection method with tournament of three copies can keep the diversity of population.The simulation results show that new algorithm can effectively solve VRPTW,and get better results than common GA.New algorithm＇s searching efficiency and convergence probability are effectively enhanced.

关 键 词：单亲遗传算法 模拟退火 三复本锦标选择 车辆路径问题 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]