Abstract. On-demand ride-sharing is a promising way to improve mobility efficiency and reliability. The quality of passenger experience and the profit achieved by these platforms are strongly affected by the vehicle dispatch policy. However, existing ride-sharing research seldom considers travel time uncertainty, which leads to inaccurate dispatch allocations. This paper proposes a framework for dynamic vehicle dispatch that leverages stochastic travel time models to improve the performance of a fleet of shared vehicles. The novelty of this work includes: (1) a stochastic on-demand ride-sharing scheme to maximize the service rate (percentage of requests served) and reliability (probability of on-time arrival); (2) a technique based on approximate stochastic shortest path algorithms to compute the reliability for a ride-sharing trip; (3) a method to maximize the profit when a penalty for late arrivals is introduced. Based on New York City taxi data, it is shown that by considering travel time uncertainty, ride-sharing service achieves higher service rate, reliability and profit.