arXiv:2412.17252cs.LGmath.OC2024-12被引 1

用博弈论优化无人机与地面车协同送货,提升城市末端配送效率。

A Coalition Game for On-demand Multi-modal 3D Automated Delivery System

  • 构建无人机与自动配送车的联盟博弈模型,实现多模式协同调度。
  • 在密西沙加市案例中,相比传统方法,配送效率显著提升且适应复杂约束。
  • 适用于高密度城区、紧急配送等实际场景,适合智能物流研究者参考。

我们提出一种基于联盟博弈的多模态自主配送优化框架,用于城市环境中由无人机(UAVs)和自动配送机器人(ADRs)组成的两层重叠网络,解决高密度区域及时间敏感型应用下的末端配送问题。该问题被建模为带时间窗约束的多起点取送问题,需考虑电池续航、任务先后时窗及建筑遮挡等运营限制。通过联盟博弈理论,研究不同配送模式间的合作结构,探索战略协作如何提升整体路径效率。设计了一种广义强化学习模型,用于评估成本分摊与分配机制,以学习多种真实场景下的合作行为。方法采用端到端深度多智能体策略梯度算法,结合新颖的时空邻域图注意力网络与异构边增强注意力模型及变换器架构。在密西沙加市的多个数值实验表明,尽管图网络覆盖范围广、训练结构复杂,该模型仍能有效处理现实运营约束,生成高质量解,优于现有基于变换器与经典方法。模型对非均匀数据分布表现良好,具备跨尺度与配置的泛化能力,在随机场景下展现稳健的协同性能,联盟分析与成本分配结果充分体现了合作优势。

原文摘要 · Abstract (English)

We introduce a multi-modal autonomous delivery optimization framework as a coalition game for a fleet of UAVs and ADRs operating in two overlaying networks to address last-mile delivery in urban environments, including high-density areas and time-critical applications. The problem is defined as multiple depot pickup and delivery with time windows constrained over operational restrictions, such as vehicle battery limitation, precedence time window, and building obstruction. Utilizing the coalition game theory, we investigate cooperation structures among the modes to capture how strategic collaboration can improve overall routing efficiency. To do so, a generalized reinforcement learning model is designed to evaluate the cost-sharing and allocation to different modes to learn the cooperative behaviour with respect to various realistic scenarios. Our methodology leverages an end-to-end deep multi-agent policy gradient method augmented by a novel spatio-temporal adjacency neighbourhood graph attention network using a heterogeneous edge-enhanced attention model and transformer architecture. Several numerical experiments on last-mile delivery applications have been conducted, showing the results from the case study in the city of Mississauga, which shows that despite the incorporation of an extensive network in the graph for two modes and a complex training structure, the model addresses realistic operational constraints and achieves high-quality solutions compared with the existing transformer-based and classical methods. It can perform well on non-homogeneous data distribution, generalizes well on different scales and configurations, and demonstrates a robust cooperative performance under stochastic scenarios across various tasks, which is effectively reflected by coalition analysis and cost allocation to signify the advantage of cooperation.

智能物流多智能体博弈论配送优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。