带时间窗的同时取送货车辆路径和三维装箱联合优化研究

作     者：何林伟 

作者单位：长安大学 

学位级别：硕士

导师姓名：胡大伟

授予年度：2023年

学科分类：08[工学] 082303[工学-交通运输规划与管理] 082302[工学-交通信息工程及控制] 0823[工学-交通运输工程] 

主      题：三维装箱 同时取送货 车辆路径问题 自适应大邻域搜索 处理成本 

摘      要：近年来,为实现提质增效降本的目标,减少车辆数、提高车辆装载率成为物流企业降低营运成本的重要手段,车辆路径和装箱联合优化问题也愈发受到关注。考虑到具有取送货特性的物流配送在现实中的普遍性,本文研究带时间窗的同时取送货车辆路径和三维装箱联合优化问题(Vehicle routing problem with simultaneous pickup and delivery with time windows and three-dimensional loading,3L-VRPSPDTW),并设计算法以实现取送货物流系统的降本增效。论文首先分析了带时间窗的同时取送货车辆路径和三维装箱相关文献,对3L-VRPSPDTW进行扩展。针对同时取送货中存在的取送物品相互阻碍问题,提出按车厢X轴垂直切割(X-Vertical space partition,XVSP)和按车厢Z轴方向垂直切割(Z-Vertical space partition,ZVSP)两种切割模式。以营运成本最小化为目标,建立了考虑处理成本的带时间窗的同时取送货车辆路径和三维装箱联合优化模型(3L-VRPSPDTW considering handling cost,3L-VRPSPDTW-H)。为贴合现实物流运作,该模型考虑了时间窗、三维装箱、送货空间后进先出、取货空间重新处理等约束。由于问题复杂性,对一维VRPSPDTW数学模型采用求解器进行求解测试。本文设计了适用求解3L-VRPSPDTW问题的路径-装箱混合算法,算法基于路径优先,装箱其次思想,在自适应大邻域搜索算法中嵌入装箱启发式算法。算例实验结果表明:自适应大邻域搜索算法求解VRPSPDTW具有较好的性能。路径-装箱混合算法求解3L-VRPSPDTW时,嵌入开放空间启发式的路径-装箱混合算法具有更好的求解性能;后进先出约束会导致车辆空间装载率显著下降,XVSP模式优于ZVSP模式,可行装载空间选择策略采用空间定物品策略更具计算效率。混合算法求解3L-VRPSPDTW-H时,重新处理操作在小、中、大规模算例上实现平均装载率46.67%、10.53%、24.14%的提升。敏感性分析表明:在取送物品比例相同下,XVSP切割以0.6-0.7为比例进行取货空间划分较好;最小支撑面积参数与空间利用率成正比。本文数学模型和算法,为带时间窗的同时取送货车辆路径和三维装箱联合优化的深入研究提供理论基础和现实参考依据。