Production, Manufacturing and Logistics
Applying Ant System for solving Unequal Area Facility Layout Problems

https://doi.org/10.1016/j.ejor.2009.06.016Get rights and content

Abstract

Ant Colony Optimization (ACO) is a young metaheuristic algorithm which has shown promising results in solving many optimization problems. To date, a formal ACO-based metaheuristic has not been applied for solving Unequal Area Facility Layout Problems (UA-FLPs). This paper proposes an Ant System (AS) (one of the ACO variants) to solve them. As a discrete optimization algorithm, the proposed algorithm uses slicing tree representation to easily represent the problems without too restricting the solution space. It uses several types of local search to improve its search performance. It is then tested using several case problems with different size and setting. Overall, the proposed algorithm shows encouraging results in solving UA-FLPs.

Introduction

Ant System (AS) is the first variant of Ant Colony Optimization (ACO) which was introduced by Dorigo and his colleagues in the early 1990s (Blum, 2005). ACO works by imitating the foraging behavior of ants when searching for the shortest path to reach their food source. ACO was initially developed for solving the Traveling Salesman Problems (TSPs). Thereafter, its application was extended to solve various kinds of discrete optimization problems including the Quadratic Assignment Problems (QAPs), Vehicle Routing Problems (VRPs), Job-Shop Scheduling Problems (JSPs), etc.

This paper attempts to investigate the performance of AS when solving the Unequal Area Facility Layout Problems (UA-FLPs). To date, a formal ACO-based metaheuristic has not been applied to solve them. Recent research has mainly used it to deal with QAPs (Hani et al., 2007, Stützle and Dorigo, 1999, See and Wong, 2008, Wong and See, 2009a, Wong and See, 2009b). Besides this, it has also been used for solving machine layout problems (Corry and Kozan, 2004). Generally, ACO has been proven to perform outstandingly when solving QAPs, which are the backbone problems for UA-FLPs (Stützle and Dorigo, 1999). This motivates the authors to create a new AS for solving UA-FLPs, and to investigate its performance.

UA-FLPs were originally formulated by Armour and Buffa (1963). Conceptually, the main objective of UA-FLPs is to partition a given area/region into departmental sub-regions so that the total material movement cost between departments could be minimized. The constraints for solving UA-FLPs (Meller and Gau, 1996) are: (1) all departments must be located within a given area or facility, (2) all departments must not overlap with each other, and (3) the layout must fulfill the maximum ratio constraints (or minimum value restrictions) for the dimension of departments (length and width of each department).

This paper is structured as follows: Section 2 describes the fundamentals of AS and current research in UA-FLPs. Section 3 discusses about the new AS formulation created by the authors to solve UA-FLPs. Section 4 mentions the parameter settings and case problems which are used to test the proposed algorithm. Section 5 analyzes and describes the evaluation results obtained. Finally, this paper ends with conclusions in Section 6.

Section snippets

Literature review

ACO is a discrete optimization technique which imitates the foraging behavior of an ant colony. Particularly, it resembles the behavior of an ant colony in finding the shortest path to reach its food source. After the initialization of parameters and input of problem data, every ACO iteration consists of ant solutions construction, local search procedures (optional), and pheromone information update. The explanations of these three components are as follows (Blum, 2005):

ConstructAntSolutions( ).

Formulation

In this section, a detailed explanation of the proposed AS algorithm will be given. Specifically, it describes the ant solution representation used and the three main phases of the proposed algorithm, i.e., ant solutions construction, local search procedures, and pheromone information update.

Numerical experiments

The proposed algorithm was tested using various problem sets taken from the literature. They are O7, O8 and O9 from Meller et al. (1999), vC10 from van Camp et al. (1992), Ba12 and Ba14 from van Camp (1989), AB20 from Armour and Buffa (1963), SC30 and SC35 from Liu and Meller (2007), and Du62 from Dunker et al. (2003). These problem sets are chosen because of their variety in size (from 7 departments until 62 departments). In addition, they are chosen because they are widely used in previous

Results and discussion

The statistical results obtained after running the proposed algorithm are shown in Table 1. From the table, it is shown that the proposed algorithm is robust since the percentage of gap between the best and worst solutions is relatively low. The computation time needed is acceptable considering the fact that various types of local search are used in the algorithm. In addition, facility layout planning is not a time-critical issue (See and Wong, 2008).

The local search procedures contribute to

Conclusions

This paper has proposed an AS algorithm with slicing tree representation for solving UA-FLPs. This is probably the first paper which investigates the use of ACO for solving UA-FLPs. The proposed algorithm is quite robust and has improved several problem instances as compared to previous research. It performs better than GA with flexible bay representation which was proposed by Tate and Smith (1995). In comparison to Liu and Meller (2007)’s and Scholz et al. (2009)’s approaches, the proposed

Acknowledgements

The authors would like to thank the Ministry of Science, Technology and Innovation (MOSTI), Malaysia for funding this research under the E-Science Grant Number: 03-01-06-SF0024. We would also like to thank the three anonymous referees for their valuable comments.

References (23)

  • P. Corry et al.

    Ant colony optimisation for machine layout problems

    Computational Optimization and Applications

    (2004)
  • Cited by (125)

    • Addressing Unequal Area Facility Layout Problems with the Coral Reef Optimization algorithm with Substrate Layers

      2020, Engineering Applications of Artificial Intelligence
      Citation Excerpt :

      In this section, the performance of the proposed CRO-SL system is evaluated in a large set of UA-FLPs and compared to existing previous approaches. This way, the following UA-FLPs instances have been tested: Slaughterhouse detailed in Salas-Morera et al. (1996); CartonPacks and ChoppedPlastic from García-Hernández et al. (2013a); O7, O8 and O9 (formulated as Wong and Komarudin, 2010), stated by Meller et al. (1998); VC10 (considering all aspect ratio options) explained in van Camp et al. (1992); MB12 described by Bozer and Meller (1997); Ba12 presented in Bazaraa (1975); Ba14 detailed in Komarudin and Wong (2010) of the UA-FLP stated in Bazaraa (1975); AB20 stated by Armour and Buffa (1963) with different aspect ratio constrains; SC30, considering formulation of Komarudin and Wong (2010) of the UA-FLP explained in Liu and Meller (2007); SC35 described by Liu and Meller (2007); and DU62 detailed by Dunker et al. (2003). An important point in the CRO-SL is the selection of the number of substrate layers and its composition.

    • A novel multi-objective Interactive Coral Reefs Optimization algorithm for the Unequal Area Facility Layout Problem

      2020, Swarm and Evolutionary Computation
      Citation Excerpt :

      In order to address the UA-FLP, different techniques and algorithms have been considered. Following the classification by Komarudin and Wong [26], it is possible to divide them into deterministic methods and heuristics (or meta-heuristics) approaches. Regarding the first category, a first proposal based on a branch and bound method was suggested by Meller et al. [27].

    View all citing articles on Scopus
    View full text