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

Abstract: 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.

Key words: reverse logistics, vehicle routing problem, simultaneous delivery and pickup, time windows, backtracking search optimization algorithm