原文传递
多车型绿色车辆路径问题的分支定价算法
| 论文题名： | 多车型绿色车辆路径问题的分支定价算法 |
| 关键词： | 多车型;绿色车辆路径问题;分支定价;精确算法 |
| 摘要： | 空气污染对地球环境所造成的负面影响与日俱增，其中交通运输所带来的尾气排放占很大比例。为了减轻交通运输活动对环境造成的不良影响，提出了绿色车辆路径问题(Greenvehicleroutingproblem，GVRP)。如何在满足客户需求并充分考虑到各项限制的条件下尽可能地降低碳排放量是GVRP研究的重点。在实际运输过程中，并不仅仅采用单一车型，因此多车型GVRP（HeterogeneousfleetGVRP，HFGVRP）研究便应运而生。在多车型条件下，使用不同类型的车辆对客户进行服务，既避免了车辆容量资源浪费的问题，也能有效减少运输过程中的碳排放。截至目前，所有HFGVRP研究都是基于启发式算法或元启发式算法，仍然没有开发出相应的精确算法。 本文针对多车型条件下带时间窗约束的绿色车辆路径问题（HFGVRPwithtimewindows，HFGVRPTW）的精确算法展开相关研究，目的是开发出求解一定规模HFGVRPTW的分支定价算法，本研究对GVRP领域进行了拓展和丰富。主要研究内容如下: (1)开发了求解HFGVRPTW的分支定价算法。并通过计算实验，分析了多车型和单车型在相同实例下碳排放和使用车辆数的差异。 (2)针对HFGVRPTW分支定价算法中子问题求解效率较低的缺点，提出了多车型近似动态规划算法（英文全称，MVADP）。该算法将多车型条件下的子问题求解由多次整合为一次，有效减少了求解过程中的计算次数和计算时间。 (3)改进了HFGVRPTW分支定价算法中上界收敛速度慢的缺点，提出了整数分支方法。该方法通过将当前分支节点求解的列导入到集划分模型中，利用CPLEX求解整数解。一旦该整数解小于上界，就对上界进行更新，从而加快上界的收敛并减少分支数和计算时间。 (4)最后使用改进后的分支定价算法对大量benchmark实例进行求解。结果表明该改进算法能有效地求解中小规模实例。 |
| 作者： | 王思寒 |
| 专业： | 系统工程 |
| 导师： | 于洋 |
| 授予学位： | 硕士 |
| 授予学位单位： | 东北大学 |
| 学位年度： | 2018 |
检索历史
应用推荐
