学位论文 > 优秀研究生学位论文题录展示

考虑装箱约束的集散货物路径问题研究

作　者: 李林
导　师: 李建
学　校: 南京农业大学
专　业: 物流工程
关键词: 车辆路径问题 二维装箱约束 集散货物 迭代搜索算法 变邻域下降搜索
分类号: U492.22
类　型: 硕士论文
年　份: 2013年
下　载: 1次
引　用: 0次
阅　读: 论文下载
 

内容摘要


已有集散货物路径问题的研究主要考虑车辆的载重约束,但由于现实配送物品中,不少物品属于轻型货物,体积成为制约装载量的重要约束。若仅考虑重量约束而不考虑体积约束,将导致计划装车的货物无法放入车厢。本文针对此,研究了一类特殊的带体积约束的车辆路径问题——考虑二维体积约束的集散车辆路径问题(Vehicle routing problem of simultaneous deliveries and pickups with two-dimensional loading constraints,2L-CVRPSDP).该问题中的客户需求可简化为不同尺寸和不同重量的二维矩形,目标为在满足车辆载重和容积约束的情况下选择运输成本最小的路径。该问题可应用于轻型且不宜堆叠的货物配送中,如家电、玻璃制品及精密部件等易损、易碎物品的配送。本文建立了2L-CVRPSDP问题的数学模型,提出了解决该问题的一种改进的迭代局域搜索算法：首先使用改进的节约算法产生初始解,然后采用变邻域下降搜索改进当前解,若当前解没有改进,则采用重起和扰动策略,改变搜索方向继续迭代搜索,直到达到设定的迭代代数为止。其中,为了判断解的体积约束可行性,该算法嵌入了基于四种装配规则的二维装箱启发式算法。为了验证本文算法的有效性,首先在Iori的标准算例(用于2L-CVRP问题)的基础上,设计了2L-CVRPSDP的测试算例；通过实验确定了算法的相关参数,测试了扰动和VND对计算结果的影响；然后,测试了2L-CVRPSDP的特例2L-CVRP问题,并与相关文献比较,结果表明该算法更新了部分最好解,改进了文献最好解的平均值。进而,给出了2L-CVRPSDP的计算结果。此外,本文还应用该算法开发了一款考虑装箱约束的智能配送管理系统,实现配送路线的自动生成和优化,该系统操作简单、方便,可以根据用户需求快速的生成一种最佳配送路线方案,同时还可以把路线和箱子的装载位置直观的呈现给用户。本研究拓展了已有集散货物路径问题的研究,考虑了重量和体积的双重约束,增强了应用范围；开发的相应优化系统,能为物流配送提供重要的决策支持,进一步增强了实用性。

全文目录


摘要  6-7
ABSTRACT  7-9
第一章 绪论  9-13
  1.1 研究背景  9-10
  1.2 研究意义  10-11
  1.3 研究目标和主要内容  11-12
  1.4 研究方法和技术路线  12-13
第二章 国内外研究综述  13-23
  2.1 车辆路径问题描述  13
  2.2 车辆路径问题组成  13-14
  2.3 车辆路径问题的分类  14-15
  2.4 车辆路径问题(VRP)研究综述  15-23
    2.4.1 集散货物路径问题(VRPSDP)研究综述  17-19
    2.4.2 二维装箱问题(2BPP)研究综述  19-20
    2.4.3 带二维装箱约束的车辆路径问题(2L-CVRP)研究综述  20-23
第三章 车辆路径问题主要元启发式算法概述  23-29
  3.1 NP完全问题  23
  3.2 车辆路径问题主要元启发式算法介绍  23-29
    3.2.1 遗传算法  23-25
    3.2.2 蚁群算法  25-26
    3.2.3 模拟退火算法  26-27
    3.2.4 禁忌搜索算法  27
    3.2.5 迭代局域搜索算法  27-28
    3.2.6 变邻域搜索算法  28-29
第四章 2L-CVRPSDP问题模型及改进迭代算法设计  29-40
  4.1 模型的建立  29-31
    4.1.1 问题描述  29
    4.1.2 数学模型的建立  29-31
  4.2 改进迭代算法设计  31-40
    4.2.1 初始解的产生  32
    4.2.2 邻域结构设计  32-34
    4.2.3 变邻域下降搜索  34-35
    4.2.4 重起和扰动算子的设计  35
    4.2.5 二维装箱约束算法的设计  35-40
第五章 数据实验  40-51
  5.1 数据来源  40
  5.2 2L-CVRPSDP测试算例特征  40-42
  5.3 参数设置  42-45
  5.4 2L-CVRP数据实验  45-47
  5.5 2L-CVRPSDP数据实验  47-48
  5.6 2L-CVRPSDP算例验证分析  48-51
第六章 系统开发  51-59
  6.1 系统开发工具简要介绍  51
  6.2 系统分析  51-53
    6.2.1 系统结构层次分析  51-52
    6.2.2 系统需求分析  52
    6.2.3 系统基本流程分析  52-53
  6.3 系统功能实现  53-59
第七章 总结与展望  59-60
  7.1 研究工作总结  59
  7.2 研究展望  59-60
参考文献  60-63
致谢  63-64
攻读学位期间已发表的论文  64

相似论文

  1. 规模动态增长的车辆路径优化问题,U116.2
  2. 基于克隆免疫算法的应急物流车辆路径模型的研究,U116.2
  3. 基于DDE_VND算法的同等并行机调度问题的研究,TH186
  4. 基于磁滞优化的车辆路径问题研究,O224
  5. 带软时间窗和同时取送货的车辆路径问题研究,TP18;O242.1
  6. 基于改进遗传算法的物流配送路径优化研究,U116.2
  7. 大规模实时动态车辆路径问题研究,F224
  8. 非限定车场车辆路径问题研究,TP18
  9. 基于Web的免费机场接送服务系统的初步设计与实现,TP311.52
  10. 遗传算法在多车场车辆路径问题中的应用研究,TP18
  11. 基于遗传算法的物流配送车辆路径问题研究,TP18
  12. 物流配送中车辆路径问题的多目标优化算法研究,TP301.6
  13. 电力操作队最优运维策略的研究,TM711
  14. 环东物流公司配送问题的算法研究与应用,TP18
  15. 军事物流配送路径优化问题研究,E075
  16. 遗传算法和模拟退火算法在车辆线路问题上的研究及应用,TP18
  17. 车辆路径问题的量子进化算法研究,TP18
  18. 遗传算法及其在物流路径优化中的应用研究,TP18
  19. 蚁群算法在有时间窗的VRP问题中的应用研究,TP301.6
  20. 遗传算法在组合优化中的应用研究,TP18
  21. 城市应急物流中多目标车辆路径问题研究,F224

中图分类: > 交通运输 > 公路运输 > 交通工程与公路运输技术管理 > 运营技术 > 行车组织 > 车辆调度与运行管理
© 2012 www.xueweilunwen.com