Reinforcement Learning from Optimization Proxy for Ride-Hailing Vehicle Relocation (Extended Abstract)

1 Introduction

The rapid growth of ride-hailing markets has transformed urban mobility, offering on-demand mobility services via mobile applications. While major ride-hailing platforms such as Uber and Didi leverage centralized dispatching algorithms to find good matching between drivers and riders, operational challenges persist due to frequent imbalances between demand and supply. Consider morning rush hours as an example: most trips originate from residential areas to business districts where a large number of vehicles accumulate and remain idle. Relocating these vehicles back to the demand areas is crucial to maintaining quality of service and income for the drivers.

∗The full paper has been published at Journal of Artificial Intelligence Research [Yuan et al., 2022]

Extensive studies have focused on vehicle relocation problems in real time. Existing methodologies fit broadly into two categories: model-based and model-free approaches. Modelbased approaches, e.g., Model Predictive Control (MPC) involves the solving of an optimization program using expected demand and supply information over a future horizon [Miao et al., 2015; Miao et al., 2017; Iglesias et al., 2017; Tsao et al., 2018; Riley et al., 2020]. Model-free approaches (predominantly Reinforcement Learning) train a state-based decision policy by interacting with the environment and observing the rewards [Verma et al., 2017; Lin et al., 2018; Wen et al., 2017; Holler et al., 2019; Oda and Joe-Wong, 2018; Gu´eriau and Dusparic, 2018; Lin et al., 2018; Jiao et al., 2021]. While both approaches have demonstrated promising performance in simulation and (in some cases) real-world deployment [Jiao et al., 2021], they have obvious drawbacks: the optimization needs to be solved in real-time and often trades off model fidelity (and hence solution quality) for computational efficiency. Reinforcement learning does not require a model but needs a large number of samples to train. Consequently, most work simplifies the problem (e.g., by restricting relocations to nearby regions and/or limiting coordination among the fleet) to reduce computational complexity.

This paper addresses these challenges by proposing a Reinforcement Learning from Optimization Proxy (RLOP) approach that combines optimization, supervised learning, and reinforcement learning. The RLOP framework is a special case of Reinforcement Learning from Expert Demonstration (RLED) where the expert is an optimization algorithm [Ram´ırez et al., 2021]. The RLOP has two main steps:

1. It first applies supervised learning to obtain an optimization proxy for a relocation optimization, i.e., it trains a machine learning model that approximates the mapping between the inputs of the optimization and its actionable decisions.
2. It then seeds an RL component with the optimization proxy as the initial policy. The RL component further improves this policy by interacting with the environment and capturing the real system dynamics and long-term effects that are beyond the capabilities of the modelbased optimization.

To the best of the authors' knowledge, this paper is the first application of an RLED framework to tackle vehicle relocation problems, and one of the few RL models with a fully centralized policy. The only other paper using a centralized formulation only demonstrates their approach in a simplified setting due to computational complexity [Mao et al., 2020].

The RLOP framework has three important benefits. First, The optimization proxy approximates the model-based optimization with high fidelity and is order of magnitude faster. Second, The RL component is significantly easier to train since it starts with a high-quality policy. Third, The RL component improves the optimization proxy by capturing longterm effects and real system dynamics present in sample trajectories.

The application of RLOP framework to relocation problems comes with several challenges. First, the relocation decisions are typically high-dimensional (e.g., number of vehicles to relocate between each zone) and sparse. This creates great difficulty for supervised and reinforcement learning. Second, the predicted relocation decisions may be infeasible since most learning algorithms cannot enforce integrality or physical constraints that the decisions need to satisfy.

To tackle these challenges, this paper proposes an aggregation-restoration-disaggregation procedure. It predicts the relocation decisions at an aggregated level, restores them back to feasible solutions, and then disaggregates them to the original granularity by applying a polynomial-time transportation optimization. As a result, the dimensionality and sparsity of the decisions are reduced considerably, and the approach remains computationally efficient.

The proposed RLOP framework is evaluated on the New York Taxi data set. The experimental results show that RLOP reduces the relocation costs by 10% while being order of magnitude faster than pure optimization and RL. These results suggest that the RLOP framework provides a promising approach for the real-time operations of ride-hailing systems. It is also important to stress that the RLOP framework is general and can be applied with any relocation optimization and RL techniques.

2 ProblemDefinition

The real-time ride-hailing system, depicted in Figure 1, has three key components: vehicle routing, idle vehicle relocation, and dynamic pricing. The vehicle routing algorithm matches requests to vehicles and chooses the vehicle routes. It operates at the individual request level with high frequency (e.g., every 15 - 60 seconds). Because of the tight time constraints and large number of requests, the routing algorithm is usually myopic, taking only the current demand and supply into account. Idle vehicle relocation and dynamic pricing, on the other hand, are forward-looking in nature. Idle vehicle relocation repositions the vehicles preemptively to anticipate demand, and dynamic pricing balances expected demand and supply in a future horizon. The two decisions also take place at a lower frequency (e.g., every 5 - 20 minutes). This paper focuses on idle vehicle relocation and abstracts away the other two components. The goal is to reduce rider waiting time by relocating idle vehicles while accounting for the relocation costs. This paper assumes that the ride-hailing platform uses a fleet of autonomous vehicles or their own pool of drivers who follow instructions exactly - the platform can thus relocate the vehicles at will.

