A Robust optimization approach for the Vehicle Routing problem with uncertain travel cost

The Robust Vehicle Routing problem (RVRP) with discrete scenarios is studied here to handle uncertain traveling time, where a scenario represents a possible discretization of the travel time observed on each arc at a given traffic hour. The goal is to build a set of routes considering the minimization of the worst total cost over all scenarios. A Genetic Algorithm (GA) is proposed for the RVRP considering a bounded set of discrete scenarios and the asymmetric arc costs on the transportation network. Tests on small and medium size instances are presented to evaluate the performance of the proposed GA for the RVRP. On small-size instances, a maximum of 20 customers, 3 vehicles and 30 discrete scenarios are handled. For medium-size instances, 100 customers, 20 vehicles and 20 scenarios are tested. Computational results indicate the GA produces good solutions and retrives the majority of proven optima in a moderate computational time.