Variable neighbourhood search for the variable sized bin packing problem

被引:40
作者
Hemmelmayr, Vera [1 ]
Schmid, Verena [1 ]
Blum, Christian [2 ]
机构
[1] Univ Vienna, Dept Business Adm, Vienna, Austria
[2] Univ Politecn Cataluna, ALBCOM Res Grp, Barcelona, Spain
关键词
Variable sized bin packing; Variable neighbourhood search; Hybrid algorithms;
D O I
10.1016/j.cor.2011.07.003
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1097 / 1108
页数:12
相关论文
共 50 条
[41]   Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem [J].
Albert Corominas ;
Alberto García-Villoria ;
Rafael Pastor .
TOP, 2013, 21 :296-312
[42]   Solving the Multi-activity Shift Scheduling Problem using Variable Neighbourhood Search [J].
Qu, Yi ;
Curtois, Timothy .
PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS (ICORES), 2020, :227-232
[43]   Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem [J].
Corominas, Albert ;
Garcia-Villoria, Alberto ;
Pastor, Rafael .
TOP, 2013, 21 (02) :296-312
[44]   A flexible variable neighbourhood search algorithm for different variants of the Electric Vehicle Routing Problem [J].
Souza, Andre L. S. ;
Papini, Marcella ;
Penna, Puca H. V. ;
Souza, Marcone J. F. .
COMPUTERS & OPERATIONS RESEARCH, 2024, 168
[45]   Multi-objective genetic algorithm with variable neighbourhood search for the electoral redistricting problem [J].
Vanneschi, Leonardo ;
Henriques, Roberto ;
Castelli, Mauro .
SWARM AND EVOLUTIONARY COMPUTATION, 2017, 36 :37-51
[46]   A Variable Neighbourhood Search-Based Algorithm for the Transit Route Network Design Problem [J].
Iliopoulou, Christina ;
Tassopoulos, Ioannis ;
Beligiannis, Grigorios .
APPLIED SCIENCES-BASEL, 2022, 12 (20)
[47]   Variable neighbourhood search for close-open vehicle routing problem with time windows [J].
Brito, Julio ;
Exposito, Airam ;
Moreno, Jose A. .
IMA JOURNAL OF MANAGEMENT MATHEMATICS, 2016, 27 (01) :25-38
[48]   Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms [J].
Chu, CB ;
La, R .
SIAM JOURNAL ON COMPUTING, 2001, 30 (06) :2069-2083
[49]   A Variable Neighbourhood Search Approach for Crew Transportation Problems [J].
Jarumaneeroj, Pisit ;
Kunaporn, Siriwat .
2017 4TH INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND APPLICATIONS (ICIEA), 2017, :229-233
[50]   A simple randomized variable neighbourhood search for nurse rostering [J].
Zheng, Ziran ;
Liu, Xiyu ;
Gong, Xiaoju .
COMPUTERS & INDUSTRIAL ENGINEERING, 2017, 110 :165-174