Undominated Sorting Genetic Algorithm II for Solving the Cross-Docking Distribution Vehicle Path Problem

越库是一种有效的物流策略，然而，物流费用高、客户满意度低仍是越库配送模式存在的主要问题。本文基于软时间窗约束，研究了带软时间窗的越库配送车辆路径问题(VRPCDTW)。模型的目标是使经济成本之和最小化，平均顾客满意度最大化。结合模型的特征，提出了一种改进的非支配排序遗传算法Ⅱ进行求解。最后，实验数据表明，通过与其他多目标进化算法进行比较，该算法能在不同规模算例下有效求解模型，算法综合性能更高。所提出的方法有效地降低了总配送成本，提高了客户满意度。Cross-docking is an efficient logistics strategy; however, high logistics costs and low customer satisfaction remain key issues in cross-docking distribution. This paper investigates the Vehicle Routing Problem with Cross-Docking and Time Windows (VRPCDTW) under soft time window constraints. The objective of the model is to minimize total economic costs and maximize average customer satisfaction. Based on the model’s characteristics, an improved Non-dominated Sorting Genetic Algorithm II (NSGA-II) is proposed to solve the problem. Experimental results demonstrate that, compared with other multi-objective evolutionary algorithms, the proposed algorithm effectively solves the model across various instance scales and shows superior overall performance. The method successfully reduces total distribution costs and enhances customer satisfaction.