弧路径优化问题作为经典的组合优化问题, 在近 40 年内受到广泛关注, 并产生了大量的研究成果. 基于此, 从问题、算法和应用三个角度对考虑容量限制的弧路径优化问题(capacitated arc routing problem, CARP)的研究现状进行综述. 首先, 基于问题特征对问题进行分类并介绍其常见数学模型. 其次, 综述求解 CARP 的精确算法、构造启发式算法及元启发式算法, 并根据基准算例求解结果对比算法效果. 再者, 归纳垃圾回收、道路管理等 CARP 常见应用场景. 最后, 展望未来研究发展方向. |