检索结果-内蒙古大学图书馆

A block-building constraint programming model for the container loading problem

Computers & Operations Research 2025年 182卷

作者： Chang Liu Kate Smith-Miles Tony Wauters Alysson M. Costa School of Mathematics and Statistics The University of Melbourne Parkville Melbourne Australia Department of Computer Science CODeS KU Leuven Gebroeders De Smetstraat 1 9000 Ghent Belgium ARC Training Centre in Optimisation Technologies Integrated Methodologies and Applications (OPTIMA) The University of Melbourne Parkville Melbourne Australia

The container loading problem involves packing a set of given rectangular boxes into a larger rectangular container of fixed size, with the objective of maximizing the volume of the loaded boxes. Most of the literature on the container loading problem and its variants proposes heuristic approaches that can find good solutions quickly. Current exact methods are mostly limited to mixed-integer programming (MIP) formulations, which often struggle to obtain good solutions for large problem instances. In this paper, we introduce two exact constraint programming models for the container loading problem. The first model uses integer and binary variables to assign boxes to valid positions and orientations within the container. The second model enhances this by incorporating the concept of block-building, commonly used in heuristic methods. Extensive computational experiments on classical benchmark instances from the literature show that the solutions obtained with the proposed models significantly outperform those achieved with existing MIP models. We also perform an instance space analysis of the proposed models to map the models’ performances across problem instances, providing deeper insights into the strengths and weaknesses of the block-building approach.

关键词： Packing container loading problem Constraint programming Mathematical modeling Block building Instance space analysis

来源：评论

学校读者我要写书评

暂无评论

A beam search algorithm for the biobjective container loading problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期286卷 417-431页

作者： Araya, Ignacio Moyano, Mauricio Sanchez, Cristobal Pontificia Univ Catolica Valparaiso Escuela Ingn Informat Ave Brasil 2950 Valparaiso V Region Chile

In this work we deal with a biobjective variant of the single container loading problem. The problem consists in packing a set of boxes into a large box or container. In addition to the usual objective related to maximize the volume utilization, we include a second objective consisting on maximizing the total profit (e.g., weight or priority) of the loaded boxes. We propose to adapt bsg, a state-of-the-art single-objective algorithm for solving the biobjective problem. bsg can be seen as an incomplete version of a breadth first search in which each level of the search tree is restricted to a fixed number of promising nodes. In order to select the most promising nodes, the algorithm constructs a solution from them by using a greedy algorithm and evaluates the objectives. To deal with two objectives, we propose to select nodes by using well-known multi-objective criteria based on dominance and crowding distance related to the greedy evaluations. We go a little bit further and orient the greedy algorithm to one objective or the other by using a mechanism which changes the configuration of the heuristic function dynamically. The proposal is compared with bsg in a set of well-known instances reporting a 24% increase in the hypervolume indicator. Compared to other biobjective approaches, the reported results are also promising. Codes and test instances are available in: https://***/rilianx/Metasolver#bo-bsg (C) 2020 Elsevier B.V. All rights reserved.

关键词： multiobjective optimization container loading problem beam search greedy

来源：评论

学校读者我要写书评

暂无评论

The container loading problem with cargo stability: a study on support factors, mechanical equilibrium and grids

引用

ENGINEERING OPTIMIZATION 2021年第7期53卷 1192-1211页

作者： Oliveira, Liliane de Azevedo de Lima, Vinicius Loti de Queiroz, Thiago Alves Miyazawa, Flavio Keidi Univ Fed Goias Inst Math & Technol Catalao Brazil Univ Estadual Campinas Inst Comp Campinas Brazil

Approaches based on mechanical equilibrium are described for handling cargo stability in the container loading problem. This problem is expressed as an integer programming model and solved with a branch-and-cut algorithm. Cutting planes are added to avoid generating unstable packings. Three grids of points are used to pack items, and then their weakness and advantages, when combined with the cargo stability, are discussed. Computational results on 180 instances from the literature show that the support factor underestimates the solution, as the proposed approaches allowed stable packings with a higher volume.

关键词： container loading problem cargo stability equilibrium of material bodies support factor integer linear programming

来源：评论

学校读者我要写书评

暂无评论

VCS: A new heuristic function for selecting boxes in the single container loading problem

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 82卷 27-35页

作者： Araya, Ignacio Guerrero, Keitel Nunez, Eduardo Pontificia Univ Catolica Valparaiso Escuela Ingn Informat Avenida Brasil 2950 Vregion Chile

The single container loading problem consists of a container that has to be filled with a set of boxes. The objective of the problem is to maximize the total volume of the loaded boxes. For solving the problem, constructive approaches are the most successful. A key element of these approaches is related to the selection of the box to load next. In this work, we propose a new evaluation function for ranking boxes. Our function rewards boxes that fit well in the container, taking into account the previously placed ones. To construct a more robust function, we consider some other well-known evaluation criteria such as the volume of the block and the estimated wasted volume in the free space of the container. Our approach shows promising results when compared with other state-of-the-art algorithms on a set of 1600 well known benchmark instances. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： container loading problem Load planing Combinatorial optimization Constructive algorithms Evaluation function

来源：评论

学校读者我要写书评

暂无评论

Dynamic stability metrics for the container loading problem

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2015年第Nov.期60卷 480-497页

作者： Galrao Ramos, A. Oliveira, Jose F. Goncalves, Jose F. Lopes, Manuel P. Univ Porto INESC TEC P-4100 Oporto Portugal Univ Porto Fac Engn P-4100 Oporto Portugal Polytech Porto Sch Engn CIDEM Oporto Portugal Univ Porto INESC TEC LIAAD P-4100 Oporto Portugal Univ Porto Fac Econ P-4100 Oporto Portugal

