【作者】 张琳；

【导师】 刘虹；

【作者基本信息】 福州大学 ， 管理科学与工程， 2015， 硕士

【摘要】 在物流运输中,车辆路径问题具有广泛的现实基础和经济应用价值,多年来一直是物流学术界研究的热点之一。在众多分支当中,带能力约束的车辆路径问题是车辆路径问题中最为常见和重要的问题之一。实际运输物品当中存在许多易碎、易损品,这类商品对装箱要求高,这就涉及到二维装箱问题。因此,在运输过程中,二维装箱和车辆路径需要同时考虑,即产生带二维装箱约束的车辆路径问题,二维装箱和车辆路径结合将提高实际运输的效果与效率。与此同时,物流活动对环境的污染问题日益突出,推进现代物流降低运输成本、节约能源、降低污染是提高物流效率的迫切需要。因此,本文研究考虑能耗的二维装箱车辆路径问题具有较强的理论和现实意义。针对单配送中心、多车辆、多客户、多物品装箱的物流网络优化,本文研究两类优化问题:(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算法求解考虑能耗的二维装箱车辆路径优化模型是有效的。更多还原

【Abstract】 During the transportation of logistics,Vehicle Routing Problem possesses wide practical foundation and the value of economical application.Over the years,it has been one of research hotspots in logistics academia.In many branches,capacitated vehicle routing problem is one of the most common and important problem in VRP.In the actual transportation,the items demanded by customers are usually fragile,which has high requirement when packed into vehicles.This is called Two-Dimensional Container Loading Problem.Therefore,this is a new problem that combine the two classical problems of vehicle routing problem and two-dimensional container loading problem,called Vehicle Routing Problem with Two-Dimensional Loading Constraints,to improve the efficiency and effect of transportation.Moreover,the environmental pollution caused by logistics activities has been increasingly prominent.Promoting modern logistics to reduce transportation costs,save energy,reduce pollution is an urgent need to improve the efficiency of logistics.Therefore,2L-CVRP considering the fuel consumption has the theoretical value and practical significance.For distribution network with one distribution center,multiple vehicles,multiple customers,multiple items loading,two kinds of optimization problems were put forward,one with 2L-CVRP,and established a Model I taking distance as an object,the other with 2L-CVRP considering the fuel consumption,and established a Model Ⅱtaking fuel consumption as an object.The models determine the optimal vehicle driving scheme and goods packing plan.The selection of path and the arrangement of loading are integrated to optimize considering the influence of fuel consumption,which conforms the trend of environmental logistics.For the solving of the two optimization model,this paper designs Particle Swarm Optimization algorithm nested Local Search,and solve it by broking them down into two sub-problems of two-dimensional container loading optimization problem and vehicle routing optimization problem.PSO-LS include two parts.For vehicle routing optimization problem,this paper has designed the PSO based on Greedy Algorithm,to determine the path of vehicles,using Greedy Algorithm to deal with the constraints of capacity.For two-dimensional container loading optimization problem,this paper has designed the LS based on Bottom-Left-Fill Algorithm,to determine the scheme of loading,using BLF to judge the feasibility of loading.The experimental results show the distance of Model II is a little longer than that of Model I,but it saves the fuel consumption,which not only has the fuel saving potential but also reduces the pollution of the environment.In addition,the convergence speed of PSO-LS is fast in the process of solving problem.更多还原