Online to Offline Business: Urban Taxi Dispatching with Passenger-Driver Matching Stability
Huanyang Zheng and Jie Wu
Temple University, Temple University

In the Online to Offline (O2O) taxi business (e.g., Uber), the interests of passengers, taxi drivers, and the company may not align with each other, since taxis do not belong to the company. To balance those interests, this paper studies the taxi dispatch problem for the O2O taxi business. The interests of passengers and taxi drivers are modeled. For non-sharing taxi dispatches (multiple passenger requests cannot share a taxi), a stable marriage approach is proposed. It can deal with unequal numbers of passenger requests and taxis through matching them to dummy partners. The existence of stable matchings with dummy partners is proved. Three rules are presented to find out all possible stable matchings. For sharing taxi dispatches (multiple passenger requests could share a taxi), passenger requests are packed through solving a maximum set packing problem. Packed passenger requests are regarded as a single request for matching taxis. Extensive real data-driven experiments demonstrate the performance of our approach. The proposed algorithms have a limited performance gap to the literature in terms of the dispatch delay and the passenger satisfactory, but significantly improves the existing algorithms in terms of the taxi satisfactory. Index TermsTaxi dispatch schedule, passenger requests, taxi drivers, matching stability, sharing and non-sharing.