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

摘要：

在经典的车辆路径优化问题的基础上,考虑顾客有同时取货和送货的需求,且每个顾客都有独立的时间窗,研究带时间窗和同时取送货的车辆路径问题(VRPSPDTW).提出模拟退火算法求解该问题,算法使用Residual capacity and radial surcharge (RCRS)算法求得初始解,通过模拟退火过程和4种局部搜索方法(路径内搜索:2-opt法和or-opt法;路径间搜索:swap/shift法和2-opt*法)进行优化,并选取Wang和Chen测试数据集中的15个算例对算法性能进行测试.测试结果表明,提出的模拟退火算法优于Wang和Chen的遗传算法,能有效地求解VRPSPDTW问题,并且可以被灵活的扩展解决其他车辆路径问题和组合优化问题.

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

所属期刊栏目：26

分类号：O221.1;U116.2(运筹学)

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

在线出版日期：2014-12-04（万方平台首次上网日期，不代表论文的发表时间）

页码：2618-2623