An average-case asymptotic analysis of the Container Relocation Problem

被引：8

作者：

Galle, V. ^{[1
]}

Boroujeni, S. Borjian ^{[1
]}

Manshadi, V. H. ^{[2
]}

Barnhart, C. ^{[1
,3
]}

Jaillet, P. ^{[1
,4
]}

机构：

[1] MIT, Ctr Operat Res, 77 Massachusetts Ave, Cambridge, MA 02139 USA

[2] Yale Univ, Sch Management, 165 Whitney Ave, New Haven, CT 06511 USA

[3] MIT, Civil & Environm Engn, 77 Massachusetts Ave, Cambridge, MA 02139 USA

[4] MIT, Elect Engn & Comp Sci, 77 Massachusetts Ave, Cambridge, MA 02139 USA

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 06期

关键词：

CRP; Asymptotic analysis; Expected lower bound; BLOCKS;

D O I：

10.1016/j.orl.2016.08.006

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Container Relocation Problem (CRP) involves finding a sequence of moves of containers that minimizes the number of relocations needed to retrieve all containers in a given order. In this paper, we focus on average case analysis of the CRP when the number of columns grows asymptotically. We show that the expected minimum number of relocations converges to a simple and intuitive lower-bound for which we give an analytical formula. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：723 / 728

页数：6

共 6 条

[1] A mathematical formulation and complexity considerations for the blocks relocation problem [J].

Caserta, Marco ;

Schwarze, Silvia ;

Voss, Stefan .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 219 (01) :96-104

[2] A heuristic rule for relocating blocks [J].

Kim, KH ;

Hong, GP .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (04) :940-954

[3] Loading, unloading and premarshalling of stacks in storage areas: Survey and classification [J].

Lehnfeld, Jana ;

Knust, Sigrid .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 239 (02) :297-312

[4]

Matousek J., 2008, LECTURENOTES

[5] Average case analysis of Blocks Relocation heuristics [J].

Olsen, Martin ;

Gross, Allan .

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8760 :81-92

[6] Operations research at container terminals: a literature update [J].

Stahlbock, Robert ;

Voss, Stefan .

OR SPECTRUM, 2008, 30 (01) :1-52

← 1 →