比较研究：蚁群算法、迪杰斯特拉与最近邻在垃圾收集网络路径效率中的表现

为何更智能的垃圾路径很重要

每辆驶过你街道的垃圾车背后都有一个复杂的难题：如何在访问众多垃圾桶和街区的同时尽量减少行驶里程。随着城市产生数十亿吨垃圾且燃料成本与排放上升，即便是微小的路径改进也能节省开支、减少污染并缓解交通。本论文提出一个面向现代城市的实用问题：在为垃圾车计算路线的三种常见方法中，当网络规模变大、流量增加时，哪一种真正表现最好？

三种寻路方式

研究比较了三类路径规划方法，每一类都反映了不同风格的决策机制。第一类称为蚁群优化（ACO），其灵感来自真实蚂蚁如何释放并跟随信息素：有前景的路径会随时间被强化，而较差的路径则逐渐减弱。第二类是迪杰斯特拉算法（Dijkstra），这是一个经典的数学方法，在条件固定且已知时总能找到网络中的最短路径。第三类最近邻（Nearest Neighbour）方法则模拟人类的快速猜测：从当前所在位置出发，直接前往最近的未访问点，然后重复此过程。三种方法都被应用于同一类抽象城市地图，其中路口和垃圾收集点被表示为节点，节点间的道路以反映距离和拥堵的代价相连。

构建虚拟城市以检验这些思路

作者没有依赖某一个特定城镇，而是构建了类似典型城市布局的合成路网。这些网络较为稀疏，每个点仅与少数其他点相连，规模从10个点到50多个点不等，以模拟从小型街区到较大城市区域的情况。路段带有“拥堵加权”代价，因此更繁忙或更长的道路使用成本更高。在每张虚拟地图上，要求三种算法在选定的起点和终点之间寻找低成本路径。为保证比较公平，三者使用相同的代价结构，并对更具随机性的算法进行多次运行，以便研究者能测量其平均表现与波动性。

正面较量揭示的结果

结果显示出清晰的格局。在小型、中型和大型网络中，蚁群算法持续发现平均总成本最低的路线。其“蚂蚁”通过漫游、从经验中学习并逐步集中到成本更低的路径上，这在网络规模增大且路段代价更加不均时尤其有价值。迪杰斯特拉算法非常稳定：在相同的地图和代价下，它总是返回相同的路径，结果几乎没有波动。然而，在考虑拥堵加权代价和更复杂的布局时，其路径的成本略高于调优良好的蚁群算法。最近邻方法运行最快，但表现最差：由于总是追逐下一个最近点，它往往忽视更聪明的长期捷径，产生最昂贵且最不一致的路线。

验证差异是否真实存在

为确保这些性能差距不是随机波动的偶然结果，作者使用了一种称为威尔科克森符号秩检验（Wilcoxon signed-rank test）的统计工具。该检验比较在相同网络实例上算法配对的结果，而不假定数据服从正态分布。在所研究的每一种网络规模下，该检验均表明蚁群算法相对于迪杰斯特拉和最近邻在成本上具有统计显著的节约，而非偶然。同时，结果的分布显示了稳定性与灵活性之间的权衡：迪杰斯特拉的路径几乎不发生变化，而蚁群算法的结果在多次运行中会有轻微变化，因为它在探索替代方案后逐步趋近于较优路径。

对城市街道的含义

对城市管理者而言，论文的结论既实用又直观。如果路网规模较小且条件相对稳定，像迪杰斯特拉这样的经典最短路径方法简单且可靠。当网络规模较大且拥堵或其他代价在空间上变化时，受蚂蚁启发的方法能够挤出显著更低成本的路线，即便其在幕后需要更多的计算。尽管最近邻策略因速度诱人，但它始终会留下可节省的资金与燃料。总体而言，这项研究提供了经验证的指南：在小而可预测的环境中选择确定性方法，而在规划现代、扩张城市中可扩展且成本敏感的垃圾收集时，应优先采用自适应的群体式优化方法。

引用: Anitha, R., Parthiban, A. Comparative study of ACO, dijkstra, and NN for routing efficiency in waste collection networks. Sci Rep 16, 13346 (2026). https://doi.org/10.1038/s41598-026-42866-5

关键词: 城市垃圾收集, 路径优化, 蚁群优化, 最短路径算法, 智慧城市物流