Overlap Packing Optimization for Spacecraft Layout Design
Packing optimization is a common problem that is encountered on a day-to-day basis and has led to an extensive study over the years. One variant of the packing problem that is beginning to emerge is the overlap cuboid packing problem (OCPP), which allows for items that need to be packed to share space in order to further minimize the dimensions of the container. The objective of this study is to investigate a mathematical model, specifically a mixed-integer linear program (MILP), that can effectively provide an overlap packing solution in the context of designing the layout for a spacecraft module. For this particular layout design problem, the items that need to be packed are represented as task volumes, known as gradient cuboids, where astronauts perform various tasks and the container is the spacecraft module. A bi-objective function was proposed to allow the dimensions of the module to be minimized, as well as enforcing specific adjacency requirements that might exist between gradient cuboids.Following the formulation of the model, the efficacy of the model is evaluated on test problems that consist of 20 randomly generated small-scale instances with seven cuboids and one full-scale instance with 24 cuboids. In this numerical study, each of the test instances were solved under 10 different design scenarios, which varied depending on the enforced vertical overlap and restrictions on the dimensions of the container. To obtain solutions of the MILPs, a commercial solver, Gurobi, was called from Matlab. The visualization of results demonstrates how the proposed model effectively generates layout designs. We also observed how the proposed model can accommodate prioritization between two criteria: size of the container and enforcement of adjacency requirements.Noting that OCPP is a generalization of the NP-hard packing problem, it is unlikely to efficiently find an optimal solution as the problem size increases. It consumed 81.02 seconds on average to solve small-scale instances. However, the solution of the full-scale problem had to be terminated after a 4-hour run, when the optimality gap was 62.53% on average for 10 layout designs. Observing the large optimality gap, we turned our attention to further enhance the model to help reduce the computational burden when finding a solution. As a result, seven additional sets of constraints were proposed.An additional numerical study was performed where each constraint was added to the base model individually using the test problem in order to determine which constraints provide the most benefit to solving the model across a set of scenarios. Following this, combinations of constraints were created for different layout designs on the randomly generated problems to determine if further improvement was possible. It was observed that there was an average improvement of 65.12% in solution time when applied to small-scale instances. These combinations were applied to the full-scale problem, where it was observed that there was an average improvement of 14.92% in optimality gap after 4-hours.