Abstract: On the basis that in original literature minimum vehicle scheduling cost was set as the only objective, it sets the maximum customer satisfaction index as another objective, and proposes a mathematical model for the linehaul-feeder multi-objective vehicle routing problem with time windows and virtual depots . The new model economizes the replenishment number of round trips, distance and time. K-means clustering method was applied to select some customers as the replenishment points, the problem was solved through the multi-objective evolutionary algorithm, based on sub-regions and the max-min strategy, and some instances were tested in the VRP web question bank. The experimental results show that the proposed model is more effective than the traditional non linehaul-feeder VRPTW.

Key words: virtual depot；linehaul feeder；Vehicle Routing Problem (VRP); multiobjective optimization; multiobjective evolutionary algorithm