Particle Swarm Optimization for Open Vehicle Routing Problem with Time Dependent Travel Time

Abstract Open Vehicle Routing Problem with Time Dependent Travel Time (OVRPTD) is different from most variants of vehilce routing problems from the liteture in that the vehicle dosen't return to the depot after serving the last customer and the travle time is time dependent. The travle time is presented by a continuous dynamic network time dependent function. Particle Swarm Optimization with self-adaptive inertia weight is presented. Each particle regulates its inertia weight according to the corresponding position with itself and the best particle in the population. Different updating rules are applied to the excellence particles and the inferior particles. For the excellence particles, compute their information entropy after server iterations, and update their position according to the new position updating function. And for the inferior particles, record them in the bulletin board, then after several iteration, use the new particles displace the inferior according the appearance frequency in the board. In the experiment, the influence of the population, iteration, inertia weight for the optimization result is discussed. By the experiment, give the field of the parameter. Compare the particle swarm optimization with other algorithms by the benchmark. The result shows the algorithm in the paper is the efficiency for the OVRPTD.