# SPO-VCS: An End-to-End Smart Predict-then-Optimize Framework with Alternating Differentiation Method for Relocation Problems in Large-Scale Vehicle Crowd Sensing

arXiv: https://arxiv.org/abs/2411.18432 · HTML: https://mlsanity.com/paper/2411.18432/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 82 references that are in the map.
- First posted on arXiv 27 Nov 2024.

## Builds on (most cited first, 23 of 23)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [T-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction](https://mlsanity.com/paper/1811.05320/) (2018)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems](https://mlsanity.com/paper/1911.10092/) (2019)
- [Is Attention Better Than Matrix Decomposition?](https://mlsanity.com/paper/2109.04553/) (2021)
- [On Training Implicit Models](https://mlsanity.com/paper/2111.05177/) (2021)
- [Reinforcement Learning for Ridesharing: An Extended Survey](https://mlsanity.com/paper/2105.01099/) (2021)
- [Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning](https://mlsanity.com/paper/2103.04555/) (2021)
- [Alternating Differentiation for Optimization Layers](https://mlsanity.com/paper/2210.01802/) (2022)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [Joint predictions of multi-modal ride-hailing demands: a deep multi-task multigraph learning-based approach](https://mlsanity.com/paper/2011.05602/) (2020)
- [Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas: A Receding Horizon Control Approach](https://mlsanity.com/paper/1603.04418/) (2016)
- [Reward Design for Driver Repositioning Using Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2002.06723/) (2020)
- [Model Predictive Control of Autonomous Mobility-on-Demand Systems](https://mlsanity.com/paper/1509.03985/) (2015)
- [Deep-MAPS: Machine Learning based Mobile Air Pollution Sensing](https://mlsanity.com/paper/1904.12303/) (2019)
- [A survey of urban drive-by sensing: An optimization perspective](https://mlsanity.com/paper/2302.00622/) (2023)
- [HyTasker: Hybrid Task Allocation in Mobile Crowd Sensing](https://mlsanity.com/paper/1805.08480/) (2018)
- [DROP: Deep relocating option policy for optimal ride-hailing vehicle repositioning](https://mlsanity.com/paper/2109.04149/) (2021)
- [Exploring the drive-by sensing power of bus fleet through active scheduling](https://mlsanity.com/paper/2211.13414/) (2022)
- [Trip-based mobile sensor deployment for drive-by sensing with bus fleets](https://mlsanity.com/paper/2302.11489/) (2023)

## Abstract (arXiv)

Ubiquitous mobile devices have catalyzed the development of vehicle crowd sensing (VCS). In particular, vehicle sensing systems show great potential in the flexible acquisition of spatio-temporal urban data through built-in sensors under diverse sensing scenarios. However, vehicle systems often exhibit biased coverage due to the heterogeneous nature of trip requests and routes. To achieve a high sensing coverage, a critical challenge lies in optimally relocating vehicles to minimize the divergence between vehicle distributions and target sensing distributions. Conventional approaches typically employ a two-stage predict-then-optimize (PTO) process: first predicting real-time vehicle distributions and subsequently generating an optimal relocation strategy based on the predictions. However, this approach can lead to suboptimal decision-making due to the propagation of errors from upstream prediction. To this end, we develop an end-to-end Smart Predict-then-Optimize (SPO) framework by integrating optimization into prediction within the deep learning architecture, and the entire framework is trained by minimizing the task-specific matching divergence rather than the upstream prediction error. Methodologically, we formulate the vehicle relocation problem by quadratic programming (QP) and incorporate a novel unrolling approach based on the Alternating Direction Method of Multipliers (ADMM) within the SPO framework to compute gradients of the QP layer, facilitating backpropagation and gradient-based optimization for end-to-end learning. The effectiveness of the proposed framework is validated by real-world taxi datasets in Hong Kong. Utilizing the alternating differentiation method, the general SPO framework presents a novel concept of addressing decision-making problems with uncertainty, demonstrating significant potential for advancing applications in intelligent transportation systems.