交通信息驱动的最后一公里配送混合启发式方法优化

《Future Transportation》：Traffic-Informed Optimization of Last-Mile Delivery Using Hybrid Heuristic Approaches Afia Yeboah, Deo Chimba and Malshe Rohit

　　

电子商务的快速增长加剧了城市最后一公里配送的运营和可持续性挑战，因此需要能够在实际交通和空间条件下可靠执行的路由方法。本研究评估了三种路由算法：最近邻算法 (Nearest Neighbor, NN)、Clarke-Wright 节约算法 (Clarke–Wright Savings, CWS) 和蚁群优化算法 (Ant Colony Optimization, ACO)。研究使用了纳什维尔都市区按运营路线分组的 1764 个真实亚马逊配送站点数据，共分为十个运营集群。通过谷歌地图距离矩阵应用程序接口 (Google Maps Distance Matrix API) 在驾驶模式下获取了行驶距离和时间，以反映实际的道路网络结构和典型交通状况。研究观察到不同算法和集群配置之间存在显著的性能差异。NN 在紧凑集群中表现出色（集群 4：18.43 英里和 58.48 分钟），但在分散集群中表现不佳（集群 9：82.44 英里和 196.48 分钟），反映出对空间分散性的高度敏感性。相比之下，CWS 在所有集群中持续减少了行驶距离和时间，实现了最短的观测路线（集群10：18.50 英里和 47.82 分钟）。相对于 ACO，CWS 在高分散性集群中将行驶距离减少了高达 42%（集群 9），并将行驶时间减少了超过 45%。ACO 表现出最高的变异性，其距离可达 98.77 英里，行驶时间超过 218 分钟。使用效率比、分布分析、性能象限可视化和复合性能指数 (Composite Performance Index, CPI) 进行的多标准评估证实了 CWS 的优越性。在相同的交通信息输入下，CPI 得分（CWS：1.00，NN：0.78，ACO：0.00）反映了其平衡的空间和时间效率。结果表明，在准静态城市配送系统中，基于确定性节约原理的路由方法提供了卓越的稳定性、效率和可扩展性。然而，本研究未将所评估的算法与最先进的精确旅行商问题求解器（如 Concorde、LKH）或更新的元启发式算法（如遗传算法或变邻域搜索）进行基准比较。研究目标是在一致的交通信息成本矩阵下提供受控的实证比较，而非确定全局最优边界。因此，尽管研究结果在所评估的框架内强烈支持 Clarke-Wright 节约算法的相对优越性，但未来结合先进精确算法和混合优化方法的研究将进一步阐明算法的性能背景。

**研究背景与问题**
随着电子商务的快速发展，消费者对高效、经济、及时的配送服务需求激增，尤其是在城市地区。最后一公里配送，即物流链中将货物从配送中心或本地设施直接运送给消费者的最终环节，已成为当今物流和电子商务公司面临的最关键挑战之一。此阶段可占货物总运输成本的 53%，其低效直接影响客户满意度、运营成本和环境可持续性。该问题本质上可归结为经典的旅行商问题 (Traveling Salesman Problem, TSP)，即在给定一组地点中寻找访问每个地点恰好一次并返回起点的最短路径。由于 TSP 属于非确定性多项式困难 (nondeterministic polynomial hard, NP-hard) 问题，难以在多项式时间内找到所有实例的最优解，因此业界和学术界致力于开发能在合理计算时间内生成近似最优解的启发式和元启发式算法。在城市实际配送运营中，交通拥堵是影响最大的不可预测因素之一，常导致配送延误、客户满意度下降、燃料消耗和温室气体排放增加。因此，减少行驶时间不仅是物流问题，也是环境要求。目前，在利用真实交通数据优化路由策略以应对现实约束方面，仍存在研究空白，特别是使用实际商业配送数据进行系统化算法基准测试的研究相对有限。

**研究目的与意义**
本研究旨在利用真实世界的亚马逊最后一公里配送数据，在纳什维尔都市区的实际城市配送条件下，严格评估所选路由优化算法的有效性和运营适用性。研究具体比较了三种广泛应用的路由方法：最近邻算法 (NN)、Clarke-Wright 节约算法 (CWS) 和蚁群优化算法 (ACO)。通过使用谷歌地图距离矩阵 API 获取交通信息驱动的行驶距离和时间，研究人员评估了算法在不同空间配置的配送集群中的性能，并采用多标准性能评估框架（包括效率比、性能象限分析和复合性能指数）进行综合分析。这项研究的意义在于，它通过使用真实的运营数据和交通信息成本矩阵，为经典路由算法在实践中的表现提供了受控的、可重复的基准，有助于物流管理者在复杂的城市环境中选择更高效、稳定的路由策略，从而降低运营成本、减少延误和环境影响。相关成果发表在《Future Transportation》期刊上。

