The objective of this paper is to consider the vehicle routing problem with time windows under two uncertainties: service and travel times. We introduce new resolution approaches for the robust problem and an efficient parallel procedure for the generation of all possible scenarios. The best robust solution of each scenario can be achieved by using a parallel adaptive large neighborhood search metaheuristic. Through our analysis, we expect to find the best compromise between the reduced running time and a best good solution, which leads to four distinct combinations of parallel/sequential approaches. The computational experiments are performed and tested on Solomon’s benchmark and large randomly generated instances. Furthermore, our results can be protected against delay in service time in a reasonable running time especially for large instances.