Two evolutionary metaheuristics for the vehicle routing problem with time windows

The vehicle routing problem with time windows (VRPTW) is an extension of th e well-known vehicle routing problem with a central depot. The objective is to design an optimal set of routes that services all customers and satisfi es the given constraints, especially the time window constraints. The objec tive function considered here combines the minimization of the number of ve hicles (primary criterion) and the total travel distance minimization (seco ndary criterion). In this paper, two evolution strategies for solving the V RPTW are proposed. The evolution strategies were tested on 58 problems from the literature with sizes varying from 100 to 417 customers and 2 to 54 ve hicles. The generated new best known solutions indicate that evolution stra tegies are effective in reducing both the number of vehicles and the total travel distance.