The vehicle routing problem with hard time windows and stochastic travel and service time

In real-world environments, the variability is always present and influences the level and cost service offered to customers. In this scenario, the present work develops a strategy to solve the Vehicle Routing Problem with Time Windows (VRPTW) in which the travel time among the customers is known only probabilistically and the vehicles are not allowed to start the service before the earliest time windows. The fact there is waiting time brings a challenge to the model because the arrival time distribution at a customer can be truncated, affecting the arrival time in the following customers. A new method is developed to estimate the vehicle arrival time at each customer and to estimate the vehicle's probability to respect the customer's time window. The metaheuristic based on Iterated Local Search finds the best route with minimal expected cost, and it guarantees that certain levels of service are met. A benchmark is used to evidence the superior performance and accuracy of the proposed method. (C) 2016 Elsevier Ltd. All rights reserved.