In this chapter, several constructive algorithms developed for the cumulative vehicle routing problem with limited duration are used as an initial solution generator algorithm for various metaheuristics. Their performance on the solution quality obtained by solution-based and population-based metaheuristics is investigated. Data sets from the literature are used for the computational tests. The computational experiments show that the performance of simulated annealing is significantly affected by the initial solution generator. Although initial solution generators do not affect the performance of genetic algorithms as much as simulated annealing, choosing the best initial solution generator is still an important issue to obtain high-quality solutions in a proper computational time.