Passenger Search Problem and Solutions for Ride Sharing

Abstract

Ride sharing is a way of energy saving and carbon footmark reduction. The current systems or websites still depend on manual ways to couple drivers with passengers. They do not make good use of prevailing map information to well organize the temporal and spatial information in user routes. The paper proposes a payment scheme that encourages people to join the carpool and provides a goal for coupling drivers with passengers. We define and research into the passenger search problem and propose an efficient method that can find good results based on the characteristic between passengers’ routes and the driver’s payments. We also design a method that guarantees to find the optimal solution. Experiment results show that our method can improve the efficiency in computation and make a tradeoff between the quality of answer and the execution time. Our result will help the construction of a more automatic carpool system.