Aiming at the problem of simultaneous vehicle routing optimization under the condition of road driving speed varying with time and soft time window, with the goals of minimizing the total distribution cost and maximizing customer satisfaction, and considering constraints such as vehicle load constraints, a cargo distribution routing optimization model for oil-electric vehicle hybrid fleets under time-varying traffic is constructed. According to the characteristics of the model, a multi-objective hybrid heuristic algorithm considering spatio-temporal distance and based on Pareto non-dominated sorting is designed. The genetic algorithm is combined with the variable neighborhood search algorithm to enhance the local search ability of the algorithm. Taking some customers of type C101 in Solomon as examples for case analysis, comparative analysis of customer points of different scales and comparative experiments between simulated data and real data are carried out. The research results show that compared with algorithms such as the multi-objective collaborative optimization genetic algorithm, the algorithm proposed reduces the total cost to 7,008.47 yuan, with reductions of 4.59%, 5.46%, 6.80%, 10.77% and 8.41%, respectively, and the customer satisfaction rate increases to 0.841. Considering the sensitivity analysis of parameters under different circumstances, a reasonable distribution weight can save the total distribution cost by 69.28%, 28.14% and 38.61%, respectively. A reasonable vehicle load capacity can save distribution costs by 31.2% and 62.3%, respectively. The research results show that the constructed model and proposed algorithm can rationally allocate different types of vehicles, scientifically plan vehicle routes, reduce the total cost of logistics distribution, decrease vehicle carbon emissions, and improve the economic benefits of enterprises.