Optimizing order dispatch for ride-sharing systems

Yubin Duan, Ning Wang, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Ride-sharing companies such as Didi and Uber have served billions of passenger requests from all over the world. The efficiency of the ride-sharing is highly depended on the order dispatch system which assigns passenger requests to idle drivers. However, designing such a dispatch system is challenging because of the spatial-temporal dynamic of passenger requests, and the trade-off between the benefits for passengers and drivers. Existing order dispatch systems use either a system-assigning approach or a driver-grabbing approach. However, either approach has its own flaws. In this paper, we propose to combine the two existing approaches and jointly considers both passengers'' and drivers'' interest. In our approach, a passenger request is broadcast to the drivers in a dispatch region chosen by the system. The size of the dispatch region could iteratively increase until the request is accepted. We formulate an optimization problem to determine the increase speed of the dispatch region. Drivers'' idle driving distances and passengers'' waiting time are jointly considered. We propose a dynamic programming algorithm to optimally solve the increase ratio of the size of the dispatch region for a case that different dispatch regions are not overlapped. We further investigate the overlapped case and modify the dynamic programming algorithm correspondingly. We provide a discussion on the effect of the overlapping in a spatial case, where the driver and passenger locations are uniformly distributed. Experiments are conducted based on the synthetic dataset and the real-world dataset from Didi Inc. Results show that our approach can effectively reduce the expected driver pickup distance and keep the dispatching time short, which balances both passengers'' and drivers'' interests.

Original languageEnglish (US)
Title of host publicationICCCN 2019 - 28th International Conference on Computer Communications and Networks
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728118567
DOIs
StatePublished - Jul 2019
Event28th International Conference on Computer Communications and Networks, ICCCN 2019 - Valencia, Spain
Duration: Jul 29 2019Aug 1 2019

Publication series

NameProceedings - International Conference on Computer Communications and Networks, ICCCN
Volume2019-July
ISSN (Print)1095-2055

Conference

Conference28th International Conference on Computer Communications and Networks, ICCCN 2019
Country/TerritorySpain
CityValencia
Period7/29/198/1/19

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'Optimizing order dispatch for ride-sharing systems'. Together they form a unique fingerprint.

Cite this