An algorithm for the distribution of fresh vegetables in which the perishability represents a critical factor was developed. This particular problem was formulated as a vehicle routing problem with time windows and time-dependent travel-times (VRPTWTD) where the travel-times between two locations depends on both the distance and on the time of the day. The model considers the impact of the perishability as part of the overall distribution costs and a heuristic approach, based on the tabu search is used to solve the problem. The performance of the algorithm was verified using modified Solomon's problems. Using parameters typical of the Slovenian food market, different schedules were achieved, giving improvements of up to 47% reduction in perished goods. (c) 2007 Elsevier Ltd. All rights reserved.