The Dial-a-Ride Problem (DARP) consists of designing a set of routes to transport clients from pickup node to delivery node, taking into account vehicle capacity, time windows and riding time constraints. The Stochastic DARP (SDARP) is a practical variant of the DARP in which the travel time between nodes is a random variable related to traffic jam, road maintenance or weather conditions. The solution robustness is the probability that a solution remains feasible considering different distribution laws and the driving policy which defines the driver procedure to follow when vehicle arrives earlier or later than the planned schedule. Three policies are introduced to model the wide spread transportation industry behaviours. For stochastic routing problems, classical approaches require either simulation based evaluation method to provide a useful estimation of the robustness or analytical methods. Both are too time consuming to be efficiently integrated into an iterative improvement scheme. A new method is introduced to estimate the robustness. It relies on an indirect approach using a specific criterion which is shown to be correlated to the robustness and which can be easily computed. This indirect approach is embedded into both an Evolutionary Local Search (ELS) metaheuristic and a multi-criteria population-based method. The solutions obtained at the end of the process are highly robust with respect to this criterion. Their robustness can be evaluated and confirmed by simulation. Numerical results are presented to analyse the robustness of the best published solutions for the DARP in the context of stochastic travel times. Many of them appear to be very sensitive to random variations. Computational results for the ELS and the population-based algorithm for the SDARP are then reported. They show the robustness can be significantly improved, without significant impact on the cost of the solution.