| 离散灰狼优化算法求解VRPSPDTW问题 |
| |
| 引用本文： | 陈凯,邓志良,龚毅光.离散灰狼优化算法求解VRPSPDTW问题[J].计算机系统应用,2023,32(11):83-94. |
| |
| 作者姓名： | 陈凯 邓志良 龚毅光 |
| |
| 作者单位： | 南京信息工程大学 自动化学院, 南京 210044 |
| |
| 基金项目： | 国家重点研发计划(2018YFC1405703) |
| |
| 摘 要： | 本文针对带时间窗约束的同时送取货车辆路径问题,建立了以总配送距离最小化为目标的数学模型.根据模型的特征,在保留灰狼算法(GWO)搜索机制的基础上,提出了离散灰狼优化算法(DGWO)进行求解.采用多种策略构建种群的初始解,并允许出现不可行解,扩大种群的搜索区域;引入带评分策略的邻域搜索策略,调整每种算子的概率,使算法选择优化效果更好的算子;使用移除-插入机制,对优质解区域进行探索,加速种群的收敛.在仿真实验中对标准数据集进行了测试,将实验结果和p-SA算法、DCS算法、VNS-BSTS算法和SA-ALNS算法进行了对比,实验表明DGWO算法能有效地解决带时间窗约束的同时送取货车辆路径问题.
|
| 关 键 词： | 车辆路径问题 同时送取货 灰狼算法 时间窗 邻域搜索 |
| 收稿时间： | 2023/5/9 0:00:00 |
| 修稿时间： | 2023/6/6 0:00:00 |
Discrete Grey Wolf Optimization Algorithm for VRPSPDTW Problem |
| |
| CHEN Kai,DENG Zhi-Liang,GONG Yi-Guang.Discrete Grey Wolf Optimization Algorithm for VRPSPDTW Problem[J].Computer Systems& Applications,2023,32(11):83-94. |
| |
| Authors: | CHEN Kai DENG Zhi-Liang GONG Yi-Guang |
| |
| Affiliation: | School of Automation, Nanjing University of Information Science & Technology, Nanjing 210044, China |
| |
| Abstract: | In this study, a mathematical model aiming at minimizing the total distribution distance is established for the vehicle routing problem of simultaneous delivery and pickup with time window constraints. According to the characteristics of the model, a discrete grey wolf optimization (DGWO) algorithm is proposed to solve the problem on the basis of preserving the search mechanism of the grey wolf optimization (GWO) algorithm. Multiple strategies are adopted to construct the initial solution of the population, and the unfeasible solution is allowed to expand the search area of the population; the neighborhood search strategy with scoring strategy is introduced to adjust the probability of each operator so that the algorithm can select the operator with better optimization effect; the deletion-insertion mechanism is used to explore the high-quality solution region and accelerate the convergence of the population. The standard data set is tested in the simulation experiment, and the experimental results are compared with the p-SA algorithm, DCS algorithm, VNS-BSTS algorithm, and SA-ALNS algorithm. The experiment shows that the DGWO algorithm can effectively solve the vehicle routing problem of simultaneous delivery and pickup with time window constraints. |
| |
| Keywords: | vehicle routing problem (VRP) simultaneously deliver and pick up the goods grey wolf optimization (GWO) algorithm time window neighborhood search |
|
| 点击此处可从《计算机系统应用》浏览原始摘要信息 |
|
点击此处可从《计算机系统应用》下载全文 |
|
