基于模拟退火算法求解VRPSPDTW问题  

Solving VRPSPDTW Problem Using Simulated Annealing Algorithm

作　　者：王超[1] 穆东[1] 

机构地区：[1]北京交通大学经济管理学院,北京100044

出　　处：《系统仿真学报》2014年第11期2618-2623,共6页Journal of System Simulation

基　　金：国家自然科学基金重点资助项目(71132008);国家自然科学基金面上项目(71473013);国家留学基金委公派访学项目(201207090034);中央高校基本科研业务专项基金(2012YJS034)

摘　　要：在经典的车辆路径优化问题的基础上,考虑顾客有同时取货和送货的需求,且每个顾客都有独立的时间窗,研究带时间窗和同时取送货的车辆路径问题(VRPSPDTW)。提出模拟退火算法求解该问题,算法使用Residual capacity and radial surcharge(RCRS)算法求得初始解,通过模拟退火过程和4种局部搜索方法(路径内搜索:2-opt法和or-opt法;路径间搜索:swap/shift法和2-opt*法)进行优化,并选取Wang和Chen测试数据集中的15个算例对算法性能进行测试。测试结果表明,提出的模拟退火算法优于Wang和Chen的遗传算法,能有效地求解VRPSPDTW问题,并且可以被灵活的扩展解决其他车辆路径问题和组合优化问题。A variant of classic vehicle routing problem in which customers require simultaneous pickup and delivery goods during specific individual time windows （VRPSPDTW） was addressed. A simulated annealing algorithm （SAA） was proposed for solving this problem. In the algorithm, the initial solution was calculated by Residual capacity and radial surcharge （RCRS） heuristic and improved by simulated annealing process combined with four types of moves in the local search, which are 2-opt move and or-opt move for intra-route exchange, swap/shift move and 2-opt＊ move for inter-route exchange, and then it was tested in a set of 15 test problems from Wang and Chen＇s benchmark. Computational results show that the proposed SAA is better than Wang and Chen＇s genetic algorithm （GA）, could solve VRPSPDTW effectively and could be extended to handle other variants of vehicle routing problems and other combinatorial optimization problems.

关 键 词：车辆路径 模拟退火算法 同时取送货 时间窗 

分 类 号：O221.1[理学—运筹学与控制论] U116.2[理学—数学]