Abstract:

In order to improve the operation efficiency of the parallel saving algorithm, the reasonable neighborhood selection strategy and data structure were  used to reduce the space and time complexity of the algorithm. A new scheme of the adaptive neighborhood selection strategy was adopted to improve the rationality of neighborhood selection through optimizing the neighborhood radius and data structure, with the data dimensions and customer distribution condition of VRP as the breakthrough point with comprehensive consideration of the relationship among the neighborhood range of the customer, distance, dimensions and distribution. Comparing the proposed scheme with other non-adaptived schemes, the results showed that the former had obvious advantages on concentrated VRP by significantly reducing computation time and storage space while guaranteeing the operation quality. Taking the rl5915 as an example, its operation time was 50％ less than other non-adaptived strategies. Theory research and experimental results showed that adaptive neighborhood selection strategy could  improve the operation efficiency of the saving algorithm.

Key words: saving algorithm, adaptive neighborhood selection, neighborhood, vehicle routing problem, performance evaluation