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, Donghui Li, Jie Feng, Chen Zhang, Xuetao Ding, Jinghua Hao, Renqing He
分类: cs.AI, cs.LG
发布日期: 2024-06-20
备注: Accepted in KDD 2024 ADS Track
💡 一句话要点
提出SCDN模型，利用骑手经验增强图表示学习，优化即时众包订单分配。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 即时配送 订单池化 图神经网络 异构图嵌入 骑手经验学习
📋 核心要点
- 即时配送中订单池化是提升效率的关键，但实时性和复杂性限制了传统方法的应用，且离线环境存在诸多未知因素。
- 论文构建熟练骑手配送网络（SCDN），通过图嵌入学习骑手经验，挖掘潜在的订单组合，缩小搜索空间。
- SCDN已在美团部署，显著提升订单池化质量和骑手效率，高峰期效率提升45-55%，同时保证交付时效。
📝 摘要（中文）
本文针对即时配送（OFD）服务中，如何在保证消费者和骑手体验的同时，通过订单池化提高平台效率这一关键问题，提出了一种基于熟练骑手（SC）配送网络的解决方案。由于订单分配的复杂性和实时性，以及离线环境中的未知因素，传统的订单合并方法面临挑战。本文构建了一个SC配送网络（SCDN），利用增强的属性异构网络嵌入方法，从丰富的时空信息中提取特征，挖掘SC轨迹中潜在的订单组合。通过低维向量的可扩展相似度计算，有效缩小订单分配的搜索空间，从而更容易地识别全面且高质量的池化结果。SCDN已在美团调度系统中部署，在线测试表明，池化质量和范围得到显著提高，在中午高峰时段，系统可以将骑手的效率提高45-55%，同时保证及时的交付承诺。
🔬 方法详解
问题定义：即时配送场景下，如何在实时订单分配中高效地进行订单池化，以提高平台效率并兼顾消费者和骑手的体验。现有方法受限于订单分配的复杂性和实时性要求，难以进行大规模计算，且离线环境的未知因素使得订单池化决策面临挑战。
核心思路：利用熟练骑手（SC）的经验，他们对环境有深入了解，其配送行为蕴含了潜在的订单组合信息。通过学习SC的配送轨迹，可以提升系统对环境的感知能力，从而指导订单池化决策。
技术框架：整体框架包括以下几个阶段：1) 构建熟练骑手配送网络（SCDN），这是一个属性异构网络，节点包括订单、骑手、地点等，边表示骑手的配送行为。2) 使用增强的属性异构网络嵌入方法，从SCDN中学习节点的低维向量表示，捕捉时空信息和潜在的订单组合关系。3) 利用学习到的向量表示，通过相似度计算来评估不同订单组合的质量，从而缩小订单分配的搜索空间。4) 在实时订单分配过程中，根据相似度计算结果，选择高质量的订单组合进行池化。
关键创新：关键创新在于利用熟练骑手的经验来指导订单池化。与传统方法相比，SCDN能够更好地感知环境，挖掘潜在的订单组合，从而提高订单池化的质量和效率。此外，通过图嵌入学习低维向量表示，可以实现可扩展的相似度计算，满足实时性要求。
关键设计：SCDN是一个属性异构网络，节点属性包括订单的起止位置、时间戳、价格等，骑手的历史配送数据等。增强的属性异构网络嵌入方法包括节点嵌入、边嵌入和属性嵌入三个部分，分别学习节点的结构信息、边的关系信息和节点的属性信息。损失函数包括结构损失、属性损失和对比损失，用于优化嵌入向量的质量。相似度计算采用余弦相似度，用于评估不同订单组合的质量。
🖼️ 关键图片
📊 实验亮点
在线测试表明，SCDN在美团调度系统中部署后，显著提高了订单池化的质量和范围。在中午高峰时段，骑手的效率提高了45-55%，同时保证了及时的交付承诺。这些数据表明，SCDN能够有效地利用熟练骑手的经验，优化订单分配策略，从而提高整体的配送效率。
🎯 应用场景
该研究成果可广泛应用于即时配送、外卖、跑腿等O2O服务领域，通过优化订单分配策略，提高配送效率，降低运营成本，提升用户体验。此外，该方法还可以扩展到其他涉及资源分配和路径规划的场景，例如车辆调度、物流配送等。
📄 摘要（原文）
The recent past has witnessed a notable surge in on-demand food delivery (OFD) services, offering delivery fulfillment within dozens of minutes after an order is placed. In OFD, pooling multiple orders for simultaneous delivery in real-time order assignment is a pivotal efficiency source, which may in turn extend delivery time. Constructing high-quality order pooling to harmonize platform efficiency with the experiences of consumers and couriers, is crucial to OFD platforms. However, the complexity and real-time nature of order assignment, making extensive calculations impractical, significantly limit the potential for order consolidation. Moreover, offline environment is frequently riddled with unknown factors, posing challenges for the platform's perceptibility and pooling decisions. Nevertheless, delivery behaviors of skilled couriers (SCs) who know the environment well, can improve system awareness and effectively inform decisions. Hence a SC delivery network (SCDN) is constructed, based on an enhanced attributed heterogeneous network embedding approach tailored for OFD. It aims to extract features from rich temporal and spatial information, and uncover the latent potential for order combinations embedded within SC trajectories. Accordingly, the vast search space of order assignment can be effectively pruned through scalable similarity calculations of low-dimensional vectors, making comprehensive and high-quality pooling outcomes more easily identified in real time. SCDN has now been deployed in Meituan dispatch system. Online tests reveal that with SCDN, the pooling quality and extent have been greatly improved. And our system can boost couriers'efficiency by 45-55% during noon peak hours, while upholding the timely delivery commitment.