Ride-hail vehicle routing (RIVER) as a congestion game

The RIde-hail VEhicle Routing (RIVER) problem describes how drivers in a ride-hail market form a dynamic routing strategy according to the expected reward in each zone of the market. We model this decision-making problem as a Markov decision process (MDP), and view the drivers as playing an MDP routing game, with “congestion” induced by competitive matching in a zone. The meeting probability (i.e., the probability of successfully picking up a passenger after cruising in a zone for one period) is derived from a physical model, which is specified for street-hail and e-hail service modes separately, and calibrated with simulation data. We define a Wardrop equilibrium for the MDP routing game, and then prove it exists and can be obtained by solving a fixed-point problem. We further show a system optimum – corresponding to the maximum total expected reward accumulated over time by all drivers – can be achieved if drivers make individual routing decisions according to a cooperative reward rather than the personal reward. In other words, the proposed cooperative strategy “decentralizes” the system optimal solution in the MDP routing game. The results from numerical experiments, including a case study of Chicago, indicate the service mode plays a critical role in shaping system performance. While e-hail enjoys a higher fleet utilization rate than street-hail thanks to its more advanced matching technology, it may lead to a more uneven spatial distribution of vacant vehicle supply. As expected, cooperative routing improves system performance in terms of both total reward and equal distribution of supply. Yet, its benefit is much stronger in e-hail than in street-hail, especially when the supply is overly abundant. We also find, when a local demand surge occurs, the cooperative rewards rise in sync, similar to surge pricing on the supply side. Interestingly, the impact of the price surge spreads broadly in space, propagating far beyond the epicenter of the demand surge.