We investigate the  multi-trip vehicle routing problem with time windows and release dates (MTVRP-TW-RD) in the context of city logistics distribution system. Firstly, this transportation scheduling problem is formally described and a mathematical model is designed to minimize the total delivery time. Then, we propose a beam-PSO algorithm to quickly obtain satisfactory solutions. According to the characteristics of the MTVRP-TW-RD, we propose a new coding and decoding method based on random keys to overcome the shortcoming of the basic particle swarm optimization (PSO) which is that it cannot be directly applied to discrete problems. In addition, a local search process based on the beam search optimization technique is designed to enhance the performance of the beam-PSO. Simulations are carried out, and experimental results demonstrate the feasibility and validity of the proposed algorithm.

 ,