Research

An improved approach using Ant Colony Optimization for solving the Dynamic Facility layout problem

Project Details

Abstract

This research presents an improved Ant Colony Optimization algorithm, ACOII, to solve the dynamic construction site layout problem, a variant of the Dynamic Facility Layout Problem (DFLP) encountered in manufacturing.  The DFLP has been extensively studied in the literature and good reviews can be found in Meller and Gau (1996), Balakrishnan and Chen (1998), and Zhu et al. (2018).  The DFLP is known to be NP-complete. Recent solution approaches to the DFLP focused on adaptation of well-known metaheuristics.  Among the metaheuristic approaches used for solving the different variants of the DFLP, Zhu et al. (2018) reported that Genetic Algorithms (GA), Simulated Annealing (SA), and Tabu Search (TS) and hybridizations of these methods account for the majority of approaches in the literature with only 4.7% of the surveyed algorithms using Ant Colony Optimization (ACO).   This paper contributes to the body of literature on using ACO for solving the DFLP with equal-area facilities and proposes an efficient algorithm to solve the problem.  ACOII uses a construction approach in building the layout solutions over time and uses a discrete dynamic search with heuristic info based on both relocation and flow costs to influence facilities’ placement in different time periods.  The heuristic info used in influencing the probability with which ants choose locations of TFs is inversely proportional to distance-based relocation costs making it unattractive to relocate facilities unless the tradeoff between flow costs and relocation costs justifies it.  The layouts are improved as they are constructed for every period using a greedy heuristic based on the well-known pairwise-exchange method.  The performance of ACOII is investigated using randomly generated data sets where the number of facilities and the number of time periods in the planning horizon vary to mimic what happens on a construction site over time.  The experimental results show that ACOII is effective in solving the problem.  ACOII was benchmarked against 11 existing heuristics using 48 test instances from the literature on the DFLP with known results.  The results show that ACOII outperform the benchmarked heuristics for the larger size problems of 30 facilities and 5 and 10 time periods where improved solutions for 15 out of 16 problems were found.

Publication

2019-2020-URE-ime-kattan.jpg