The Bin Packing Problem with Item Fragmentation: A worst-case analysis

被引:10
作者
Bertazzi, Luca [1 ]
Golden, Bruce [2 ]
Wang, Xingyin [3 ]
机构
[1] Univ Brescia, Dept Econ & Management, Brescia, Italy
[2] Univ Maryland, RH Smith Sch Business, College Pk, MD 20742 USA
[3] Singapore Univ Technol & Design, Engn Syst & Design, Singapore, Singapore
关键词
Bin Packing Problem; Split Delivery Vehicle Routing Problem; Item Fragmentation; Worst-case analysis; SPLIT; COMPLEXITY; BOUNDS;
D O I
10.1016/j.dam.2018.08.023
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We provide a worst-case analysis of two variants of the classical Bin Packing Problem based on item splitting: The Bin Packing Problem with Item Fragmentation and the Bin Packing Problem with an x, 1 - x Split Rule. In the former case, there is no restriction on item splitting, while, in the latter case, items are allowed to be split in only one way according to their sizes. We provide the worst-case performance bound of the classical Bin Packing Problem with respect to both variants, in the general case and in some classes of instances. Finally, since the Vehicle Routing Problem reduces to the Bin Packing Problem when all customers are in the same location, we show how these results relate to the Split Delivery Vehicle Routing Problem and to the Split Delivery Vehicle Routing Problem with an x, 1 - x Split Rule. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:63 / 77
页数:15
相关论文
共 25 条
[1]   Worst-case analysis for split delivery vehicle routing problems [J].
Archetti, C ;
Savelsbergh, MWP ;
Speranza, MG .
TRANSPORTATION SCIENCE, 2006, 40 (02) :226-234
[2]   Vehicle routing problems with split deliveries [J].
Archetti, C. ;
Speranza, M. G. .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2012, 19 (1-2) :3-22
[3]   To split or not to split: That is the question [J].
Archetti, Claudia ;
Savelsbergh, Martin W. P. ;
Speranza, M. Grazia .
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2008, 44 (01) :114-123
[4]   Complexity of the VRP and SDVRP [J].
Archetti, Claudia ;
Feillet, Dominique ;
Gendreau, Michel ;
Speranza, M. Grazia .
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES, 2011, 19 (05) :741-750
[5]  
Burrows W., 1988, 24th Annual Conference of the Operational Research Society of New Zealand, P33
[6]   Exactly solving packing problems with fragmentation [J].
Casazza, Marco ;
Ceselli, Alberto .
COMPUTERS & OPERATIONS RESEARCH, 2016, 75 :202-213
[7]   Mathematical programming algorithms for bin packing problems with item fragmentation [J].
Casazza, Marco ;
Ceselli, Alberto .
COMPUTERS & OPERATIONS RESEARCH, 2014, 46 :1-11
[8]   Lower and upper bounds for the Bin Packing Problem with Fragile Objects [J].
Clautiaux, Francois ;
Dell'Amico, Mauro ;
Iori, Manuel ;
Khanafer, Ali .
DISCRETE APPLIED MATHEMATICS, 2014, 163 :73-86
[9]  
Coffman E.G., 2013, Bin Packing Approximation Algorithms: Survey and Classification, Vsecond, P455, DOI DOI 10.1007/978-1-4419-7997-135
[10]  
de Niz D, 2006, INT J EMBED SYST, V2, P196, DOI 10.1504/IJES.2006.014855