This paper presents a tabu search algorithm to optimize the structure of cold chains for distribution of chilled or frozen foods. The physical distribution system is structured in such a way that the cost for storage and transportation in the whole distribution system is minimized, while the product quality requirement is fulfilled. A dynamic tabu list and penalty costs are used in the tabu search procedure. Numerical results for test problems are reported. (C) 2003 Elsevier Science Ltd. All rights reserved.