跳到正文

学术论文

配送与末端履约

基于技能型骑手的高效订单池优化:提升实时多对一任务分配效率5.3%

本文提出了一种基于技能型骑手(SCs)的配送网络(SCDN),通过增强图表示学习来优化即时食品配送(OFD)中的订单池化。实验结果显示,SCDN 显著提高了订单池的质量和范围,总 MD 分数提高了 5.3%,特别是在午高峰期间,新建立的模式将骑手的平均增量取货时间减少了 51%。

原始来源: arXiv

基于技能型骑手的高效订单池优化:提升实时多对一任务分配效率5.3%

就这篇报道问 SCI.AI

📋 本文要点

本文提出了一种基于技能型骑手(SCs)的配送网络(SCDN),通过增强图表示学习来优化即时食品配送(OFD)中的订单池化。实验结果显示,SCDN 显著提高了订单池的质量和范围,总 MD 分数提高了 5.3%,特别是在午高峰期间,新建立的模式将骑手的平均增量取货时间减少了 51%。

论文:Harvesting Efficient On-Demand Order Pooling from Skilled Couriers: Enhancing Graph Representation Learning for Refining Real-time Many-to-One Assignments

作者:Yile Liang, Jiuxia Zhao 等

发表日期:2024-06-20

发表:arXiv preprint

原文链接:https://arxiv.org/abs/2406.14635

研究背景

近年来,即时食品配送(OFD)服务在全球范围内迅速普及,消费者只需点击几下即可在几十分钟内享受到美味的食物。然而,如何在保证配送时效的同时提高平台效率成为了一个关键问题。

随着即时食品配送市场的快速增长,订单池化成为了提高配送效率的重要手段。通过将多个订单合并为一次配送,可以有效减少配送成本并提高整体效率。然而,由于订单分配的复杂性和实时性,传统的计算方法难以满足需求。此外,线下环境中的不确定性因素也给平台的感知和决策带来了挑战。

现有方法主要依赖于地理位置和预计送达时间来进行订单池化,但这种方法过于简单,限制了整合的可能性。一些研究提出了更复杂的算法,如基于整数规划的精确算法,但这些方法通常需要大量的计算资源,无法实现实时应用。因此,亟需一种能够在保持高效率的同时,实现高质量订单池化的新方法。

即时食品配送平台面临的主要挑战之一是计算复杂度。在每个调度周期中,系统需要评估所有可能的订单组合,并选择最优的配送方案。这不仅需要大量的计算资源,还要求在短时间内完成。例如,在中国的一些大城市,午高峰期间每批次需要处理超过 3000 个订单,而每个订单平均有 100 个可用的骑手。假设每个骑手最多可以接受 5 个订单,那么计算量将达到 (C(3000, 2) + C(3000, 3) + C(3000, 4) + C(3000, 5)) × 100。这种巨大的计算量使得传统的计算方法难以实现实时应用。

另一个挑战是线下环境的复杂性和动态性。即时食品配送平台需要处理各种不可预见的因素,如道路封闭、自然障碍和疫情相关的封锁。这些因素使得平台难以获取详细的时空数据,从而影响了订单池化的决策质量。例如,平台可能因为地图精度不足或数字能力有限,无法准确预测交通状况,导致订单池化不合理,增加了绕路和超时的风险。

综上所述,现有的订单池化方法在计算复杂度和系统感知方面存在明显不足,亟需一种新的方法来解决这些问题。

核心发现解读

构建技能型骑手配送网络(SCDN)

本文提出了一种基于技能型骑手(SCs)的配送网络(SCDN),通过增强图表示学习来优化订单池化。SCDN 的核心在于利用 SCs 的丰富经验和行为数据,提取潜在的订单组合,并通过低维向量的相似度计算来简化大规模搜索空间。

