Towards Real-Time Automated Stowage Planning - Optimizing Constraint Test Ordering

Container stowage planning is a complex task in which multiple objectives have to be optimized while ensuring that the stowage rules as well as the safety and balance requirements are observed. Most algorithms for solving the problem are comprised of 2 parts: a container-location selection mechanism and a constraint evaluation engine. The former selects one or more container-location pairs for allocation iteratively and the latter evaluates whether the selected container-location pairs violate any of the constraints. We observe that, using the same selection mechanism, the order in which the constraints are evaluated can have significant impact on the overall efficiency. We propose Sequential Sample Model (SSM) as an improvement over the existing Random Sample Model (RSM) for analysis of the problem. We present and evaluate several strategies in optimizing the constraint evaluation engine. We show how to achieve the optimal constraint ordering with respect to SSM. However, such ordering requires perfect information on the constraint tests which is impractical. We present alternative strategies and show empirically that their efficiencies are close to the optimum. Experiments show that, when compared to an arbitrary ordering, an average of 2.42 times speed up in the evaluation engine can be achieved.