Towards Minimum Fleet for Ridesharing-Aware Mobility-on-Demand Systems

The rapid development of information and communication technologies has given rise to mobility-on-demand (MoD) systems (e.g., Uber, Didi) that have fundamentally revolutionized urban transportation. One common feature of today's MoD systems is the integration of ridesharing due to its cost-efficient and environment-friendly natures. However, a fundamental unsolved problem for such systems is how to serve people's heterogeneous transportation demands with as few vehicles as possible. Naturally, solving such minimum fleet problem is essential to reduce the vehicles on the road to improve transportation efficiency. Therefore, we investigate the fleet minimization problem in ridesharing-aware MoD systems. We use graph-theoretic methods to construct a novel order graph capturing the complicated inter-order shareability, each order's spatial-temporal features, and various other real-world factors. We then formulate the problem as a tree cover problem over the order graph, which differs from the traditional coverage problems. Theoretically, we prove the problem is NP-hard, and propose a polynomial-time algorithm with a guaranteed approximation ratio. Besides, we address the online fleet minimization problem, where orders arrive in an online manner. Finally, extensive experiments on a city-scale dataset from Shenzhen, containing 21 million orders from June 1st to 30th, 2017, validate the effectiveness of our algorithms.