Aheuristicblock-loadingalgorithmbasedonmulti-layersearchforthe资源-CSDN文库

Container

problem

需积分: 9 42 浏览量 2014-09-20 20:16:47 上传评论收藏 716KB PDF 举报

资源推荐

资源详情

资源评论

A heuristic block-loading algor ithm based on multi-layer search for the

container loading problem

Defu Zhang

, Yu Peng

, Stephen C.H. Leung

Department of Computer Science, Xiamen University, 361005, China

Department of Computer Science, Hong Kong University, Hong Kong

Department of Management Sciences, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong

article info

Available online 25 October 2011

Keywords:

Container loading problem

Heuristic algorithm

Depth-ﬁrst search

abstract

This paper presents an efﬁcient heuristic block-loading algorithm based on multi-layer search for the

three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is

introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing

phase, according to a ﬁxed strategy, until no blocks are available. Second, the concept of composite

block is introduced, the difference between traditional block and composite block being that composite

block can contain multiple types of boxes in one block under some restrictions. Third, based on the

depth-ﬁrst search algorithm, a multi-layer search algorithm is developed for determining the selected

block in each packing phase, and making this result closer to the optimal solution. Computational

results on a classic data set show that the proposed algorithm outperforms the best known algorithm in

almost all the test data.

1. Introduction

In logistics and transportation industries, three-dimensional

packing problems often occur. Improving the efﬁciency of packing

(space utilization) has become a very important issue as the

global economy is becoming ever more competitive. An effective

method for solving three-dimensional packing problems is not

only of great economic importance in logistics and transportation

processes but also has environmental implications since lower

fuel consumption helps to reduce pollution.

The container loading problem is a typical three-dimensional

packing problem that involves several practical applications

having different optimization objectives and loading constraints.

Thus there exist many variants of the problem. Dyckhoff and

Finke [1] outline the different types of loading problems, and give

the corresponding classiﬁcation, such as a single container load-

ing problem, multi-container loading problem, homogeneous

loading problem (containing only one type of box) and hetero-

geneous loading problems (including many types of boxes). The

single container loading problem considered by this paper can be

described as follows.

Assume a container (of volume V) and a series of boxes to be

packed into the container. The container and the boxes are of

cuboid shape. The objective is to determine a feasible loading plan

that meets the given loading constraints and maximizes utiliza-

tion of space in the container, i.e. the ﬁlling rate (S/V  100%) is as

large as possible, where S is the total volume of boxes loaded in

the container. A feasible loading plan must meet the following

criteria:

(1) Any loaded box cannot overlap with the container, and no two

boxes can overlap each other;

(2) The surface of the loaded boxes is parallel to the surface of the

container.

When solving real-world container loading problems, one has

to consider some practical constraints, such as orientation con-

straints, loading stability, load bearing strength of boxes, handling

constraints, container weight limit and so on [2]. This paper

considers the following two constraints:

(C1) Orientation constraint: for certain box types, up to ﬁve of

the maximum six possible orientations are prohibited.

(C2) Support constraint: in a given packing plan the area of

each box not placed on the ﬂoor of the container must be

supported completely (i.e. 100%) by other boxes.

The remainder of this paper is organized as follows. In the next

section an overview of literature is provided. In Section 3 main

parts of the proposed algorithm are introduced. In Section 4

computational experiments are described and analyzed. Finally,

in Section 5 conclusions are drawn.

Contents lists available at SciVerse ScienceDirect

journal homepage: www.elsevier.com/locate/caor

Computers & Operations Research

doi:10.1016/j.cor.2011.10.019

Corresponding author. Tel.: þ 852 28578465; fax: þ852 25598447.

E-mail address: ypeng@cs.hku.hk (Y. Peng).

Computers & Operations Research 39 (2012) 2267–2276

2. Literature review

The container loading problem is a typical NP-hard problem

[3], so there is no polynomial-time optimal algorithm for solving

it. Exact algorithms often encounter the ‘‘combinatorial explo-

sion’’ phenomenon as the problem size increases. Studies on

the exact algorithms show that they solve problems of limited

size only. Therefore, heuristic methods become the ﬁrst choice

of theoretical studies and practical applications. George and

Robinson [4] ﬁrst presented a wall-building heuristic algorithm.

Bischoff and Marriott [5] compared 14 kinds of layer-based

approaches. Based on the idea of plane, Bischoff et al. [6]

presented a heuristic algorithm for the heterogeneous loading

problem. Constructive algorithms have also been developed by

Bischoff and Ratcliff [2] and Bischoff [7]. Lim et al. [8] developed a

heuristic algorithm. Juraitis et al. [9] presented a randomized

heuristic algorithm. Huang and He [10,11] proposed two effective

heuristic algorithms based on the idea of caving degree for a class

of container loading problems.

By combining with constructive algorithms, many meta-heur-

istic algorithms have been proposed. A series of research results

have been obtained using tabu search [12], genetic algorithm [13]

andhybridalgorithms[14]. In order to improve the performance of

metaheuristics, the parallelization technique is used by Gehring and

Bortfeldt [15], Bortfeldt et al. [16] and Mack et al. [17]. Based on the

