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

Variable Neighborhood Search for Single Row Layout Problem

作　　者：张则强[1] 谭思捷[1] 黄玉真[1] 程文明[1] 

机构地区：[1]西南交通大学,成都610031

出　　处：《中国机械工程》2013年第20期2791-2796,共6页China Mechanical Engineering

基　　金：国家自然科学基金资助项目(51205328);教育部人文社会科学研究青年基金资助项目(12YJCZH296);高等学校博士学科点专项科研基金资助项目(200806131014);四川省循环经济研究中心课题(XHJJ-1205);中央高校基本科研业务费专项资金资助项目(SWJTU09CX022)

摘　　要：设施布局问题对于企业内部的物流合理化起着重要作用,单行布局问题作为设施布局问题的一个典型特例,属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.

关 键 词：单行布局问题 变邻域搜索算法 设施布局问题 优化 

分 类 号：TH181[机械工程—机械制造及自动化] TP391[自动化与计算机技术—计算机应用技术]