Xiaoxiao Song
email: xiaoxiao.song@ec-nantes.fr

Emilie Poirson
email: emilie.poirson@ec-nantes.fr

Yannick Ravaut
email: yannick.ravaut@thalesgroup.com

Fouad Bennis
email: fouad.bennis@ec-nantes.fr

Interactive Design Optimization of Layout Problems

Keywords: Layout problem, Hybrid constructive placing strategy, Interactive design

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.

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 [START_REF] Bénabès | Interactive modular optimization strategy for layout problems[END_REF], 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 Supported by China Scholarship Council optimizes the objectives and respects a set of constraints. Generally, each placement problem presents non-overlap and non-protrusion constraints. These constraints 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. Constructive heuristic and meta-heuristic methods that can provide sub-optimal solutions have been developed to solve multi-objective LPs. Constructive heuristic procedures build a layout from scratch by successively selecting and placing facilities until a completed layout is obtained [START_REF] Hosseini Nasab | Classification of facility layout problems: a review study[END_REF]. The efficiency of Simulated Annealing (SA) in solving complex combinatorial problems making it interesting for extension to multi-objective optimization [START_REF] Pllana | Customizing pareto simulated annealing for multi-objective optimization of control cabinet layout[END_REF]. In addition, it is worth noting that more and more researchers now work on hybrid methods by combining different optimization strategies [START_REF] Guan | Multi-objective particle swarm optimization for multi-workshop facility layout problem[END_REF][START_REF] Kropp | A multi-objective approach to water and nutrient efficiency for sustainable agricultural intensification[END_REF][START_REF] Lima | Combining genetic algorithm with constructive and refinement heuristics for solving the capacitated vehicle routing problem[END_REF][START_REF] Mariem | A methodology for solving facility layout problem considering barriers -genetic algorithm coupled with A* search[END_REF].

LPs are generally considered as optimization problems and most search algorithms 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 simple 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 [START_REF] Gonçalves | A biased random-key genetic algorithm for the unequal area facility layout problem[END_REF], 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 guarantee 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 [START_REF] Bénabès | Interactive modular optimization strategy for layout problems[END_REF], 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 [START_REF] Müllner | Modern hierarchical, agglomerative clustering algorithms[END_REF] 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 considering the virtual and real components. Subsequently, the detailed similarity description and visualization tool is introduced. Finally, conclusion and future work are given.

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) [START_REF] Lai | Developing a simulated annealing algorithm for the cutting stock problem[END_REF]. EMSs represent the list of largest rectangle empty space in the container. In the LP, there are real components 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 relatives 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). 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.

C i = {x i , y i , w i , h i }, i ∈ n, n is the number of components and a list of associate n i virtual compo- nents v ij = {x vij , y vij , w vij , h vij }, j ∈ n i (see Fig.

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.

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 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.

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.

Application

To evaluate the performance of the hybrid optimization algorithm, we select different 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. Single-container LP is a shelter proposed in [START_REF] Bénabès | Interactive modular optimization strategy for layout problems[END_REF] (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 [START_REF] Bénabès | Interactive modular optimization strategy for layout problems[END_REF] 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. 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 nonprotrusion 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.

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 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 [START_REF] Müllner | Modern hierarchical, agglomerative clustering algorithms[END_REF] 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.

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 position 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 rectangular 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. Furthermore, 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.

Fig. 1 .

 1 Fig. 1. Component representation: (a) Before rotation, (b) After rotation.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Example of wall convention: (a) Space generation after placing C1, (b) Space generation after placing v11, (c) Slicing tree of S, (d) Slicing tree of S .

4 .

 4 (a) CAD model. [1] 4.(b) 2D model.

Fig. 4 .

 4 Fig. 4. Model of single-container LP.

5 .

 5 (a) Single-container LP. 5.(b) Multi-container LP.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Display of Pareto front.

Fig. 7 .

 7 Fig. 7. Display of Pareto-optimal designs of multi-container LP.

  8.(a) Similarity matrix. 8.(b) Hierarchical cluster dendrogram.

Fig. 8 .

 8 Fig. 8. Similarity analysis.