EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Heuristics for the One-Dimensional Bin Packing Problem with Time Windows

Huibing Cheng, Hong He, Shanshui Zheng, Jian Tu, Dengheng Zheng

Frontiers in Applied Mathematics and Statistics · 29.06.2026 · 12

DOI: 10.3389/fams.2026.1741977 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Frontiers in Applied Mathematics and Statistics, online erschienen am 29.06.2026. Verfasst von Huibing Cheng und 4 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper investigates the one-dimensional bin packing problem with time windows (1DBPP-TW), a practical variant of the bin packing problem widely applied in logistics. Existing relevant studies mainly focus on bin packing problems with variable-sized bins under time constraints, while 1DBPP-TW with homogeneous bins and a shared time window requirement for items in one bin has not been fully explored. Given the NP-completeness of the bin packing problem, exact algorithms are not applicable to large-scale instances, so this paper first establishes a mathematical model for 1DBPP-TW and generates two benchmark datasets including optimal-solution-known instances and random instances for verification, then proposes two efficient algorithms: the Greedy on Time Range (GTR) heuristic which ensures real-time response and obtains reliable solutions within 0.001 seconds for large instances, and the Iterative Local Search (ILS) metaheuristic equipped with three neighborhood operators to improve convergence rate and reduce the number of used bins by an average of 7.3% compared with GTR. Comparative experiments with the CPLEX solver within a 3600-second time limit show that the two proposed algorithms have higher computational efficiency and equivalent or better solution quality for medium and large instances. In practice, these algorithms resolve logistics industry problems including low loading efficiency and time window conflicts, and theoretically, this research advances the combinatorial optimization theory of time-constrained bin packing variants and provides standard benchmarks for follow-up studies. This study is limited to homogeneous bins and synthetic test instances, and future work will expand to multi-dimensional packing, dynamic time window constraints and practical verification with real industrial data.

Zitieren

APA

Cheng, H., He, H., Zheng, S., Tu, J., & Zheng, D. (2026). Heuristics for the One-Dimensional Bin Packing Problem with Time Windows. Frontiers in Applied Mathematics and Statistics, 12. https://doi.org/10.3389/fams.2026.1741977

Vancouver

Cheng H, He H, Zheng S, Tu J, Zheng D. Heuristics for the One-Dimensional Bin Packing Problem with Time Windows. Frontiers in Applied Mathematics and Statistics. 2026;12. doi:10.3389/fams.2026.1741977

BibTeX
@article{Cheng2026,
  author = {Cheng, Huibing and He, Hong and Zheng, Shanshui and Tu, Jian and Zheng, Dengheng},
  title = {Heuristics for the One-Dimensional Bin Packing Problem with Time Windows},
  journal = {Frontiers in Applied Mathematics and Statistics},
  year = {2026},
  volume = {12},
  doi = {10.3389/fams.2026.1741977}
}
Kostenlos starten →