# Interactive Design Optimization of Layout Problems

Xiaoxiao Song, Emilie Poirson, Yannick Ravaut, Fouad Bennis

► To cite this version:

Xiaoxiao Song, Emilie Poirson, Yannick Ravaut, Fouad Bennis. Interactive Design Optimization of Layout Problems. IFIP International Conference on Advances in Production Management Systems (APMS 2021), Sep 2021, Nantes, France. pp.387-395, 10.1007/978-3-030-85914-5_41. hal-03553943

HAL Id: hal-03553943

https://hal.science/hal-03553943

Submitted on 23 Feb 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Interactive Design Optimization of Layout Problems*

Xiaoxiao Song¹(✉)[0000-0001-8076-9562], Emilie Poirson¹[0000-0002-0666-8162], Yannick Ravaut², and Fouad Bennis¹

¹ Laboratoire des sciences du numérique de Nantes (LS2N), ECN, UMR 6004, 44321 Nantes, France.
{Xiaoxiao song, Emilie.poirson, Fouad.bennis}@ec-nantes.fr
² Thales Communications, 49300 Cholet, France.
yannick.ravaut@thalesgroup.com

**Abstract.** Layout optimization plays an important role in the field of industrial engineering. The layout problem presented here involves the real and virtual rectangular components. The real components can be the devices or buildings depending on the application. The space of accessibility associated with the real component is virtual, which allows the user to access the real component in reality, such as facility maintenance. However, most of the layout problems are NP hard. The great complexity of layout problems increase the difficulty in finding a feasible layout design in a reasonable time. To resolve these problems, we propose a hybrid constructive placing strategy which makes the search of feasible designs easier. The multi-objective application presented in this study demonstrates the effectiveness and portability of the method. Since the number of optimal layout designs can be very large, a cluster approach is followed to group all similar solutions. First, the notion of pairwise similarity indicator is introduced to analyze the similarity among the optimized layout designs. Second, the visualization of the hierarchical clustering of similarity matrix is customized. Then for each design, the user can interact with it by locally modifying the position or rotation of the component. The interactivity helps the user evaluate performance of the designs and preferable results are typically achieved.

**Keywords:** Layout problem · Hybrid constructive placing strategy · Interactive design

## 1 Introduction

The layout problems (LPs) concern placing a given number of components with known dimensions in a given number of containers. The component can be the equipment, device, cabinet or building, work-space depending on the application. The innovative formulation of LP came out in [1], which introduces the virtual component to resolve the problem of accessibility in the practical applications. Solving a multi-objective LP consists of finding several solutions that

<footnote>* Supported by China Scholarship Council</footnote>
optimizes the objectives and respects a set of constraints. Generally, each place-
ment problem presents non-overlap and non-protrusion constraints. These con-
straints express the fact that there is no overlap between real components and
each component must stay inside the container.

Various methods have been developed to solve optimization problems. Con-
structive heuristic and meta-heuristic methods that can provide sub-optimal
solutions have been developed to solve multi-objective LPs. Constructive heuris-
tic procedures build a layout from scratch by successively selecting and placing
facilities until a completed layout is obtained [4]. The efficiency of Simulated An-
nealing (SA) in solving complex combinatorial problems making it interesting
for extension to multi-objective optimization [10]. In addition, it is worth not-
ing that more and more researchers now work on hybrid methods by combining
different optimization strategies [3,5,7,8].

LPs are generally considered as optimization problems and most search al-
gorithms are developed for global optimization. However, LPs are not like other
mathematics optimization problems, the complexity of the design space, and the
discontinuities in the search space that make it hard to optimize analytically. In
addition, in practical applications, the needs of users cannot be expressed as sim-
ple mathematical expressions. The great complexity of layout problems increase
the difficulty in finding a feasible layout design in a reasonable time. Motivated
by previous works [2], we propose an efficient SA based algorithm coupled with
a constructive placing strategy, which makes it easier to search feasible designs
in multi-objective LPs. First, using SA based optimization to determine the
placement order of components. Second, to explore the feasible space and guar-
antee constraints, a constructive placing strategy is applied to benefit overlap
between virtual components while keeping the maximal free space and respect
non-overlap constraint where real components cannot overlap with others. In the
experiment study, it proves the efficiency and portability of the algorithm.

