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

中国机械工程 ›› 2013, Vol. 24 ›› Issue (20): 2791-2796.

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

张则强;谭思捷;黄玉真;程文明

西南交通大学,成都,610031

出版日期:2013-10-25 发布日期:2013-10-25
基金资助:
国家自然科学基金资助项目(51205328);教育部人文社会科学研究青年基金资助项目(12YJCZH296);高等学校博士学科点专项科研基金资助项目(200806131014);四川省循环经济研究中心课题(XHJJ-1205);中央高校基本科研业务费专项资金资助项目(SWJTU09CX022)
National Natural Science Foundation of China（No. 51205328）;

Research Fund for the Doctoral Program of Higher Education of China（No. 200806131014）
Fundamental Research Funds for the Central Universities( No. SWJTU09CX022 )

Variable Neighborhood Search for Single Row Layout Problem

Zhang Zeqiang;Tan Sijie;Huang Yuzhen;Cheng Wenming

Southwest Jiaotong University,Chengdu,610031

Online:2013-10-25 Published:2013-10-25
Supported by:

National Natural Science Foundation of China（No. 51205328）;

Research Fund for the Doctoral Program of Higher Education of China

（No. 200806131014）
Fundamental Research Funds for the Central Universities( No. SWJTU09CX022 )

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: single row layout problem(SRLP), variable neighborhood search(VNS), facility layout problem, optimization

中图分类号:

TH181
TP391

张则强;谭思捷;黄玉真;程文明. 求解单行布局问题的一种变邻域搜索算法[J]. 中国机械工程, 2013, 24(20): 2791-2796.

Zhang Zeqiang;Tan Sijie;Huang Yuzhen;Cheng Wenming. Variable Neighborhood Search for Single Row Layout Problem[J]. China Mechanical Engineering, 2013, 24(20): 2791-2796.

参考文献

[1]Loiola E M,de Abreu N M M.Boaventura一 Netto PO, et al. A Survey for the Quadratic AssignmentProblem[J]. European Journal of Operational Re-search,2007 ,176(2) :657-690.
[2]Djellab H,Gourgand M. A New Heuristic Procedurefor the Single-row Facility Layout Problem[J]. In-ternational Journal of Computer Integrated Manu-facturing ^2001 ,14(3) :270-280.
[3]Simmons D M. One— dimensional Space Allocation:an Ordering Algorithm [J]. Operations Research,1969,17(5):B12-826.
[4]Heragu S S, Kusiak A. Efficient Models for the Fa-cility Layout Probiem[J]. European Journal of Op-erational Research,1991 ,53(1) : 1-13.
[5]Love R F, Wong J Y. On Solving A One- dimen-sional Space Allocation Problem with Integer Pro-gramming[J], INFOR Journal, 1976 ,14 (Compend-ex):139-143.
[6]Amaral A R S. On the Exact Solution of a FacilityLayout Problem[J]. European Journal of Operation-al Research,2006 ,173(2) : 508-518.
[7]Amaral A R S. An Exact Approach to the One-di-mensional Facility Layout Problem [J], OperationsResearch,2008,56(4) ;1026-1033.
[8]Datta D, Amaral A R S, Figueira J R. Single RowFacility Layout Problem Using a Permutation —based Genetic Algorithm [J]. European Journal ofOperational Research,2011,213(2) :388-394.
[9]Samarghandi H,Taabayan P,Jahantigh F F. A Par-ticle Swarm Optimization for the Single Row Facili-ty Layout Problem[J]. Computers & Industrial En-gineering, 2010,58 (4) :529-534.
[10]锁小红[1],刘战强[1].基于物流路径的单行布局建模与仿真研究[J].中国机械工程,2007,18(21):2576-2579.
[11]祝恒云[1,2],叶文华[1].模拟退火粒子群算法在动态单元布局中的应用[J].中国机械工程,2009,10(2):181-185.
[12]Hansen P, Mladenovic N, Moreno P J. VariableNeighborhood Search [J]. European Journal ofOperational Research,2008,191(3) : 593-595.
[13]董红宇.变邻域搜索算法综述.控制工程,2009,16:1-5.
[14]Samarghandi H, Eshghi K. An Efficient Tabu Al-gorithm for the Single Row Facility Layout Prob-lem [J European Journal of Operational Re-search, 2010,205(1) -.98-105.
[15]Kothari R,Ghosh D. Tabu Search for the SingleRow Facility Layout Problem Using Exhaustive 2—opt and Insertion Neighborhoods [J ]. EuropeanJournal of Operational Research,2013 .224(1) : 93-100.
[16]Heragu S S,Kusiak A. Efficient Models for the Fa-cility Layout Problem [J]. European Journal ofOperational Research,1991,53(11) ; 1-13.
[17]Ravi Kumar K, Hadjinicola G C, Lin 丁 L. A Heu-ristic Procedure for the Single— row Facility Lay-out Problem[J]. European Journal of OperationalResearch,1995 ,87(1) : 65-73.
[18]Hungerlander P,Rendl F. Semidefinite Relaxationsof Ordering Problems[J]. Mathematical Program-ming,2013 ,140(1) :77-97.