This study has extended a vehicle routing problem, with time-windows (VRPTW), by considering the randomness of the perishable food delivery process, and constructing a SVRPTW model, to obtain optimal delivery routes, loads, fleet dispatching and departure times for delivering perishable food from a distribution center. Our objective was to minimize not only the fixed costs for dispatching vehicles, but also the transportation, inventory, energy and penalty costs for violating time-windows. We also discussed time-dependent travel and time-varying temperatures, during the day, modifying the objective functions as well as the constraints in the above mathematical programming models. Algorithms were developed to solve the proposed models; results indicated that inventory and energy costs can significantly influence total delivery costs. It was found that our proposed models yielded better results than the traditional VRPTW models. (c) 2006 Elsevier Ltd. All rights reserved.