The container loading problem (CLP) literature has traditionally evaluated the dynamic stability of cargo by applying two metrics to box arrangements: the mean number of boxes supporting the items excluding those placed directly on the floor (M1) and the percentage of boxes with insufficient lateral support (M2). However, these metrics, that aim to be proxies for cargo stability during transportation, fail to translate real-world cargo conditions of dynamic stability. In this paper two new performance indicators are proposed to evaluate the dynamic stability of cargo arrangements: the number of fallen boxes (NFB) and the number of boxes within the Damage Boundary Curve fragility test (NB_DBC). Using 1500 solutions for well-known problem instances found in the literature, these new performance indicators are evaluated using a physics simulation tool (StableCargo), replacing the real-world transportation by a truck with a simulation of the dynamic behaviour of container loading arrangements. Two new dynamic stability metrics that can be integrated within any container loading algorithm are also proposed. The metrics are analytical models of the proposed stability performance indicators, computed by multiple linear regression. Pearson's r correlation coefficient was used as an evaluation parameter for the performance of the models. The extensive computational results show that the proposed metrics are better proxies for dynamic stability in the CLP than the previous widely used metrics. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： container loading problem Dynamic stability Physics engine

来源：评论

学校读者我要写书评

暂无评论

An effective placement method for the single container loading problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2016年 97卷 212-221页

作者： Huang, Yao-Huei Hwang, F. J. Lu, Hao-Chun Southwest Jiaotong Univ Sch Econ & Management Chengdu 610031 Peoples R China Univ Technol Sydney Sch Math & Phys Sci Ultimo NSW 2007 Australia Fu Jen Catholic Univ Dept Informat Management New Taipei 24205 Taiwan

This study investigates a three-dimensional single container loading problem, which aims to pack a given set of unequal-size rectangular boxes into a single container such that the length of the occupied space in the container is minimized. Motivated by the practical logistics instances in literature, the problem under study is formulated as a zero-one mixed integer linear programming model. Due to the NP-hardness of the studied problem, a simple but effective loading placement heuristic is proposed for solving large-size instances. The experimental results demonstrate that the developed heuristic is capable of solving the instances with more than two hundred boxes and more efficient than the state-of-the-art mixed integer linear program and existing heuristic methods. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： container loading problem Mixed integer linear program Heuristic loading placement

来源：评论

学校读者我要写书评

暂无评论

A beam search approach to the container loading problem

引用

COMPUTERS & OPERATIONS RESEARCH 2014年第Mar.期43卷 100-107页

作者： Araya, I. Riff, M. -C. Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile

The single container loading problem is a three-dimensional packing problem in which a container has to be filled with a set of boxes. The objective is to maximize the space utilization of the container. This problem has wide applications in the logistics industry. In this work, a new constructive approach to this problem is introduced. The approach uses a beam search strategy. This strategy can be viewed as a variant of the branch-and-bound search that only expands the most promising nodes at each level of the search tree. The approach is compared with state-of-the-art algorithms using 16 well-known sets of benchmark instances. Results show that the new approach outperforms all the others for each set of instances. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Beam search container loading problem Load planing Combinatorial optimization Constructive algorithms

来源：评论

学校读者我要写书评

暂无评论

A hybrid genetic algorithm for the container loading problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第1期131卷 143-161页

作者： Bortfeldt, A Gehring, H Fern Univ Hagen D-58084 Hagen Germany

This paper presents a hybrid genetic algorithm (GA) for the container loading problem with boxes of different sizes and a single container for loading. Generated stowage plans include several vertical layers each containing several boxes. Within the procedure, stowage plans are represented by complex data structures closely related to the problem. To generate offspring, specific genetic operators are used that are based on an integrated greedy heuristic. The process takes several practical constraints into account. Extensive test calculations including procedures from other authors vouch for the good performance of the GA, above all for problems with strongly heterogeneous boxes. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： packing container loading problem three-dimensional knapsack problem genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

A parallel tabu search algorithm for solving the container loading problem

引用

PARALLEL COMPUTING 2003年第5期29卷 641-662页

作者： Bortfeldt, A Gehring, H Mack, D Fernuniv Fachbereich Wirtschaftswissensch D-58084 Hagen Germany

This paper presents a parallel tabu search algorithm for the container loading problem with a single container to be loaded. The emphasis is on the case of a weakly heterogeneous load. The distributed-parallel approach is based on the concept of multi-search threads according to Toulouse et al. [Issues in designing parallel and distributed search algorithms for discrete optimization problems, Publication CRT-96-36, Centre de recherche sur les transports, Universitede Montreal, Canada, 1996] i.e., several search paths are investigated concurrently. The parallel searches are carried out by differently configured instances of a tabu search algorithm, which cooperate by the exchange of (best) solutions at the end of defined search phases. The parallel search processes are executed on a corresponding number of LAN workstations. The efficiency of the parallel tabu search algorithm is demonstrated by an extensive comparative test including well-known reference problems and loading procedures from other authors. (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： container loading problem tabu search distributed-parallel search

来源：评论

学校读者我要写书评

暂无评论

A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第1期191卷 86-99页

作者： Wang, Zhoujing Li, Kevin W. Levy, Jason K. Univ Windsor Odette Sch Business Windsor ON N9B 3P4 Canada Xiamen Univ Dept Automat Xiamen 361005 Fujian Peoples R China Western Washington Univ Huxley Coll Environm Bellingham WA 98225 USA

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm. (c) 2007 Elsevier B.V. All rights reserved.

关键词： heuristics container loading problem dynamic space decomposition holistic loading tertiary tree

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：