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

同时取货和送货车辆路径问题(VRP_SPD)是经典车辆路径问题(VRP)的一个扩展,在VRP_SPD中,顾客可能要求同时取货和送货服务。本文针对这类问题,提出一种以集成方式处理取货和送货操作的改进遗传算法,通过采用一种改进的边重组交叉算子,保证了算法在遗传进化中保留父代路径上边之间邻接关系的映射信息,从而改进了算法性能;并通过在遗传进化控制参数中应用自适应策略,提高了算法的稳健性。仿真分析表明,本文算法比现有算法能取得更好的优化结果,且具有很好的稳定性。

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

The vehicle routing problem with simultaneous pickups and deliveries (VRP_SPD) is a variant of 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.