A fast and robust algorithm for solving the fresh milk distribution problem for one of the biggest diary companies in Greece was developed. This particular problem was formulated as a Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) for which, due to its high computational complexity, no exact algorithm ever has been used to solve it. In this study, a threshold-accepting based algorithm was developed aiming to satisfy the needs of the company that plans to use this methodology repeatedly to schedule their distribution many times a week. For this purpose. the proposed formulation was implemented in an efficient and reliable computer code. The algorithm manages to provide practical solutions and the early findings indicate considerable improvements in the operational performance of the company.