A Probabilistic Approach for Demand-Aware Ride-Sharing Optimization

摘要: Ride-sharing is a modern urban-mobility paradigm with tremendous potential in reducing congestion and pollution. Demand-aware design promising avenue for addressing critical challenge ridesharing systems, namely joint optimization of request-vehicle assignment routing fleet vehicles. In this paper, we develop probabilistic demand-aware framework to tackle the challenge. We focus on maximizing expected number passenger pickups, given probability distributions future demands. The key idea our approach assign requests vehicles manner. It differentiates work from existing ones allows us explore richer space puzzle performance guarantee but still keeping final solution practically implementable. problem non-convex, combinatorial, NP-hard nature. As contribution, structure propose an elegant approximation objective function dual-subgradient heuristic. characterize condition under which heuristic generates (1 -- 1/e) solution. Our simple scalable, amendable practical implementation. Results numerical experiments based real-world traces Manhattan show that, as compared conventional demand-oblivious scheme, improves pickups by up 46%. results also that at level leads 19% more than separate optimizations individual