Featured Research

On-demand matching and repositioning with Optimization & Reinforcement Learning

The ubiquitous Global Position System (GPS) based technology enables ride-sourcing companies to track real-time locations of drivers and passengers, such that these companies can match drivers and passengers more efficiently to reduce search frictions. One of the essential components of platform operations is the algorithm design for on-demand matching between passengers and drivers (i.e., dispatching passengers’ order to idle drivers), which significantly affects system performance and service quality. Our study points out that there are two key decision variables–matching time interval and matching radius–that governs the system performance of on-demand matching process. By virtue of a mathematical model for approximating on-demand matching process, we are able to determine the optimal combination of matching time interval and radius for maximizing the system performance under different spatial-temporal supply and demand conditions. Additionally, by modelling the dynamic ride-sourcing system as a Markov Decision Process, we develop a novel reinforcement learning algorithm to dynamically control matching time intervals to maximize the system performance over a long horizon. In order to seamlessly integrate ride-sourcing service into the existing multi-modal transportation system, we also propose a reinforcement learning based framework to coordinate ride-sourcing and public transit service through real-time order dispatching. Experimental results show that our proposed model can increase platform revenue by 5% and increase order fulfillment rate by 10%, compared to traditional order dispatching algorithms.

Modelling and economical analysis of on-demand mobility markets

As a symbolic icon for shared mobility in recent years, ride-sourcing service, provided by digital platforms like DiDi, Uber and Lyft, has been playing an increasingly important role in meeting mobility needs by efficiently connecting passengers and dedicated drivers through online platforms. Despite its great success in business, ride-sourcing service has also aroused many challenging issues in both platform operations and government regulations. From the perspective of a ride-sourcing platform, the main question is how to design suitable operating strategies in terms of pricing, waging, matching, idle vehicle repositioning, demand estimation, etc. to improve system efficiency and maximize its profit. From the perspective of a public regulator or government, the major question is how to induce the platform to choose a socially desirable operating strategy to well balance benefits of different stakeholders (such as passengers, drivers and the platform), alleviate traffic congestion, and reduce motor vehicle exhaust emission.

These questions are non-trivial because of the complex interactions between the strategic behaviors of multiple stakeholders in a ride-sourcing market. A ride-sourcing market is a two-sided market consisting of two groups of participants, i.e., drivers and passengers. On the demand side, potential passengers compare ride-sourcing service with other transportation modes, such as conventional street-hailing taxis and public transit, by evaluating the trip fare charged by the platform and service quality (e.g., waiting time until pick-up). On the supply side, drivers determine whether to work and when and how long to work mainly in response to their expected earning level, which depends on wage rate and vehicle’s utilization rate. A ride-sourcing platform aims to maximize profit or social welfare by leveraging various decision variables, such as the trip fare rate charged on passengers, wage rate paid to drivers, on-demand matching mechanisms, while taking into account the impact of its decisions on both passengers and drivers. Additionally, a government or public-sector regulator can affect the platform’s decisions and the resulting system equilibrium by imposing some regulatory schemes, such as vehicle fleet size control, price-cap, minimum wage guarantee, etc.

By virtue of multidisciplinary analytical tools, including operations research, machine learning, and game theory, my previous and on-going research attempts to find out the optimal platform operating strategies for profit maximization, and examines the impacts of various government regulations on the platform’s decisions as well as the resulting system’s measures. My PhD thesis “Supply and demand management in ride-sourcing markets” establishes a series of mathematical models to delineate the equilibrium state of ride-sourcing markets, and provide a systematical way to analyze and optimize platform operations and government regulations for shared mobility.

Short-term travel demand forecasting

An essential operation of smart mobility service is short-term demand forecasting, which can help the platform make better decisions in surge pricing, vehicle dispatching, and idle vehicle re-positioning, etc. For example, knowing that some locations will have excessive passenger demand in the future 10 minutes through an accurate prediction, the platform is able to proactively reposition nearby idle drivers to these locations to meet the surging demands. One main challenge of short-term demand forecasting is how to capture the complex spatial-temporal correlations between zones and time intervals. To address this issue, we have developed a few spatial-temporal deep learning models that can simultaneously capture the spatial dependencies, temporal dependencies, and exogenous dependencies between zones and time intervals. By evaluations on both public and private datasets, our proposed models are shown to outperform the benchmark algorithms by 5% to 10% in terms of predictive accuracy. In particular, one of our developed models has been tested and implemented in the system of Didi Chuxing, to support its real-time operations. In addition to estimating passenger demands originating from each location, we further extend the proposed models to estimate the real-time origin-destination (OD) demand matrix, which offers more detailed information to support the platform’s decisions. Moreover, by combining deep learning and multi-task learning, our models can simultaneously forecast passenger demands for various service options, e.g., UberX, UberPool, and Uber Black, by mining their inter-service dependences.

A universal distribution law of network detour ratios

Using trajectory data of normal taxis and ride-sourcing vehicles for 10 cities with various sizes in China, we analyze trip distance characteristics by examining the distribution of network detour ratios. The detour ratio for a specific ride is the ratio of the actual driving distance to the cor-responding Euclidean (straight-line) distance. We find that, in spite of their different sizes and geographical features, the various cities exhibit an amazingly similar distribution law of network detour ratios: the mean of the detour ratios is inversely proportional to the Euclidean distance with an intercept. We further verify our findings with extensive simulation experiments for a hypothetical circular city with a directional grid street network. Our finding of this universal distribution law of network detour ratios contrasts sharply with the traditional wisdom of modeling throughout the past 50 years that have typically assumed a constant road detour ratio or factor within the range of 1.25–1.41. Our finding in the urban context also has far-reaching implications for fundamental research in many fields such as human mobility, human geography, facility location problems, logistic distribution networks and urban transportation planning.