具体方法: SCDN 基于一个增强的属性异构网络嵌入方法(EATNE),从丰富的时空信息中提取特征。首先,考虑到骑手在一个城市内的活动范围有限,提出了一种区域聚集的负采样机制,以提高算法性能。这种机制通过在特定区域内选择负样本,避免了随机负采样的不准确性,从而提高了模型的泛化能力。其次,使用定制的边缘排名损失函数代替 GATNE 中的交叉熵损失,进一步提升嵌入质量。边缘排名损失函数能够更好地捕捉节点之间的相对距离,使得嵌入结果更加准确。最后,为了处理冷启动问题,引入了地理信息生成未见过的 FU 嵌入,扩大了覆盖范围。这种方法通过结合地理信息和其他上下文信息,生成新的 FU 嵌入,从而解决了新订单或未见过的 FU 的初始嵌入问题。

实验设置与证据: 在美团外卖系统的在线测试中,SCDN 显著提高了订单池的质量和范围。总 MD 分数提高了 5.3%,表明订单分配更加高效,减少了绕路和超时风险。特别是在午高峰期间,新建立的模式将骑手的平均增量取货时间减少了 51%。实验还显示,在高峰期,SCDN 能够在秒级时间内完成订单分配,比传统方法快了 80% 以上。

具体来说,SCDN 通过以下步骤实现了高效的订单池化:

1. **数据收集与预处理**:收集骑手的历史行为数据,包括取货点、送货点、配送时间和路线等信息。通过预处理,将这些数据转换为适合图表示学习的格式。
2. **图建模**:构建一个基于 SC 行为序列的配送网络,其中节点代表流单元(FU),边代表 SC 的行为序列。FU 是一个从取货兴趣区域(AOI)到送货 AOI 的有向向量。
3. **嵌入生成**:利用 EATNE 方法生成 FU 的嵌入。通过区域聚集的负采样机制和定制的边缘排名损失函数,提高嵌入的质量。
4. **相似度计算**:通过计算 FU 嵌入之间的相似度,快速找到潜在的订单组合。
5. **骑手召回**:根据相似度计算结果,召回最合适的骑手进行配送。

MOA 搜索空间优化与 OFD 应用

通过使用 FU 嵌入,本文重构了美团调度系统中的订单组合和骑手召回机制,实现了更高质量的实时订单池化。SCDN 通过细化 MOA 的广阔搜索空间,发现了独立且小规模的子空间,从而促进了全面和高质量的订单池化。

具体方法: 利用 FU 嵌入,本文设计了一种新的配送模式,不仅提高了骑手效率,还确保了服务可靠性。通过分析 SCs 的行为序列,SCDN 能够识别出具有高潜力的订单组合,并通过低维向量的相似度计算来快速匹配最佳骑手。具体来说,SCDN 通过以下步骤实现订单组合和骑手召回:

1. **FU 嵌入生成**:利用 EATNE 方法生成 FU 嵌入,每个 FU 代表一个从取货点到送货点的路径。
2. **相似度计算**:通过计算 FU 嵌入之间的相似度,快速找到潜在的订单组合。
3. **骑手召回**:根据相似度计算结果,召回最合适的骑手进行配送。

实验设置与证据: 实验结果表明,在午高峰期间,SCDN 将配送效率提高了 45-55%,同时保持了及时配送的承诺。此外,SCDN 还能够显著减少骑手的绕路和超时风险,提高了整体配送体验。实验还显示,SCDN 在处理大规模订单时表现出色,能够处理每批次超过 3000 个订单的情况,而传统方法在这种情况下往往会崩溃。

具体来说,SCDN 通过以下步骤实现了高效的订单池化:

1. **数据收集与预处理**:收集骑手的历史行为数据,包括取货点、送货点、配送时间和路线等信息。通过预处理,将这些数据转换为适合图表示学习的格式。
2. **图建模**:构建一个基于 SC 行为序列的配送网络,其中节点代表流单元(FU),边代表 SC 的行为序列。FU 是一个从取货兴趣区域(AOI)到送货 AOI 的有向向量。
3. **嵌入生成**:利用 EATNE 方法生成 FU 的嵌入。通过区域聚集的负采样机制和定制的边缘排名损失函数,提高嵌入的质量。
4. **相似度计算**:通过计算 FU 嵌入之间的相似度,快速找到潜在的订单组合。
5. **骑手召回**:根据相似度计算结果,召回最合适的骑手进行配送。

与相关工作的对比

