超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题

Hyper-heuristic estimation of distribution algorithm for solving vehicle routing problem with simultaneous pickup and delivery and soft time windows

本文针对带软时间窗的同时取送货车辆路径问题(VRPSPDSTW),以最小化车辆行驶总里程和最大化服务准时率为优化目标,提出一种超启发式分布估计算法(HHEDA)进行求解.全局搜索阶段,首先,提出3种启发式规则生成初始个体,以确保初始种群的质量和分散性;其次,根据问题特点,构造3个概率矩阵分别学习和积累优质解的排序信息、客户间的距离信息和捆绑信息,并通过采样概率矩阵生成新个体,以增强算法全局搜索发现解空间中优质区域的能力.局部搜索阶段,将11种邻域操作组成备选集合,进而设计学习型超启发式局部搜索(LHHLS),用于动态选择备选集合中的部分邻域操作构成多种新的有效启发式算法,以执行对解空间中优质区域的深入搜索.最后,仿真实验和算法比较验证了HHEDA的有效性.

This paper proposes a hyper-heuristic estimation of distribution algorithm(HHEDA)for the vehicle routing problem with simultaneous pickup and delivery and soft time windows(VRPSPDSTW),whose optimization objectives are to minimize the total mileage of vehicles and maximize the on-time rate of service at the same time.In the global search stage.Firstly,three heuristic rules are presented to generate initial individuals to ensure the quality and diversity of the initial population.Secondly,according to the characteristics of the problem,three probability matrices are constructed to learn and accumulate the ordinal information of high-quality solutions,the distance information and the binding information among customers,respectively,and new individuals are generated by sampling these probability matrixes.By this way,the algorithm’s global search ability of finding the high-quality regions in solution space can be enhanced.In the local search stage,eleven kinds of neighborhood operations are used to form the alternative set,and then a learning hyper-heuristic local search(LHHLS)is designed to dynamically select some neighborhood operations in the alternative set to form a variety of new effective heuristic algorithms,so as to execute the in-depth searches from the high-quality regions in solution space.Finally,simulation experiments and algorithm comparisons verify the effectiveness of the proposed HHEDA.