2019/01/22 by Tan, Zeren
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph)
paper · doi:10.48550/arxiv.1901.07906
Ride-sharing can reduce traffic congestion and thus reduce gas emissions and save travel time. However, transportation system with ride-sharing is currently inefficient due to low occupancy rate, high travel demand and some other factors. Existing literature did not consider ride-sharing with multi-request grouped in one trip. In our paper, we firstly proposed a graph-based algorithm that can obtain an approximation solution in polynomial time and then proposed an exact algorithm to solve this problem with maximizing the number of passenegers served in O(1.2312|E|) time.