The ridematching problem with time windows in dynamic ridesharing: A model and a genetic algorithm

摘要

The increasing ubiquity of mobile handheld devices paved the way for the dynamic ridesharing which could save travel cost and reduce the environmental pollution. The ridematching problem with time windows in dynamic ridesharing considers matching drivers and riders with similar routes (with drivers detour flexibility) and time schedules on short notice. This problem is hard to solve. In this work, we model the ridematching problem with time windows in dynamic ridesharing as an optimization problem and propose a genetic algorithm to solve it. We consider minimizing the total travel distance and time of the drivers (vehicles) and the total travel time of the riders and maximizing the number of the matches. In addition, we provide datasets for the ridematching problem, derived from a real world travel survey for northeastern Illinois, to test the proposed algorithm. Experimentation results indicate that the idea of dynamic ridesharing is feasible and the proposed algorithm is able to solve the ridematching problem with time windows in reasonable time.