求解CARPSD问题的自适应局部搜索算法  

Adaptive Local Search Algorithm for Solving CARPSD Problem

作　　者：王立斌[1] 林丹[1] 

机构地区：[1]天津大学数学系,天津300072

出　　处：《计算机工程》2013年第2期211-215,共5页Computer Engineering

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]