Abstract: For the Capacitated Arc-routing Problem with Stochastic Demand(CARPSD), an adaptive local search algorithm is proposed. It generates the initial population which is based on Stochastic Path Scanning(SPS), and selects the best one as the initial solution. Adaptive local search is implemented to speed up the convergence rate. For the selection of search operation, two local search mechanism are designed. Experimental results show that the optimum solution of this algorithm is improved, the running time is shorten by 60% compared with the Adaptive Large Neighborhood Search(ALNS) algorithm.

Key words: Capacitated Arc-routing Problem(CARP), local search, stochastic path scanning, adaptivity, stochastic demand, weight

摘要： 针对带有随机需求的弧路径规划问题，提出一种自适应局部搜索算法。采用随机路径扫描算法产生初始种群，选出最优者作为初始解，以自适应的方式进行局部搜索，并设计2种局部搜索机制。实验结果表明，与自适应大邻域搜索算法相比，该算法的最优解得到改进，运行时间平均缩短60%。

关键词: 带有容量限制的弧路径规划问题, 局部搜索, 随机路径扫描, 自适应性, 随机需求, 权重

CLC Number: 

• TP301.6