SPO-VCS: An end-to-end smart predict-then-optimize framework with alternating differentiation method for relocation problems in large-scale vehicle crowd sensing

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 extensive spatio-temporal urban data through built-in smart sensors under diverse sensing scenarios. However, vehicle systems like taxis often exhibit biased coverage due to the heterogeneous nature of trip requests and varying routes. To achieve a high sensing coverage, a critical challenge lies in how to optimally relocate vehicles to minimize the divergence between the spatio-temporal distributions of vehicles 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 prediction. 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 using two real-world taxi datasets ranging from mid-size to large-scale in Hong Kong and Chengdu, China. 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 logistics and intelligent transportation systems.