| 引用本文: | 张烜荧,胡蓉,钱斌.超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题[J].控制理论与应用,2021,38(9):1427~1441.[点击复制] |
| ZHANG Xuan-ying,HU Rong,QIAN Bin.Hyper-heuristic estimation of distribution algorithm for solving vehicle routing problem with simultaneous pickup and delivery and soft time windows[J].Control Theory and Technology,2021,38(9):1427~1441.[点击复制] |
|
| 超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题 |
| Hyper-heuristic estimation of distribution algorithm for solving vehicle routing problem with simultaneous pickup and delivery and soft time windows |
| 摘要点击 1838 全文点击 674 投稿时间：2020-07-02 修订日期：2021-08-27 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2021.00408 |
| 2021,38(9):1427-1441 |
| 中文关键词 同时取送货车辆路径问题 软时间窗 多目标优化 超启发式分布估计算法 |
| 英文关键词 vehicle routing problem with simultaneous pickup and delivery soft time windows multi-objective optimization hyper-heuristic estimation of distribution algorithm |
| 基金项目 国家自然科学基金项目(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. |
|
|
|
|
|