【作者】 侯丽晓；

【导师】 靳志宏；

【作者基本信息】 大连海事大学 ， 物流工程与管理， 2010， 硕士

【摘要】 随着物流在社会中的地位越来越重要,物流系统的优化问题也成为了研究热点。车辆装载问题(Vehicle Filling Problem)和车辆路径规划问题(Vehicle Routing Problem)属于物流运营管理中的优化问题,也是当前物流配送服务的两个核心问题,它们直接关系到整个物流系统的效率和效益,需从理论到应用全面研究。VFP和VRP两个过程之间的联系是非常紧密的,如VFP中的待装货物的装卸顺序是由VRP的结果直接决定的,而VRP的求解过程中又必须考虑对应VFP的装载过程中车辆的载重情况以及空间利用情况,所以应该将车辆货物装载问题(VFP)与车辆路径规划问题(VRP)统一考虑。本文将两个问题整合,通过找到VFP和VRP联合优化的切入点,建立了联合优化模型,并提出了一种适合于模型求解的交互式启发算法。在联合优化的VFP部分考虑了货物的易损性、装载的稳定性、物品不可倒置、车辆平衡性、先下后装等现实约束条件,这样不仅可以保证货物运输的安全性,同时避免了卸货时货物的翻倒而导致的卸货效率低下以及造成货损货差的情况,而且可以保证VRP的求解方案的可行性,即在车辆的装载过程中不会出现一条运输线路上所要经过的卸货点的货物不能全部装进车厢的情况。本文采用的交互式启发算法(CA)是装载启发式算法(MLH)和基于节约值蚁群算法(MCW-ACO)的有效结合,即在MCW-ACO搜索路径解空间的同时通过MLH判断装载的可行性,其中,MLH算法采用了剩余空间合并和多次搜索空隙规则,使每辆车的空间都得到了充分利用,提高了车辆的有效装载率：MCW-ACO在标准蚁群算法的基础上,引入了C-W算法,更改了线路转移规则和信息素更新规则,提高了搜索速度并改善了搜索结果。本文对提出的算法进行了Bench-mark数据测试,结果表明交互式联合优化算法不仅能够解决大规模的VFP&VRP问题,而且得到了令人满意的解。更多还原

【Abstract】 With the logistics status in society becoming more and more important, optimization problems in the logistics system has become a hotspot. Both vehicle filling problem and vehicle routing problem belong to the optimization problems in logistics operation and management, besides they are two core issues. They are directly related to the entire logistics system efficiency and effectiveness, so they must be studied comprehensively from theory to application.Vehicle routing problem, VRP for short, and vehicle filling problem, VFP for short are interrelated closely. For example, the loading sequence in VFP is directly determined by VRP while the solution process of VRP must take vehicle loading weight and space of VFP into accout. That is why VFP and VRP should be considered together.By finding the entry point for the VFP&VRP combined optimization, this paper incorporates the two problems, builds the integrated and optimized model and proposes a combined algorithm which is suitable for the model. In the loading part we consider the cargo fragility, loading stability, oriented loading, balance weight distribution, last in first out and other practical constrains. This not only can assure the transportation safety and prevent low efficiency and cargo damage because of cargo overturned but also ensure that the solution for VRP is feasible, that is cargoes at the same route can be loaded completely.The combined algorithm is made of modified loading heuristics(MLH) and modified C-W based ant colony algorithm(MCW-ACO), that is searching the VRP solution by MCW-ACO while checking the feasibility of VFP by MLH. MLH adopts the strategies of searching and merging residual spaces which makes room for each vehicle fully utilized, thus improving the loading efficiency. Based on the standard ACO, MCW-ACO introduces the thought of saving algorithm and modifies the transition rule and pheromone update formula, which improves the searching speed and results. For proving the feasibility and correctness of model and algorithm, the paper gives the Bench-mark test result. It shows that the CA can solve the large-scale VFP&VRP and get satisfactory solutions.更多还原