求解同时取货和送货车辆路径问题的改进遗传算法  

Improved Genetic Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries

作　　者：彭春林[1] 梁春华[1] 周泓[1] 

机构地区：[1]北京航空航天大学经济管理学院,北京100083

出　　处：《系统仿真学报》2008年第9期2266-2270,共5页Journal of System Simulation

基　　金：国家自然科学基金(70371005;70521001);新世纪优秀人才支持计划(NCET)

摘　　要：同时取货和送货车辆路径问题(VRP_SPD)是经典车辆路径问题(VRP)的一个扩展,在VRP_SPD中,顾客可能要求同时取货和送货服务。本文针对这类问题,提出一种以集成方式处理取货和送货操作的改进遗传算法,通过采用一种改进的边重组交叉算子,保证了算法在遗传进化中保留父代路径上边之间邻接关系的映射信息,从而改进了算法性能;并通过在遗传进化控制参数中应用自适应策略,提高了算法的稳健性。仿真分析表明,本文算法比现有算法能取得更好的优化结果,且具有很好的稳定性。The vehicle routing problem with simultaneous pickups and deliveries （VRP SPD） is a variant ot the classical vehicle routing problem （VRP） where clients may require simultaneous pickups and deliveries service. An improved genetic algorithm was proposed to deal with pickups and deliveries in an integrated manner, instead of traditional insert-based heuristics. An enhanced edge recombination crossover was designed, which could keep the inheritance of edge-adjacency relationship between the two parent routings and thus result in an improved performance. A self-adaptation strategy was applied to control parameters which achieved a better robustness. Numerical experiments and simulation have been conducted which demonstrate that the algorithm can obtain even better results compared with the heuristic method commonly in use, and demonstrates a good robustness under the random environment.

关 键 词：车辆路径问题 遗传算法 边重组交叉 自适应策略 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]