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

  • 2021-07-21 16:39:16
  • Enpeng Yuan, Pascal Van Hentenryck
  • 0

Abstract

Large-scale ride-sharing systems combine real-time dispatching and routingoptimization over a rolling time horizon with a model predictive control (MPC)component that relocates idle vehicles to anticipate the demand. The MPCoptimization operates over a longer time horizon to compensate for the inherentmyopic nature of the real-time dispatching. These longer time horizons arebeneficial for the quality of relocation decisions but increase computationalcomplexity. Consequently, the ride-sharing operators are often forced to use arelatively short time horizon. To address this computational challenge, thispaper proposes a hybrid approach that combines machine learning andoptimization. The machine-learning component learns the optimal solution to theMPC on the aggregated level to overcome the sparsity and high-dimensionality ofthe solution. The optimization component transforms the machine-learningprediction back to the original granularity through a tractable transportationmodel. As a consequence, the original NP-hard MPC problem is reduced to apolynomial time prediction and optimization, which allows the ride-sharingoperators to consider a longer time horizon. Experimental results show that thehybrid approach achieves significantly better service quality than the MPCoptimization in terms of average rider waiting time, due to its ability tomodel a longer horizon.

 

Quick Read (beta)

loading the full paper ...