idea of free space, Moura and Oliveira [18] proposed a greedy

random adaptive search algorithm (GRASP). Parren

o et al. [19]

further developed GRASP using the concept of maximal space, a

nondisjoint representation of free space in a container. Zhang

et al. [20] presented a combinational heuristic algorithm that

combined personiﬁcation heuristics and simulated annealing

algorithm. Zhang et al. [21] further developed a hybrid simulated

annealing algorithm based on the block heuristic idea. Recently,

Parren

o et al. [22] presented a variable neighborhood search

(VNS) algorithm that combines a constructive procedure based

on the concept of maximal-space. He and Huang [23] developed a

ﬁt degree algorithm by combining the constructive algorithm

with local search for the container loading problem.

In addition, incomplete tree search or graph search methods

have also been applied successfully to the 3D-CLP. Morabito and

Arenales [24] presented a search method based on And/Or graph.

Eley [25] designed an algorithm based on the same block. Hiﬁ [26]

proposed a tree search method. Pisinger [27] presented an

algorithm that ﬁrst divides the whole container space into several

vertical layers, then divides layers into a number of horizontal or

vertical strips and then uses an algorithm for the knapsack

problem. Bortfeldt and Mack presented a heuristic algorithm that

was derived from a branch-and-bound approach [28]. Fanslau and

Bortfeldt

[29] proposed an effective tree search algorithm based

on the idea of composite block, which is the best algorithm in

existing literature.

In this paper, a heuristic block-loading algorithm based on

multi-layer search is proposed; experimental results show that

the proposed algorithm outperforms the existing algorithm in the

literature.

3. Heuristic block-loading algorithm based on multi-layer

3.1. Basic heuristic block-loading algorithm

Heuristic algorithms are preferred because of practical needs

and the resultant complexity of the loading problem. A good

heuristic algorithm should not only be able to quickly ﬁnd a

solution close to the optimal solution, but also provide the

necessary ﬂexibility for different situations and needs. In this

paper, a block-loading heuristic algorithm is proposed for solving

the container loading problem. This algorithm works as follows.

First generate a list of all feasible blocks, and initialize the residual

space in the stack to contain the container as the sole residual

space, and then start the iteration process. Each iteration takes

algorithm BasicHeuristic (isComposite, searchParams, problem)

if isComposite then

blockTable : = GenSimpleBlock (problem.container, problem.box List, problem.num)

else then

blockTable : = GenSimpleBlock (problem.container, problem.box List, problem.num)

endif

set search parameters according to search Params

s.avail : = problem.num

s.plan : = {}

s.volume = 0

s.spaceStack : = {}

s.spaceStack .push ( problem.container )

while ps.spaceStack ≠ {} do

space := ps.spaceStack.top ()

blockList := GenBlock List ( ps.space, ps.avail )

if blockList ≠ {} then

block := FindNextBlock ( ps, blockList )

ps.spaceStack .pop ()

ps.avail := ps.avail - block.require

ps.plan := ps.plan + (space, block )

ps.plan.volume := ps.plan.volume + block.volume

ps.spaceStack.push (GeResidulSpace(space , block ))

else then

TransferSpace(space, ps.spaceStack)

endif

endwhile

return ps.plan

Fig. 1. Basic block-loading heuristic algorithm.

D. Zhang et al. / Computers & Operations Research 39 (2012) 2267–22762268

剩余9页未读，继续阅读

评论收藏

内容反馈

linjiaxiaonao

粉丝: 0
资源: 1

A heuristicblock-loadingalgorithmbasedonmulti-layersearchforthe

最新资源

A heuristicblock-loadingalgorithmbasedonmulti-layersearchforthe

《计算机网络自顶向下（第七版）》课后题最全答案-含题目

软考网络工程师（中级）04-20历年真题及答案解析 .zip

cisco 模拟器 校园网 课程设计 毕业设计

AUTOSAR_SWS_CANNetworkManagement_4.3_中文版本.pdf

某智能化小区网络设计及规划.rar

putty.zip PuTTY中文版

项目管理PMP培训课件(完整版).ppt

计算机网络课程设计组建校园网pkt文件.zip

校园网规划方案

王道课程计算机网络PPT.rar

网络工程师知识点（背下必过）

2018年网络工程师学习视频和各类资料（全部内容免费）

山东大学计算机网络往年期末考试题，与考试经验总结

山东大学计算机网络往年期末考试题PPT与考试经验总结最新版本2021-2022.zip

无线传感器网络：理论及应用

华为eNSP 设备文件 NE40E系列

吉林大学软件学院网络协议分析期末复习

运维管理SLA列表.pdf

《计算机网络》谢希仁第七版课后答案详解.pdf

小型校园网的设计与组建实验报告.docx

数据分析与应用习题答案

计算机网络考研按章节题库

visio 模具.rar

计算机网络课程设计--中小企业组网.zip

Axure典型例子

TCPIP网络编程

《计算机控制技术（第2版）》于海生（电子课件）

山东大学软件学院大三下软件项目管理资料.docx

计算机网络(谢希仁版)复习资料整理(期末考试必备).pdf

VirtualBox版本及ensp

最新资源

cisco 模拟器校园网课程设计毕业设计