求解单行布局问题的一种变邻域搜索算法

Variable Neighborhood Search for Single Row Layout Problem

设施布局问题对于企业内部的物流合理化起着重要作用,单行布局问题作为设施布局问题的一个典型特例,属NP-hard问题,常规方法难以精确求解。针对单行布局问题的复杂性,提出了一种改进的变邻域搜索算法进行求解。首先构建单行布局问题的数学模型,然后分析模型并构造一种有效的初始解;针对问题特征,设计了4种邻域结构,该邻域结构采用了从简单到复杂的推进搜索机制;改进了局部搜索算法并对邻域结构进行搜索;最后进行了实例验证,并与多种经典算法进行了对比,结果表明,所提变邻域搜索算法可在短时间内得到单行布局问题高质量的近优解。

Facility layout problem plays an important role in the rationalization of enterprise internal logistics.SRLP is a special example of the facility layout problem.SRLP is a NP-hard problem that it is difficult to solve the exact results for conventional methods.A modified VNS algorithm was proposed to solve SRLP.First,a mathematical model of SRLP was given,and then,the model was analyzed and an initial solution algorithm was designed.According to the characteristics of the SRLP,four types corresponding neighborhood structure were designed,which adopted advance search mechanism from the simple to the complex.The local search used in the search of neighborhood structure was also improved.Finally,through calculating a large number of instances with the VNS and comparing many successful classical algorithms,the results show that the proposed VNS can obtain near optimal solutions of high quality in a short time.