In response to the problems of high logistics costs, low customer satisfaction and significant pressure for carbon reduction under vehicle routing problem for cross-docking, a method for calculating road travel time across time periods based on time-varying vehicle speeds was proposed, enabling more accurate assessments of cost and time. By comprehensively considering soft time window constraints and the impact of driving speed on carbon emissions, a bi-objective model was developed to simultaneously optimize the conflicting objectives of total system cost and waiting delay time. A hybrid heuristic algorithm combining variable neighborhood search (VNS) and non-dominated sorting genetic algorithm II (NSGA-II) was presented to solve the model. Numerical experiments show that the algorithm effectively solves the model across instances of varying scales and demonstrates high overall performance. The time-varying speed model enhances customer satisfaction compared to static networks.