退火单亲遗传算法求解带软时间窗的车辆路径问题

Simulated Annealing Partheno Genetic Algorithm for VRP with Soft Time Windows

为有效求解带软时间窗的车辆路径问题，在单亲遗传算法中加入模拟退火选择操作，与倒位算子和2-change算子相结合，构建了退火单亲遗传算法。实现了以虚拟自然数代表中心点，使得可以直接利用求解旅行商问题的有效遗传算子。在选择操作中，采用三复本锦标选择的方式，保持了种群的多样性。计算结果表明该方法能有效求解车辆路径问题，取得较一般遗传算法更优的结果，算法的搜索效率和收敛概率均得到大幅度提高。

To resolve the vehicle routing problem with soft time window, the partheno genetic algorithms combined with sim- ulated annealing is proposed in this paper, inverse operator and 2 - change operator are presented. Centre point is replaced by the dummy natural number, then it is easy to make use of the available methods using by travel saleman problem. A se- lection method with tournament of three copies can remain the diversity of population. The simulation results show that new algorithm can resole vehicle routing problem with time windows effectively, and get better results than common genetic algo- rithm, new algorithm＇ s searching efficiency and convergence probability are improved effectively.