项目成员：叶梓元、蓝文兴、阮沛均
指导老师：姚新 教授
城市垃圾收运路径规划问题常常被建模为NP-hard的车辆路径问题。在本项目中，我们使用实际生活中的真实数据，待收运的垃圾点数以千计。与现有的工作相比，数据规模更大且问题更复杂。本项目设计了基于启发式的算法来对城市垃圾收运路径进行规划，优化目标为尽可能减少收运行驶里程。我们在锐明科技股份有限公司提供的大规模真实数据集上进行问题的分析与抽象、建模，并设计基于启发式的算法对问题优化求解。
本项目提出的基于启发式的算法分为两个阶段，第一阶段是生成高质量初始解的算法，第二阶段是基于启发式的优化算法。
第一阶段算法(Heuristic-assisted Solution Initialization, HaSI)使用了贪心的思想，通过安排最近的待回收的收集点来进行路径规划。同时算法通过收缩约束来尽可能避免产生违反约束的解，利用剩余待回收的收集点和停车场之间的启发式信息来调整垃圾车的安排顺序。
第二阶段算法(Extended Local Search, ELS)改进了经典的启发式算法—局部搜索算法，对初始解进行优化。考虑到解决的是一个大规模问题，我们提出了3个新的搜索算子：限定区域的单点交换算子、限定区域的段交换算子、随机多点交换算子，减少了在解空间中的无效搜索的同时还在一定程度上避免搜索时陷入局部最优。
本项目设计并完成了整个算法的实现，并在包含3000个收集点，3个停车场和3个倾倒点的大规模真实数据集上进行了实验。实验结果表明，第一阶段的算法产生的初始解相比于随机算法和节约算法有明显的提升。第二阶段的算法对于产生的初始解可以实现约12%的行驶里程优化。目前较少有文献研究对于如此大规模的复杂路径规划问题，该项目进行了初步的尝试，优化效果显著。未来的工作可以着眼于优化算法的运行效率，减少算法优化所需要的计算时间。
