Abstract
Modern resource allocation problems often involve a hybrid of static, pre-planned tasks and dynamic, real-time requests that compete for a shared pool of limited assets. This paper introduces the Two-Stage Resource Allocation (TS-RA) model to unify these offline and online phases. We propose the SAMP algorithm, an LP-guided sampling policy that provides robust performance guarantees based on resource sparsity. Empirical results using New York City’s Citibike data show that SAMP significantly outperforms standard greedy heuristics, maintaining high competitive ratios across varying operational conditions.
Introduction
In traditional resource allocation, researchers typically distinguish between two paradigms: offline scheduling, where all information is known beforehand, and online matching, where requests arrive sequentially and require immediate decisions. However, modern matching markets—most notably bike-sharing systems—frequently operate across both domains simultaneously. For instance, a bike-sharing operator might use trucks to rebalance inventory between stations overnight (the Offline Phase) while offering user incentives to manage demand during the morning rush (the Online Phase).
Both phases compete for the same finite resources, such as the total operational budget and the available bike fleet. The primary challenge lies in optimizing resource expenditure in the first phase without full knowledge of future online arrivals, ensuring that high-value offline tasks do not inadvertently block even higher-value online opportunities. The TS-RA model addresses this by jointly optimizing both stages within a single framework.
Methods
To solve the TS-RA problem, we propose the SAMP (LP-guided sampling policy) algorithm. SAMP leverages a benchmark Linear Program (LP) that serves as an "ideal" upper bound on total profit by incorporating arrival probabilities and budget constraints.
The SAMP Algorithm
- Phase I (Offline): The algorithm samples assignments based on the LP's optimal solution, adjusted by a scaling factor ($\eta$). To maintain feasibility, an "alteration" step discards any samples that would violate the budget.
- Phase II (Online): As new requests arrive, the algorithm continues to sample potential matches based on the LP, executing only those that are "safe" relative to the remaining resources.
The Role of Sparsity
A key technical contribution is that SAMP's performance guarantee is tied to resource sparsity ($\ell$)—the maximum number of distinct resources any single assignment requires (e.g., one bike and one station). By tying performance to $\ell$ rather than the total number of resources ($K$), SAMP remains highly scalable for complex urban networks.
Results
The researchers evaluated the TS-RA model using real-world data from New York City’s Citibike system. Focusing on Manhattan’s 374 stations, the study clustered these into 50 sites and analyzed the top 10 supplying and demanding locations during peak morning hours. Using 34 days of historical data to model arrival distributions, SAMP was tested against various greedy heuristics.
Empirical Superiority
The empirical results highlight SAMP’s superiority. Across all tested scenarios, SAMP maintained a competitive ratio approximately 0.3 higher than the best greedy baselines. As illustrated in Figure 1, SAMP exhibits remarkable stability. While greedy methods struggle as the cost of offline labor ($\lambda$) increases or as arrival rates ($\beta$) fluctuate, SAMP variants consistently approach the theoretical optimum. This robustness confirms that using a global "weather map" provided by the LP leads to better local decision-making than myopic greedy strategies.
Conclusion
The TS-RA model and SAMP algorithm represent a significant step toward unifying static and dynamic resource allocation. By focusing on resource sparsity and LP-guided sampling, the framework provides both strong theoretical guarantees and practical performance gains in real-world applications like bike-sharing. Future research will explore the integration of online learning to handle non-stationary arrival distributions and investigate the structural properties of real-world networks that allow SAMP to exceed its worst-case theoretical bounds.
Summary updated