THESIS
2019
xi, 89 pages : illustrations ; 30 cm
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 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.
Post a Comment