Hybrid genetic algorithm for ridesharing with timing constraints: Efficiency analysis with real-world data

Ridesharing is an effective, affordable and environment-friendly way of transportation. This paper proposes a Hybrid Genetic Algorithm(HGA) using elements from Simulated Annealing(SA) and Local search(LS) which is very suitable for Ridesharing related applications. The designed algorithm efficiently handles advanced constraints like timing windows for pick-up, detour time(or distance), and waiting-time minimization. To quantify the effectiveness of HGA for the Ridesharing problem, we study Ridesharing as a close variant of the Orienteering Problem(OP) and Orienteering Problem with Time Windows(OPTW). Both these problems have been extensively studied and have many benchmark data sets. The experiments performed on popular benchmark instances of orienteering problems show that HGA for orienteering problems outperforms all the available algorithms in the literature. Further, for many of the instances, our HGA has discovered solutions that are better than the current Best Known solutions. Using our HGA for orienteering problems, we have developed a prototype system for Ridesharing. The experiments using real-world New York taxi trip data [19] shows that the system ensures that about 40%-50% of the rides could have been shared, and 60%-70% of customers could have shared rides. The detailed data analysis shows how to tune the parameters for the system to achieve the best possible performance.