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

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

针对带随机需求的限量弧路径规划(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.