区域物流中VRPTWSDP问题的混合遗传算法

Hybrid Genetic Algorithm for VRPTWSDP problem in Regional Logistics

研究了区域物流中带时间窗约束的具有同时集送货需求的车辆路径问题(VRPTWSDP),给出了VRPTWSDP的混合整数规划模型,设计了求解VRPTWSDP的混合遗传算法(Hybrid GA,HGA)。算法以最优划分方法计算适应值,邻域搜索法作为变异算子,设计了新颖的交叉算子和群体更新策略,定义了群体多样性结构和变异概率的变化规律。对典型VRPTWSDP实例进行测试的结果表明:HGA算法能较快地获得小规模问题的最优解,并能有效地求解大规模的问题。

The paper studies the vehicle routing problem with time window and demand for simultaneous delivery and pick-up （VRPTWSDP） of regional logistics, offers a mix-integer programming model and presents the hybrid genetic algorithm （HGA） for its solution. The algorithm employs the optimal splitting procedure to obtain the fitness value, uses local search as the mutation operator, designs＇ a novel crossover and a replacement scheme and defines the structure of population diversity and the adjustment rule of mutation probability. A sub- sequent case study on the classic VRPTWSDP demonstrates that HGA can obtains rather speedily the optimal solution to problems of small scale and can also be effective in dealing with problems of large scale.