Background Food safety and quality management is attracting more and more attention. Fresh foods are characterized by their perishable and temperature-sensitive nature. Thus, there is a need for cold chain management. In order to ensure delivery of safe, fresh, high-quality foods to customers, strict time and temperature control are special requirements which must be incorporated during distribution planning. Scope and approach This study modeled a cold chain food distribution planning problem, aiming to generate a distribution plan for fulfilling customer requirements for various foods with pre-appointed quality levels at the lowest distribution cost. The quality level was defined based on the estimated shelf life, which varies by food type and storage temperature, and is characterized by a stepped decrease as time goes on. Upward substitution of quality levels is implemented in the shipment of customer orders to ensure customers receiving the foods with ordered quality levels. The optimization of temperature setting for food storage in multi-item-multi-temperature vehicles was also involved in distribution planning. To solve the problem, an algorithm based on adapting Biogeography-based Optimization (BBO) was developed. The genetic algorithm was employed as a benchmarking method. Two designed examples regarding chilled meat distribution are illustrated. Key findings and conclusions The results indicate that the generated distribution plan can ensure the fulfillment of customer requirements for various foods and food quality levels at the lowest cost. The superiority of the proposed adaptive BBO in both the solution quality and stability was also demonstrated.