In increased competition environment, ensuring customer satisfaction has received a lot of attention from the companies. One of the most challenging sectors in providing customer satisfaction is the food sector dealing with perishable foods. This study considers the distribution problem of the perishable foods and formulates it as a bi-objective vehicle routing problem with objectives of maximization of freshness and minimization of total traveled distances. First, we propose a goal programming formulation of the problem. Since the vehicle routing problem is in the class of NP-hard problems, its goal programming variation is also NP-hard. Second, we develope a heuristic algorithm based on simulated annealing to solve the problem. Efficiency of the develped heuristic algorithm is tested on various size problems derived from Solomon vehicle routing problem with time windows benchmarks. Results show that the proposed algorithm is quite effective in reaching optimal or near-optimal solutions.