摘要： 针对无向网络中带有收益值有容限的弧路径问题，提出一种变邻域搜索算法。生成需求边的有序列，以相同概率初始化每条边的方向，采用分割算法构造初始解，运用6种邻域结构进行广域搜索，使用局部搜索算法改进解，利用旋轮法选择邻域结构。实验结果表明，该算法能提高效率，避免早期陷入局部最优，稳定性较好。

关键词: 带有收益有容量限制的弧路径问题, 变邻域搜索算法, 局部搜索, 分割算法, 邻域结构, 旋轮法

Abstract: For the problem that Undirected Capacitated Arc Routing Problem with Profits(UCARPP), a Variable Neighborhood Search(VNS) algorithm is proposed. Generating the sequence of the demand side, initializing each edge of the same probability in the direction, the initial solution is generated by the split algorithm, six kinds of neighborhood structures are designed to do the wide area search, local search is proposed to improve the solution, the rotary wheel algorithm is applied to select the neighborhood structure. Experimental results show that the algorithm can improve the efficiency, avoid the early convergence and have better stability.

Key words: Undirected Capacitated Arc Routing Problem with Profits(UCARPP), variable neighborhood search algorithm, local search, split algorithm, neighborhood structure, rotation wheel method

中图分类号: 

• TP301.6