The Robust Vehicle Routing problem (RVRP) is a variant of the Vehicle Routing Problem (VRP) in which uncertain data is considered as a set of discrete scenarios for arc costs. The objective is to select the set of routes which minimize the worst total cost over all scenarios, such that each route starts and ends at the depot, and visits each customer without surpassing the vehicles capacity. In this work, we propose heuristics and a Genetic Algorithm (GA) for the RVRP which take into account two main issues, the scenarios and the asymmetric arc costs. Small and medium size instances were generated to test the performance of the proposed GA for the RVRP, and to analyze the impact of the discrete scenarios. A maximum of 20 customers, 3 vehicles and 30 discrete scenarios are handled for the small instances. On medium size instances, 100 customers, 20 vehicles and 20 scenarios as maximum are tested. Results obtained show that the proposed GA produces good solutions for the RVRP in a moderate computational time.