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 candidat...[ Read more ]

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 approximation ratios as 0.5 and 1/2(1-1/β) respectively.

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.