基于带随机需求的限量弧路径规划概率型邻域搜索算法  

Probabilistic Neighborhood Search Algorithm Based on Capacitated Arc Routing Planning with Stochastic Demand

作　　者：王立斌[1] 安志朋 林丹[2] 

机构地区：[1]河北金融学院基础部,河北保定071051 [2]天津大学数学系,天津300072

出　　处：《计算机工程》2015年第5期197-201,共5页Computer Engineering

摘　　要：针对带随机需求的限量弧路径规划(CARPSD)问题,建立基于期望与方差的数学模型,设计一种概率型邻域搜索算法。采用随机路径扫描产生初始种群,构建最优解集。根据影响解的质量的4个关键指标,构建4种领域结构。应用算法的概率机制,计算邻域搜索的强度,进行大小邻域结构的转化,指导邻域搜索。通过Restart策略,扩大解空间的范围。实验结果表明,该算法可有效解决CARPSD问题,比自适应较大的邻域算法具有更强的寻优能力。A mathematical model based on expectation and variance is constructed,and a Probabilistic Neighborhood Search（PNS） is proposed for the Capacitated Arc Routing Planning with Stochastic Demand（CARPSD）. The heuristic generates the initial solution through Stochastic Path Scanning（ SPS） to construct the set of optimal solution. According to four key indicators having an influence on the solution quality,it builds four neighborhood structure,applies probabilistic mechanism of heuristic to calculate the intensity of neighborhood search. The size of neighborhood structure is transformed to guide the neighborhood search. Restart strategy is implemented to expand the scope of the solution space and avoids excessive local search, improving efficiency of the algorithm. Computational results show CARPSD is effectively solved and the optimization superiority of this algorithm is over the Adaptive Large Neighborhood Search （ ALNS） algorithm.

关 键 词：带随机需求的限量弧路径规划 邻域搜索 概率机制 随机需求 随机路径扫描 相似度 

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