具有同时集送货需求的车辆路径问题的自适应混合遗传算法  

Adaptive hybrid genetic algorithm for vehicle routing problem with simultaneous delivery and pick-up

作　　者：龙磊[1] 陈秋双[1] 华彦宁[1] 徐亚[1] 

机构地区：[1]南开大学信息技术科学学院,天津300071

出　　处：《计算机集成制造系统》2008年第3期548-556,共9页Computer Integrated Manufacturing Systems

基　　金：天津市自然科学基金资助项目(05YFJMJC01300);天津市科技发展计划资助项目(043185111-12)~~

摘　　要：为满足配送货物和收集货物的需求,给出了具有同时集送货需求的车辆路径问题的混合整数规划模型,设计了求解该模型的自适应混合遗传算法。该算法以最优划分方法计算适应值,邻域搜索法作为变异算子,设计了新颖的交叉算子和群体更新策略,定义了群体多样性结构和变异概率的变化规律。通过仿真实验,并与已有优化算法比较,表明该算法是求解具有同时集送货需求的车辆路径问题和一般车辆路径问题的一个有效方法。To satisfy demand of delivery and pick-up, a mix-integer programming model for Vehicle Routing Problem with Simultaneous Delivery and Pick-up （VRPSDP） was presented. An adaptive hybrid genetic algorithm was developed to solve VRPSDP, which used a special optimal splitting procedure to get the fitness values, and took a local search as the mutation operator. A novel crossover and a population replacement scheme were designed. Measurement of population diversity and the adjustment rules of mutation probability were also defined. Numerical computations indicated that it was an effective algorithm for solving VRPSDP and VRP.

关 键 词：车辆路径问题 集送货需求 混合遗传算法 邻域搜索 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置] U116.2[自动化与计算机技术—控制科学与工程]