Solving the ridematching problem in dynamic ridesharing

Abstract

Among the transportation demand management strategies that can be used to reduce the power consumption, air pollution and traffic congestion is the ridesharing. A flexible form of ridesharing in which a rideshare can be arranged on a very short notice is called dynamic ridesharing. Recently there are many active research areas in dynamic ridesharing including but not limited to security, privacy protection, payment and ridematching. This work is mainly focused on solving the ridematching problem. The ridematching problem is to match riders and drivers, who wish to take part in ridesharing, in the best possible way taking into account the timing and end points of their trips and other constraints that can be imposed by the participants. Computerized ridematching that requires the minimal effort from the ridesharing participants is the heart of any dynamic ridesharing system. The ridematching problem in realistic dynamic ridesharing scenarios could be an extremely complex optimization problem that becomes intractable for larger problem instances. To attack the ridematching problem, we consider different variants of it and attack them by going from the more restricted to the more general variants. For each ridematching variant, we provide a model for the ridematching problem and propose an algorithm to solve it. All of the proposed algorithms are meta-heuristics as even the restricted variants of the ridematching problem are hard optimization problems in their own. The proposed algorithms are tested on artificial and realistic ridematching. Our experimentation indicates that our proposed algorithms can efficiently solve the ridematching problem by providing good quality solutions in reasonable time. In addition, a reasonable number of ridematches can be found in real world scenarios and a considerable amount of travel distances can be saved which in turn could reduce power consumption, air pollution and traffic congestion.