A near-optimal algorithm for constraint test ordering in automated stowage planning

• Main Authors: Lee, Zhuo Qi, Fan, Rui, Hsu, Wen-Jing
• Other Authors: School of Computer Science and Engineering
• Format: Article
• Language: English
• Published: 2019
• Subjects: DRNTU::Engineering::Computer science and engineering; Automation; Logistics
• Online Access: https://hdl.handle.net/10356/106121; http://hdl.handle.net/10220/47888; http://dx.doi.org/10.1109/TASE.2017.2779470
• Institution: Nanyang Technological University

The container stowage planning problem is known to be NP-hard and heuristic algorithms have been proposed. Conventionally, the efficiency of the stowage planning algorithms are improved by pruning or reducing the search space. We observe that constraint evaluation is the core of most algorithms. In addition, the order at which the constraints are evaluated can have significant impact on the efficiency of the constraint evaluation engine. We propose random sample model (RSM) and sequential sample model (SSM) for analysis of the problem. We present and evaluate seven strategies in optimizing the constraint evaluation engine. We show how to achieve the optimal constraint ordering with respect to RSM and SSM, respectively. However, the optimal ordering for SSM requires perfect information about the states of the constraint tests, which is impractical. We present an alternative strategy and show empirically that its efficiency is close to the optimal. Experiments show that, compared to a naïve ordering, an average of 2.74 times speed up in the evaluation engine can be achieved.