Two-Level Approach for Simultaneous Component Assignment and Layout Optimization with Applications to Spacecraft Optimal Layout
Source abstract
Abstract
Optimal layout problems consist in positioning a given number of components in order to minimize an objective function while satisfying geometrical or functional constraints. Such kinds of problems appear in the design process of aerospace systems such as satellite or spacecraft design. These problems are NP-hard, highly constrained and dimensional. This paper describes a two-stage algorithm combining a genetic algorithm and a quasi-physical approach based on a virtual-force system in order to solve multi-container optimal layout problems such as satellite modules. In the proposed approach, a genetic algorithm assigns the components to the containers while a quasi-physical algorithm based on a virtual-force system is developed for positioning the components in the assigned containers. The proposed algorithm is experimented and validated on the satellite module layout problem benchmark. Its global performance is compared with previous algorithms from the literature.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Manufacturing and Logistics Optimization · Optimization and Packing Problems · Optimization and Search Problems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
ONERA, DTIS, Université Paris-Saclay, 91120 Palaiseau, France
CNRS/CRIStAL, Centre Inria de l’Université de Lille, Université de Lille, 59491 Villeneuve d’Ascq, France
Funding
INRIA
References (100+)
Show source-provided references
1. Deremaux, Y., Pietremont, N., Negrier, J., Herbin, E., and Ravachol, M. (2008, January 10–12). Environmental MDO and uncertainty hybrid approach applied to a supersonic business jet. Proceedings of the 12th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Victoria, BC, Canada.10.2514/6.2008-5832 ↗
2. A survey of computational approaches to three-dimensional layout problems10.1016/S0010-4485(01)00109-9 ↗
3. A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints10.1016/j.cie.2013.08.010 ↗
4. Jacquenot, G. (2010). Méthode générique pour l’optimisation d’agencement géométrique et fonctionnel. [Doctoral Dissertation, Ecole Centrale de Nantes (ECN)]. (In French).
5. Peralta, J., Andretta, M., and Oliveira, J. (2018, January 24–26). Packing Circles and Irregular Polygons using Separation Lines. Proceedings of the International Conference on Operations Research and Enterprise Systems, 7th International Conference on Operations Research and Enterprise Systems (ICORES 2018), Funchal, Portugal.10.5220/0006602700710077 ↗
6. Benabes, J., Bennis, F., Poirson, E., and Ravaut, Y. (2011). An interactive-based approach to the layout design optimization. Global Product Development, Proceedings of the 20th CIRP Design Conference, Ecole Centrale de Nantes, Nantes, France, 19–21 April 2010, Springer.10.1007/978-3-642-15973-2_52 ↗
7. Meng, X., Sun, H., and Kang, J. (2021). Equipment layout optimization based on human reliability analysis of cabin environment. J. Mar. Sci. Eng., 9.10.3390/jmse9111263 ↗
8. Solving a big-scaled hospital facility layout problem with meta-heuristics algorithms
9. Wind farm layout optimization in complex terrain: A preliminary study on a Gaussian hill10.1088/1742-6596/524/1/012146 ↗
10. Geometry-based models for studying the effects of wind farm layout10.1175/JTECH-D-14-00199.1 ↗
11. Differential evolution with a new encoding mechanism for optimizing wind farm layout10.1109/TII.2017.2743761 ↗
12. Coverage optimization of LTE networks based on antenna tilt adjusting considering network load10.1109/CC.2017.7942314 ↗
13. Soman, R., Kudela, P., Balasubramaniam, K., Singh, S., and Malinowski, P. (2019). A study of sensor placement optimization problem for guided wave-based damage detection. Sensors, 19.10.3390/s19081856 ↗
14. Zhao, Q., Li, C., Zhu, D., and Xie, C. (2022). Coverage optimization of wireless sensor networks using combinations of PSO and chaos optimization. Electronics, 11.10.3390/electronics11060853 ↗
15. Genetic algorithms: Concepts and applications [in engineering design]10.1109/41.538609 ↗
16. Optimal layout design of a satellite module10.1080/03052150310001602335 ↗
17. Xu, Y., Xiao, R., and Amos, M. (2007, January 25–28). A novel genetic algorithm for the layout optimization problem. Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore.
18. 2d multi-objective placement algorithm for free-form components
19. A collaborative design method for satellite module component assignment and layout optimization10.1177/0954410019847864 ↗
20. A dual-system variable-grain cooperative coevolutionary algorithm: Satellite-module layout design10.1109/TEVC.2009.2033585 ↗
21. Cooperative co-evolutionary scatter search for satellite module layout design10.1108/02644400910985161 ↗
22. Bliek1ú, C., Bonami, P., and Lodi, A. (2014, January 16–17). Solving mixed-integer quadratic programming problems with IBM-CPLEX: A progress report. Proceedings of the Twenty-Sixth RAMP Symposium, Tokyo, Japan.
23. On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square10.1016/j.dam.2012.07.020 ↗
24. Kohara, D., Yamamoto, H., and Suzuki, A. (2008, January 3–5). Efficient algorithms based on branch and bound methods for multi floor facility layout problems. Proceedings of the 9th Asia Pacific Industrial Engineering & Management Systems Conference, Bali, Indonesiam.
25. A branch-and-bound algorithm for the continuous facility layout problem10.1016/j.compchemeng.2007.05.003 ↗
26. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation10.1016/j.ejor.2007.08.007 ↗
27. Dynamic programming algorithms for generating optimal strip layouts10.1007/s10589-005-3067-y ↗
28. An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem10.1016/j.ejor.2017.03.061 ↗
29. Koopmans, T., and Beckmann, M. (1957). Assignment problems and the location of economic activities. Econom. J. Econom. Soc., 53–76.10.2307/1907742 ↗
30. Montreuil, B. (1990, January 19–21). A Modelling Framework for Integrating Layout Design and Flow Network Design. Proceedings of the Material Handling Research Colloquium, Hebron, Kentucky.10.1007/978-3-642-84356-3_8 ↗
31. Budianto, F., Halim, J., and Sembiring, A. (2020, January 25–27). Redesigning Furniture Production Floors Using Systematic Layout Planning and ALDEP Method to Minimize Material Handling Costs. Proceedings of the 2020 3rd International Conference on Mechanical, Electronics, Computer, and Industrial Technology (MECnIT), Medan, Indonesia.10.1109/MECnIT48290.2020.9166613 ↗
32. Layout design using the analytic hierarchy process10.1016/0360-8352(91)90026-3 ↗
33. Plant layout optimization using CRAFT and ALDEP methodology
34. An improvement-type layout algorithm for single and multiple-floor facilities10.1287/mnsc.40.7.918 ↗
35. Analysis of plant layout design for operational efficiency with craft algorithms
36. A typical manufacturing plant layout design using CRAFT algorithm10.1016/j.proeng.2014.12.334 ↗
37. A simulated annealing algorithm for dynamic layout problem10.1016/S0305-0548(00)00049-6 ↗
38. A thermodynamically motivated simulation procedure for combinatorial optimization problems10.1016/0377-2217(84)90231-5 ↗
39. A new simulated annealing algorithm for the facility layout problem10.1080/00207549608904990 ↗
40. A simulated annealing algorithm for allocating space to manufacturing cells10.1080/00207549208942878 ↗
41. Carrabs, F., Cerrone, C., and Cerulli, R. (2014, January 10–12). A tabu search approach for the circle packing problem. Proceedings of the 2014 17th International Conference on Network-Based Information Systems, Salerno, Italy.10.1109/NBiS.2014.28 ↗
42. A tabu-search heuristic for the dynamic plant layout problem10.1287/ijoc.9.4.374 ↗
43. The strategies of tabu search technique for facility layout optimization10.1016/j.autcon.2008.01.001 ↗
44. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces10.1016/j.ejor.2004.11.016 ↗
45. An improved genetic algorithm based robust approach for stochastic dynamic facility layout problem10.1155/2018/1529058 ↗
46. An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks10.1109/TCYB.2013.2250955 ↗
47. Unequal-area stochastic facility layout problems: Solutions using improved covariance matrix adaptation evolution strategy, particle swarm optimisation, and genetic algorithm10.1080/00207543.2015.1070217 ↗
48. Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem10.1016/j.eswa.2018.02.035 ↗
49. Two hybrid compaction algorithms for the layout optimization problem10.1016/j.biosystems.2006.12.007 ↗
50. Wagner, M., Veeramachaneni, K., Neumann, F., and O’Reilly, U. (2011). Optimizing the layout of 1000 wind turbines. Eur. Wind Energy Assoc. Annu. Event, 205209.
51. A shape-based block layout approach to facility layout problems using hybrid genetic algorithm10.1016/S0360-8352(02)00018-9 ↗
52. A hybrid swarm intelligence based particle-bee algorithm for construction site layout optimization10.1016/j.eswa.2012.02.134 ↗
53. Multi-objective hybrid algorithms for layout optimization in multi-robot cellular manufacturing systems10.1016/j.knosys.2016.12.026 ↗
54. Chen, X., Yao, W., Zhao, Y., Chen, X., Zhang, J., and Luo, Y. (2018, January 8–13). The hybrid algorithms based on differential evolution for satellite layout optimization design. Proceedings of the 2018 IEEE Congress on Evolutionary Computation (CEC), Rio de Janeiro, Brazil.10.1109/CEC.2018.8477969 ↗
55. An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container10.1016/j.cor.2017.12.002 ↗
56. Global optimization method for finding dense packings of equal circles in a circle10.1016/j.ejor.2010.11.020 ↗
57. An improved algorithm for the packing of unequal circles within a larger containing circle10.1016/S0377-2217(01)00241-7 ↗
58. Bibliometric study on the use of machine learning as resolution technique for facility layout problems10.1109/ACCESS.2021.3054563 ↗
59. Deep generative Bayesian optimization for sensor placement in structural health monitoring10.1111/mice.12799 ↗
60. A neural network approach to facility layout problems10.1016/0377-2217(95)00051-8 ↗
61. Vashisht, D., Rampal, H., Liao, H., Lu, Y., Shandbhag, D., Fallon, E., and Kara, L. (2020). Placement integrated circuits using cyclic reinforcement learning and simulated annealing. arXiv.
62. A survey of repair methods used as constraint handling techniques in evolutionary algorithms10.1016/j.cosrev.2009.07.001 ↗
63. Constraint-handling in nature-inspired numerical optimization: Past, present and future10.1016/j.swevo.2011.10.001 ↗
64. A tutorial for competent memetic algorithms: Model, taxonomy, and design issues10.1109/TEVC.2005.850260 ↗
65. The facility layout problem10.1016/0377-2217(87)90238-4 ↗
66. An exact penalty function method for optimising QAP formulation in facility layout problem10.1080/00207543.2016.1229068 ↗
67. Optimal 3D layout of industrial facilities10.1080/00207540110118622 ↗
68. A general mathematical programming approach for process plant layout10.1016/S0098-1354(99)00005-8 ↗
69. Optimal multi-floor process plant layout10.1016/S0098-1354(01)00781-5 ↗
70. CORELAP-computerized relationship layout planning
71. SPACECRAFT for multi-floor layout planning10.1287/mnsc.28.4.407 ↗
72. Reactive GRASP for the strip-packing problem10.1016/j.cor.2006.07.004 ↗
73. GRASP for set packing problems10.1016/S0377-2217(03)00263-7 ↗
74. A novel grasp algorithm for solving the bin packing problem
75. A review of different approaches to the facility layout problems10.1007/s00170-005-0087-9 ↗
76. Variable neighborhood search for large offshore wind farm layout optimization
77. An efficient variable neighborhood search for the space-free multi-row facility layout problem10.1016/j.ejor.2021.03.027 ↗
78. Adaptive variable neighborhood search for solving multi-objective facility layout problems with unequal area facilities10.1016/j.swevo.2012.07.003 ↗
79. GA and GWO algorithm for the special bin packing problem encountered in field of aircraft arrangement10.1016/j.asoc.2021.108060 ↗
80. Heuristics in spatial analysis: A genetic algorithm for coverage maximization10.1080/00045600903120594 ↗
81. Optimal layout design of obstacles for panic evacuation using differential evolution10.1016/j.physa.2016.08.021 ↗
82. Hasan, R., Mohammed, M., Ţăpuş, N., and Hammood, O. (2017, January 21–23). A comprehensive study: Ant colony optimization (ACO) for facility layout problem. Proceedings of the 16th RoEduNet Conference: Networking in Education and Research (RoEduNet), Targu-Mures, Romania.10.1109/ROEDUNET.2017.8123738 ↗
83. Ant colony optimization and local search for bin packing and cutting stock problems10.1057/palgrave.jors.2601771 ↗
84. A scatter search algorithm for the single row facility layout problem10.1007/s10732-013-9234-x ↗
85. An improved scatter search for circles packing problem with the equilibrium constraint10.3724/SP.J.1016.2009.01214 ↗
86. Galanos, T., Liapis, A., Yannakakis, G., and Koenig, R. (2021, January 10–14). ARCH-Elites: Quality-diversity for urban design. Proceedings of the Genetic and Evolutionary Computation Conference Companion, Online.10.1145/3449726.3459490 ↗
87. Nikfarjam, A., Do, A.V., and Neumann, F. (2022). Analysis of Quality Diversity Algorithms for the Knapsack Problem. Parallel Problem Solving from Nature–PPSN XVII, Proceedings of the 17th International Conference, PPSN 2022, Dortmund, Germany, 10–14 September 2022, Springer International Publishing. Proceedings, Part II.10.1007/978-3-031-14721-0_29 ↗
88. Zhang, Y., Fontaine, M., Bhatt, V., Nikolaidis, S., and Li, J. (2023). Multi-Robot Coordination and Layout Design for Automated Warehousing. arXiv.10.24963/ijcai.2023/611 ↗
89. Potter, M.A., Jong, D., and Kenneth, A. (1994). A cooperative coevolutionary approach to function optimization. International Conference on Parallel Problem Solving from Nature, Springer.10.1007/3-540-58484-6_269 ↗
90. A survey on cooperative co-evolutionary algorithms10.1109/TEVC.2018.2868770 ↗
91. A coevolutionary algorithm for a facility layout problem10.1080/0020754031000118125 ↗
92. Xu, Y.C., Dong, F.M., Liu, Y., Xiao, R.B., and Amos, M. (2010). Ant colony algorithm for the weighted item layout optimization problem. arXiv.
93. Evolutionary approach for spatial architecture layout design enhanced by an agent-based topology finding system10.1016/j.foar.2016.11.003 ↗
94. Energy-efficiency virtual machine placement based on binary gravitational search algorithm10.1007/s10586-019-03021-0 ↗
95. DGSA: Discrete gravitational search algorithm for solving knapsack problem
96. A graph placement methodology for fast chip design10.1038/s41586-021-03544-w ↗
97. Bayesian optimization over permutation spaces
98. Thermal design optimization of electronic circuit board layout with transient heating chips by using Bayesian optimization and thermal network model10.1016/j.ijheatmasstransfer.2021.122263 ↗
99. NASA (2007). System Engineering Handbook; NASA SP-2007-6105, Rev 1.
100. Sousa, F.D., Galski, R., Rocco, E., Becceneri, J., Santos, W., and Sandri, S. (2013, January 3–7). A toll for multidisciplinary design conception of spacecraft equipment layout. Proceedings of the 22nd International Congress of Mechanical Engineering (COBEM, 2013), Ribeirão Preto, Brazil.