Order Dispatch for Online Car-hailing services

PhD Thesis Proposal 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 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 three 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 the orders or 
rejects all the orders. For this mode, we manage to maximize the 
platform’s throughput by maximizing workers' acceptance. We show that the 
problem is NP-hard, and we propose a greedy-based and a local search based 
algorithm with different approximation ratios.

In the compulsory-dispatch mode, drivers always accept the orders 
dispatched by the platform. We consider the ride-sharing scenario because 
the non-sharing scenario can be simply addressed by using 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 riders to bid their payments. We propose a ranking-based 
order dispatch and pricing algorithm which maximizes the overall utility 
of the auction with an approximation ratio as 1 over m (m is the number of 
orders) while satisfying the desired auction properties.


Date:			Monday, 1 April 2019

Time:                  	3:00pm - 5:00pm

Venue:                  Room 2408
                         (lifts 17/18)

Committee Members:	Prof. Lei Chen (Supervisor)
 			Dr. Xiaojuan Ma (Chairperson)
 			Dr. Qiong Luo
 			Dr. Wei Wang


**** ALL are Welcome ****