To improve the production/distribution efficiency of perishable products with short lives under Make-To-Order (MTO) mode, considering the operational costs of business and customer demand for freshness degree of delivered products, a bi-objective model was established to coordinate the production scheduling and vehicle routing with minimum freshness limitations, which aims to minimize the total distribution cost and maximize the total freshness degree of delivered products. And an elitist nodominated sorting genetic algorithm with chromosomes encoded by two substrings was devised to optimize the proposed model. Firstly, the customers' time windows were described and freshness degrees of delivered products were defined with average degree level for multiple kinds of products. The bi-objective model was constructed to schedule production and delivery simultaneously. Then, the hard constraints and two objective functions were transformed. Chromosomes were encoded by two substrings and the computation framework of elitist nodominated sorting genetic algorithm with some key operators was adopted to solve the proposed model. Finally, the proposed algorithm was tested with the comparison of Pareto based simulated annealing on a numerical example. The simulation results show that the two objectives have a trade-off conflict and the proposed algorithm can provide Pareto optimal solutions. The sensitivity analysis of minimum limitation of freshness degree demonstrates that the two objectives are affected significantly when fewer vehicles are put into use.