摘要： 针对带随机需求的限量弧路径规划(CARPSD)问题,建立基于期望与方差的数学模型,设计一种概率型邻 域搜索算法。采用随机路径扫描产生初始种群,构建最优解集。根据影响解的质量的4 个关键指标,构建4 种领 域结构。应用算法的概率机制,计算邻域搜索的强度,进行大小邻域结构的转化,指导邻域搜索。通过Restart 策 略,扩大解空间的范围。实验结果表明,该算法可有效解决CARPSD 问题,比自适应较大的邻域算法具有更强的寻 优能力。

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

Abstract: 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.

Key words: Capacitated Arc Routing Planning with Stochastic Demand(CARPSD), neighborhood search, probabilistic mechanism, stochastic demand, Stochastic Path Scanning(SPS), similarity

中图分类号: 

• TP301.6