基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题

发布时间：2021-01-14 16:54

　　为了求解带时间窗和同时送取货的车辆路径问题（VRPSDPTW）,首次设计了回溯搜索优化算法（BSA）求解该问题。使用随机选择法、最近邻居法、最远者优先法、剩余承载力和径向附加费节约算法产生初始种群。然后在BSA算法框架下,在交叉和变异操作中使用6种路径间搜索算子和4种路径内搜索算子更新当前局部最优解。选取文献[1]测试数据集中的6个算例,将BSA算法的计算结果与文献中已知的遗传算法、并行模拟退火算法和离散布谷鸟算法的结果进行比较,对算法性能进行测试。BSA算法获得了2个已知国际最好解,并更新了1个已知国际最好解。Friedman检验显示,在α=0.1%的显著性水平下,这4种算法不存在显著性差异。因此,所提出的BSA算法是求解VRPSDPTW的有效算法。 

【文章来源】：计算机集成制造系统. 2019,25(09)北大核心

【文章页数】：11 页

【文章目录】：
1 问题的提出
2 考虑时间窗和同时送取货的车辆路径优化问题
3 VRPSDPTW问题的回溯搜索优化算法设计
    3.1 回溯搜索优化算法流程和步骤
    3.2 解空间的编码与重构
    3.3 初始种群的构造
    3.4 改进试验种群的变异和交叉操作
4 测试算例和算法性能比较
    4.1 测试算例
    4.2 算法性能分析
5 结束语
    附录1
    附录2


【参考文献】：
期刊论文
[1]基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J]. 王超,刘超,穆东,高扬.  计算机集成制造系统. 2018(03)
[2]基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 穆东,王超,王胜春,周圣川.  计算机集成制造系统. 2015(06)



本文编号：2977205