Stochastic optimization approach for the car placement problem in ridesharing systems

With the increasing fuel prices and the pressure towards greener modes of transportation, ridesharing has emerged as an alternative to private car ownership and public transportation. In this paper, we focus on a common destination ridesharing system which is of interest in large organizations such as companies and government offices. Particularly, such organizations are looking at using company owned vehicles to offer a ridesharing service by which employees carpool to work thus leading to several benefits that include decreasing pressure on on-campus parking spaces, lowering localized on-campus congestion, in addition to offering a greener transportation mode while lowering transportation costs for employees. Based on discussions with our industry partners, optimizing the distribution of limited number of company vehicles while insuring robustness against unlikely vehicle unavailability is of critical importance. Thus in this paper, we present a stochastic mixed integer programming model to optimize the allocation of shared vehicles to employees while taking into account the unforeseen event of vehicle unavailability which would require some participants to take own vehicles or rerouting of existing vehicles. Since solving the proposed model to optimality is computationally challenging for problems of large sizes, we also propose a heuristic that is capable of finding good quality solutions in limited computational time. The proposed model and heuristic are tested on several instances of varying sizes showing the computational performance. Finally, a test case based on the city of Rome, Italy is presented and insights related to vehicle distribution and travel time savings are discussed.