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

来源：计算机集成制造系统杂志2019年第9期北京时间：

作者：王超,高扬,刘超,王明刚

单位：1.北京工业大学经济与管理学院2.波士顿大学物理系3.南京师范大学数学科学学院

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

关键词：逆向物流,车辆路径,同时送取货,时间窗,回溯搜索优化算法

基金资助：国家自然科学基金青年基金资助项目(61603011,61603010);国家自然科学基金面上资助项目(61773029,71503132);北京市社会科学基金研究基地资助项目(16JDGLC005);博士后国际交流计划资助项目(20170016);江苏省青蓝工程资助项目(2017)。