Since multi-objective optimization usually solves objectives simultaneously.
Therefore there is no single optimal solution but a set of compromised solutions,
widely known as Pareto optimal set. However, there may be similarities within
the design set. In [1], the author distinguishes two configurations geometrically.
For example, the design *i* differs from the design *j* if one of the components of the
layout has been moved from at least a certain distance. In fact, it can filter very
similar designs. But a more precise method is to evaluate the similarity globally
rather than comparing between one of the components. In order to find the ideal
solution without making the user tired, a similarity indicator is proposed for each
pair of Pareto optimal design and a hierarchical clustering [9] is performed. By
visualizing the hierarchical similarity, the user could select the most appropriate
solution.

A hybrid constructive placing strategy is developed to solve the LP con-
sidering the virtual and real components. Subsequently, the detailed similarity
description and visualization tool is introduced. Finally, conclusion and future
work are given.
## 2 Hybrid Constructive Placing Strategy

For the hybrid optimization, we need to determine the placing order and the placing strategy. Suppose we have 8 real components, the permutations of placing order are 8!. Exploring all possibilities is time consuming. So we use SA algorithm to optimize the order of placing components into the container. The constructive placing strategy is based on the difference process to update these empty maximal spaces (EMSs) [6]. EMSs represent the list of largest rectangle empty space in the container. In the LP, there are real components $C_i = \{x_i, y_i, w_i, h_i\}, i \in n, n$ is the number of components and a list of associate $n_i$ virtual components $v_{ij} = \{x_{v_{ij}}, y_{v_{ij}}, w_{v_{ij}}, h_{v_{ij}}\}, j \in n_i$ (see Fig. 1). The virtual components can be considered as a set of rectangles that are defined in the local frame of real component and can be deduced by the relative coordinates to the associates real component. If there is rotation, the coordinates and size will update in the corresponding local frame as shown in Fig. 1(b).

<figure><img src="image_2.png" /><figcaption>Fig. 1. Component representation: (a) Before rotation, (b) After rotation.</figcaption></figure>

Considering the non-overlap constraint, we use two EMSs lists to track the empty space generation where current real components, real and virtual components are placed, named $S, S'$ respectively. The space in $S'$ is used to place new real components and guarantees non-overlap of real components, while the space in $S$ is used to place new virtual components and benefits overlap between virtual components. In the following sections, we describe the main idea of the constructive placing strategy and the application.

### 2.1 Placing Convention

The placement of component is determined by respecting a placement convention. Without loss of universality, there are three predefined convention options that guarantee non-overlap and non-protrusion constraints:

- Wall convention: Place the real components along the boundary of the empty space. Measure the real components and then the associated virtual components where the components being placed fit.
- Center convention: Place the virtual components along the boundary of the empty space. Measure the virtual components and then the associated real components where the components being placed fit.

- Random convention: Place components randomly along the boundary of the empty space. Mix the first two conventions mentioned above.

## 2.2 Space Generation

The EMS is a rectangle like and defined by its bottom left vertices, width and height along x-axis and y-axis where $s = [x_s, y_s, w_s, h_s]$. A space generation example of wall convention is shown in Fig. 2. At beginning, there is no component inside the container, the empty space $s_0 = [0, 0, W, H]$ in $S$ and $S'$ is initialized to the size of the container. After placing the real component $C_1$, new empty spaces are generated. So we update $S$ and $S'$ as $\{s_1, s_2\}$. A slicing tree illustrates the space generation in Fig. 2(c), (d). If there is a virtual component attached to the real component, for example $v_{11}$, the placement of $v_{11}$ will generate new empty spaces $\{s_3, s_2\}$ in $S'$. With these two lists, we can track the empty spaces generated by the placed components during the placing procedure. Fig. 3 illustrates a placement example of center convention. In this case, the virtual components will be measured first and the real components are followed later.

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Example of wall convention: (a) Space generation after placing $C_1$, (b) Space generation after placing $v_{11}$, (c) Slicing tree of $S$, (d) Slicing tree of $S'$.</figcaption></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 3.** Example of center convention: (a) Space generation after placing $v_{11}$, (b) Space generation after placing $C_1$, (c) Slicing tree of $S'$, (d) Slicing tree of $S$.</figcaption></figure>
## 2.3 Placing Strategy

To place the component properly, first enumerate all permutations of the space in *S* and *S'*. Then apply the placing convention to determine the configuration of the components. The constructive placing strategy is formulated as follows:

1. Initialize the empty space in *S* and *S'* to the container space.

