Online to Offline Business: Urban Taxi Dispatching with Passenger-Driver Matching Stability

摘要

In the Online to Offline (O2O) taxi business (e.g., Uber), the interests of passengers, taxi drivers, and the company may not align with one another, since taxis do not belong to the company. To balance these 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. Given dummy partners, stable matchings are proved to exist. Three rules are presented to find out all possible stable matchings. For sharing taxi dispatches (multiple passenger requests can 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 how well our approach performs. The proposed algorithms have a limited performance gap to the literature in terms of the dispatch delay and the passenger satisfaction, but they significantly improve upon existing algorithms in terms of the taxi satisfaction.