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

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 261卷

关键词：

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].