Integrating adaptive pattern learning and fuzzy logic for online bin packing

Abstract

The online bin packing problem (BPP) faces critical challenges in real-world applications due to inherent uncertainties in unknown future input. Current approaches-whether learning-augmented algorithms or fuzzy logic systems-operate in isolation, failing to synergise historical knowledge exploitation with flexible and uncertainty-tolerant decision-making. This thesis bridges this gap through three interconnected innovations that advance decision-making under uncertainty for online BPP and its vector generalisation.

First, we present a pattern-learning method for online BPP using symmetrical partitioning to discretise item sizes, prioritising practical performance over worst-case guarantees. Unlike the Harmonic algorithm’s rigid partitioning, our approach combines discretised items into adaptive packing patterns informed by historical data-a novel strategy in online BPP heuristics. Compared to the exact placeholder mechanism of ProfilePacking (PrP), a contemporary learning based online BPP algorithm, our pattern-based plans offer tunable generalisation and inherent compatibility with continuous item sizes. The derived PatternPack algorithm outperforms Best-Fit in computational efficiency and solution quality, with stability against distribution shifts. This data-driven pattern framework may extend to other online optimisation problems requiring input-stream adaptability.

Second, we introduce a fuzzy-logic model for online BPP, replacing static policies with dynamic, uncertainty-aware bin selection. Unlike crisp-parameter heuristics, our approach integrates runtime statistics via type-1 fuzzy systems and could be extended with type-2 fuzzy sets using the novel weighted-Or (Wor) operator. Wor outperforms traditional type-2 operators in adaptability, enabling problem-specific tuning and excelling in uncertainty quantification, particularly for out-of-distribution scenarios, where it achieves state-of-the-art results. Validated across regression, classification, and BPP tasks, this model, together with the Wor operator, provides a flexible yet uncertainty-tolerant approach for decision-making in pattern-based online BPP algorithms and online packing algorithms with constraints.

Third, we design the FuzzyPatternPack (FPP) algorithm, integrating pattern-based planning and fuzzy logic for adaptive bin selection in online BPP. Unlike the PrP algorithm, which relies on strict matching mechanisms, FPP reduces the performance gap relative to offline solutions and demonstrates stronger tolerance to prediction errors caused by evolving input distributions. Extending FPP to Vector BPP using DBSCAN clustering algorithm, we address multi-dimensional resource constraints and scalability in more complex scenarios. With the ability to unify pattern-learning, fuzzy logic, and machine learning, FPP establishes a practicality-focused paradigm for online packing problems with intricate constraints.

By harmonising pattern-driven adaptability with error tolerance in fuzzy decision-making, this work establishes a paradigm for uncertainty-aware online BPP and related online packing problems. The proposed methods transcend bin packing, offering generalisable insights for logistics, scheduling, and resource allocation systems where uncertainty and partial observability dominate.

Date of Award	20 Aug 2025
Original language	English
Awarding Institution	University of Nottingham
Supervisor	Jiawei Li (Supervisor), Huan Jin (Supervisor) & Tianxiang Cui (Supervisor)