摘 要：本文对考虑三维装载的车辆路径规划问题进行研究，给出了问题的数学模型。设计了一个两层结构的算法来求解该问题，外层的车辆路径规划算法采用禁忌搜索算法，内层的装箱检验算法采用了邻域搜索算法。装箱算法的检验策略集由三种启发式策略构成。另外还设计了算法加速策略使求解速度在已有基础上提高3至8倍。对国际上研究同类问题所采用的标杆问题进行求解，本文设计的算法获得了多个标杆问题的新的最好解，另外有多个标杆问题在更短的求解时间内获得与现有最好解相同的结果。

关键字：车辆路径问题 三维装箱问题 禁忌搜索邻域搜索

1.  引言

进行车辆路径规划和制定车辆装载计划是物流配送中的两项重要工作内容。若先进行车辆路径规划再根据路径规划结果制定车辆装载计划则无法保证装载的可行性，若先制定车辆装载计划再根据装载安排规划车辆路径则无法实现车辆行程的最优。一种合理的做法是将这两项工作结合在一起优化，在进行车辆路径优化的同时检验每一辆车所需配送物品是否满足车辆装载要求。

考虑三维装载的车辆路径规划问题（Three-Dimensional Loading Capacitated Vehicle Routing Problem，3L-CVRP）就是将车辆路径规划和车辆装载集成优化的问题。3L-CVRP问题由Gendreau^[1]等提出，该问题假设客户的需求都是由一些长方体状物品组成，物品尺寸和客户分布已知，车辆为单一车型，车辆尺寸已知，要求安排合理的行车路线，在满足所有客户需求及车辆装载要求的情况下，使总的车辆行程最短。

该问题具有很强的理论研究价值，3L-CVRP问题本质上是由带容量限制的车辆路径规划问题（CVRP）和三维装箱问题（3BPP）问题组合而成的系统优化问题，是一个复杂的NP难问题。

同时该问题还具有很强的应用价值，考虑三维装载的配送车辆调度系统可以满足家电配送、包裹配送、烟草配送等诸多行业的需要，通过减少车辆行驶里程，可以实现降低配送成本的经济效益和节能减排的社会效益。

2.  文献回顾

VRP问题是一个经典的组合优化问题，Dantzig和Ramser^[2]在1959年提出VRP问题并给出求解算法，1964年Clarke和Wright^[3]改进了Dantzig的算法，提出了著名的Clarke-Wright（CW）节约法，这是一种更有效的启发式算法。由于VRP问题具有很强的理论研究价值和广泛的应用背景，很多学者对该问题或其演变问题进行了研究探索，使该问题成为“最近十年运筹学领域最成功的研究之一”^[4]。VRP本身也衍生出了很多个研究方向，同时也发展出了很多求解算法，包括精确算法、经典启发式算法、元启发式算法和混合启发式算法。

由于精确算法求解的局限性，元启发式算法得到了更好的发展，求解VRP问题的元启发式算法主要有：禁忌搜索算法(TabuSearch)、模拟退火算法(SimulatedAnnealing)、遗传算法(Genetic Algorithm)、蚁群优化算法(Ant Colony Optimization)等。Gendreau^[5]等人最先将禁忌搜索算法应用于VRP。Robuste^[6]等人和Alfa^[7]等人最早提出了两种求解VRP问题的模拟退火算法，但获得的解的质量都比较差。Osman^[8]通过使用更好的初始解、自适应调整算法参数、搜索更大的解空间以及复杂的降温策略，提高了模拟退火算法的性能。Lawrence^[9]最先将遗传算法用于VRP问题的研究。Bullnheimer首次运用蚁群算法来求解VRP，并提出了一个VRP的混合蚁群系统算法^[10]。