详情

原文传递多点互运的车辆路径问题研究

论文题名：	多点互运的车辆路径问题研究
关键词：	车辆路径问题;产品运输;多点互运机制;数学模型;启发式算法
摘要：	本论文对传统的VRP问题进行拓展，供应点和需求点之间的匹配及其运量未预先给定，而是与路径一样作为决策变量。此类VRP问题在有原材料和产品互运的多点生产系统中比较常见，可定义为多点互运车辆路径问题。根据产品种类数量多少，可进一步将此问题分为复杂度各异的两个子问题，本文为每个子问题建立相应的数学模型，并提出求解算法。具体而言，本文主要的创新性工作总结如下：　　一是建立单产品模式下的多点互运车辆路径问题数学模型。在该模型中不仅考虑车辆运输成本，同时也考虑产品变动生产成本。该问题是NP难题，优化软件CPLEX只能求解小规模的此类问题。针对该模型，提出了快速有效的禁忌搜索算法，通过拉格朗日松弛算法和改进的Dijkstra算法求得该问题解的下界。最后采用随机生成的算例测试，确认拉格朗日松弛算法得出的下界是紧的，且禁忌搜索算法可以为大规模的算例求得满意的结果。　　二是建立多产品模式下的多点互运车辆路径问题数学模型。在该模型中，允许车辆多次对客户开展取货或送货服务，而送货或取货的地点和产品数量是未预知的。针对该模型，首先提出易于操作的启发式方法快速获得可行的初始方案；然后基于变邻域搜索算法提出6类邻域结构，改进和优化初始解；最后，算例测试结果验证了变邻域搜索算法能在合理的运算时间内获得最优或近似最优的解决方案。　　三是建立基于产品单元化的多点互运车辆路径问题数学模型。采用单元化供需产品数量方法消除供需匹配和车辆路径的耦合关系。针对该模型，以命题形式分析了8个最优解特性，并提出8类有效不等式。最后，CPLEX基于分支定界方法计算了Hennig et al.（2012b）中同等规模算例，测算结果验证了产品单元化方法以及这些特性和有效不等式能有助于更快求解问题。　　四是结合产品单元化方法，提出基于变邻域搜索的启发式算法求解更大规模问题。为了获得更好的解，在进行扰动操作后，采用基于改进最短路径法的局域搜索方法进一步改善每个邻域解。在线路延伸计算时，充分利用所得的最优解性质来减少节点数，并在节点标签更替控制条件中增加车容积和车辆工作时间因素来减少标签数量，加快计算速度。
作者：	陈青丰
专业：	管理科学与工程
导师：	刘志学;李昆鹏
授予学位：	博士
授予学位单位：	华中科技大学
学位年度：	2014
正文语种：	中文