内容简介
In the operations research literature, container loading problems are a
class of geometric optimization problems in which three ⁃ dimensional items
have to be loaded, entirely and without overlap, into large cubic spaces,
such that one or more objectives are optimized. Many variants of container
loading problems have been studied in the past several decades, but most of
them are too simplified to describe a practical situation when loading
containers.
In this book, we introduce the Generalized Container Loading Problem
(GCLP) to model a more practical container loading issue. In this problem,
we are given a set of three⁃dimensional containers and several sets of three⁃
dimensional items. Each set of items can be further divided into two groups:
mandatory items and optional items. Each container has a cost and each item
has a value. We need to select one set of items and load all of its mandatory
items, together with some or all of its optional items, into the container(s),
such that the unit shipping cost is minimized. The unit shipping cost is
defined as the quotient of the total cost of selected containers and the total
value of loaded items. This problem successfully describes the multi ⁃ layer
2 Generalized Container Loading Problem and Its Applications
decision⁃making process and the trade⁃off between cost and value,which are
common issues in logistics management.
Two applications of the generalized container loading problem are also
demonstrated in this book, both of which represent real issues encountered
by manufacturers in their logistics processes.
In the first application, an international audio equipment manufacturer
would like to help its customers reduce unit shipping costs by adjusting order
quantity according to product preference. We introduce the problem faced by
the manufacturer as the Multiple Container Loading Problem with Preference
(MCLPP) . We prove that the MCLPP is a generalized container loading
problem and propose a combinatorial formulation for the MCLPP. We develop
a two⁃phase algorithm to solve the problem. In phase one, we estimate the
most promising region of the solution space, based on performance statistics
of the sub⁃problem solver. In phase two, we find a feasible solution in the
promising region by solving a series of 3D orthogonal packing problems. We
generate a large set of test instances based on the data provided by the
manufacturer and conduct extensive computational experiments to
demonstrate the effectiveness of our approach. A unique feature of our
approach is that we estimate the average capability of the SCLP sub⁃routine in
phase one and take it into account in the overall planning. To obtain a useful
estimate, we randomly generate a large set of SCLP instances that are
statistically similar to the manufacturers historical order data.
The second application also comes from a manufacturer
章节目录
1 Introduction/1
1.1 Introduction/1
1.2 Contributions/4
1.3 Book Organization/6
2 Literature Review/7
2.1 Cutting and Packing Problems/7
2.2 Typical Container Loading Problems/8
2.3 Modeling Techniques/11
2.4 Exact and Approximation Algorithms/12
2.5 Heuristic Methods/16
3 Generalized Container Loading Problem/25
3.1 Introduction/26
3.2 Problem Definition and Formulation/27
2 Generalized Container Loading Problem and Its Applications
3.3 Special Cases of the Generalized Container Loading Problems in
Literature/38
3.4 Conclusion/41
4 The Multiple Container Loading Problem with Preference/43
4.1 Introduction/44
4.2 Problem Definition/48
4.3 The MCLPP is a Generalized Container Loading Problem/50
4.4 A Combinatorial Formulation/52
4.5 A Two⁃Phase Heuristic/55
4.6 Computational Experiments/65
4.7 Conclusion/78
5 The Single Container Mix⁃Loading Problem/79
5.1 Introduction/80
5.2 Problem Definition/82
5.3 The SCMLP is a Generalized Container Loading Problem/83
5.4 A Two⁃Phase Constructive Method/85
5.5 Computational Experiments/99
5.6 Conclusion/103
6 Conclusion/105
Bibliography/109
Index/117