2. Place the new component sequentially according to the placing order. If the pair of space (*s'*, *s*), *s'* ∈ *S'*, *s* ∈ *S* satisfies the size requirement for the component, then go through 4-way orientations of the component to find all the feasible configurations. By default, the placement of the component always closes to the boundary of the selected empty space *min(s', s)* or *max(s', s)* and generates new empty spaces with less margin. If there is feasible configuration, record the temporary configuration of component. If one component has several feasible placements, the one with maximal free space after placing the component will be selected as the prior choice.

3. Update *S* and *S'*. Repeat placing new components until a complete layout is finished. Otherwise, marked the placing order as unfeasible.

## 2.4 Application

To evaluate the performance of the hybrid optimization algorithm, we select different experiments including single-container LP and multi-container LP. The configuration of the component is determined successively by constructive placement according to the optimized order. During the optimization process, the non-dominated solutions will be kept in the external archive.

<figure><img src="image_9.png" /><figcaption>Fig. 4. Model of single-container LP.</figcaption></figure>

Single-container LP is a shelter proposed in [1] (see Fig. 4(a)) minimizes the difference of center of gravity that indicated by the blue and red points(objective 1) while maximizes the distance among cabinets and electrical box(objective 2). The simplified model is shown in Fig. 4(b) which formulates by rectangles with
mass (real components) and dotted rectangles without mass (virtual components). For example the space of accessibility of desk allows the user sit down. If the virtual components are considered in optimization, then the components density increases until 90%. The high density of the LP makes it harder to find the feasible solutions. However, the proposed hybrid optimization takes less than 5 minutes to finish 400 iterations and 4 solutions are Pareto optimal designs. The Pareto front is shown in Fig. 5(a) and the corresponding layout designs are displayed in Fig. 6(a) to (d). The previous optimal solution based on interactive modular optimization that presented in [1] is shown in Fig. 6(e) which is dominated by solution (b) and (c). The hybrid constructive placing strategy splits the space to evaluate the non-overlap constraint and the obtained high-quality results prove the optimization efficiency.

<figure><img src="image_10.png" /><figcaption>Fig. 5. Display of Pareto front.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 6. Display of Pareto-optimal designs of single-container LP.</figcaption></figure>

The innovative optimization method is also extended to solve multi-container LPs by mixing container loading and component placing. In general, the implementation in multi-container LP is quite straight forward by taking the space
of different containers as the initial empty space in *S* and *S'*. We conduct the proposed method to optimize the center of gravity along the *x*-axis(objective 1) and separate the components(objective 2) on a two containers LP. The obtained Pareto front after 400 iterations is shown in Fig. 5(b) and the corresponding layout designs are displayed in Fig. 7. All designs satisfy non-overlap and non-protrusion constraints and have different configurations. The computation complexity remains in the same level as in the single-container LP because of the same number of components. Experimental results show the portability of the proposed algorithm.

<figure><img src="image_12.png" /><figcaption>**Fig. 7.** Display of Pareto-optimal designs of multi-container LP.</figcaption></figure>

# 3 Interactive Design

In the real-world LPs, there are subjective requirements, for example the components should be accessible from the entry, which is not easy to be integrated into the problem formulation. However, by displaying the obtained Pareto front, the user can use his expertise to interact and explore the design space by manipulating locally the configuration of some components, and find the design that satisfies all the requirements. In other words, the user plays a major role in the selection of the ideal result of the application. For the optimized solutions, there may be similarities within the design set. Therefore, we define a similarity indicator to evaluate the similarity of the design, which helps the user distinguish between layout design. A similarity indicator represents how closely the current layout design resembles the others.

To calculate the similarity indicator, first, permute all the layout designs that belongs to Pareto optimal set. For each pair, calculate an element-wise, in other word, pixel by pixel difference. Then, calculate the percentage of the same elements among all elements. The value of indicator is in the range of 0 to 1. The larger the indicator is, the more closely the layout designs are. The similarity
<figure><img src="image_13.png" /><figcaption>Fig. 8. Similarity analysis.</figcaption></figure>

matrix is formulated by the symmetrical matrix where the lower/upper triangu-
lar part containing the similarity indicator of each paired designs. The similarity
matrix of the multi-container LP is represented in Fig. 8(a). By comparison, it
turns out that optimal designs of Fig. 7(d), Fig. 7(e) and Fig. 7(h); Fig. 7(f)
and Fig. 7(g) has higher similarity value because of some similar configurations.
Considering the different type of similar layout designs, it is necessary to cluster
the optimal set.

For the similarity matrix, we apply the hierarchy cluster algorithm [9] to
build nested clusters by merging similar solutions successively. At each iteration,
a distance matrix of clusters is maintained. When only one cluster remains, the
algorithm stops, and this cluster becomes the root. The hierarchical similarity
relation is shown in Fig. 8(b). For example, optimal designs of Fig. 7(d) and
Fig. 7(e) with highest similarity are grouped into the cluster 1 and the design
in Fig. 7(h) with smaller similarity value is grouped with the cluster 1 as the
cluster 2. The visualization tool can provide the hierarchy similarity information
of the designs and help the user select the preferable solutions quickly.

4 Conclusion and Future Work

The proposed hybrid constructive algorithm is the first attempt to search directly the feasible space of multi-objective LPs that formulated by the rectangular real and virtual components. In the practical applications, the conventional optimization usually takes a couple of hours or days to solve the problem which is computationally expensive. By contrast, the hybridization of SA and constructive placing strategy takes less computational efforts to find the high-quality layout designs even if the density of the problem is quite high. The user can therefore select the final design according to the preference which guarantees the interaction in time. What's more, it can be easily adopted to multi-container LP which
involves the assignment and placement of components. The experimental results
prove the effectiveness and portability of the proposed algorithm. Moreover, a
indicator that can provide similarity information is defined, based on the posi-
tion and rotation of all components. From a practical point of view, similarity
analysis is very important and useful for users to distinguish layout designs and
then make the final decision by choosing one of these optimal designs.

Actually, the proposed algorithm is based on the difference process of rect-
angular empty spaces, it could be interesting to extend the algorithm to other
applications, for example the LP with free-form components, where the update
of the empty spaces should also adapt to the shape of the component. Further-
more, the accessibility of the optimal designs should be taken into account during
the optimization process. For example in Fig. 7(c), some virtual components are
blocked such that the related real component is not accessible. Afterwards, the
complex layout problem in three-dimensional space will be considered. Expand
the possibility of interaction between virtual reality and optimized spatial layout,
which are more suitable for manipulating objects in three-dimensional space.

References

1. Bénabès, J., Poirson, E., Bennis, F., Ravaut, Y.: Interactive modular optimization strategy for layout problems. In: ASME 2011 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference - 37th Design Automation Conference. vol. 5, pp. 553–562 (2011)

2. Gonçalves, J.F., Resende, M.G.: A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research 246, 86–107 (2015)

3. Guan, C., Zhang, Z., Liu, S., Gong, J.: Multi-objective particle swarm optimization for multi-workshop facility layout problem. Journal of Manufacturing Systems 53, 32–48 (2019)

4. Hosseini nasab, H., Fereidouni, S., Ghomi, S., Fakhrzad, M.: Classification of fa-
cility layout problems: a review study. The International Journal of Advanced
Manufacturing Technology 94, 957–977 (2018)

5. Kropp, I., Nejadhashemi, A.P., Deb, K., Abouali, M., Roy, P.C., Adhikari, U., Hoogenboom, G.: A multi-objective approach to water and nutrient efficiency for sustainable agricultural intensification. Agricultural Systems 173, 289–302 (2019)

6. Lai, K., Chan, J.W.: Developing a simulated annealing algorithm for the cutting stock problem. Computers & Industrial Engineering 32, 115–127 (1997)

7. Lima, S.J.d.A., Santos, R.A.R., Alves de Araujo, S., Triguis Schimit, P.H.: Com-
bining genetic algorithm with constructive and refinement heuristics for solving
the capacitated vehicle routing problem. In: Advances in Production Management
Systems. pp. 113–121. Springer International Publishing (2016)

8. Mariem, B., Marc, Z., AFFONSO, R., Masmoudi, F., Haddar, M.: A methodology for solving facility layout problem considering barriers – genetic algorithm coupled with A* search. Journal of Intelligent Manufacturing 31, 615–640 (2019)

9. Müllner, D.: Modern hierarchical, agglomerative clustering algorithms. ArXiv abs/1109.2378 (2011)

10. Pllana, S., Memeti, S., Kolodziej, J.: Customizing pareto simulated annealing for multi-objective optimization of control cabinet layout. In: 2019 22nd International Conference on Control Systems and Computer Science. pp. 78–85 (2019)