More about HKUST
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 ****