Learning Model-Based Vehicle-Relocation Decisions for Real-Time Ride-Sharing: Hybridizing Learning and Optimization

• URL: http://arxiv.org/abs/2105.13461v1
• Date: Thu, 27 May 2021 21:48:05 GMT
• Title: Learning Model-Based Vehicle-Relocation Decisions for Real-Time Ride-Sharing: Hybridizing Learning and Optimization
• Authors: Enpeng Yuan, Pascal Van Hentenryck
• Abstract summary: Large-scale ride-sharing systems combine real-time dispatching and routing optimization over a rolling time horizon. MPC component that relocates idle vehicles to anticipate the demand operates over a longer time horizon. This paper proposes a hybrid approach that combines machine learning and optimization.
• Score: 15.80796896560034
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale ride-sharing systems combine real-time dispatching and routing optimization over a rolling time horizon with a model predictive control(MPC) component that relocates idle vehicles to anticipate the demand. The MPC optimization operates over a longer time horizon to compensate for the inherent myopic nature of the real-time dispatching. These longer time horizons are beneficial for the quality of the decisions but increase computational complexity. To address this computational challenge, this paper proposes a hybrid approach that combines machine learning and optimization. The machine-learning component learns the optimal solution to the MPC optimization on the aggregated level to overcome the sparsity and high-dimensionality of the MPC solutions. The optimization component transforms the machine-learning predictions back to the original granularity via a tractable transportation model. As a consequence, the original NP-hard MPC problem is reduced to a polynomial time prediction and optimization. Experimental results show that the hybrid approach achieves 27% further reduction in rider waiting time than the MPC optimization, thanks to its ability to model a longer time horizon within the computational limits.

Related papers

• Transformer-based Model Predictive Control: Trajectory Optimization via Sequence Modeling [16.112708478263745]
  We present a unified framework combine the main strengths of optimization-based methods for learning. Our approach entails embedding high-capacity, transformer-based neural network models within optimization process. Compared to purely optimization-based approaches, results show that our approach can improve performance by up to 75%.
  arXiv  Detail & Related papers  (2024-10-31T13:23:10Z)
• Fractional Deep Reinforcement Learning for Age-Minimal Mobile Edge Computing [11.403989519949173]
  This work focuses on the timeliness of computational-intensive updates, measured by Age-ofInformation (AoI) We study how to jointly optimize the task updating and offloading policies for AoI with fractional form. Experimental results show that our proposed algorithms reduce the average AoI by up to 57.6% compared with several non-fractional benchmarks.
  arXiv  Detail & Related papers  (2023-12-16T11:13:40Z)
• Deep Model Predictive Optimization [21.22047409735362]
  A major challenge in robotics is to design robust policies which enable complex and agile behaviors in the real world. We propose Deep Model Predictive Optimization (DMPO), which learns the inner-loop of an MPC optimization algorithm directly via experience. DMPO can outperform the best MPC algorithm by up to 27% with fewer samples and an end-to-end policy trained with MFRL by 19%.
  arXiv  Detail & Related papers  (2023-10-06T21:11:52Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• A Meta-Learning Based Precoder Optimization Framework for Rate-Splitting Multiple Access [53.191806757701215]
  We propose the use of a meta-learning based precoder optimization framework to directly optimize the Rate-Splitting Multiple Access (RSMA) precoders with partial Channel State Information at the Transmitter (CSIT) By exploiting the overfitting of the compact neural network to maximize the explicit Average Sum-Rate (ASR) expression, we effectively bypass the need for any other training data while minimizing the total running time. Numerical results reveal that the meta-learning based solution achieves similar ASR performance to conventional precoder optimization in medium-scale scenarios, and significantly outperforms sub-optimal low complexity precoder algorithms in the large-scale
  arXiv  Detail & Related papers  (2023-07-17T20:31:41Z)
• Time-sensitive Learning for Heterogeneous Federated Edge Intelligence [52.83633954857744]
  We investigate real-time machine learning in a federated edge intelligence (FEI) system. FEI systems exhibit heterogenous communication and computational resource distribution. We propose a time-sensitive federated learning (TS-FL) framework to minimize the overall run-time for collaboratively training a shared ML model.
  arXiv  Detail & Related papers  (2023-01-26T08:13:22Z)
• Predictive GAN-powered Multi-Objective Optimization for Hybrid Federated Split Learning [56.125720497163684]
  We propose a hybrid federated split learning framework in wireless networks. We design a parallel computing scheme for model splitting without label sharing, and theoretically analyze the influence of the delayed gradient caused by the scheme on the convergence speed.
  arXiv  Detail & Related papers  (2022-09-02T10:29:56Z)
• Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
  We introduce a spectral efficiency optimization approach in vehicular OCC. We model the optimization problem as a Markov decision process (MDP) to enable the use of solutions that can be applied online. We verify the performance of our proposed scheme through extensive simulations and compare it with various variants of our approach and a random method.
  arXiv  Detail & Related papers  (2022-05-05T14:25:54Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks. In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
  arXiv  Detail & Related papers  (2022-03-26T20:37:14Z)
• Learning Model Predictive Controllers for Real-Time Ride-Hailing Vehicle Relocation and Pricing Decisions [15.80796896560034]
  Large-scale ride-hailing systems often combine real-time routing at the individual request level with a macroscopic Model Predictive Control (MPC) optimization for dynamic pricing and vehicle relocation. This paper addresses these computational challenges by learning the MPC optimization. The resulting machine-learning model then serves as the optimization proxy and predicts its optimal solutions.
  arXiv  Detail & Related papers  (2021-11-05T00:52:15Z)
• Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with Heterogeneous Learning Tasks [53.1636151439562]
  Mobile edge computing (MEC) provides a natural platform for AI applications. We present an infrastructure to perform machine learning tasks at an MEC with the assistance of a reconfigurable intelligent surface (RIS) Specifically, we minimize the learning error of all participating users by jointly optimizing transmit power of mobile users, beamforming vectors of the base station, and the phase-shift matrix of the RIS.
  arXiv  Detail & Related papers  (2020-12-25T07:08:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.