用多重最小生成树构建高效抗毁的外卖配送网络
Multi-Agent Training-free Urban Food Delivery System using Resilient UMST Network
- 通过随机扰动生成多棵最小生成树并合并，实现稀疏但鲁棒的网络结构
- 相比全连接图减少20至40倍边数，订单拼单参与率达75%~83%
- 无需训练即可达到96%成功率，速度比学习模型快30倍，适合城市配送系统
配送系统已成为城市生活的核心，支撑食物、药品及其他商品需求。然而传统物流网络脆弱，难以应对道路封闭、事故及需求波动。在线外卖平台现为城市物流支柱，全球市场规模预计2030年将超5000亿美元。设计高效且具韧性的配送网络仍是重大挑战：全连接图虽灵活但计算不可行，单一最小生成树（MST）虽高效却易受破坏。本文提出最小生成树并集（UMST）方法，通过随机边扰动生成多棵MST并合并，构建稀疏而鲁棒的配送网络。在多个美国城市测试中，UMST相较全连接图减少20–40×边数，同时实现75%–83%的订单拼单参与率。相比基于学习的基线方法（如MADDPG和图神经网络），UMST无需训练即可达到88%–96%的成功率与44%–53%的距离节省，执行速度提升30倍，并保持可解释的路由结构。其结构效率与运营灵活性结合，为城市配送网络提供可扩展、抗毁的基础。
原文摘要 · Abstract (English)
Delivery systems have become a core part of urban life, supporting the demand for food, medicine, and other goods. Yet traditional logistics networks remain fragile, often struggling to adapt to road closures, accidents, and shifting demand. Online Food Delivery (OFD) platforms now represent a cornerstone of urban logistics, with the global market projected to grow to over 500 billion USD by 2030. Designing delivery networks that are efficient and resilient remains a major challenge: fully connected graphs provide flexibility but are computationally infeasible at scale, while single Minimum Spanning Trees (MSTs) are efficient but easily disrupted. We propose the Union of Minimum Spanning Trees (UMST) approach to construct delivery networks that are sparse yet robust. UMST generates multiple MSTs through randomized edge perturbations and unites them, producing graphs with far fewer edges than fully connected networks while maintaining multiple alternative routes between delivery hotspots. Across multiple U.S. cities, UMST achieves 20--40$\times$ fewer edges than fully connected graphs while enabling substantial order bundling with 75--83% participation rates. Compared to learning-based baselines including MADDPG and Graph Neural Networks, UMST delivers competitive performance (88-96% success rates, 44-53% distance savings) without requiring training, achieving 30$\times$ faster execution while maintaining interpretable routing structures. Its combination of structural efficiency and operational flexibility offers a scalable and resilient foundation for urban delivery networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。