利用精英策略ST-ACO算法对UA-FLP的优化求解.pdf

CAD/CAE/CAPP/CAM
现代制造工程( Modern Manufacturing Engineering)
2012年第12期
利用精英策略ST-ACO算法对UA-ILP的优化求解
杨嫏嫏,徐克林
(同济大学机械工程学院工业工程系,上海201804)
摘要:针对制造业中常见的不等面积设施布局优化问题(UA-FILP),提出了一种精英策略蚁群优化算法(ACO)。该算法
的主要特点是采用基于切片树(ST)的编码方法,将解分成三部分,即一只蚂蚁代表一个解,它有三部分的信息素;然后
结合启发式信息,进行更新寻优,得到最小的物流费用;同时采用比较新颖的边界曲线(BC)回溯方法求出最小物流费用
所对应的设施布局尺寸,并确定设施之间最优的输入、输出点(10)位置;最后,通过算例对比证明了该方法在解决中小
规模实际问题中的有效性及相比于某些现存方法的优越性。
关键词:不等面积设施布局优化;精英策略蚁群优化算法;切片树;边界曲线回溯方法;输入/输出点位置
中图分类号:TR491文献标志码;A文章编号:1671-3133(2012)12-0056-06
Optimization of unequal area facility layout problem based on
ST-ACO with elitist strategy
Yang Nana, Xu Kelin
College of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China
bstract: For the unequal area facility layout problem in manufacturing, an ACO algorithm with elitist strategy is put forward
This algorithm adopts the coding method based on slicing tree to divide the solution into three parts, which stand for three types of
pheromone of an ant, then combined with heuristic information to find the optimal solution that minimizes the total material flow
cost. At the same time, a new method called bounding curve backtracking is used to visualize the facility layout corresponding to
the optimal solution, and the inputoutput point position of each facility can also be confirmed during the search. Finally, several
experiments are performed to prove the validity of this algorithm in solving small and medium problems as well as its superiority to
some other existing methods
Key words: Unequal Area Facility Layout Problem(Ua-flp) Ant Colony Optimization(ACO ) algorithm with elitist strategy
Slicing Tree(ST); bounding curve backtracking method; inputoutput point position
0引言
输人、输出点(1、O)位置对物流费用的影响,将精英策
略蚁群优化( Ant Colony Optimization,ACO)算法、ST
车间设施布局间题( Facility Layout Problem,FIP)编码方式和BC曲线回溯方法相结合,求解设施面积
是决定如何在平面内安排设施位置的问题。过去FLP给定但纵横比在一定范围内变化的不等面积设施布
通常作为二次规划问题或应用有向图法求解,这类方局问题(UA-FLP),通过启发式搜索,得到了最优的设
法的主要缺点是无法充分考虑如设施的面积不等等施布局并确定较优的输入、输出点位置。
几何约束。 Bazaraa'曾提出不等面积设施布置的一
般二次规划模型,但无法保证布局的连续性。Tam/23)1问题描述与数学模型
提出了切片树( Slicing Tree,ST)的概念,但无法确定1.1问题假设
设施的具体尺寸,因此边界曲线( Bounding Curve,BC)
考虑在给定面积的平面区域内合理地摆放N个
概念被提出。
设施,并确定设施的输入、输出点位置,需要进行以下
本文所研究的不等面积设施布局问题( Unequal的问题假设及约東限制。1)车间场地用一个矩形表
Area Facility Layout Problen,UA-FLP)针对上述文献中示,其尺寸已知;2)所有设施的面积均预先给定,设施
的不足,不仅考虑设施面积的差异,而且顾及设施的纵横比在一定范围内变化,所有设施均为矩形但可具
56
万方数据