Genetic algorithms are nowadays commonly used in simulation-based optimization of vehicle routing problems. These algorithms work with a population of solutions that are iteratively improved in an evolutionary process. Usually, the initial population is created randomly. In general, this is not very efficient since it takes unnecessarily long time before sufficiently good solutions have evolved. For a better performance of genetic algorithms, this work describes the use of heuristic search for creating the initial population. A new heuristic search procedure is described in the paper and evaluated using a real-world problem of garbage collection. The results from the evaluation show that the new procedure is able to improve a genetic algorithm.