A Multi-Start Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows

Vehicle Routing Problems have been analyzed to reduce transportation costs of people and goods. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a very common characteristic in real world picking up and delivery problems. Using minimization of the total distance as the main objective to be fulfilled, this work implements an efficient hybrid system which associates a nonmonotonic Simulated Annealing technique to a Hill Climbing Strategy with Random Restart (Multi-Start). The algorithm performance is evaluated by comparing the results achieved with the best published works found in the literature of the 56 Solomon instances. The results outperformed or paired the individual best previous results in 36 out of the 56 instances.