z
Available online at http://www.journalcra.com
http://www.journal
INTERNATIONAL JOURNAL
OF CURRENT RESEARCH
International Journal of Current Research
Vol. 9, Issue, 07, pp.53529-53533, July, 2017
ISSN: 0975-833X
RESEARCH ARTICLE
FLOOR LAYOUT OPTIMIZATION USING GENETIC ALGORITHM
*Nitin Choubey
Department of Computer Science & Information Technology, SVKM’s NMIMS University, MPSTME, Shirpur
Shirpur, India
ARTICLE INFO ABSTRACT
Article History: This papers present a floor layout optimization system with Genetic algorithms. Efficient market floor
Received 30th April, 2017 layour management is required for better customes satisfaction and increased visibility of the product.
Received in revised form It can be achieved through propoer allocation of the shelves
shelves on shop floor. The paper also compares
12th May, 2017 the results for layout optimization for different sizes with the on varying population size.
Accepted 07th June, 2017
Published online 22nd July, 2017
Key words:
Genetic Algorithms, Floor planning,
Crossover, Mutation, Optimization.
Copyright©2017, Nitin Choubey. This is an open access article distributed under the Creative Commons Attribution
Attribution License, which permits unrestricted use,
distribution, and reproduction in any medium, provided the original work is properly cited.
Citation: Nitin Choubey, 2017. “Floor algorithm International Journal of Current Research
Floor layout optimization using genetic algorithm”, Research, 9, (07), 53529-53533.
INTRODUCTION to develop ways in which the mechanisms of natural adaptation
might be utilized into computer systems. Holland (1975) in
Facility planning is arrangement of the goods, services, shelves ‘Adaptation in Natural and Artificial Systems’ presented the
for production of goods or for delivery of the services (Figure GA as an abstraction of biological evolution and gave a
1). The main objective of the facility planning is to bring our theoretical framework for adaptation under the GA. Many
maximum customer satisfaction. Research (Juel-Jacobsen, problems in engineering and related areas require the
2015) on pathway design has shown that well-established
well simultaneous genetic optimization for a number of possibly
principles of urban retail designs are very important for retail competing objectives. These have been solved by combining
managers, in particular for supermarkets and larger retail the multiple objectives in to single scalar by the approach of
stores. The store layout influences both shopping atmosphere linear combination. The combining coefficients, however,
and shopping behaviorr of consumers visiting the store usually based on heuristic or guesswork can exert an unknow
unknown
(Lewison, 1994).. A well designed store layout can contribute to influence on the outcome of the optimization. A more
a positive shopping atmosphere, which results in the kind of satisfactory approach is to use the notion of Pareto optimality
shopping behavior, a retailer wants to achieve. According to by Goldberg (1989) in which an optimal set of solutions
study by Timjen Elbers (2016), Grid layout, long pathways prescribe some surface ‘The Pareto front’ in the vector space of
which are placed parallel to each other, facilitates an efficient the objectives (Goldberg,
Goldberg, 1989
1989). For a solution on the Pareto
and fast shopping experience. Retailers are in favor of grid front no objective can be improved without simultaneously
layout style because the rectangular arrangement of the shelves degrading at least one other. This is routinely used to generate
fits well in the shopping behavior of consumers
consu and has useful solutions to optimization and search problems. Genetic
universally the most preferred layout style by supermarket algorithms belong to the larger class of evolutionary algorithms
retailers. Tompkins and White (1996) discuss about 50% of (EA), generates solution to optimization problems using
total operating expenses can be reduced through a good techniques inspired by natural evolution, such as inheritance,
placement of facilities. John Holland invented GA in 1960s mutation, selection, and crossover. In a genetic algorithm, a
(Holland, 1975).. In contrast with evolution strategies and population of strings (called chrom
chromosomes or the genotype of
evolutionary programming, Holland’s original goal was not to the genome), which encode candidate solutions (called
design algorithms to solve specific problems, but to formally individuals, creatures, or phenotypes) to an optimization
study the phenomenon of adaptation as it occurs in nature and problem, evolves toward better solutions. Traditionally,
solutions are represented in binary as strings of 0’s and 1’s
1’s, but
*Corresponding author: Nitin Choubey, other encodings are also possible. The evolution usually starts
Department of Computer Science & Information Technology, from a population of randomly generated individuals and
SVKM’s NMIMS University, MPSTME, Shirpur,, India. happens in generations. In each generation, the fitness of every
53530 Nitin Choubey, Floor layout optimization using genetic algorithm
individual in the population is evaluated, multiple individuals 3. Perform selection of the individual by Tournament
are stochastically selected from the current population (based selection method.
on their fitness), and modified (recombined and possibly 4. Generate offspring by single point crossover.
randomly mutated) to form a new population. The new 5. Generate offspring by swap bit mutation.
population is then used in the next iteration of the algorithm. 6. Calculate fitness for the generated offspring.
Commonly, the algorithm terminates when either a maximum 7. Combine offspring generated in step 4 & step 5 with
number of generations has been produced, or a satisfactory current population to get next population by overlapped
fitness level has been reached for the population. If the population method.
algorithm has terminated due to a maximum number of 8. Repeat steps 3 through 7 until termination criterion is
generations, a satisfactory solution may or may not have been reached.
reached. Genetic algorithm (GA) has been widely used in
optimization with binary and continuous variable and is The offspring are generated separately by the process of
popular in solving facility layout problem, R. Haupt and Haupt crossover and mutation and the entire collection is treated as
(2004). GA are found to be efficient search methods for finding child population. The resultant child populations is them
solution of Travelling Salesperson problem (Choubey, 2012; combined with parent population to get next population.
Choubey, 2013), Travelling Tournament problem (Choubey,
2010), Solving different maze structures (Choubey, 2012), Chromosome structure and Mapping
grammar induction (Choubey and Kharat, 2012; Nitin Choubey
and Madan Kharat, 2011; Choubey and Kharat, 2010) etc. The chromosome structure encoding uses decimal numbers for
Misola and Navarro (2014) presented genetic algorithm to representing the cells for shelves placement. Figure gives the
solve facility layout problem to minimize total cost function chromosome representation and the equivalent for the
(Maricar G. Misola and Bryan B. Navarro, 2014). Dalgic used chromosome representation. To get the optimal length of the
GA for Market floor planning. The objective of the paper is to chromosome, it is kept at size of twice that of the number of
find the optimal grid-shelf layout for the floor planning using racks (Shelves). The chromosome bit is encoded as 4-tuple
Genetic Algorithm with different level of complexity for the {Row, Column, Direction, Length}. The codes for direction are
specific rectangular floor dimension. 0, 1, 2 & 3 for arrangement of the shelves from row-column
position to Right, Left, down and up respectively. The sample
chromosomes structure for 10 shelves placed in rectangular
layout of size 6 by 6 is shown in the Figure 2. The fitness of a
chromosome is calculated based on several criteria’s as given
below.
1. No shelve should be placed in overlapping with another
cell.
2. The ENTRY and EXIT cells should not be blocked.
3. No shelve should have more than three shelves kept
adjacent to it.
4. The Grid layout should be followed.
5. There should not be isolated/unreachable areas from
either ENTRY or EXIT in the layout.
The penalty is applied in case of each violation of the criteria
mentioned above.
Experimental Setup and Result
Figure 1. Typical Market shop floor (Maricar G. Misola and The experiment is conducted JDK 1.6 on Experiment is done
Bryan B. Navarro, 2014) with JDK 1.4 on an Intel Core™2 CPU with 2.66 GHZ and 2
GB RAM. The experiment was examined for varying
Methodology Used population size and the shelves to be placed in a 10 by 10 shop
floor space. Maximum number of generation = 100000,
The following subsections introduce the various important Crossover Rate = 0.8 and mutation rate = 0.1 is used for the
components used in the genetic algorithm process. purpose of experiment. The length of chromosome is
considered equal to the length double to the size of the number
Genetic Algorithm of racks to be placed. The Generation run is terminated, if the
solution with desired fitness values is found before reaching to
The GA produces successive generations of individuals, the maximum number of generations. Comparison of
computing their “fitness” at each step and selecting the best of generation runs for the various numbers of shelves
them, when the termination condition arises. Genetic arrangements (25, 30, 35, 40) with different population size
Algorithm approach used in the papers is given below. (10, 20, 30) are shown in the Figure 3. As GA’s works on
initial random seed population, the collected data is represented
1. Create initial random population. as average of the best fitness over generation runs for ten
2. Calculate fitness of the individuals in the population. executions samples for the purpose of comparison. The result
obtained for the arrangement of 25, 30, 35 and 40 racks are
shown in Figure 4.
53531 International Journal of Current Research, Vol. 9, Issue, 07, pp.53529-53533, July, 2017
Figure 2. Chromosome structure and equivalent Layout
Figure 3. Generation Charts
53532 Nitin Choubey, Floor layout optimization using genetic algorithm
Figure 4. 10 by 10 Layout results for 25, 30, 35, 40, 45 numbers of shelves
Conclusion Choubey N. S. 2010. A Novel Encoding Scheme for Traveling
Tournament Problem using Genetic Algorithm, JCA
Genetic algorithms proved to be efficient method for finding Special Issue on Evolutionary Computation for
the optimal results in market shop floor layout planning. It is Optimization Techniques (ECOT), International Journal of
found that Gas required higher number of generations to find Computer Application,, pp 79
79-82.
optimal layout when used for higher number of shelves to be Choubey N. S. 2012. “A-Mazer
Mazer with Genetic Algorithm”,
placed in the given floor dimension. Genetic Algorithms found International Journal of Computer Applications
Applications, (0975-
to provide multiple optimal solutions to the given number of 8887)58(17), November.
shelves requirement in the given area. Choubey N. S. 2012. Solving TSP using DARO, International
Journal of Computer Applications
Applications, (0975 – 8887) Volume
REFERENCES 58– No.9, November 2012.
Choubey N. S. 2013. Movingoving Target Travelling Salesman
Carl Heintz, How do you approach retail stores to sell your Problem using Genetic Algorithm, International Journal of
products?, August 2016 https://ceanow.org/marketing-
https://ceanow.org/marketing Computer Applications, (0975
(0975–8887) Volume 70–No.2,
sales/approach-retail-stores-sell-products/
products/ May.
53533 International Journal of Current Research, Vol. 9, Issue, 07, pp.53529-53533, July, 2017
Choubey N. S. and Kharat M. U. 2012. Hybrid system for Lewison, D. M. 1994. Retailing. New York: Macmillan
handling premature convergence in GA – Case of grammar College Publishing Company.
induction, Appl. Soft Computing J., http://dx.doi.org/10. Maricar G. Misola and Bryan B. Navarro, 2014. Optimal
1016/j.asoc.2012.03.069. Facility Layout Problem Solution Using Genetic Algorithm,
Choubey N.S. and Kharat M.U. 2010. “Grammar Induction World Academy of Science, Engineering and Technology,
Strategy Using Genetic Algorithm: Case Study of Fifteen International Journal of Mechanical, Aerospace, Industrial,
Toy Languages”. Pacific Journal of Science and Mechatronic and Manufacturing Engineering, Vol:7, No:8.
Technology, 11(1):294-300. Nitin Choubey and Madan Kharat, 2011. Approaches for
Goldberg D.E. 1989. Genetic Algorithms in Search, handling premature convergence in CFG Induction Using
Optimizations and Machine Learning, Addison-Wesley. GA, Gaspar-Cunha et al. (Eds.): Soft Computing in
Haupt R. and S. Haupt 2004. Practical Genetic Algorithms, Industrial Applications, AISC 96, pp. 55–66, Springer-
Second Edition, John Wiley and Sons, Inc. Verlag Berlin Heidelberg.
Holland, J.H. 1975. Adoption in Natural and Artificial System, Timjen Elbers, 2016. The effects of in-store layout- and shelf
University of Michigan Press, Ann Arbor, MI. designs on consumer behavior, http://edepot.wur.nl/369091
Juel-Jacobsen, 2015. L.G. Aisles of life: outline of a customer- Tompkins J. A. and J. A. White 1996. Facilities Planning. 2nd
centric approach to retail space management, International Ed., New York, John Wiley.
Review of Retail, Distribution and Consumer Research, 25
(2), pp. 162-180
*******
