颜 瑞，张 群，胡 睿



考虑三维装箱约束的多车场车辆路径问题

颜 瑞1，张 群2，胡 睿2

（1.北京信息科技大学经济管理学院，北京 100192；2.北京科技大学东凌经济管理学院，北京 100083）

针对实际物流配送问题的特点，研究三维装箱约束车辆路径问题，首次建立考虑多车场的三维装箱约束车辆路径问题模型，并提出求解该问题的混合算法。混合算法采用遗传算法求解车辆路径问题，采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能，试验结果表明混合算法能够在较短时间内得到质量较高的近似最优解。通过数值仿真检验模型的可解性。

车辆路径问题；多车场；三维装箱；遗传算法

0引言

车辆路径问题（Vehicle Routing Problem，VRP）和装箱问题（Bin Packing Problem，BPP）都是经典的组合优化问题，且都属于NP-Hard问题。在过去的几十年里，对VRP和BPP的研究都取得了非常丰硕的成果，但是关于这两个问题的研究是独立进行的。然而，现实的物流配送中有很多情况是需要同时考虑“装箱”和“运输”这两个问题的，比如家电、家具的送货上门服务。这类配送问题通常具有相似的特征，比如运输工具是带长方体封闭式车厢的货车，货物通常装在长方体的包装箱内，车辆需要拼装运送不同体积、不同重量的货物。对于这类问题，“装箱”和“运输”这两方面是不可分割、相互制约的，只有同时考虑这两点才能即保证选择的配送路线成本最低，又保证货物可以全部合理地装入车辆。近几年，这类问题开始吸引国内外学者的关注，并且已经取得了一些成果。……