Abstract: Based on the traditional static penalty strategy of the Guided Local Search algorithm (GLS), a dynamic penalty strategy was proposed. Then an improved GLS algorithm was developed to solve the period vehicle routing problem (PVRP). Standard instances of the PVRP were applied for computational tests. Comparison of static penalty and dynamic penalty strategies show that the improved GLS algorithm is efficient and effective for the PVRP.