3 The RLOP Framework

The RLOP framework has two stages: supervised learning and reinforcement learning. The supervised-learning stage trains an optimization proxy, i.e., a machine-learning model that approximates the actionable decisions of an optimization model. The reinforcement-learning stage takes the optimization proxy as the initial policy and refines it by a policy gradient method.

3.1 The Optimization Proxy

The supervised-learning stage trains a machine-learning model to predict the actionable decisions of a zone-level relocation model M : S → W where S is the model input andW is the relocation decision, i.e., the number of vehicles to relocate between each zone in the dispatch area. Hence |W| = |Z|2 , where Z is the set of zones in the dispatch area. The training data can be generated by running M on a set of problem instances and extracting its results. It is important to stress that the framework is general and can work with any relocation model as long as the decisions are at the zone-tozone level.

The machine-learning model takes the optimization model's input S and predicts its relocation decisions w = [xrij ]i,j∈Z - number of vehicles to relocate between each zone pair (i, j). In reality, w is high-dimensional (|W| = |Z|2 ) and sparse, since most vehicles relocate to a few high-demand zones. The high-dimensionality and sparsity makes supervised learning difficult. It also imposes significant challenges for RL in the second stage since sampling in highdimensional action space is expensive and makes the training unstable. Therefore, this paper designs an aggregationdisaggregation procedure - it predicts w at the aggregated (zone) level and then disaggregates the predictions via an efficient optimization procedure.

More precisely, the zone-level relocation decision a ∈ A - number of vehicles to relocate into and out of each zone i ∈ Z - is predicted by a machine-learning model ˆ Oθ : S → A, rounded and restored to a feasible solution, and disaggregated to zone-to-zone level by a transportation optimization problem T O : A → W. Since T O can be solved in polynomial time, the procedure remains computationally efficient. Readers are referred to the original paper for a detailed description of this procedure [Yuan et al., 2022]. To ensure that the machine-learning model can be refined by the policy gradient method in the RL stage, ˆ Oθ needs to be differentiable with respect to its parameters θ. For example, ˆ Oθ can be an artificial neural network or a linear regression parametrized by θ. The RLOP framework however is general and can accommodate any other machine-learning model.

3.2 Reinforcement Learning

The supervised-learning stage trains an optimization proxy ˆ Oθ : S → A from an relocation model. The RL process starts from ˆ Oθ and improves it by a policy gradient method. Specifically, the RL step models the relocation problem as a Markov Decision Process (MDP). MDP is characterized by a state space S, an action space A, a reward function R(s, a), a transition function P(s′ |s, a), and a discount factor γ ∈ [0, 1]. The goal is to find a stochastic decision policy πθ : S → P(A) parametrized by θ, i.e., a mapping from the state space to a probability distribution over the action space, that maximizes the total expected discounted reward

For the present application, the state and action space are the same as the input and output space of the optimization proxy ˆ Oθ : S → A so that ˆ Oθ can be transformed into an initial policy for RL. The details of this transformation will be presented shortly. The reward function R(st, at) = -ut -βvt is a weighted average of customer satisfaction and system cost, where ut is the total waiting time of riders who emerges in epoch t, vt is the expected time that vehicles will relocate due to action at, and β is a hyperparameter.

The policy is trained iteratively based on the policy gradient theorem [Sutton and Barto, 2018]

where Gt = ∑Te τ=t γ τ-tRτ is the total (discounted) reward since epoch t in the trajectory τ = (s0, a0,R0, ..., sTe , aTe ,RTe ) and Pπθ (at|st) is the probability of taking action at in state st under the decision policy πθ. In reality, the expectation term in (2) is intractable to compute and is approximated by Monte-Carlo sampling.

It remains to specify how the optimization proxy ˆ Oθ can be turned into an initial policy for RL. Recall that ˆ Oθ : S → A is a deterministic mapping from the state space to the action space. RL starts from a Gaussian policy π0 θ (·) = N( ˆ Oθ(·),Σ) centered around ˆ Oθ with covariance Σ. The covariance matrix Σ is a diagonal matrix whose diagonal entry Σii is the (sampling) variance of an relocation action ai (ai is an entry of a ∈ A). Note that ai is one of the prediction labels of ˆ Oθ, so its empirical distribution can be estimated in the supervised-learning stage. Therefore, Σii can be taken as a certain percentage of ai's characteristic statistics such as its empirical mean or median in the supervised-learning dataset. Prior knowledge on Σ is extremely valuable since a

Algorithm 1: RLOP

well-chosen Σ can lead to a more efficient exploration during training.

