考虑LIFO约束的2L-CVRP优化  

2L-CVRP vehicle routing problem with LIFO loading constraint

作　　者：尚正阳 顾寄南[2] 潘家保 SHANG Zhengyang;GU Jinan;PAN Jiabao(School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu 241000, China;Mechanical Information Research Center, Jiangsu University, Zhenjiang 212000, China)

机构地区：[1]安徽工程大学机械与汽车工程学院,安徽芜湖241000 [2]江苏大学机械工程学院,江苏镇江212000

出　　处：《计算机集成制造系统》2021年第7期2134-2143,共10页Computer Integrated Manufacturing Systems

基　　金：安徽高校自然科学研究资助项目(KJ2019A0148)。

摘　　要：针对精准管控的现代物流需求,为实现二维装载约束下的车辆路径问题(2L-CVRP)求解,分别设计了最少开放空间(LOS)的货物装箱方法与带有回火过程的模拟退火操作(ISA),并开发了ISA-LOS算法。LOS装箱方法通过容器内的剩余开放空间数量与格局状态评价,构造综合适应度,引导货物循环装载。给出了基于Skyline的开放空间生成策略,能够迅速生成放置效果适应度,支撑LOS装箱方法高效运行。考虑车辆载重与装载的双重约束,ISA通过回火过程引入,增强了算法的全局搜索能力,有利于寻优质量的提升。结合不同模块的加速结构与参数设置,完成了整体算法的构建。针对标准算例的对比实验表明,ISA-LOS能够有效求解2|SO|L约束下的2L-CVRP,且运算结果接近于已知文献最优解。同时,算例的寻优过程与装载效果验证了ISA与LOS的有效性,其调度方法能够为相关问题优化提供参考。Aiming at the demand for precision control by modern logistics,for solving Two-dimensional Loading Capacitated Vehicle Routing Problem(2L-CVRP),the Least Open Space(LOS)heuristics and the Improved Simulated Annealing(ISA)operation were designed respectively,and an ISA-LOS algorithm was developed.LOS evaluated the comprehensive fitness of pattern status according to the residual open space in the container,and thereby guided the continuous loading of goods.Specifically,a skyline-based open space generation strategy was presented,which could rapidly yield the placement effect fitness and support the efficient operation of LOS.Considering the dual constraints of vehicle loading,the global search capability of ISA was enhanced through the introduction of the tempering process,which was conducive to the optimization and quality improvement.The overall algorithm was constructed by combining the accelerating structures and parameter settings of different modules.Comparative tests with standard cases implied that ISA-LOS could effectively solve the 2L-CVRP problem under the 2|SO|L constraint,and could return the result close to the reported optimal solution.The optimizing processes and loading effects of the cases validated the effectiveness of ISA and LOS.Therefore,the scheduling methods could provide reference for the research of related problems.

关 键 词：二维装载约束下的车辆路径问题 最少开放空间 二维装箱问题 改进模拟退火算法 后进先出约束 物流 

分 类 号：U116[交通运输工程] TP18[自动化与计算机技术—控制理论与控制工程]