A Near-Optimal Algorithm for Constraint Test Ordering in Automated Stowage Planning

doi:10.1109/TASE.2017.2779470

	A Near-Optimal Algorithm for Constraint Test Ordering in Automated Stowage Planning
	Zhuo Qi Lee 1; Rui Fan2 ; Wen-Jing Hsu 1
	2018-07
发表期刊	IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
ISSN	1545-5955
卷号	15 期号:3 页码:1298-1308
发表状态	已发表
DOI	10.1109/TASE.2017.2779470
摘要	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 naive ordering, an average of 2.74 times speed up in the evaluation engine can be achieved.
关键词	Automation logistics Markov processes optimization methods testing
URL	查看原文
收录类别	SCI ; SCIE ; EI
语种	英语
WOS研究方向	Automation & Control Systems
WOS类目	Automation & Control Systems
WOS记录号	WOS:000437415300033
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
WOS关键词	MULTIOBJECTIVE OPTIMIZATION ; CONTAINERSHIP ; HEURISTICS
原始文献类型	Article
来源库	IEEE
引用统计
文献类型	期刊论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/27423
专题	信息科学与技术学院信息科学与技术学院_PI研究组_范睿组
作者单位	1.School of Computer Science and Engineering, Nanyang Technological University, Singapore 2.School of Information Science and Technology, ShanghaiTech University, Shanghai, China
推荐引用方式 GB/T 7714	Zhuo Qi Lee,Rui Fan,Wen-Jing Hsu. A Near-Optimal Algorithm for Constraint Test Ordering in Automated Stowage Planning[J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING,2018,15(3):1298-1308.
APA	Zhuo Qi Lee,Rui Fan,&Wen-Jing Hsu.(2018).A Near-Optimal Algorithm for Constraint Test Ordering in Automated Stowage Planning.IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING,15(3),1298-1308.
MLA	Zhuo Qi Lee,et al."A Near-Optimal Algorithm for Constraint Test Ordering in Automated Stowage Planning".IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 15.3(2018):1298-1308.