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

Vehicle routing problem with simultaneous delivery and pickup problem solving by backtracking search optimization algorithm

作　　者：王超[1,2] 高扬 刘超[1] 王明刚[2,3] WANG Chao;GAO Yang;LIU Chao;WANG Minggang(School of Economics and Management,Beijing University of Technology,Beijing 100124,China;Departments of Physics,Boston University,Boston 02215,USA;School of Mathematical Science,Nanjing Normal University,Nanjing 210042,China)

机构地区：[1]北京工业大学经济与管理学院,北京100124 [2]波士顿大学物理系,波士顿美国02215 [3]南京师范大学数学科学学院,江苏南京210042

出　　处：《计算机集成制造系统》2019年第9期2237-2247,共11页Computer Integrated Manufacturing Systems

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

摘　　要：为了求解带时间窗和同时送取货的车辆路径问题(VRPSDPTW),首次设计了回溯搜索优化算法(BSA)求解该问题。使用随机选择法、最近邻居法、最远者优先法、剩余承载力和径向附加费节约算法产生初始种群。然后在BSA算法框架下,在交叉和变异操作中使用6种路径间搜索算子和4种路径内搜索算子更新当前局部最优解。选取文献[1]测试数据集中的6个算例,将BSA算法的计算结果与文献中已知的遗传算法、并行模拟退火算法和离散布谷鸟算法的结果进行比较,对算法性能进行测试。BSA算法获得了2个已知国际最好解,并更新了1个已知国际最好解。Friedman检验显示,在α=0.1%的显著性水平下,这4种算法不存在显著性差异。因此,所提出的BSA算法是求解VRPSDPTW的有效算法。To solve the Vehicle Routing Problem with Simultaneous Delivery-Pickup and Time Windows(VRPSDPTW)problem,the Backtracking Search optimization Algorithm(BSA)was applied.The initial population was created by randomly selection algorithm,nearest neighbor insertion algorithm,farthest first algorithm and Residual Capacity&Radical Surcharge(RCRS)algorithm.Based on the framework of backtracking search optimization algorithm,6 types of inter-route improvement strategies and 4 types of intra-route improvement strategies were used to update the current best local solution in the process of mutation and crossover.The benchmark instance from ref[1]were used and the performance of BSA had been compared with genetic algorithm,parallel-simulated annealing and discrete cuckoo search.Computational results showed that BSA obtained 3 best known solutions to 6 instances,including 1 new best solution.The Friedman test revealed that there was no significant difference between these four algorithms with a significance level of,thus the effectiveness of BSA for VRPSDP problem was proved.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]