arXiv:2501.19208stat.MLcs.LG2025-01

解决共享出行中车辆位置重配难题,用简单策略实现近优性能。

Spatial Supply Repositioning with Censored Demand Data

  • 提出多站点基线库存重配策略,适用于需求相关网络。
  • 在历史数据下可高效计算最优策略,在线学习中达到最优后悔率。
  • 适合关注共享交通调度与数据受限场景的从业者和研究者。

本文研究由单向按需车辆共享服务启发的网络库存系统。在不确定且相关的网络需求下,运营商需周期性重配车辆,以将固定供给匹配至空间分布的需求,同时最小化成本。在一般库存网络中寻找最优重配策略在分析和计算上均具挑战性。本文引入一种基线库存重配策略,作为经典库存规则在n个地点的多维推广,并在两个实际相关情形下证明其渐近最优性。通过精确重构,可在离线设置中高效计算最佳基线策略。在在线设置中,通过后悔下界分析揭示了在网络系统中带截断数据学习的挑战,并证明了其他算法的次优性。本文提出代理优化与自适应重配算法,证明其达到最优后悔率 $O(n^{2.5} \ sqrt{T})$,该结果在T上与下界一致,且对n为多项式依赖。研究表明,库存重配对共享出行商业模式的可行性至关重要,而数据与网络复杂性带来了内在挑战。结果表明,如本文分析的状态无关基线策略等简单、可解释的策略,可提供显著实用价值并实现近优性能。

原文摘要 · Abstract (English)

We consider a network inventory system motivated by one-way, on-demand vehicle sharing services. Under uncertain and correlated network demand, the service operator periodically repositions vehicles to match a fixed supply with spatial customer demand while minimizing costs. Finding an optimal repositioning policy in such a general inventory network is analytically and computationally challenging. We introduce a base-stock repositioning policy as a multidimensional generalization of the classical inventory rule to $n$ locations, and we establish its asymptotic optimality under two practically relevant regimes. We present exact reformulations that enable efficient computation of the best base-stock policy in an offline setting with historical data. In the online setting, we illustrate the challenges of learning with censored data in networked systems through a regret lower bound analysis and by demonstrating the suboptimality of alternative algorithmic approaches. We propose a Surrogate Optimization and Adaptive Repositioning algorithm and prove that it attains an optimal regret of $O(n^{2.5} \sqrt{T})$, which matches the regret lower bound in $T$ with polynomial dependence on $n$. Our work highlights the critical role of inventory repositioning in the viability of shared mobility businesses and illuminates the inherent challenges posed by data and network complexity. Our results demonstrate that simple, interpretable policies, such as the state-independent base-stock policies we analyze, can provide significant practical value and achieve near-optimal performance.

库存优化共享出行在线学习数据截断

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