摘要
本文针对带软时间窗的同时取送货车辆路径问题(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.
作者
张烜荧
胡蓉
钱斌
ZHANG Xuan-ying;HU Rong;QIAN Bin(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming Yunnan 650500,China;Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming Yunnan 650500,China)
出处
《控制理论与应用》
EI
CAS
CSCD
北大核心
2021年第9期1427-1441,共15页
Control Theory & Applications
基金
国家自然科学基金项目(61963022,51665025)资助。
关键词
同时取送货车辆路径问题
软时间窗
多目标优化
超启发式分布估计算法
vehicle routing problem with simultaneous pickup and delivery
soft time windows
multi-objective optimization
hyper-heuristic estimation of distribution algorithm