In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off or delivery services. We take into account the random trip time, non-negligible service time and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. We build a stochastic mixed-integer program to minimize the operational cost plus expected penalty cost of customers’ waiting time, vehicles’ idleness and overtime. Furthermore, to handle real-time arrived service requests, we develop K-means clustering-based algorithms to dynamically update planned routes and schedules. The algorithms assign customers to vehicles based on similarities and then plan schedules on each vehicle separately. We conduct numerical experiments based on diverse instances generated from census data and data from the Ford Motor Company’s GoRide service, to evaluate result sensitivity and to compare the in-sample and out-of-sample performances of different approaches. Managerial insights are provided using numerical results based on different parameter choices and uncertainty settings.