原文传递
带硬时间窗的车辆路径优化算法研究
| 论文题名： | 带硬时间窗的车辆路径优化算法研究 |
| 关键词： | 车辆交通;路径优化;时间窗;全局最优解;混合算法 |
| 摘要： | 近二十年，车辆路径问题一直是数学应用、计算机应用、交通运输、管理科学等领域的研究重点。其中，求解带硬时间窗的车辆路径问题被证明是NP难问题，难以用传统方法解决，通常采用启发式算法来求解。然而，启发式算法存在收敛速度慢、容易陷入局部最优等缺陷。此外，带硬时间窗车辆路径问题的多个目标之间往往相互矛盾，需要考虑各目标之间的平衡。因此，对多目标带硬时间窗车辆路径问题的研究具有重要意义。本文结合邻域搜索策略和智能算法对该问题展开研究，提出一种求解双目标的混合变邻域禁忌搜索算法，同时为进一步满足实际需求，提出求解多目标的混合邻域进化算法，都得到了较好的结果。具体如下： 1）针对带硬时间窗车辆路径问题，建立最小化车辆数和总行驶距离的双目标非线性优化模型，提出一种混合变邻域禁忌搜索求解算法。一方面，采用改进的节约算法生成初始解，设计了三种删除算子和一种插入算子对初始解进行扰动优化，为后续禁忌搜索提供优良的初始解；另一方面，基于四种邻域构造算子进行禁忌迭代搜索，利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解，最终实现全局优化。在Solomon和Homberger数据集上的实验结果表明，该算法的求解质量优于文献中两种同类型搜索算法，具有良好的收敛性和稳定性。 2）在双目标非线性优化模型基础上，增加最小化最长路径行驶距离的目标，提出一种混合邻域进化算法。采用进化算法来进行全局搜索，邻域搜索算法来进行局部优化。在每次迭代中，混合邻域进化算法首先利用进化算法生成一组种群，然后利用基于特定目标函数的局部搜索算子对种群中的个体进行优化，得到一组局部最优解。接着，通过快速非支配排序和拥挤度计算比较全局最优解和局部最优解，选择一组最优解作为下一代初始种群。同时，引入速度，对Solomon数据集进行调整，实验结果表明，该方法的收敛性和分布性优于带精英解的快速非支配排序遗传算法。 |
| 作者： | 贺琪 |
| 专业： | 系统科学 |
| 导师： | 官礼和 |
| 授予学位： | 硕士 |
| 授予学位单位： | 重庆交通大学 |
| 学位年度： | 2023 |
检索历史
应用推荐
