Constraint Programming-Based Solution Approaches for Three-Dimensional Loading Capacitated Vehicle Routing Problems

The 3L-CVRP which integrates the three-dimensional loading problem with the capacitated vehicle routing problem. To solve this np-hard problem, we formulated all constraints and objective functions in the context of constraint programming and developed five models: two integrated, two decomposed CP-based, and one decomposed hybrid model. The hybrid model uses a CP model for the routing part and a genetic algorithm for the loading part. First, we compared these models and a MIP model adapted from the literature by solving 24 small-size problems. The hybrid model (CP&EA) gave the highest performance based on the comparison results. Then, a computational study was conducted with Moura and Oliveira's (2009), Bortfeldt and Homberger's (2013) and Gendreau et al. (2006)’s benchmark instances to test the hybrid model's performance in large-size problems. We improved the solution values for 36 of 93 problems and found better results on average than the existing approaches, considering the computational results on bigger problem instances. According to the computational results, Thus, it has been shown that the proposed CP&EA model can help solve the problems in distribution logistics. The related benchmark instances and computational results has been attached the website.

三维装载受限车辆路径问题（3L-CVRP）是一类融合三维装载问题与容量约束车辆路径问题的复合型优化问题。为求解这一NP难问题，本研究基于约束规划（Constraint Programming, CP）框架构建了全部约束条件与目标函数，并开发了五类模型：2个集成式模型、2个基于约束规划的分解式模型，以及1个分解式混合模型。该混合模型针对路径规划模块采用约束规划模型，针对装载模块则采用遗传算法（Genetic Algorithm, EA）。首先，本研究通过求解24个小规模测试问题，对上述五类模型以及1个从已有文献中改编得到的混合整数规划（Mixed Integer Programming, MIP）模型开展对比实验；结果显示，本文提出的混合模型（CP&EA）综合性能最优。随后，本研究采用Moura与Oliveira（2009）、Bortfeldt与Homberger（2013）以及Gendreau等人（2006）提出的基准测试实例集，针对大规模问题场景验证了该混合模型的求解性能。针对93个测试问题中的36个，本研究得到了更优的解值；结合大规模问题的计算结果来看，本方法的平均求解效果优于现有同类研究方案。综合上述计算结果可知，本文提出的CP&EA混合模型可有效支撑配送物流领域的优化问题求解。相关基准测试实例与计算结果已上传至本研究配套的官方网站。