车辆装载和路径安排联合优化问题研究
|
摘要
随着物流在社会中的地位越来越重要,物流系统的优化问题也成为了研究热点。车辆装载问题(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问题,而且得到了令人满意的解。
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.
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问题,而且得到了令人满意的解。
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.
引文
[1]Dyckhoff H. A Typology of Cutting and Packing Problem. European Journal of Operation Research, 1990,44:145-159
[2]王金敏,马丰宁,刘黎.集装箱装入算法的研究.沈阳工业大学学报,200017(12)：6-9
[3]George J A & Robinison D F. A Heuristic for Packing Boxes into a container[J]. Computer and Operational Research,1980,7:147-156.
[4]E.E.Bischoff, M. D. Marriott. A comparative evaluation of heuristics for container loading. European Journal of Operational Research,1990,44:267-276.
[5]姜义东,查建中,何大勇.装载矩形货物的布局研究.铁道学院,2000,22(6)：13-18
[6]樊建华,黄有群,刘嘉敏.集装箱装入算法的研究.沈阳工业大学学报,2002，24(4)：306-308.
[7]靳志宏,计明军,朴惠淑.集装箱多式联运系统拼箱集运优化问题[J].系统工程,2006,24,Suppl.1.
[8]卜雷,袁新江等.基于遗传算法的集装箱单箱三维装载优化问题.中国铁道科学报,2004,25(4)：108-111
[9]Burke EK, Kendall G, Whitwell G. A new placemen heuristic for the orthogonal stock-cutting problem. Operations Research,2004,52:655-71
[10]Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing probles. INFORMS Journal on Computing,1999,11(4):345-57
[11]黄文齐,何琨.求解三维矩形布局的最大穴度算法.华中科技大学学报,2008,36(3)：90-95
[12]Linus Schrage. Formulation And Structure of More Complex/Realistic Routing and Scheduling Problem. Networks,1981,11:229-232
[13]Bodin L, Golden B. Classification in Vehicle Routing and Scheduling. Networks,1981,11:7-108
[14]Bodin L, Golden B L, Assad A A, Ball M. Rousting and Scheduling of Vehicles and Crews. The State of Art, Computers & Operations Research,1983,10:63-211
[15]Assad A A.Modeling and Implementation Issues in Vehicle Routing. Management Science and Systems,1988,16:7-45
[16]Desrocherg M, Lcustra J K, Savelsbergh M W. A Classification Scheme for Vehicle Routing and scheduling Problems. European Journal of Operation Research,1990,42:322-332
[17]赵鲁华.城市配送中心车辆调度优化研究：[硕士学位论文].吉林大学,2005
[18]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005
[19]陈文兰,戴树贵.车辆路径安排问题算法研究综述.滁州学院学报,2007,9(3)：19-25
[20]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法.中国公路学报,2006,19(4)：123-126
[21]Alba E,Dorronsoro B. Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm. Information Processine Letters,2006
[22]史玉敏.物流配送环节中车辆路径问题研究[硕士论文].山东师范大学,2007,4
[23]丁秋雷.带有时间窗的车辆路径问题的混合蚁群算法研究[硕士论文].大连理工大学,2005,11
[24]郑小雪.引入启发式函数蚁群算法的VRP研究.西南林学院学报,2009.29(3)：44-48
[25]李志威.基于动态扫描和蚁群算法的物流配送网络优化研究.管理工程学报,2006,20(4)：9-12
[26]M.Gendreau, M.Iori, G.Laporte, S.Martello. A tabu search algorithm for a routing and container loading problem. Transportation Science,2006,40:342-350
[27]M.Fuellerer, K.F.Doerner, R.Hartl, M.Iori. Ant colony optimization for the two-dimensional loading vehicle routing problem. Computer&Operations Research.,2009(36):655-673
[28]K.F.Doerner, G.Fuellerer, M.Gronalt, R.Hartl, M.Iori. Metaheuristics for vehicle routing problems with loading constraints. Networks,2007,49(4):294-307
[29]Pisinger. http://www.diku.dk/pisinger/
[30]程满中.蚂蚁算法在车辆路径问题中的研究[硕士论文].中南民族大学,2007,5
[31]M.Reimann, K.F.Doerner, R.F.Hartl. Savings based ants divide and conquer the vehicle routing problem. Comperter&Operations Research,2004,31(4):563-591
[32]M.Reimann, M.Stummer, K.F.Doerner. A savings based ant system for the vehicle routing problem. Proceeding of the Genetic and Evolutionary Computation Conference2002,2002
[33]李军,郭耀煌.物流配送车辆优化调度理论与方法.中国物资出版社,2001
[34]郭贝贝.复杂集装箱装载问题研究及可视化实现[硕士论文].大连海事大学,2009
[2]王金敏,马丰宁,刘黎.集装箱装入算法的研究.沈阳工业大学学报,200017(12)：6-9
[3]George J A & Robinison D F. A Heuristic for Packing Boxes into a container[J]. Computer and Operational Research,1980,7:147-156.
[4]E.E.Bischoff, M. D. Marriott. A comparative evaluation of heuristics for container loading. European Journal of Operational Research,1990,44:267-276.
[5]姜义东,查建中,何大勇.装载矩形货物的布局研究.铁道学院,2000,22(6)：13-18
[6]樊建华,黄有群,刘嘉敏.集装箱装入算法的研究.沈阳工业大学学报,2002，24(4)：306-308.
[7]靳志宏,计明军,朴惠淑.集装箱多式联运系统拼箱集运优化问题[J].系统工程,2006,24,Suppl.1.
[8]卜雷,袁新江等.基于遗传算法的集装箱单箱三维装载优化问题.中国铁道科学报,2004,25(4)：108-111
[9]Burke EK, Kendall G, Whitwell G. A new placemen heuristic for the orthogonal stock-cutting problem. Operations Research,2004,52:655-71
[10]Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing probles. INFORMS Journal on Computing,1999,11(4):345-57
[11]黄文齐,何琨.求解三维矩形布局的最大穴度算法.华中科技大学学报,2008,36(3)：90-95
[12]Linus Schrage. Formulation And Structure of More Complex/Realistic Routing and Scheduling Problem. Networks,1981,11:229-232
[13]Bodin L, Golden B. Classification in Vehicle Routing and Scheduling. Networks,1981,11:7-108
[14]Bodin L, Golden B L, Assad A A, Ball M. Rousting and Scheduling of Vehicles and Crews. The State of Art, Computers & Operations Research,1983,10:63-211
[15]Assad A A.Modeling and Implementation Issues in Vehicle Routing. Management Science and Systems,1988,16:7-45
[16]Desrocherg M, Lcustra J K, Savelsbergh M W. A Classification Scheme for Vehicle Routing and scheduling Problems. European Journal of Operation Research,1990,42:322-332
[17]赵鲁华.城市配送中心车辆调度优化研究：[硕士学位论文].吉林大学,2005
[18]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005
[19]陈文兰,戴树贵.车辆路径安排问题算法研究综述.滁州学院学报,2007,9(3)：19-25
[20]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法.中国公路学报,2006,19(4)：123-126
[21]Alba E,Dorronsoro B. Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm. Information Processine Letters,2006
[22]史玉敏.物流配送环节中车辆路径问题研究[硕士论文].山东师范大学,2007,4
[23]丁秋雷.带有时间窗的车辆路径问题的混合蚁群算法研究[硕士论文].大连理工大学,2005,11
[24]郑小雪.引入启发式函数蚁群算法的VRP研究.西南林学院学报,2009.29(3)：44-48
[25]李志威.基于动态扫描和蚁群算法的物流配送网络优化研究.管理工程学报,2006,20(4)：9-12
[26]M.Gendreau, M.Iori, G.Laporte, S.Martello. A tabu search algorithm for a routing and container loading problem. Transportation Science,2006,40:342-350
[27]M.Fuellerer, K.F.Doerner, R.Hartl, M.Iori. Ant colony optimization for the two-dimensional loading vehicle routing problem. Computer&Operations Research.,2009(36):655-673
[28]K.F.Doerner, G.Fuellerer, M.Gronalt, R.Hartl, M.Iori. Metaheuristics for vehicle routing problems with loading constraints. Networks,2007,49(4):294-307
[29]Pisinger. http://www.diku.dk/pisinger/
[30]程满中.蚂蚁算法在车辆路径问题中的研究[硕士论文].中南民族大学,2007,5
[31]M.Reimann, K.F.Doerner, R.F.Hartl. Savings based ants divide and conquer the vehicle routing problem. Comperter&Operations Research,2004,31(4):563-591
[32]M.Reimann, M.Stummer, K.F.Doerner. A savings based ant system for the vehicle routing problem. Proceeding of the Genetic and Evolutionary Computation Conference2002,2002
[33]李军,郭耀煌.物流配送车辆优化调度理论与方法.中国物资出版社,2001
[34]郭贝贝.复杂集装箱装载问题研究及可视化实现[硕士论文].大连海事大学,2009