Packing Problems in Space Solved by CPLEX: An Experimental Analysis

Cargo loading of module and vehicles, as well as satellite/spacecraft layout design, notoriously represent very challenging space engineering tasks, deemed to become, day after day, ever more demanding in the perspective of the upcoming exploration adventures. Extremely thought provoking packing optimization problems have to be coped with, in the presence of intricate geometries, operational conditions and, usually, very tight balancing requirements. A modeling-based (as opposed to a pure algorithmic) approach has been the object of a dedicated long lasting research, carried out by Thales Alenia Space. In this chapter, an extension of the classical container loading problem is considered, allowing for tetris-like items, (convex) non-rectangular domains, (non-prefixed) separation planes and static balancing. The relevant space engineering framework is illustrated firstly, contextualizing its relationship with the more general subject of packing optimization and the topical literature. The problem in question is stated, outlining the underlying mathematical model in use (formulated in terms of Mixed Integer Linear Programming, MILP) and the overall heuristic approach adopted to obtain efficient solutions in practice. An extensive experimental analysis, based on the utilization of CPLEX, as the MILP optimizer, represents the core of this work. Both the MILP model and the related heuristic have been tested on a number of quite demanding case studies, investigating effective MILP strategies up to obtaining satisfactory solutions from a global-optimization point of view. The results shown well pave the way for a promising further dedicated research.