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.

In this paper, we present an efficient heuristic for the vehicle routing problem with time windows (VRPTW), inspired by the Adaptive Large Neighborhood Search (ALNS) previously suggested by Røpke and Pisinger [21]. The proposed heuristic uses the Modified Choice function (MCF) of Drake [12] as an elegant selection mechanism to favor the most successful operators instead of the roulette wheel selection. This general method is denoted Modified Adaptive Large Neighborhood Search (MALNS). The computational experiments are performed and the comparison with the classical ALNS is given according to Solomon’s benchmark, and its extension the instances of Gehring and Homberger’s benchmark.