Elite Trajectory Exploration for Pareto Front Approximation in Dynamic Bin Packing*

Abstract

The Dynamic Multi-Objective Bin-Packing Problem (DMOBPP) presents significant challenges in simultaneously optimizing bin usage (z1), thermal heat (z2), and delivery time (z3). This paper proposes AMSS-PATH, a hybrid metaheuristic integrating Strategic Path Relinking into an Adaptive Multi-Objective Scatter Search (AMSS) framework with three specialized operators (Φ1,Φ2,Φ3), each targeting a distinct objective. By exploring elite-solution trajectories, the method densifies the Pareto frontier through targeted intensification at every intermediate point. Experimental results on toy and full-scale instances yield a Net Front Contribution (NFC) of 100%, a Binary Conflict Index (BCI) of ≈ 0, and a 4.8% hypervolume gain over base AMSS, significantly outperforming GAMMA-PC, MOMA, and NSGA-II. A Wilcoxon signed-rank test (p ≈ 0.031) confirms statistical significance.