Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem

https://doi.org/10.1016/j.cie.2014.07.012Get rights and content

Highlights

  • A multi-objective genetic algorithm was developed for container loading.

  • This approach applied multi-population strategy to improve effectiveness.

  • This approach employed fuzzy logic controller (FLC) to improve efficiency.

  • Numerical experiments have validated its practical viability.

  • This solution can enhance the space utilization and the total value of container.

Abstract

The container loading problem (CLP) has important industrial and commercial application for global logistics and supply chain. Many algorithms have been proposed for solving the 2D/3D container loading problem, yet most of them consider single objective optimization. In practice, container loading involves optimizing a number of objectives. This study aims to develop a multi-objective multi-population biased random-key genetic algorithm for the three-dimensional single container loading problem. In particular, the proposed genetic algorithm applied multi-population strategy and fuzzy logic controller (FLC) to improve efficiency and effectiveness. Indeed, the proposed approach maximizes the container space utilization and the value of total loaded boxes by employing Pareto approach and adaptive weights approach. Numerical experiments are designed to compare the results between the proposed approach and existing approaches in hard and weak heterogeneous cases to estimate the validity of this approach. The results have shown practical viability of this approach. This study concludes with discussions of contributions and future research directions.

Introduction

The container loading problem (CLP) has important industrial and commercial application for global logistics and supply chains. In particular, the uses of containers have been increasing for overseas and land transportation (Guenther & Kim, 2006). The CLP is a cutting and packing problem in which one or more large rectangular boxes (i.e., the containers) will be filled with smaller rectangular boxes (goods) of different sizes. Wäscher, Haußner, and Schumann (2007) proposed a typology to classify the cutting and packing problem. Their criteria include dimensionality, kind of assignment, assortment of small items, assortment of large objects, and the shapes of small items. According to the typology, the present problem focused on three-dimensional cutting and packing for single container (only one large object) with rectangular small items in different heterogeneous levels.

Many algorithms have been proposed for solving the 2D/3D container loading problem and most of them concern single objective optimization rather than multi-objective optimization problems. In the real world, almost every problem involves optimization of several objectives. The container space utilization is to maximize the space for goods of customers, and the total boxes value is to maximize the profit of the logistics company. Even there are some relationships between these two objectives since the fee is based on the volume of goods. However, these two objectives are not perfect the same since the weight of goods, the batch size, and other factors (Egeblad, Garavelli, Lisi, & Pisinger, 2010).

This study aims to develop a bi-objective multi-population biased random-key genetic algorithm and provide the solution including the location of each box and the corresponding orientation. This study focuses on single container loading problem which place a set of rectangular boxes of known dimensions and numbers into a single container of known dimensions so as to maximize the container space utilization and the total boxes value by Pareto approach and adaptive weights approach. The proposed genetic algorithm applied multi-population strategy and fuzzy logic controller (FLC) to improve efficiency and effectiveness. Thus, the logistics company can keep their space utilization and maximize the value of goods in limited container. The workers can get better result and avoid adjusting the patterns to save time.

The remaining of this paper is organized as follows: Section 2 reviews the related studies for CLP. Section 3 employs linear programming for problem structuring. Section 4 presents the proposed methodology. Section 5 discusses the results of different heterogeneous levels and problem scales for validation. Section 6 concludes with contribution and future research directions.

Section snippets

Literature review

Many approaches have been proposed for container loading that can be classified as the heuristic, mathematical programming, and meta-heuristic. For example, Chien and Wu, 1998, Chien and Wu, 1999 proposed a framework of modularized heuristics and developed a recursive computational procedure for determining the container loading patterns. Chien and Deng (2004) proposed a heuristic for container packing to determine the container packing patterns and visualize the results with a decision support

MILP for 3D-container loading problem

The CLP is a three-dimensional cutting and packing problem in which one or more large rectangular boxes (the containers) has to be filled with smaller rectangular boxes (goods) of different sizes. Let the container length, width, and height be denoted by L, W, and H, respectively. Suppose there are N types of rectangular boxes. Let the various lengths, widths, and heights of the considered boxes be denoted by li, wi, and hi, i = 1, 2, …, N, respectively.

We assume (1) All boxes are for the same

Co-evolutionary multi-objective GA

Genetic algorithms have been applied for various optimization problems such as combinatorial optimization, flow-shop sequencing, job-shop scheduling, transportation scheduling, rehabilitation scheduling, reliability optimization, facility layout design, and multi-resource allocation and scheduling (Chamnanlor et al., 2014, Chien and Chen, 2007a, Chien and Chen, 2007b, Chien et al., 2008, Gen and Cheng, 1997, Gen et al., 2008, Hao et al., 2013, Li and Lo, 2014, Wu and Chien, 2008, Wu et al., 2012

Experiment

To estimate the validity of the proposed approach, two numerical experiments were designed and conducted for comparison. In particular, the objectives are to maximize container space utilization and the total boxes value. In the first experiment, we use the same data set as Chien et al. (2009). Let the length, width, height of the container be 40, 8, and 8 feet, respectively. That is, (L, W, H) = (40, 8, 8). There are three sizes of boxes to be loaded. The length, width, height, and the value of

Conclusion

This study proposed a multi-population biased bi-objective genetic algorithm with random key representation for encoding and decoding to solve the three-dimensional cutting and packing problem for single container loading with two objectives. The proposed approach employed Pareto approach and adaptive weights to evaluate space utilization and the value. Because of the combinatorial complexity of the container loading problem, exact solution procedures are unlikely to be effective. The proposed

Acknowledgements

This research is partially supported by the National Science Council Taiwan (NSC100-2628-E-007-017-MY3; NSC102-2221-E-007-057-MY3; NSC102-2811-E-007-005), the Advanced Manufacturing and Service Management Research Center of National Tsing Hua University (103N2075E1), and the Grant-in-Aid for Scientific Research (C) of Japan Society of Promotion of Science (JSPS: No. 24510219).

References (34)

  • S.-H. Huang et al.

    Heuristic algorithms for container pre-marshalling problems

    Computers & Industrial Engineering

    (2012)
  • L. Junqueira et al.

    Three-dimensional container loading models with cargo stability and load bearing constraints

    Computers & Operations Research

    (2012)
  • X. Li et al.

    An energy-efficient scheduling and speed control approach for metro rail operations

    Transportation Research Part B: Methodological

    (2014)
  • G. Wäscher et al.

    An improved typology of cutting and packing problems

    European Journal of Operational Research

    (2007)
  • C. Chamnanlor et al.

    Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy

    International Journal of Production Research

    (2014)
  • C.-F. Chien et al.

    Using genetic algorithms (GA) and a coloured timed petri net (CTPN) for modeling the optimization-based schedule generator of a generic production scheduling system

    International Journal of Production Research

    (2007)
  • C.-F. Chien et al.

    A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based Setups

    OR Spectrum

    (2007)
  • Cited by (47)

    • On-line three-dimensional packing problems: A review of off-line and on-line solution approaches

      2022, Computers and Industrial Engineering
      Citation Excerpt :

      For instance, in 3D-PPs, volume maximization and weight maximization are two conflicting objectives when the volume of an item is not proportional to its weight. The conducted review reveals that most of the algorithms that have been proposed for 3D-PPs tackled single-objective problems, and only a few studies focused on multi-objective problems (Dereli & Das, 2010; González, Miranda, & León, 2016; Hasan et al., 2019; Zheng et al., 2015). Hence, as a wide range of real-world 3D-PPs requires high-quality decisions for more than one objective, the development of multi-objective optimization for packing problems may become a productive line of research.

    View all citing articles on Scopus
    View full text