Order Dispatch for Online Car-hailing Services

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Order Dispatch for Online Car-hailing Services"

By

Mr. Libin ZHENG


Abstract

With the rapid development of mobile networks and the great prevalence of 
smartphones, online car-hailing services have been widely employed in recent 
years. In Didi Chuxing, the largest car-hailing platform (service provider) in 
China, the number of orders reaches 7.43 billion in 2017. Order dispatch is the 
key problem for the car-hailing platform developers, which has a great impact 
on the platform performance, such as throughput and profit. In this work, we 
classify the order dispatch process into three modes, i.e., driver-selection 
mode, compulsory-dispatch mode, and auction-based dispatch mode. For each of 
these modes, we propose algorithms to realize the effective and efficient 
matching between orders and drivers.

In the driver-selection mode, the platform pushes candidate order sets to 
individual drivers, and a driver either accepts one of them or makes a 
rejection. For this mode, we aim to maximize the platform’s throughput (number 
of accepted orders). We propose a greedy-based and a local search based 
algorithm with different approximation ratios.

In the compulsory-dispatch mode, drivers always accept the dispatched orders. 
We consider the ridesharing scenario because the non-sharing scenario can be 
simply addressed by the Kuhn-Munkres algorithm. We propose the packing-based 
matching algorithm which firstly packs the orders and then dispatches the order 
packs to the drivers.

The auction-based dispatch mode follows the compulsory-dispatch principle but 
enables the order requesters to bid their payments. We propose a ranking-based 
order dispatch and pricing algorithm to effectively implement the auction 
mechanism.


Date:			Wednesday, 12 June 2019

Time:			3:00pm - 5:00pm

Venue:			Room 2463
 			Lifts 25/26

Chairman:		Prof. Man Yu (ISOM)

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Yangqiu Song
 			Prof. Qian Zhang
 			Prof. Yang Wang (MATH)
 			Prof. Jian Pei (Simon Fraser University)


**** ALL are Welcome ****