Vehicle Routing Problem (VRP) is a well known NP-hard optimization problem with a number of real world applications and a variety of different versions. Due to its complexity, large instances of VRP are hard to solve using exact methods. Instead, various heuristic and meta-heuristic algorithms were used to find feasible VRP solutions. This work proposes a Differential Evolution for VRP that simultaneously looks for an optimal set of routes and minimizes the number of vehicles needed. The algorithm is used to solve Stochastic VRP with Real Simultaneous Pickup and Delivery based on real-world data obtained from Anbessa City Bus Service Enterprise (ACBSE), Addis Ababa, Ethiopia. Additionally, the algorithm is evaluated on several well known VRP instances.