Abstract:
The variable neighborhood search algorithm may have difficulty in searching a better feasible solution in some neighborhoods for a long time in later stage. Aiming at the shortcoming, this paper proposes an adaptive variable neighborhood search algorithm based on neighborhood selection probability. The proposed algorithm can adjust the selection probability in some neighborhoods adaptively according to the optimization circumstance of this neighborhood such that the optimization efficiency can be improved. This paper designs two select probability update methods and analyzes their characteristics. By setting the minimum selection probability, the selection probability may be avoided to reduce to zero and the diversity of the neighborhood can be ensured. Due to battery capacity limitations and charging requirements, the optimization problem of the electric vehicle route is more complicated than the traditional vehicle route problem. By modeling and analyzing the large-scale electric vehicle routing problem under the actual urban distribution logistics, this paper propose an efficient initial solution generation algorithm according to the geographic location and the time window of the service customer. Some neighborhood operators using segmentation-exchange, 2-opt, and relocation are designed to achieve the adaptive variable neighborhood search. Finally, the simulation experiments with different scales data are made. It is shown from the results that the variation curves of the two select probability update methods have the same tendency, which verifies the rationality of minimum selection probability vector setting. Compared with the traditional variable neighborhood search algorithm, the proposed adaptive variable neighborhood search algorithm can effectively jump out of the local optimal solution and reduce the logistical cost under urban distribution.