This paper introduces a real-life variant of a periodic traveling salesman problem (V_PTSP) for a retail distribution system. A warehouse is allocated to serve specified retail districts where a large number of retailers are located and the deliveries are planned according to the visiting frequency of each retailer. The objective is to determine daily vehicle routes over a given planning period adhering to the visiting frequency restrictions while minimizing the total distance traveled. Initially, the V_PTSP is formulated as an integer programming model. Since this model can only solve small size problems, a nested simulated annealing procedure is developed for solving large size V_PTSPs. A series of computational tests are performed for evaluating the performance of the heuristic procedure. The results show that the proposed approach gives good solutions in reasonably short computation times. (C) 2013 Elsevier Ltd. All rights reserved.