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

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

作　　者：张烜荧 胡蓉[1,2] 钱斌[1,2] 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)

机构地区：[1]昆明理工大学信息工程与自动化学院自动化系,云南昆明650500 [2]昆明理工大学云南省人工智能重点实验室,云南昆明650500

出　　处：《控制理论与应用》2021年第9期1427-1441,共15页Control Theory & Applications

基　　金：国家自然科学基金项目(61963022,51665025)资助。

摘　　要：本文针对带软时间窗的同时取送货车辆路径问题(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.

关 键 词：同时取送货车辆路径问题 软时间窗 多目标优化 超启发式分布估计算法 

分 类 号：F252[经济管理—国民经济] TP18[自动化与计算机技术—控制理论与控制工程]