Bin Packing Problem with Item Time Window Conflict Dependent Profits

被引：0
作者：
Ren J. [1 ]
机构：
[1] Business School, Hohai University, Jiangsu, Nanjing
来源：
Applied Mathematics and Nonlinear Sciences | 2024年 / 9卷 / 01期
关键词：
Boxing problem; GRASP-VND algorithm; Iterative local search; Time window; Time-dependent profit;
D O I：
10.2478/amns-2024-0708
中图分类号：
学科分类号：
摘要：
The problem of packing with items with conflicting time-window dependence on profit considering departure time is studied in the context of consolidation of goods in transport, which is a practical problem in the logistics industry. The objective is to select the loading plan that is most profitable based on the volume and time windows of the items. The time windows of items in the same box must intersect, and the intersection of the items’ time windows affects the box’s departure time and hence the profit-dependent time. The problem is identified as an integer programming model for decision making, and two modeling strategies are proposed to address it by improving the GRASP heuristic. Multi-class examples are used in experiments to confirm that the improved algorithm can solve the problem efficiently, find the near-optimal solution in a shorter time, and enhance customer satisfaction. © 2023 Jiayue Ren, published by Sciendo.
引用
收藏
相关论文
共 21 条
  • [11] Liu Q., Cheng H., Tian T., Wang Y., Leng J., Zhao R., Zhang H., Wei L., Algorithms for the variable-sized bin packing problem with time windows, Computers & Industrial Engineering, 155, (2021)
  • [12] Dell'Amico M., Furini F., Iori M., A branch-and-price algorithm for the temporal bin packing problem, Computers & operations research, 114, (2020)
  • [13] Baldi M.M., Crainic T.G., Perboli G., Tadei R., Branch- and-price and beam search algorithms for the variable cost and size bin packing problem with optional items, Annals of Operations Research, 222, pp. 125-141, (2014)
  • [14] Jansen K., Ohring S., Approximation algorithms for time constrained scheduling, Information and computation, 132, 2, pp. 85-108, (1997)
  • [15] Gendreau M., Laporte G., Semet F., Heuristics and lower bounds for the bin packing problem with conflicts, Computers & Operations Research, 31, 3, pp. 347-358, (2004)
  • [16] Khanafer A., Clautiaux F., Talbi E.-G., New lower bounds for bin packing, European journal of operational research, 206, 2, pp. 281-288, (2010)
  • [17] Elhedhli S., Li L., Gzara M., Naoum-Sawaya J., A branch-and-price algorithm for the bin packing problem with conflicts, INFORMS Journal on Computing, 23, 3, pp. 404-415, (2011)
  • [18] Capua R., Frota Y., Ochi L.S., Vidal T., A study on exponential- size neighbourhoods for the bin packing problem with conflicts, Journal of Heuristics, 24, pp. 667-695, (2018)
  • [19] Bacci T., Nicoloso S., A heuristic algorithm for the bin packing problem with conflicts on interval graphs, (2017)
  • [20] Munien C., Ezugwu A.E., Metaheuristic algorithms for one-dimensional bin-packing problems: a survey of recent advances and applications, Journal of Intelligent Systems, 30, 1, pp. 636-663, (2021)
123