本文研究了现代物流算法中两个最重要的问题，车辆路径问题和装箱问题，这两个问题已经被证明是NP—Hard，单独针对两个问题，目前已经有大量的论文，但是对这两个问题的综合（3L—CVRP）目前研究还比较少，该问题由2006年首次被提出。\n 本文使用两阶段的禁忌搜索算法来安排车辆路径，并通过局部搜索求解带有各种约束的装箱问题，最后通过分枝定界法进行后续优化。与现有文献中使用的装箱方法不同，本文将两种经典的二维装箱方法Bottom Left with Fill和Touching Perimeter进行了修改，并将其推广到三维情形，在综合考虑了3L—CVRP中各种装箱约束下，提出了非常高效的实现算法Deepest Bottom Left with Fill和Touching Area。新的装箱算法的提出大大增加了车辆的空间利用率，大量的实验结果表明，应用了Bottom Left with Fill和Touching Area的两阶段禁忌搜索算法无论在求解质量上还是求解时间上均好于目前已发表的论文，与Fuellerer等人的ACO算法相比，解的质量提高了大约2．9％，而求解时间大约为其一半。
暂无评论