与现有的订单池化方法相比,SCDN 具有以下优势:

1. **实时性**:SCDN 通过低维向量的相似度计算,大幅降低了计算复杂度,能够在秒级时间内完成订单分配,而传统方法往往需要几分钟甚至更长时间。例如,在高峰期,SCDN 可以在 5 秒内完成订单分配,而传统方法可能需要 30 秒以上。
2. **灵活性**:SCDN 不仅考虑了地理位置和预计送达时间,还结合了骑手的行为数据,使得订单池化更加灵活和高效。通过分析骑手的历史行为,SCDN 能够识别出最优的订单组合,从而提高了配送效率。
3. **可扩展性**:通过区域聚集的负采样机制和冷启动缓解机制,SCDN 能够处理大规模的数据集,并在实际应用中表现出良好的可扩展性。实验显示,SCDN 在处理大规模订单时表现出色,能够处理每批次超过 3000 个订单的情况,而传统方法在这种情况下往往会崩溃。

具体来说,SCDN 与现有方法的对比如下:

– **计算复杂度**:传统方法通常需要大量的计算资源来评估所有可能的订单组合,而 SCDN 通过低维向量的相似度计算,大幅降低了计算复杂度。例如,在高峰期,SCDN 可以在 5 秒内完成订单分配,而传统方法可能需要 30 秒以上。
– **灵活性**:传统方法主要依赖于地理位置和预计送达时间来进行订单池化,而 SCDN 结合了骑手的行为数据,使得订单池化更加灵活和高效。通过分析骑手的历史行为,SCDN 能够识别出最优的订单组合,从而提高了配送效率。
– **可扩展性**:传统方法在处理大规模订单时容易崩溃,而 SCDN 通过区域聚集的负采样机制和冷启动缓解机制,能够处理大规模的数据集。实验显示,SCDN 在处理大规模订单时表现出色,能够处理每批次超过 3000 个订单的情况。

批评/局限

计算复杂度仍然较高

尽管 SCDN 通过低维向量的相似度计算大大降低了计算复杂度,但在某些极端情况下,如订单数量急剧增加时,计算量仍然可能成为一个瓶颈。这可能导致系统响应时间延长,影响用户体验。

影响: 在高峰期,订单数量激增可能会导致系统响应时间延长,从而影响配送效率和服务质量。例如,在某些极端情况下,SCDN 的响应时间可能会从 5 秒增加到 10 秒。

缓解方向: 可以通过进一步优化算法,例如引入更高效的负采样机制或采用分布式计算框架,来进一步降低计算复杂度。此外,还可以通过增加计算资源,如使用 GPU 或分布式计算集群,来提高系统的处理能力。例如,可以通过引入更高效的负采样机制,减少不必要的计算;或者采用分布式计算框架,将计算任务分散到多个节点上,从而提高系统的处理能力。

依赖于历史数据

SCDN 的效果在很大程度上依赖于历史数据的质量和完整性。如果历史数据存在偏差或不完整,可能会导致嵌入结果不准确,进而影响订单池化的质量。

影响: 如果历史数据存在偏差或不完整,可能会导致嵌入结果不准确,进而影响订单池化的质量。例如,如果某些地区的订单数据不足,SCDN 可能无法准确识别该地区的最优订单组合。

缓解方向: 可以通过引入更多的数据源和数据清洗技术,提高历史数据的质量和完整性。此外,还可以结合在线学习方法,不断更新和优化嵌入模型。例如,可以通过实时收集和分析骑手的行为数据,动态调整嵌入模型,从而提高其准确性。具体来说,可以通过引入更多的数据源,如天气数据、交通数据等,来丰富历史数据;或者采用数据清洗技术,去除噪声和异常值,提高数据质量。此外,还可以结合在线学习方法,不断更新和优化嵌入模型,使其能够适应不断变化的环境。

冷启动问题

对于新出现的订单或未见过的 FU,SCDN 依赖于地理信息生成嵌入,但这可能会导致初始嵌入结果不够准确。

影响: 对于新出现的订单或未见过的 FU,初始嵌入结果可能不够准确,从而影响订单池化的质量。例如,在某些新开发的地区,SCDN 可能无法准确识别最优的订单组合。