**关键技术方法**
为达成研究目标，研究人员主要采用了以下关键技术方法：首先，数据收集与预处理。研究使用了纳什维尔都市区包含 1764 条记录的亚马逊包裹配送真实数据集。数据包含每个配送站点的精确地理空间坐标（经纬度）、地址、时间戳、包裹物理属性等。预处理确保了关键地理空间属性的完整性，并基于数据集中已有的运营路线标识符 (Route ID) 将站点划分为十个配送集群进行分析，未应用额外的聚类算法。其次，路由算法实现与评估。研究将问题建模为无能力约束的单车辆路由实例（即 TSP 问题），分别实现了 NN、CWS 和 ACO 三种算法。NN 采用从仓库开始的贪心构造策略；CWS 采用经典的节约算法公式，无容量约束；ACO 则采用标准蚁群系统 (Ant System) 公式，参数固定（信息素重要性 α=1，启发式重要性 β=5，蒸发率 ρ=0.5，信息素常数 Q=1.0，蚂蚁数量 m=10，最大迭代次数 100）。所有算法均使用相同的输入进行评估。最后，多标准性能评估框架。为了进行平衡的、面向决策的比较，研究采用了多标准性能评估，包括计算效率比（距离/时间）、使用箱线图进行分布分析、绘制性能象限图以及构建复合性能指数，以综合空间和时间性能为一个整体路由有效性度量。

**研究结果**
1. **最近邻算法 (NN) 的性能**：NN 算法的性能在不同集群间差异显著，反映了其对空间配置的敏感性。在紧凑的集群 4 中，它取得了最佳性能（18.43 英里，58.48 分钟）。然而，在分散的集群 9 中，它产生了最长的路线（82.44 英里，196.48 分钟），显示出其贪心决策的局限性。其他集群表现出中等性能，距离和时间随空间分散程度而变化。
2. **Clarke-Wright 节约算法 (CWS) 的性能**：CWS 算法在所有集群中均表现出减少行驶距离和时间的稳定能力。它在集群 10 实现了最短观测路线（18.50 英里，47.82 分钟）。即使在最具挑战性的集群 9，其路线（57.21 英里，110.52 分钟）也远优于 NN 和 ACO。结果表明，该算法在空间紧凑和分散的集群中都能提供高效的路由。
3. **蚁群优化算法 (ACO) 的性能**：ACO 算法表现出最高的性能变异性。虽然在某些集群（如集群 8：44.75 英里，148.45 分钟）中表现尚可，但在其他集群（如集群 5 和 9）中产生了最长的距离（分别为 84.49 和 98.77 英里）和最长的行驶时间（集群 7：218.40 分钟），表明其在半静态框架下的收敛稳定性较差。
4. **多标准性能比较与复合性能指数 (CPI) 分析**：
* **效率比与分布**：效率比（距离/时间）分析显示 CWS 在大多数集群中具有最高的效率，表明其路线紧凑且时间利用率高。箱线图分布分析证实 CWS 在距离和时间上的分布最为集中，变异性最低，而 ACO 的变异性最高。
* **性能象限**：性能象限图（以平均距离和时间为界划分四个区域）显示，CWS 位于最优的低距离-低时间象限，NN 位于中等性能区域，而 ACO 则位于高距离-高时间的最差性能象限。
* **复合性能指数**：CPI 将归一化的距离和时间性能聚合为单一指标。结果显示，CWS 获得了最高的 CPI 值（1.00），NN 为 0.78，ACO 为 0.00。这进一步证实了 CWS 在综合空间和时间效率方面的优越性。

**讨论与结论**
本研究使用真实世界的亚马逊最后一公里配送数据，在交通信息输入条件下，评估了 NN、CWS 和 ACO 三种路由优化算法在十个配送集群中的性能。研究结论表明，Clarke-Wright 节约算法 (CWS) 在最小化总行驶距离和行驶时间方面 consistently 表现出卓越性能。例如，在高分散性的集群 9 中，CWS 将距离减少了约 30%（相对于 NN）和 42%（相对于 ACO）；在集群 1 中，将时间减少了约 44%（相对于 NN）和 65%（相对于 ACO）。最近邻算法 (NN) 在紧凑集群中表现良好，但在分散集群中性能显著下降，显示出对空间配置的敏感性。蚁群优化算法 (ACO) 表现出最高的变异性，在多个集群中产生了最长的距离和时间，表明其在既定半静态路由框架下的收敛稳定性不足。多标准评估框架（包括效率比、分布分析、性能象限和复合性能指数）的结果一致地支持了 CWS 的优越性，表明其在空间和时间效率上提供了最可靠、最稳定的路由解决方案。

然而，本研究存在一些局限性：路由问题被建模为无能力约束的单车辆旅行商问题实例，未纳入车辆容量限制、服务时间、配送时间窗和多车辆协调约束。行驶时间通过谷歌地图距离矩阵 API 获取，未指定出发时间特定的拥堵参数，因此反映的是典型而非动态高峰期的交通状况。配送集群直接来源于运营路线标识符，未进行独立的聚类优化。此外，本研究未与最先进的精确求解器（如 Concorde、LKH）或先进的元启发式算法（如遗传算法、变邻域搜索）进行基准比较，因为研究目标是在相同的交通信息成本输入下进行受控的实证基准测试，而非验证全局最优性。

为了推进可扩展和自适应的最后一公里路由研究，未来工作应纳入容量和时间窗约束，集成出发时间依赖的交通建模，评估替代的聚类策略，并探索结合确定性节约路由与自适应元启发式优化的混合框架。将基准测试扩展到包括精确求解器和当代元启发式算法，将有助于进一步在最优性边界背景下评估算法性能。

总体而言，本研究表明，将真实世界的交通信息成本矩阵与多标准性能评估相结合，能够更深入地了解路由算法对城市最后一公里物流的适用性。综合使用直接路由指标、效率比、性能象限分析和复合指数，提供了一个稳健且面向决策的基准测试框架。在所评估的条件下，Clarke-Wright 节约算法展现了卓越的稳定性、效率和可扩展性，支持其作为城市最后一公里配送优化的实用基线。