A Queueing-Theoretic Framework for Vehicle Dispatching in Dynamic Car-Hailing [technical report]
With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from both the academia and the industry. In this paper, we consider an important dynamic car-hailing problem, namely \textit{maximum revenue vehicle dispatching} (MRVD), in which rider requests dynamically arrive and drivers need to serve as many riders as possible such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. In addition, the dynamic car-hailing platforms have no information of the future riders, which makes the problem even harder. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning algorithms to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose two batch-based vehicle dispatching algorithms to efficiently assign suitable drivers to riders such that the expected overall revenue of the platform is maximized during each batch processing. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Job Dispatching Policies for Queueing Systems with Unknown Service Rates
In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies s…
dFDA-VeD: A Dynamic Future Demand Aware Vehicle Dispatching System
With the rising demand of smart mobility, ride-hailing service is getting popular in the urban regions. These services maintain a system for serving the incoming trip requests by dispatching available vehicles to the pic…
A prediction-based forward-looking vehicle dispatching strategy for dynamic ride-pooling
For on-demand dynamic ride-pooling services, e.g., Uber Pool and Didi Pinche, a well-designed vehicle dispatching strategy is crucial for platform profitability and passenger experience. Most existing dispatching strateg…
GARLIC: GPT-Augmented Reinforcement Learning with Intelligent Control for Vehicle Dispatching
As urban residents demand higher travel quality, vehicle dispatch has become a critical component of online ride-hailing services. However, current vehicle dispatch systems struggle to navigate the complexities of urban …
Navigatereinforcement-learningReinforcement LearningA SUMO Framework for Deep Reinforcement Learning Experiments Solving Electric Vehicle Charging Dispatching Problem
In modern cities, the number of Electric vehicles (EV) is increasing rapidly for their low emission and better dynamic performance, leading to increasing demand for EV charging. However, due to the limited number of EV c…
Deep Reinforcement LearningReinforcement Learning (RL)