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

发布时间：2018-03-12 07:18

  本文选题：车辆路径　切入点：模拟退火算法　出处：《系统仿真学报》2014年11期 　论文类型：期刊论文

【摘要】：在经典的车辆路径优化问题的基础上,考虑顾客有同时取货和送货的需求,且每个顾客都有独立的时间窗,研究带时间窗和同时取送货的车辆路径问题(VRPSPDTW)。提出模拟退火算法求解该问题,算法使用Residual capacity and radial surcharge(RCRS)算法求得初始解,通过模拟退火过程和4种局部搜索方法(路径内搜索:2-opt法和or-opt法;路径间搜索:swap/shift法和2-opt*法)进行优化,并选取Wang和Chen测试数据集中的15个算例对算法性能进行测试。测试结果表明,提出的模拟退火算法优于Wang和Chen的遗传算法,能有效地求解VRPSPDTW问题,并且可以被灵活的扩展解决其他车辆路径问题和组合优化问题。
[Abstract]:On the basis of the classical vehicle routing optimization problem, we consider that customers have the need to pick up goods and deliver goods at the same time, and each customer has an independent time window. The vehicle routing problem with time window and delivery at the same time is studied. A simulated annealing algorithm is proposed to solve the problem. The initial solution is obtained by using the Residual capacity and radial surcharge algorithm. By simulated annealing process and four local search methods (in-path search: 2-opt method and or-opt method; inter-path search method: W swap-shift method and 2-opt * method), Fifteen examples of Wang and Chen test data sets are selected to test the performance of the algorithm. The test results show that the proposed simulated annealing algorithm is superior to the genetic algorithm of Wang and Chen and can effectively solve the VRPSPDTW problem. And can be flexibly extended to solve other vehicle routing problems and combinatorial optimization problems.
【作者单位】： 北京交通大学经济管理学院;
【基金】：国家自然科学基金重点资助项目(71132008);国家自然科学基金面上项目(71473013) 国家留学基金委公派访学项目(201207090034) 中央高校基本科研业务专项基金(2012YJS034);
【分类号】：U492.22

【共引文献】

相关期刊论文 前10条

1 于航;张凯;;基于节约里程法的鲜活农产品物流配送车辆路线的最优设计[J];安徽农业科学;2011年28期

2 路玉龙;赵扶摇;韩靖;张鸿雁;;城市生活垃圾收运路线优化的数学模型与算法[J];环境科学与管理;2010年06期

3 徐新明;陈培友;;物流调度问题的优化方法评述[J];商业研究;2009年05期

4 杨瑞臣;郝海燕;;改进的蚁群算法在物流配送路径问题求解中的应用[J];承德石油高等专科学校学报;2009年02期

5 刘士新;刘玲;张涛;;求解VRPBTW的变邻域搜索算法[J];东北大学学报(自然科学版);2008年03期

6 廖洁君,陈燕;城市物流中多目标配送模型[J];大连海事大学学报;2004年04期

7 王发鸿;达庆利;;逆向物流单车辆运输策略[J];东南大学学报(自然科学版);2006年01期

8 李建;达庆利;;逆向需求模糊的多车辆集散货物路线问题(英文)[J];Journal of Southeast University(English Edition);2008年02期

9 戴香粮;王映龙;;混合启发式算法在汽车调度中的应用[J];电子技术应用;2009年07期

10 陈诚;邱荣祖;;求解双向物流配送路径问题的改进遗传算法[J];福建农林大学学报(自然科学版);2010年05期

相关会议论文 前8条

1 何世伟;宋瑞;鲁放;杨永凯;;不确定性群组决策优化模型及其在交通运输领域中的应用研究[A];第四届中国青年运筹与管理学者大会论文集[C];2001年

2 钱贤伟;王梦光;;基于VRP模型的热轧生产批量计划及禁忌搜索算法[A];1998中国控制与决策学术年会论文集[C];1998年

3 ;A hybrid genetic algorithm for the vehicle routing problem with simultaneous pickup and delivery[A];2009中国控制与决策会议论文集（3）[C];2009年

4 ;Solving Capacitated Vehicle Routing Problem Based on Improved Genetic Algorithm[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

5 ;A TWO-PHASE HEURISTIC ALGORITHM TO SOLVE THE LARGE-SCALE VEHICLE ROUTING PROBLEM[A];2006年中国机械工程学会年会暨中国工程院机械与运载工程学部首届年会论文集[C];2006年

6 王际洲;;烟草物流配送中若干优化问题研究[A];中国烟草学会2009年年会论文集[C];2009年

7 张建勇;李军;;具有同时的配送和回收需求的逆向物流VRP研究[A];第八届中国管理科学学术年会论文集[C];2006年

8 饶卫振;金淳;蒙秋男;;城区低碳物流配送问题模型及求解策略[A];社会经济发展转型与系统工程——中国系统工程学会第17届学术年会论文集[C];2012年

相关硕士学位论文 前10条

1 蔡翱鹏;遗传算法在动态车辆调度问题中的研究[D];长沙理工大学;2010年

2 田野;东北化工销售公司石化产品运输配送优化研究[D];大连海事大学;2010年

3 邓毅;第三方物流终端配送信息系统构建的研究[D];华南理工大学;2010年

4 赵再兴;基于改进和声搜索算法的车辆路径规划问题[D];沈阳大学;2011年

5 赵思敏;粮食应急物流系统的网络构建及路径优化[D];武汉理工大学;2011年

6 任中明;运输调度问题的智能求解机制研究[D];广东工业大学;2011年

7 叶宝林;分布估计算法的一种改进与应用[D];太原科技大学;2011年

8 刘坤;人工植物优化算法混合策略的研究及应用[D];太原科技大学;2011年

9 田宇;基于系统仿真模拟退火算法的VRPTW研究[D];河北工程大学;2011年

10 赵斐;基于GA-ACO的港口集卡路径优化研究[D];河北工程大学;2011年

【二级参考文献】

相关期刊论文 前4条

1 谢如鹤,刘霆,邱祝强;基于剩余装载能力的逆向物流车辆路径问题[J];系统工程;2004年10期

2 顾志康,李旭宏,徐家兵;一种改进遗传算法在物流配送车辆调度中的应用研究[J];公路交通科技;2004年11期

3 冯辉宗,陈勇,刘飞;基于遗传算法的配送车辆优化调度[J];计算机集成制造系统;2004年S1期

4 肖健梅,李军军,王锡淮;求解车辆路径问题的改进微粒群优化算法[J];计算机集成制造系统;2005年04期

，

本文编号：1600541