首页> 正文

带时间窗车辆路径问题的分支—切割—定价算法研究

2020-12-02阅读(1048)

带时间窗车辆路径问题的分支—切割—定价算法研究

论文摘要

带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）作为物流行业中最常见的组合优化问题之一,其模型结构及算法都具有普遍性和拓展性。通过特定的转化与变形,VRPTW的模型及算法同样也适用于其他大多数的组合优化场景,公交线路规划、港口设备协同调度等资源分配问题都与其有着相似的数学结构。因此,对车辆路径问题的研究同样有助于推动其他相关领域的发展,如何有效提升该问题的求解效率对物流行业的发展有直接且重大的影响。本文将以精确算法作为研究方向,对VRPTW进行较为全面的理论探究。目前针对VRPTW精确算法的研究主要分为两个方向:整数规划以及动态规划。因VRPTW的求解属于强NP-hard问题,大多数学者更倾向于选择可在伪多项式时间内完成求解的动态规划来进行探究。而动态规划所求得的最优解的理论下界质量较差。且在时间窗约束较宽的情况下,其求解性能并不优于整数规划。相比之下,整数规划则更加灵活,它可以通过合并分支决策或加入有效不等式来实现高效求解。因此,本文将以整数规划为理论基础,对VRPTW进行算法优化。主要提出并实现的创新点及研究成果如下:（1）完成了结合列生成以及割平面的分支-切割-定价的算法框架搭建,并对原始二维车流模型中的子回路约束加以改进,使其适用于VRPTW。在算法后期引入改进后的二维车流模型来代替原有的分支过程。在其基础上猜测了最小车辆数量K的上界,目前本文完成的所有实验均证实了该猜想。（2）创新性地提出了两点及三点加强广义割集不等式,并证明其均为满足小平面定义（facet-defining）的不等式。虽然VRPTW作为经典的组合优化问题拥有很长的研究历史,但其子问题:带资源约束的最短路径问题（Elementary Shortest Path Problem with Resource Constraints,ESPPRC）方面的探究则少之又少。仅有的以整数线性规划为基础的理论研究也都是将旅行商问题的经典不等式加以变形后应用于ESPPRC。本文正面探究了ESPPRC的多胞形结构,并提出了两组适用于ESPPRC的有效不等式。（3）针对有效不等式加入策略的问题,本文以排列组合的形式尝试了所有两点及三点加强割集不等式的组合实验。最终确定以割平面回调的形式将三点割集不等式加入到子问题分支定界树的根节点上,完成了ESPPRC以及VRPTW的实验测试,并验证了割集不等式的有效性,改进后的模型性能得到显著提升。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  •   1.1 研究背景及意义
  •     1.1.1 研究背景
  •     1.1.2 研究意义
  •   1.2 课题来源
  •   1.3 国内外研究现状
  •     1.3.1 车辆路径问题研究
  •     1.3.2 带时间窗的车辆路径问题研究
  •   1.4 研究内容及结构安排
  • 第2章 相关理论及技术
  •   2.1 多面体理论
  •     2.1.1 仿射集
  •     2.1.2 多面体及小平面
  •   2.2 最短路径问题
  •   2.3 带时间窗的车辆路径问题描述
  •     2.3.1 问题定义与假设
  •     2.3.2 数学描述
  •   2.4 整数线性规划
  •     2.4.1 分支定界
  •     2.4.2 列生成
  •     2.4.3 割平面
  •   2.5 基于三维多商品网络流的数学模型
  •   2.6 基于路径不等式的数学模型
  •   2.7 本章小结
  • 第3章 带时间窗车辆路径问题的模型研究
  •   3.1 基于集合划分的数学模型
  •     3.1.1 主问题
  •     3.1.2 子问题
  •   3.2 基于二维车流的数学模型
  •   3.3 本章小结
  • 第4章 带资源约束的基本最短路问题
  •   4.1 ESPPRC问题描述与数学模型
  •     4.1.1 问题描述
  •     4.1.2 数学模型
  •   4.2 统治规则
  •     4.2.1 动态规划的统治规则
  •     4.2.2 整数规划的统治规则
  •   4.3 多面体理论分析
  •     4.3.1 两点加强割集不等式
  •     4.3.2 三点加强割集不等式
  •   4.4 有效不等式
  •     4.4.1 点边不等式
  •     4.4.2 时间前后不等式
  •     4.4.3 顺序前后不等式
  •   4.5 本章小结
  • 第5章 实验设计与结果分析
  •   5.1 ESPPRC实验设计与结果分析
  •     5.1.1 数据来源与实验环境
  •     5.1.2 实验设置与参数说明
  •     5.1.3 结果分析
  •   5.2 VRPTW实验设计与结果分析
  •     5.2.1 数据来源与实验环境
  •     5.2.2 实验设置与参数说明
  •     5.2.3 结果分析
  •   5.3 本章小结
  • 第6章 总结与展望
  •   6.1 全文总结
  •   6.2 研究展望
  • 致谢
  • 参考文献
  • 攻读硕士期间研究成果和参与项目
  •   一、发表论文
  •   二、参与项目

    • 文章来源

    类型: 硕士论文

    作者: 王维杰

    导师: 郑澜波

    关键词: 车辆路径问题,时间窗,分支切割定价算法,割平面,多面体

    来源: 武汉理工大学

    年度: 2019

    分类: 基础科学,工程科技Ⅱ辑,经济与管理科学

    专业: 数学,汽车工业,宏观经济管理与可持续发展

    单位: 武汉理工大学

    基金: 国家自然科学基金:多时间粒度下端到端煤炭供应链增效方法研究(No.71501152)

    分类号: U463.6;F252;O224

    DOI: 10.27381/d.cnki.gwlgu.2019.001830

    总页数: 77

    文件大小: 889K

    下载量: 85

    相关论文文献

    • [1].一道动点类竞赛不等式的加强与推广[J]. 数学通报 2019(12)
    • [2].条件弱(下)鞅的一类极大值不等式[J]. 兰州理工大学学报 2020(01)
    • [3].条件弱鞅的γ型概率不等式及强大数定律[J]. 四川师范大学学报(自然科学版) 2020(03)
    • [4].哈代不等式的一个注记[J]. 大学数学 2020(01)
    • [5].基于整体建构的数学综合题型解法探究——以高中数学“函数与不等式的综合题型”为例[J]. 科学咨询(教育科研) 2020(06)
    • [6].自正则化鞅的Dzhaparidze-van Zanten型不等式[J]. 西北师范大学学报(自然科学版) 2020(04)
    • [7].数学中不等式的解法研究[J]. 现代经济信息 2017(21)
    • [8].对偶混合体积循环不等式的加强[J]. 数学的实践与认识 2018(10)
    • [9].一个不等式猜想的证明及推广[J]. 大学数学 2018(03)
    • [10].一个无理不等式猜想的推广及其证明[J]. 数学通报 2014(03)
    • [11].第七届全国不等式学术年会通知[J]. 数学通报 2014(12)
    • [12].一个平凡不等式的加强[J]. 数学通报 2015(02)
    • [13].一个优美的几何不等式[J]. 数学通报 2015(02)
    • [14].关于两道猜想不等式的深入探究[J]. 数学通报 2016(05)
    • [15].涉及三角形边长与半径不等式的简证及加强[J]. 数学通报 2018(01)
    • [16].Finsler-Hadwiger型不等式的再加强[J]. 数学通报 2018(03)
    • [17].Carulan不等式的加强[J]. 数学通报 2008(05)
    • [18].两个不等式的统一推广与应用[J]. 数学通报 2008(06)
    • [19].一个不等式的几种新证[J]. 数学通报 2008(12)
    • [20].一个不等式的推广[J]. 数学通报 2008(11)
    • [21].一个几何不等式的推广[J]. 数学通报 2008(12)
    • [22].对一道不等式的推广及证明[J]. 数学通报 2009(01)
    • [23].对一个半对称不等式的加强[J]. 数学通报 2009(01)
    • [24].对一个不等式的探究[J]. 数学通报 2009(09)
    • [25].高中课程标准下不等式性质教学内容安排的思考[J]. 数学通报 2009(12)
    • [26].一个不等式的推广及其应用[J]. 数学通报 2010(12)
    • [27].一些半对称不等式的统一简证[J]. 数学通报 2010(12)
    • [28].一类二次齐次不等式的获得方法[J]. 数学通报 2010(11)
    • [29].对不等式基本性质的教学体会及一点建议[J]. 数学通报 2010(12)
    • [30].一道不等式的推广及证明[J]. 数学通报 2011(12)

    标签：;  ;  ;  ;  ;  

    带时间窗车辆路径问题的分支—切割—定价算法研究
    下载Doc文档

    猜你喜欢

    © 2024 毕论降 版权所有 鄂ICP备12018319号-6