论文部分内容阅读
在物流运输中,车辆路径问题具有广泛的现实基础和经济应用价值,多年来一直是物流学术界研究的热点之一。在众多分支当中,带能力约束的车辆路径问题是车辆路径问题中最为常见和重要的问题之一。实际运输物品当中存在许多易碎、易损品,这类商品对装箱要求高,这就涉及到二维装箱问题。因此,在运输过程中,二维装箱和车辆路径需要同时考虑,即产生带二维装箱约束的车辆路径问题,二维装箱和车辆路径结合将提高实际运输的效果与效率。与此同时,物流活动对环境的污染问题日益突出,推进现代物流降低运输成本、节约能源、降低污染是提高物流效率的迫切需要。因此,本文研究考虑能耗的二维装箱车辆路径问题具有较强的理论和现实意义。针对单配送中心、多车辆、多客户、多物品装箱的物流网络优化,本文研究两类优化问题:(1)未考虑能耗的二维装箱车辆路径优化问题,建立以行驶距离最小化为目标的Model Ⅰ;(2)考虑能耗的二维装箱车辆路径优化问题,建立以能耗最小化为目标的Model Ⅱ。模型确定最优的车辆行驶方案以及物品装箱方案。考虑能耗的二维装箱车辆路径问题是在能耗的基础上,将路径的选择和装箱的安排集成优化,更符合绿色物流的发展趋势。针对两个优化模型的求解,本文将基于最底最左填充算法(Bottom Left Fill,BLF)的局部搜索算法(Local Search,LS)和基于贪心算法的微粒群算法(Particle Swarm Optimization,PSO)结合,给出PSO-LS算法,提出将问题分解成二维装箱优化问题和车辆路径优化问题这两个子问题进行求解。PSO-LS算法分为两个层次:(1)针对车辆路径优化问题,设计了基于贪心算法的微粒群算法进行求解,得出每辆车的行驶路径,其中采用贪心算法对不满足车辆最大载重量约束的车辆路径方案进行调整;(2)针对二维装箱优化问题,设计了基于最底最左填充算法的局部搜索算法进行求解,得出每辆车的装箱方案,其中采用最底最左填充算法寻找物品摆放位置。该混合算法是在微粒群算法中嵌套局部搜索算法,以得出车辆的行驶路径和装箱方案。通过Model Ⅰ与Model Ⅱ的仿真实验,结果表明Model Ⅱ的行驶距离虽然更长,但是节约了油耗,具有更好的节油潜力,更能降低对环境的污染。PSO-LS算法求解考虑能耗的二维装箱车辆路径优化模型是有效的。