具有同时配送和回收需求的车辆路径问题的混合遗传算法

介绍了具有同时配送和回收需求的车辆路径问题(VRPSDP),并对其进行了描述,建立了该问题的数学规划模型。结合2-opt法和等级替换策略等设计了求解VRPSDP的一种混合遗传算法,给出了该算法初始种群的两种生成规则———随机生成和构造初始种群,设计了相应的交叉和变异算子,并详细阐述了违反约束条件的处理方法。通过随机模拟试验以及与其他方法的对比分析表明:该算法可有效缩短车辆行驶距离,而构造初始种群则在一定条件下可显著提高混合遗传算法的收敛速度并改善其运行结果。

Hybrid Genetic Algorithm to Vehicle Routing Problem with Simultaneous Delivery and Pick-up

Vehicle routing problem with simultaneous delivery and pick-up(VRPSDP) was introduced and described;its mathematic model was built.Then,a hybrid genetic algorithm in combination with 2-opt method and ranking replace strategy was proposed.In this algorithm,two initial population generating rules-generating initial population randomly and constructing initial population were presented;corresponding cross and mutation operators were designed and the disposal methods to the violation of constraints were illustrated in detail.Finally,the stochastic simulation and the comparing experiment indicate that the proposed hybrid genetic algorithm can reduce the vehicle traveling distance effectively;the construction of the initial population in certain circumstances can quicken the convergence speed of the genetic algorithm remarkably and improve the final results.