In an increasing urbanizing world the need for efficient transportation methods is growing. Ridesharing, sharing a taxi trip with multiple passengers, has been proposed as an effective way to contribute towards solving the traffic problems that arise in city centers. Current solutions to the problem are often more focused on optimality, and a fast algorithm is required to handle large quantities of passengers in real-time applications. We propose an algorithm that combines fast and efficient heuristics with clustering and parallelization techniques that is able to solve large problem instances within several seconds. The small response time of the algorithm is able to provide feedback to the customer rapidly, which makes it very suitable for ridesharing in real-time.
A segmentation of the customers is implemented to speed up the search. This method divides the customers into subareas based on pickup location such that each subproblem contains a similar number of customers. This division also bounds the size of each subproblem to ensure a solution can be found in real-time.
The primary search strategy uses a combination of effective local search heuristics to improve solutions for these subproblems rapidly. A technique reminiscent of variable neighborhood search is also implemented for diversification that can solve smaller instances to a greater degree. The full approach can handle problems containing over 5,000 requests and can effectively manage on-demand ridesharing in Manhattan where the current demand for yellow taxis has tripled.