Abstract:

Aiming at the multi-depot half-open vehicle routing problem and consideringthe soft time window constraints and vehicle speed changes, an optimization model with the goal of maximizing average customer satisfaction, shortest distribution distance and minimum distribution cost is established and a two-stage solution algorithm is designed. The self-adaptive grid density method and neighborhood crowding density method are used to maintain the external archives and to select the global optimal particles, and the convergence of the multi-objective particle swarm optimization (MOPSO) and the diversity of the later population can be improved to obtain the initial feasible solution. The initial feasible solution is optimized by the variable neighborhood search algorithm(VNS) to reduce the delivery distance and cost.The rationality of the model and the effectiveness of the two-stage algorithm design are verified by the simulation experiments.

Key words: ime-varying speed, soft time window, multi-depot half-open, multi-objective particle swarm optimization, variable neighborhood search algorith