Hybridizing a Grouping Metaheuristic with Reinforcement Learning for the One-Dimensional Bin Packing Problem

Jul 16, 2026

The one-dimensional Bin Packing Problem (1D-BPP) assigns items with known sizes to identical fixed-capacity bins while minimizing the number of bins and never exceeding capacity. The NP-hard nature of 1D-BPP makes exact methods quickly intractable as instances grow. This study proposes RLHGGA, a hybrid that keeps HGGA’s grouping genetic operators but replaces fixed probabilistic selection with an adaptive Q-learning policy, choosing macro-actions from the search state using rewards from solution improvement and computational cost. Experiments on Falkenauer, Scholl, and Hard28 benchmarks compare FFD, HGGA, and RL-HGGA by bins, gap to lower bound, and runtime. Results retain near-HGGA quality while substantially reducing execution time, with ablations indicating the learning component mainly improves time efficiency.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

Introduction

Problem Definition

State of the Art of Metaheuristics

Hybridization of a Grouping Metaheuristic and Reinforcement Learning for the One-Dimensional Bin Packing Problem Mostefai Mounir Sofiane, Tati Youcef, Badaoui Ikram, Bousdjira Nadine, Hasnaoui Sarah, Zitouni Rania Square Two Team – Optimization Module École Nationale Supérieure d’Informatique (ESI) Algiers, Algeria [Emails: mm_mostefai@esi.dz](Emails: mm_mostefai@esi.dz), [my_tati@esi.dz](my_tati@esi.dz), [mi_badaoui@esi.dz](mi_badaoui@esi.dz), [mn_bousdjira@esi.dz](mn_bousdjira@esi.dz), [ms_hasnaoui@esi.dz](ms_hasnaoui@esi.dz), [mr_zitouni@esi.dz](mr_zitouni@esi.dz) arXiv :2607 .023 15v 1 [ cs .NE] 2 Jul 2026 Abstract—The one-dimensional Bin Packing Problem (1D-BPP) consists of assigning a set of items with known sizes to a minimum number of identical bins of fixed capacity, without exceeding the capacity of any bin. This problem is NP-hard and quickly becomes intractable for exact methods as instance size grows. In this work, our central focus is a hybridization between the Hybrid Grouping Genetic Algorithm (HGGA) metaheuristic and reinforcement learning. The proposed approach, denoted RLHGGA, retains the classical operators of HGGA but replaces their fixed probabilistic selection with an adaptive policy learned via Q-learning. The agent observes the current state of the search, selects a macro-action, and updates its policy based on a reward derived from solution improvement and computational cost. Experiments are conducted on standard 1D-BPP benchmarks (Falkenauer, Scholl, and Hard28) and compare FFD, HGGA, and RL-HGGA in terms of number of bins used, gap to the lower bound, and execution time. Results show that HGGA remains the best reference in average solution quality, whereas RL-HGGA provides an interesting quality–time trade-off by substantially reducing computation time while maintaining quality close to that of HGGA. The ablation study shows that the ML component primarily improves the time efficiency of the search while preserving solution quality close to that of HGGA. Index Terms—Bin Packing Problem, combinatorial optimization, metaheuristics, Grouping Genetic Algorithm, HGGA, reinforcement learning, Q-learning, hybridization. I. INTRODUCTION A. Problem Definition The one-dimensional Bin Packing Problem is a grouping and assignment problem. Given a set of items I = {1,..., n}, where each item i has a size wi , and a set of identical bins of capacity C, the goal is to assign each item to a bin such that the capacity is never exceeded, while minimizing the total number of bins used. This problem arises naturally in logistics, industrial cutting, memory allocation, file storage, and resource loading. Its theoretical difficulty is well established: the 1D-BPP is NP-hard, which explains the widespread use of approximate methods as instance size increases [1], [2] . B. State of the Art of Metaheuristics The literature on solving the 1D-BPP can be organized into three main families. The first encompasses constructive heuristics, such as First Fit, Best Fit, First Fit Decreasing (FFD), and Best Fit Decreasing. These methods build a solution by scanning items in a given order and placing them in an existing bin or opening a new one. They are valued for their simplicity and speed, but remain limited by their greedy nature: a poor decision made early in construction is generally not revised afterward [2] . The second family comprises exact and near-exact methods, such as integer linear programming, branch-and-bound, and branch-and-price schemes. These approaches are important because they can prove optimality or provide reference bounds. However, their computational cost grows rapidly with instance size and difficulty. In an experimental context where multiple benchmark families must be processed, approximate methods therefore remain necessary. The third family, central to this work, is that of metaheuristics. Metaheuristics are general-purpose search methods capable of exploring a very lar

FAQs

What is the goal of the one-dimensional Bin Packing Problem (1D-BPP)?

Assign items to identical fixed-capacity bins without exceeding any bin’s capacity, while minimizing the total number of bins used.

How does RLHGGA hybridize HGGA with reinforcement learning?

RLHGGA keeps HGGA’s classical grouping genetic operators but replaces their fixed probabilistic selection with an adaptive policy learned via Q-learning, where an agent selects macro-actions and updates based on rewards tied to improvement and computational cost.

What do experiments on standard benchmarks show about RL-HGGA compared with HGGA and FFD?

HGGA remains the best reference in average solution quality, while RL-HGGA achieves an advantageous quality–time trade-off by substantially reducing computation time while keeping quality close to HGGA.

Jul 16, 2026

Upload by Emma Wilson