Multi-Objective Online Ride-Matching

Problem Definition: The job of any marketplace is to facilitate the matching of supply with demand in real-time. Success is often measured using various metrics. The challenge is to design matching algorithms to balance the trade-offs among multiple objectives in a stochastic environment, to arrive at a “compromise” solution, which minimizes say the ℓp-norm-based distance function (for some 1 ≤p ≤∞) between the attained performance metrics and the target performances.Methodology/Results: We observe that the sample-average-approximation formulation of this multi-objective stochastic optimization problem can be solved by an online algorithm that uses only gradient information from “historical” (i.e., past) sample information, and not on the current state of the system. The online algorithm relies on a set of weight functions, which are updated adaptively over time, based on real-time tracking of the gaps in attained performance and the performance target. This allows us to recast the online algorithm as a randomized algorithm to solve the original stochastic problem. When the pre-determined performance targets are attainable, our randomized policy achieves the targets with a near-optimal performance guarantee (measured by regret, or deviation away from the optimal performance). When the targets are not attainable, our policy generates a compromise solution to the multi-objective stochastic optimization problem, even when the efficient frontier for this stochastic optimization problem cannot be explicitly characterized a-priori. We implement our model to address a challenge faced by a ride-sourcing platform, that matches passengers and drivers in real-time. Four performance metrics—platform revenue, driver service score, pick-up distance, and number of matched pairs—are simultaneously considered in the design of ride-matching algorithm, without pre-specifying the weight on each performance metric. This mechanism has been extensively tested using synthetic and real data.Managerial Implications: We show that under appropriate conditions, all parties in the ride-sourcing ecosystem, from drivers, passengers, to the platform, can be better off under our compromise matching policy, compared to other popular policies currently in use. In particular, the platform can obtain higher revenue, ensure better drivers (with higher service scores) are assigned more orders, and passengers are more likely to be matched to better drivers (albeit with a slight increase in the waiting time), compared to existing policies that focus on pick-up distance minimization. The ability to balance the conflicting goals in multiple objectives in a stochastic operating environment, has the potential to contribute to the long-term sustainable growth of ride-sourcing platforms.