Abstract
Optimizing facility locations in a network is challenging when agent mobility is uncertain. This paper introduces the Robust Reward Placement (RRP) problem, which aims to maximize the worst-case performance ratio across multiple Markov Mobility Models. We prove RRP is NP-hard and propose $\Psi$-Saturate, a bicriteria approximation algorithm that balances performance guarantees with budget constraints. Extensive evaluations on synthetic and real-world Baidu Map data demonstrate the effectiveness and scalability of our approach.
Introduction
Optimizing facility locations in a network is a critical task for urban planning and marketing. While historical data provides a baseline for movement patterns, real-world mobility is dynamic, influenced by factors like weather, holidays, or construction. A placement optimized for a sunny day might perform poorly during a storm.
The Robust Reward Placement (RRP) problem addresses this uncertainty by modeling movement as a set of possible Markov Mobility Models (MMMs). The goal is to find a set of locations that performs well regardless of which scenario occurs. Specifically, the objective is to maximize the minimum ratio of collected reward to the optimal reward possible for each specific scenario, ensuring robustness across diverse conditions.
Methodology
RRP is established as both NP-hard and inapproximable within a constant factor in polynomial time. To overcome this, the researchers propose $\Psi$-Saturate, a bicriteria approximation algorithm. It uses binary search on the target ratio combined with a greedy selection process. It guarantees a solution within $\epsilon$ of the optimal ratio, provided the budget can be slightly exceeded (by a factor logarithmic in the number of mobility models).
Several baseline heuristics are compared:
- All Greedy: Solves the problem for each model individually and picks the best resulting set.
- Myopic: A standard greedy approach based on marginal gain.
- Best-Worst Search (BWS): Specifically targets the worst-performing scenario.
- DP-RRP: A dynamic programming approach adapted from the Max-Min Knapsack problem.
Experimental Evaluation
The algorithms were tested on synthetic networks (Erdős-Rényi and Scale-Free graphs) and real-world movement records from Baidu Map in Nanjing, China. The real-world dataset featured over 51,000 nodes and 13 distinct mobility graphs representing different weekly periods.
Key Results and Discussion
The experimental results highlight the trade-offs between solution quality and computational efficiency across different network topologies.
Key findings include:
- Performance: $\Psi$-Saturate consistently outperforms simple heuristics on random graphs. DP-RRP often finds the highest quality solutions but suffers from quadratic scaling, making it less suitable for very large state spaces.
- Scalability: Most proposed algorithms, including $\Psi$-Saturate, scale linearly with the graph size, proving practical for city-scale applications.
- Robustness Trends: The achievable robustness score generally decreases as the number of possible mobility models increases, reflecting the increased difficulty of satisfying an "adversarial" range of scenarios.
Conclusion
This work provides a robust framework for facility placement under mobility uncertainty. By focusing on the performance ratio rather than absolute rewards, the RRP model ensures fair treatment across scenarios with different inherent activity levels. Future research will explore optimizing the content of rewards to further influence agent behavior in these uncertain environments.
Summary updated