详情

原文传递复杂多行程车辆路径问题的精确算法研究

论文题名：	复杂多行程车辆路径问题的精确算法研究
关键词：	多行程车辆;路径规划;车流量模型;集合划分模型;分支定价切割算法
摘要：	本文以多行程车辆路径优化问题为主题，分别研究了七类变种问题的精确算法：带时间窗的多行程车辆路径问题（CMTVRPTW）、带时间窗及装载时间的多行程车辆路径问题（CMTVRPTW-LT）、带时间窗及行驶时间限制的多行程车辆路径问题（CMTVRPTW-LD）、带时间窗及发布日期的多行程车辆路径问题（CMTVRPTW-R）、关于无人机的多行程车辆路径问题（DRP）、带有时间窗口和仓库卸货队列的多行程车辆路径问题（MTVRPTW-UQD）以及速度具有时间依赖性的带时间窗的多行程车辆路径问题（TD-MTVRPTW）。多行程车辆路径问题是经典车辆路径问题的一种变体问题，普遍存在于仓库运货、城市垃圾运输、无人机运输等网络中。基于此问题较高的复杂度且目前精确算法很少有人研究，本文从建立车流量模型和集合划分模型、建立精确算法求解和实验论证的角度分别对这些问题深入研究。本文的研究成果如下：　　（1）CMTVRPTW：提出了弧流数学模型及基于单次行程的集合覆盖模型，进一步研究并设计了分支定价切割算法。通过在135个算例上进行实验并与Paradiso et al.（2020）对比分析，验证所提算法的准确性及高效性。　　（2）四类带时间窗的多行程车辆路径变种问题（CMTVRPTW-LT、CMTVRPTW-LD、CMTVRPTW-R和DRP）：基于求解CMTVRPTW的分支定价切割算法，针对四类变种问题不同的特征，定制了相关问题特有的分支定价切割算法。通过大量实验和对比可以发现，我们的算法分别可以求解CMTVRPTW-LT中135个算例中的81个，CMTVRPTW-LD中270个算例中的219个，CMTVRPTW-R中405个算例中的315个，DRP中220个算例中196个。通过与当前最优算法比较，所设计的算法在求解规模上要远优于前人。　　（3）CMTVRPTW-UQD：提出了弧流模型及基于单次行程的集合覆盖模型，模型中拥有两组互斥约束分别表示车辆上的行程和卸货过程中车辆不能重叠。基于此集合覆盖模型设计了分支定价切割算法。通过与CPLEX在小算例上对比实验验证了算法的准确性，在25个点及以上规模算例中，本算法可以在3个小时内精确求解出108个算例中的80个。　　（4）TD-MTVRPTW：首先建立了TD-MTVRPTW的弧流模型和基于单次行程的集合覆盖模型，定制了本问题的分支定价切割算法。在标签设置算法中设计了具有曲线特征的标签，并引入集合占优准则来判断标签的有效性。通过与CPLEX在小算例上对比实验验证了算法的准确性，本算法可以在2小时内求解出25个点及以上规模的81个算例中的71个。　　为了提升不同问题的下界，分别在集合覆盖模型中添加了适当的有效不等式。为了提升列生成过程速度，在标签设置算法中运用了状态空间松弛、启发式标签设置、标签删除及双向搜索策略等方法。同时采用替代松弛的主问题方法来减少线性主问题中的约束数量并缩减标签设置算法中搜索可行路径数量。
作者：	黄楠
专业：	管理科学与工程
导师：	秦虎
授予学位：	博士
授予学位单位：	华中科技大学
学位年度：	2021