Abstract: 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.

Key words: two-dimensional loading capacitated vehicle routing problem, least open space, two-dimensional bin packing problem, improved simulated annealing, last in first out constraint, logistics

摘要： 针对精准管控的现代物流需求,为实现二维装载约束下的车辆路径问题(2L-CVRP)求解,分别设计了最少开放空间(LOS)的货物装箱方法与带有回火过程的模拟退火操作(ISA),并开发了ISA-LOS算法。LOS装箱方法通过容器内的剩余开放空间数量与格局状态评价,构造综合适应度,引导货物循环装载。给出了基于Skyline的开放空间生成策略,能够迅速生成放置效果适应度,支撑LOS装箱方法高效运行。考虑车辆载重与装载的双重约束,ISA通过回火过程引入,增强了算法的全局搜索能力,有利于寻优质量的提升。结合不同模块的加速结构与参数设置,完成了整体算法的构建。针对标准算例的对比实验表明,ISA-LOS能够有效求解2|SO|L约束下的2L-CVRP,且运算结果接近于已知文献最优解。同时,算例的寻优过程与装载效果验证了ISA与LOS的有效性,其调度方法能够为相关问题优化提供参考。

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