改进蚁群算法优化周期性车辆路径问题

发布时间：2018-01-14 19:18

  本文关键词：改进蚁群算法优化周期性车辆路径问题　出处：《运筹与管理》2014年05期 　论文类型：期刊论文

  更多相关文章： 周期性车辆路径问题 蚁群算法 多维信息素 扫描法

【摘要】：周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。
[Abstract]:The periodic vehicle routing problem (PVRP) is an extension of the standard vehicle routing problem (VRP). PVRP needs to optimize the customer mix and distribution path for each delivery period. Because PVRP is an embedded VRP problem, it is more complex than the standard VRP problem. It is difficult to solve. In this paper, ant colony algorithm is used to solve PVRP, and two kinds of improvement measures are proposed to improve the performance of the algorithm: the application of multidimensional pheromone and the local optimization method based on scanning method. Nine classical PVRP examples are used to test the algorithm. The results show that the improved ant colony algorithm proposed in this paper is feasible and effective to solve the PVRP problem. At the same time, it also shows that the performance of the algorithm can be significantly improved by two kinds of improvement measures.
【作者单位】： 大连海事大学交通运输管理学院;大连理工大学机械工程学院;
【基金】：国家自然科学基金青年基金项目(51108053,51078049,51208079) 教育部新世纪人才支持计划(NCET-12-0752) 辽宁省优秀人才支持计划(LJQ2012045)
【分类号】：U492.22;TP18
【正文快照】： 0引言周期性的车辆路径问题(Period Vehicle Routing Problem,PVRP)是车辆路径问题的重要拓展。PVRP最早由Beltrami和Bodin[1]于1974年发表的会议论文上提出来的。PVRP是VRP在时间上的扩展,通常VRP解决一段时间(一天)内的路径优化问题,而PVRP是在T天里完成对客户点的服务,服务

【参考文献】

相关期刊论文 前3条

1 吴春明;陈治;姜明;;蚁群算法中系统初始化及系统参数的研究[J];电子学报;2006年08期

2 刘志硕;申金升;关伟;;车辆路径问题的混合蚁群算法设计与实现[J];管理科学学报;2007年03期

3 王晓博;李一军;;多车场多车型装卸混合车辆路径问题研究[J];控制与决策;2009年12期

【共引文献】

相关期刊论文 前10条

1 徐俊杰;;利用微正则退火算法求解车辆路径问题[J];安庆师范学院学报(自然科学版);2009年02期

2 胡中华;赵敏;;基于人工蜂群算法的TSP仿真[J];北京理工大学学报;2009年11期

3 陈文兰;戴树贵;;车辆路径安排问题算法研究综述[J];滁州学院学报;2007年03期

4 赵敏;胡中华;;一种求解机器人路径规划的智能优化算法[J];电焊机;2009年04期

5 杨盛光;李丽;高明伦;张宇昂;;面向能耗和延时的NoC映射方法[J];电子学报;2008年05期

6 苏兆品;蒋建国;梁昌勇;张国富;夏娜;;蚁群算法的几乎处处强收敛性分析[J];电子学报;2009年08期

7 张晖;董育宁;杨龙祥;朱洪波;;多媒体异构Mesh网络体系设计及跨层QoS路由算法研究[J];电子学报;2010年10期

8 孙伟峰;覃振权;李明楚;胡晶;陈媛芳;;QIACO:一种多QoS约束网格任务调度算法[J];电子学报;2011年05期

9 易伟;王佳文;潘红兵;李丽;;基于蚁群混沌遗传算法的片上网络映射[J];电子学报;2011年08期

10 刘衍珩;张婧;王健;;TrANTHOCNET:信任性蚁群自组织路由算法[J];电子学报;2012年02期

相关会议论文 前2条

1 赵刚;陈文兵;;用蚁群算法求解不定期船调度问题[A];第二十六届中国控制会议论文集[C];2007年

2 孙琳;刘惠义;徐建忠;;蚁群算法在军用车辆路径规划中的应用[A];第六届全国信号和智能信息处理与应用学术会议论文集[C];2012年

相关硕士学位论文 前10条

1 耿东山;基于蚁群算法的机器人全局路径规划[D];郑州大学;2010年

2 张文静;协同粒子群算法及其在多车场路径优化问题中的应用[D];华东师范大学;2011年

3 高俊红;110出警线路优化系统的设计与实现[D];电子科技大学;2010年

4 王肖楠;高可靠性的容错组播路由算法研究[D];解放军信息工程大学;2010年

5 徐欣;片上网络路由算法和映射算法研究[D];西安电子科技大学;2010年

6 李佳;公路旅行最佳换乘咨询系统研究与实现[D];沈阳工业大学;2011年

7 欧阳涛;物流车辆路径问题算法研究[D];吉林大学;2011年

8 李超峰;QoS路由算法及在PTN网管中应用研究[D];武汉理工大学;2011年

9 易伟;计算系统的并行化和映射问题研究[D];南京大学;2011年

10 赵金亮;基于自适应遗传算法和蚁群算法融合的配电网重构[D];兰州理工大学;2011年

【二级参考文献】

相关期刊论文 前6条

1 郎茂祥,胡思继;车辆路径问题的禁忌搜索算法研究[J];管理工程学报;2004年01期

2 邱模杰,马 良;约束平面选址问题的蚂蚁算法[J];上海理工大学学报;2000年03期

3 崔雪丽,马良;有缺货限制的VRP蚂蚁算法研究[J];上海理工大学学报;2003年01期

4 马良,项培军;蚂蚁算法在组合优化中的应用[J];管理科学学报;2001年02期

5 马良;基于蚂蚁算法的函数优化[J];控制与决策;2002年S1期

6 温文波,杜维;蚁群算法概述[J];石油化工自动化;2002年01期

【相似文献】

相关期刊论文 前10条

1 曹二保;赖明勇;张汉江;;模糊需求车辆路径问题研究[J];系统工程;2007年11期

2 唐连生;梁剑;;突发事件下的车辆路径问题研究综述[J];铁道运输与经济;2008年12期

3 刘红梅;陈杨;;车辆路径问题的形式化方法研究[J];科技资讯;2008年05期

4 徐俊杰;;利用微正则退火算法求解车辆路径问题[J];安庆师范学院学报(自然科学版);2009年02期

5 宁晓利;;车辆路径问题的组合优化算法[J];物流技术;2009年06期

6 黄敏芳;胡祥培;王征;Amy Z. Zeng;;车辆路径问题的三阶段求解方法研究[J];管理科学;2009年03期

7 孙中悦;关忠良;范高贤;;面向对象的车辆路径问题仿真研究[J];物流技术;2010年07期

8 李琳;刘涛;;带收益的车辆路径问题研究综述[J];沈阳航空工业学院学报;2010年05期

9 王科峰;叶春明;唐国春;;节点具有双重需求的车辆路径问题及其性质[J];系统科学与数学;2011年10期

10 谢秉磊;胡小明;张一U，

本文编号：1424954