需求可分割的容量限制弧路径问题的启发式算法研究

发布时间：2017-07-14 13:11

  本文关键词：需求可分割的容量限制弧路径问题的启发式算法研究

  更多相关文章： 容量约束弧路径问题 需求可分割 并行计算 进化算法 局部搜索

【摘要】：弧路径问题是一类运筹学邻域的组合优化问题,由于其在运输业,物流配送上的广泛应用而备受研究者的关注.在本文中,我们主要研究容量约束弧路径问题和需求可分割的容量约束弧路径问题,它们在邮递送货,城市垃圾回收,城市冬季供暖等方面有着非常广泛的现实应用.在容量约束弧路径问题的研究中,文中主要在现有的求解算法基础上进行构造与优化,并将并行计算应用在竞争模因算法的求解过程中,得到了并行的进化算法,在测试集上的测试表明,算法可行有效且能够节省大量时间.在需求可分割问题的研究中,文中通过需求可分割的容量约束弧路径问题与容量约束弧路径问题间的关系,提出了一种过渡模型,通过这种过渡模型对问题进行求解,从而得出了用于求解需求可分割的容量约束弧路径问题的交叉迭代算法,在CARP问题的63个基准数据集上的求解表明,算法可在有效时间内得出所有的最好解,并且,与CARP相比,算法在3个问题上得到了更好解.
【关键词】：容量约束弧路径问题 需求可分割 并行计算 进化算法 局部搜索
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224
【目录】：

• 摘要4-5
• ABSTRACT5-8
• 第一章 绪论8-13
• 1.1 问题提出及研究意义8-9
• 1.2 国内外研究现状9-11
• 1.3 本文思路与文章结构11-13
• 1.3.1 研究思路11
• 1.3.2 研究方法11-12
• 1.3.3 文章结构12-13
• 第二章 容量限制约束弧路径问题13-30
• 2.1 问题描述13-14
• 2.2 常用求解算法14-17
• 2.2.1 局部搜索算法14-16
• 2.2.2 竞争模因算法16-17
• 2.3 求解CARP的竞争模因算法构造17-21
• 2.3.1 初始解构造18-19
• 2.3.2 遗传与进化19-20
• 2.3.3 局部搜索20
• 2.3.4 算法整体结构20-21
• 2.4 数值实验21-29
• 2.4.1 实验结果与分析21-24
• 2.4.2 并行计算在CARP上的应用24
• 2.4.3 并行计算在进化算法上的可行性分析24-25
• 2.4.4 并行进化算法25-27
• 2.4.5 PEA算法数值实验27-29
• 2.5 小结29-30
• 第三章 需求可分割容量约束弧路径问题30-45
• 3.1 问题描述30-33
• 3.1.1 与CARP相比的优势31-32
• 3.1.2 求解思路32-33
• 3.2 求解SDCARP算法构造33-40
• 3.2.1 松约束的初始解构造34-35
• 3.2.2 对解进行调整已满足约束35-37
• 3.2.3 通过个体交叉形成新的起始解37-38
• 3.2.4 求解SDCARP的CO-ILS算法整体框架38-40
• 3.3 数值实验40-45
• 3.3.1 问题编码与参数设定40
• 3.3.2 实验结果40-44
• 3.3.3 结果分析44-45
• 第四章 总结与展望45-47
• 4.1 总结45
• 4.2 展望45-47
• 参考文献47-50
• 发表论文和参加科研情况说明50-51
• 致谢51-52

【相似文献】

中国期刊全文数据库 前10条

1 刘洁;何彦锋;;城市垃圾收集车辆弧路径问题研究[J];成都大学学报(自然科学版);2013年04期

2 王焕雄;;一类双权网络的最优路径问题[J];吉林化工学院学报;1988年01期

3 朱晨波;叶耀华;戴锡;;直接配送的三层随机库存路径问题[J];系统工程理论与实践;2007年12期

4 魏航;李军;蒲云;;时变条件下有害物品运输的路径问题研究[J];系统工程理论与实践;2006年10期

5 党兰学;陈小潘;孔云峰;;校车路径问题模型及算法研究进展[J];河南大学学报(自然科学版);2013年06期

6 邱素华;Hybrid数在系统网络中的应用[J];控制与决策;1989年01期

7 王莺;李军;;基于零售商系统的存贮路径问题研究[J];统计与决策;2008年11期

8 刘丞;乔金友;金鑫;;基于蚁群算法的通勤车路径问题优化研究[J];物流技术;2013年05期

9 宋宝和 ,姚炳学;一个路径问题的两种解法[J];济南大学学报(综合版);1991年04期

10 熊芳敏;岑宇森;曾碧卿;;运用蚁群算法解决物流中心拣货路径问题[J];华南师范大学学报(自然科学版);2010年02期

中国博士学位论文全文数据库 前5条

1 王娟;针对非确定和大规模限容量弧路径问题的近似算法[D];中国科学技术大学;2016年

2 李引珍;不确定环境下交通运输网络路径求解方法及应用研究[D];西南交通大学;2005年

3 傅成红;多周期库存路径问题及其算法研究[D];中南大学;2010年

4 党兰学;大规模混载校车路径问题优化算法研究[D];河南大学;2014年

5 赵达;随机需求库存—路径问题研究[D];西南交通大学;2012年

中国硕士学位论文全文数据库 前10条

1 陈静;基于电子商务环境下的库存—路径问题优化研究[D];华南理工大学;2015年

2 李惠;电煤海运库存—路径问题研究[D];大连海事大学;2015年

3 张涛;快递智能投递最优路径问题研究[D];成都理工大学;2015年

4 黄庆伟;带容量约束的开放式弧路径问题的算法研究[D];天津大学;2014年

5 孙锡梅;同时配送和回收需求的容量约束弧路径问题[D];天津大学;2014年

6 牛宁;改进蚁群算法求解多目标校车路径优化问题[D];河南大学;2015年

7 李薇;基于需求分类的生鲜农产品库存路径问题研究[D];吉林大学;2016年

8 张奕;多周期易腐品库存路径问题研究[D];北京交通大学;2016年

9 梁桉洋;需求可分割的容量限制弧路径问题的启发式算法研究[D];天津大学;2015年

10 宋颂颂;低碳化选址—路径问题优化模型研究[D];东北大学;2012年

，

本文编号：541200