Publication

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

Kenan Zhang
2023
Journal paper
Abstract

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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.