In this work metaheuristics are introduced for the solution of the vehicle routing problem with soft time windows. The tabu search algorithm is implemented in this context along with the iterated local search and tested on different parameter settings and methods. During the tests on tabu search, intensification, diversification and route minimization strategies are gradually developed and implemented. The tabu search algorithm is further tested on different types of soft time windows. Computational test results of benchmark problems are calculated and compared to results from literature. Results show that in comparison with other tabu search algorithms, the tabu search generated in this work could outperform several paper results.