arXiv:2311.01534v4 宣告类型: replace-cross 摘要: 在本文中，我们关注大型城市环境中自主多代理出租车路由问题，其中未来乘车请求的位置和数量事先未知，但可以通过经验分布进行估计。最近的理论表明，具有稳定基础策略的展开算法会产生接近最优的稳定策略。在路由设置中，如果执行过程能够保持未解决请求的数量随时间均匀有界，那么策略是稳定的。尽管基于展开的方法非常适合学习考虑未来需求的协作多代理策略，但在大型城市环境中应用此类方法可能会因为需要大量出租车以确保稳定性而代价高昂。本文旨在通过提出一个近似的两阶段多代理展开算法来解决多代理展开的计算瓶颈，从而降低计算成本，同时仍然实现一个接近最优的稳定策略。我们的方法根据预测需求和用户计算资源所能运行的最大出租车数量，将图划分成区域。然后该算法应用瞬时分配（IA）重新平衡各区域中的出租车，并在每个区域并行执行涉及整个区域的多代理展开算法。我们提供了两个主要的理论成果：1）表征确保瞬时分配稳定性的所需出租车数 $m$；2）推导出随时间推移确保瞬时分配稳定性的 $m$ 的必要条件。我们的数值结果表明，我们的方法能够确保满足理论条件的 $m$ 数值实现稳定性。我们还通过实验证明，我们提出的两阶段算法在整个地图上逐个执行的展开算法具有同等性能，但运行时间显著较低。