Ride-Sharing under Travel Time Uncertainty: Robust Optimization and Clustering Approaches

Abstract In this paper, a ride-sharing system that supports frequent updates of participants’ information is studied, for which driver-rider matching and associated routes need to be decided quickly. Uncertain travel time is considered explicitly when matching and route decisions are made; a robust optimization approach is proposed to handle it properly. To achieve computational tractability, an extended insertion algorithm in conjunction with a tabu search method is proposed, and a cluster-first-route-second approach is used to find heuristic solutions. In particular, a greedy heuristic and k-means algorithm are used to group the riders and their respective results, along with non-clustering case outcomes, are compared. Numerical examples show that the ride-sharing system considered in this paper can be a viable solution by means of our proposed approaches even for challenging cases where the scale of the system is large and decisions need to be made quickly.