Vehicle Routine Problem (VRP) consists in finding the optimal route through a number of customers from one or several depots
to a set of geographically scattered points, such every point is visited once by exactly one vehicle, all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the vehicle capacity. The objective to be minimized is usually a function of the number of vehicles in the solution, the distance driven and the service provided to the customers. One of important variation of VRP is in the demand structure where the demand of each location is unknown when the route is designed, but it follows certain probability distribution. This is known as the VRP with Stochastic Demand (VRPSD). The Algorithms for stochastic VRP such as this are rather complex than deterministic and the computational intricacy is very demanding. Various formulations and algorithms have been proposed and investigated but the work on the application of Genetic
Algorithm (GA) in VRPSD is lacking in the literature. GA is an effective search and optimization method that simulates the process of natural selection or survival of the fittest. It has seen widespread use amongst modern metaheuristics, and several applications to NP-hard problems. This approach provides satisfactory results for optimization problems that are hard to solve using exhaustive techniques. This paper presents the GA heuristic approach on VRPSD for single vehicle and single depot. The chromosome representation of the problem is based on order/permutation representation with the inclusion of the initial solution using
constructive and insertion heuristic. The GA is used to find the order in which the customers are initially visited, and a local search is applied subsequently to detect possible improvement. The approach is tested on a set of randomly generated problems following some discrete probability distributions and compared with existing heuristic procedure. The problem data are inspired by real case of VRPSD in waste collection. The results show that GA, although requiring slightly longer computational times, is better that previous algorithm in terms of solution quality.