Passenger search by spatial index for ridesharing

Ridesharing has the great opportunity to reduce the consumption of energy and the emission of harmful gases, and to let people share the traffic costs with others. Most of the current ridesharing systems simply provide a number of candidates for users to choose. Time-consuming negotiation often discourages people from ridesharing. We propose a novel approach that assigns users to form ridesharing groups according to their routes and payments. Given a driver, our goal is to find a group of passengers who will pay the driver the most. Under the payment scheme, the passengers who share rides on the same route will equally share the expense with the driver. For the prompt response to an online system, our approach aims for the near-optimal group, where the available seats on the driver route are occupied by passengers as many as possible. Compared with the previous methods, the experiment results show that our approach incurs a little overhead but obtains answers of good quality, measured by the driver's saving, under various parameter settings.