A Priori Approach Of Real-Time Ridesharing Problem With Intermediate Meeting Locations

Abstract

Ridesharing is a mobility concept in which a trip is shared by a vehicle’s driver and one or more passengers called riders. Ridesharing is considered as a more environmentally friendly alternative to single driver commutes in pollution-creating vehicles on overcrowded streets. In this paper, we present the core of a new strategy of the ridesharing system, making it more flexible and competitive than the recurring system. More precisely, we allow the driver and the rider to meet each other at an intermediate starting location and to separate at another intermediate ending location not necessarily their origins and destinations, respectively. This allows to reduce both the driver’s detour and the total travel cost. The term “A priori approach” means that the driver sets the sharing cost rate on the common path with rider in advance. An exact and heuristic approaches to identify meeting locations, while minimizing the total travel cost of both driver and rider are proposed. Finally, we analyze their empirical performance on a set of real road networks consisting of up to 3,5 million nodes and 8,7 million edges. Our experimental results show that our heuristics provide efficient performances within short CPU times and improves the recurring ridesharing approach in terms of cost-savings.