The policy gradient algorithm is summarized in Algorithm 1. Note that, after sampling action a from πθ, a should be rounded and restored to zone-to-zone level by the transportation optimization T O : A → W. Again, note that the RLOP framework is general and can incorporate any specific reinforcement-learning techniques (e.g., actor-critic, PPO, off-policy sampling, etc.) appropriate for the problem at hand.

4 Simulation Study

The RLOP framework is evaluated on Yellow Taxi Data in Manhattan, New York City [NYC, 2019]. It is trained from 2017/01 to 2017/05 and evaluated in 2017/06, 8am - 9am of weekdays, when the demand is at its peak and the need for relocation the greatest. The experiments use the end-to-end simulation framework in [Riley et al., 2020]. The simulator has two main components: a ride-sharing routing algorithm and a relocation MPC model. The routing algorithm batches riders into a time window and optimizes every 30 seconds. The relocation MPC model is executed every 5 minutes. It partitions the Manhattan area into 60 zones and time into 5minute epochs. All models must be executed in the 30 seconds batch window.

4.1 The Optimization Proxy

The optimization proxy approximates the MPC model in [Riley et al., 2020]. It is trained from 2017/01 to 2017/05. These daily instances are run by the simulator and the MPC model's inputs and outputs are extracted as training data. In total, 15, 000 data points are used in training and 2500 data points are held out for testing.

Several machine learning models are trained to learn the relocation decisions. The model inputs are expected demand Dit, expected supply Vit, and expected vehicle shortage (Dit-Vit) in each zone i and epoch t in the MPC horizon. The target is zone-level relocation decisions a. The testing loss is given in Table 1. MLP (multi-layer perceptron) is selected as the final model by virture of good performance and fewer parameters.

4.2 Reinforcement Learning

The optimization proxy is refined by reinforcement learning in 2017/05. Since the number of riders in most daily instances ranges from 22,000 to 29,000, four instances with [23960, 25768, 27117, 28312] riders are selected and the policy is trained on these representative instances. Algorithm 1 with the baseline is run with α = 0.005, β = 0.75 and γ = 0.75. The sampling variance Σii is taken as 0.05a0.75 i where a0.75 i is the 75th percentile of action ai in the supervised-learning data set (recall that ai is a prediction label for the optimization proxy). To make sure that RL does not overfit on the selected representative instances, the policy is validated on other instances in 2017/05 after each training episode and the algorithm stops when the average reward on the validation set fails to improve for 5 consecutive episodes. The training and validation curves (broken down into waiting and relocation time) in Figure 2 show that the relocation costs drop dramatically, while the waiting times stay about the same. The algorithm converges in 55 episodes: the training is significantly more efficient computationally than pure reinforcement learning algorithms, which typically converge in tens of thousands of episodes.

4.3 Evaluation Results

The trained policy is evaluated on weekdays in 2017/06. The proposed RLOP approach is compared with the optimization proxy as well as the MPC optimization. Pure reinforcement learning without an initial policy seeded with the optimization proxy (Algorithm 1 without step 1) fails to converge due to the high-dimensional state and action spaces: it is too expensive computationally to be applied in this setting. Table 2 reports average rider waiting time and vehicle relocation time (in minutes) as well as model run time (in secondss). RLOP achieves similar rider waiting time as the other two models but with less relocation cost. In particular, its relocation time is 10.1% lower than the MPC and 10.8% lower than the optimization proxy. Moreover, the optimization proxy and the RLOP are much faster than the MPC and are guaranteed to run in polynomial time. The longest MPC instance takes 9.73s while the optimization proxy and the RLOP framework remain within fractions of a second on all instances. The main computational cost of the RLOP framework lies in the offline stage where data for supervised learning and RL are generated through simulation. Nevertheless, RLOP is still more efficient than RL which requires a prohibitively large number of samples to train. The optimization proxy did slightly better than the MPC on certain metrics since the MPC optimization is based on an approximation of the ride-sharing system - its decisions are optimal for the approximation but not necessarily for the real system. Overall, these promising results show that the RLOP is an efficient and effective approach for idle vehicle relocation in real-time settings.

5 Conclusion

Preemptively relocating idle vehicles is crucial for addressing demand-supply imbalance that frequently arises in the ridehailing system. Current mainstream methodologies - optimization and reinforcement learning - suffer from computational complexity in either offline training or online deployment. This paper proposes a reinforcement learning from Optimization Proxy (RLOP) approach to alleviate their computational burden and search for better policies. It trains a machine-learning policy to approximate an optimization model and then refines the policy by reinforcement learning. To reduce dimensionality and sparsity of the prediction and action space, this paper presents an aggregationdisaggregation procedure which predicts relocation actions at the aggregated level and disaggregates the predictions via a polynomial-time optimization. On the New York City dataset, the RLOP approach achieves significantly lower relocation costs and computation time compared to the optimization model, while pure reinforcement learning is too expensive computationally for practical purposes.

Acknowledgments

This research is partly supported by NSF Awards 2112533 and 1854684. Many thanks to Professor Yao Xie for insightful comments on the paper.