缓解方向: 可以通过引入更多的上下文信息和用户反馈,逐步优化新订单或未见过的 FU 的嵌入结果。此外,还可以结合迁移学习方法,利用其他城市的类似数据进行初始化。例如,可以将其他城市的成功经验应用于新开发的地区,从而提高初始嵌入结果的准确性。具体来说,可以通过引入更多的上下文信息,如用户的偏好、商家的位置等,来丰富新订单的信息;或者结合用户反馈,不断调整和优化嵌入模型。此外,还可以采用迁移学习方法,利用其他城市的类似数据进行初始化,从而提高初始嵌入结果的准确性。

实操启示

优化配送路径

通过对技能型骑手的行为数据进行分析,可以识别出高潜力的订单组合。平台可以根据这些组合优化配送路径,减少绕路和超时风险,提高配送效率。例如,平台可以定期分析骑手的历史行为数据,识别出最优的订单组合,并将其应用于实际配送中,从而提高整体配送效率。

具体来说,平台可以通过以下步骤优化配送路径:

1. **数据收集**:收集骑手的历史行为数据,包括取货点、送货点、配送时间和路线等信息。
2. **数据分析**:通过分析这些数据,识别出高潜力的订单组合。例如,可以通过聚类分析,找出经常一起配送的订单组合。
3. **路径优化**:根据识别出的订单组合,优化配送路径。例如,可以采用贪心算法或遗传算法,找到最优的配送路径。
4. **实施与反馈**:将优化后的配送路径应用于实际配送中,并收集用户的反馈,不断调整和优化。

实时调整配送策略

SCDN 能够在秒级时间内完成订单分配,平台可以根据实时情况动态调整配送策略。例如,在高峰期可以通过增加骑手数量或调整配送范围来应对订单激增的情况。具体来说,平台可以在高峰期增加骑手的数量,或者调整配送范围,以确保所有订单都能在承诺的时间内完成配送。

具体来说,平台可以通过以下步骤实时调整配送策略:

1. **实时监控**:通过实时监控系统,收集当前的订单量、骑手位置和交通状况等信息。
2. **策略调整**:根据实时情况,动态调整配送策略。例如,在高峰期,可以增加骑手的数量,或者调整配送范围,以应对订单激增的情况。
3. **实施与反馈**:将调整后的配送策略应用于实际配送中,并收集用户的反馈,不断调整和优化。

结合用户反馈持续优化

平台可以通过收集用户和骑手的反馈,不断优化订单池化算法。例如,根据用户的满意度和骑手的配送体验,调整订单组合和配送路径,提高整体服务质量。具体来说,平台可以定期收集用户的反馈,了解他们的满意度和需求,并据此调整订单池化算法。同时,平台还可以收集骑手的反馈,了解他们在配送过程中遇到的问题,并据此优化配送路径和策略。

具体来说,平台可以通过以下步骤结合用户反馈持续优化:

1. **用户反馈收集**:通过调查问卷、在线评价等方式,收集用户的反馈,了解他们的满意度和需求。
2. **骑手反馈收集**:通过访谈、问卷等方式,收集骑手的反馈,了解他们在配送过程中遇到的问题。
3. **数据分析**:通过分析这些反馈,找出存在的问题和改进的方向。
4. **算法优化**:根据分析结果,调整和优化订单池化算法。例如,可以根据用户的反馈,调整订单组合的优先级;或者根据骑手的反馈,优化配送路径。
5. **实施与反馈**:将优化后的算法应用于实际配送中,并继续收集用户的反馈,形成闭环优化。

信息来源:https://arxiv.org/abs/2406.14635

问 SCI.AI 读完这篇报道,继续问 SCI.AI 查询相关政策、航线、企业与历史背景。 继续提问
掌握供应链动态

每周一封邮件:精选供应链动态与新增风险事件,免费。

更习惯 RSS? 文章 风险事件

Welcome Back!

Login to your account below

Create New Account!

Fill the forms below to register

Retrieve your password

Please enter your username or email address to reset your password.

微信扫码分享

打开微信,扫描二维码分享给好友

QR Code

Add New Playlist