To improve the fast and efficient distribution of fresh products with dynamic customer orders, we constructed a multi-objective vehicle routing optimization model with the objectives of minimizing the distribution costs including freshness-loss cost, cold-chain-refrigeration cost, and delay-penalty cost, and maximizing customer time satisfaction. An improved multi-objective genetic algorithm (GA)-based particle swarm optimization (MOGAPSO) algorithm was designed to quickly solve the optimal solution for the distribution routes for fresh-product orders from regular customers. Furthermore, online real-time orders of fresh products were periodically inserted into the distribution routes with local optimization solutions by applying a dynamic inserting algorithm. Finally, a case study of a fresh-product distribution company in Shenzhen, China was conducted to validate the practicality of the proposed model and algorithms. A comparison with the NSGA-Ⅱ and MOPSO algorithms showed the superiority of the proposed MOGAPSO algorithm on distribution-cost reduction and customer time-satisfaction improvement. Moreover, the dynamic inserting algorithm demonstrated a better performance on distribution-cost reduction.