A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints
研究带稳定性、易碎性及后进先出等实际约束的车辆路径与三维装载联合优化问题，提出基于列生成的启发式算法，在基准测试中优于现有禁忌搜索方法。
This paper addresses an integrated problem of vehicle routing and three-dimensional loading with additional practical constraints such as stability, fragility and LIFO. A column generation (CG) technique-based heuristic is proposed to handle this problem. To generate new columns in CG technique, first, an elementary shortest path problem is solved to find routes with negative reduced cost. Then an extreme point-based heuristic method is employed to verify feasibility of obtained routes in terms of loading and other constraints. To speed up the CG technique, fast column generation is also performed by applying an efficient heuristic pricing method. The CG technique, tested on the benchmark instances, outperforms the efficient tabu search method developed in the literature in terms of solution quality and computation time.