Enhanced Particle Swarm Optimization for Dual-Constraint Multi-Knapsack Problems: A Real-World Retail Packaging Application

2.1 Problem formulation

The Multi-Constraint Multi-Knapsack Parcel Optimization Problem (MCMKPOP) can be formally defined as follows. Given a set of items $I=\{1,2, \ldots, n\}$ and a set of bins $B= \{1,2, \ldots, m\}$, each item $i \in I$ has three attributes: price $p_i$, weight $w_i$, and computed value $v_i$. Each bin $\mathrm{j} \in \mathrm{B}$ has two capacity constraints: weight capacity $W_j$ and budget capacity $B_j$, and weight limit $W_j$.

Figure 1 illustrates the structural complexity of the Multi-Constraint Multi-Knapsack Parcel Optimization Problem (MCMKPOP) and demonstrates how the proposed PSO algorithm encodes solutions through assignment-based representation. The diagram visualizes five critical components that distinguish MCMKPOP from classical single-constraint formulations.

The Items Set (top section) represents the n retail items, each characterized by three attributes: price pᵢ (economic value), weight wᵢ (physical constraint), and computed value vᵢ (derived from the hybrid value function). This multi-attribute nature necessitates sophisticated optimization approaches that can balance competing objectives simultaneously.

The PSO Assignment Vector (middle section) demonstrates the core algorithmic innovation where each particle position X = [x₁, x₂, ..., xₙ] directly encodes bin allocation decisions. Unlike traditional binary representations that require n × m variables, this assignment-based encoding uses only n variables where xᵢ ∈ {0, 1, 2, ..., m} indicates the bin assignment for item i, with xᵢ = 0 representing non-selection. This compact representation enables more efficient search space navigation while maintaining solution interpretability.

The Bins Set (right section) illustrates the heterogeneous nature of packaging containers, each subject to dual constraints: weight capacity Wⱼ and budget capacity Bⱼ. The inclusion of unselected items emphasizes that MCMKPOP solutions need not utilize all available items, reflecting realistic retail scenarios where selective packaging maximizes value under resource limitations.

The Dual Constraints section explicitly visualizes the simultaneous constraint satisfaction requirement that differentiates MCMKPOP from simpler knapsack variants. Both weight constraint (Σᵢ∈Sⱼ wᵢ ≤ Wⱼ) and budget constraint (Σᵢ∈Sⱼ pᵢ ≤ Bⱼ) must be satisfied for each bin j, creating a complex feasible region that requires specialized constraint handling mechanisms.

Finally, the hybrid value function component highlights the multi-criteria evaluation approach that integrates normalized price contribution (40%), weight efficiency (30%), and price-to-weight ratio (30%). This balanced weighting scheme reflects retail priorities while enabling fair comparison across items with diverse characteristics.

The interconnected arrows demonstrate the information flow from item attributes through assignment decisions to constraint validation and objective evaluation, illustrating why MCMKPOP belongs to the NP-hard class and requires advanced metaheuristic approaches like the proposed PSO framework for practical solution.

1.png

Figure 1. Item-to-bin assignment structure in the Multi-Constraint Multi-Knapsack Problem (MCMKPOP)

The overall structure of item-to-bin assignment under dual constraints is illustrated in Figure 1. Each item, characterized by price, weight, and value, can be assigned to one of the bins with specific budget and weight capacities. The objective is to maximize the aggregated value while satisfying both constraints. The objective is to maximize the aggregated value across all bins while satisfying both constraints:

maximize

$Z=\sum_{j=1}^m \sum_{i \in S_j} v_i$     (1)

subject to

$\sum_{i \in S_j} w_i \leq W_i, \forall_j \in B$ (weight constraint)

$\sum_{i \in S_j} p_i \leq B_i, \forall_j \in B$ (budget constraint)

$\sum_{j=1}^m x_{i j} \leq 1, \forall_i \in I$ (assigment constraint)

$x_{i j} \in\{0,1\}, \forall \in I, \forall_j \in B$ (binary constraint)

where, $S_j$ denotes the set of items allocated to bin j , and decision variable $x_{i j} \in\{0,1\}$ indicates whether item i is assigned to bin j . This formulation belongs to the class of NP-hard problems, reflecting the computational difficulty of large-scale instances [5].

2.2 Hybrid value function

A key challenge in MCMKPOP is the evaluation of item desirability under multiple constraints. To address this, we propose a hybrid value function that balances direct economic value with resource efficiency:

$v_i=w_i \cdot \frac{p_i}{p_{\max }}+w_2 \cdot \frac{w_i}{w_{\max }}+w_3 \cdot \frac{d_i}{d_{\max }}$     (2)

where,

$\frac{p_i}{\max (p)}$ is the normalized price contribution

$\frac{w_i}{\max (w)}$ is the normalized weight contribution

$\frac{d_i}{d_{\max }}$ is the normalized price-to-weight ratio

$w_1, w_2, w_3$ are weigting parameters

Following multi-criteria decision-making principles [7], we assign $w_1=0.4$, $w_2=0.3$, and $w_3=0.3$. This reflects the higher priority of price (40%) in retail revenue optimization, while still emphasizing weight efficiency and balance. Similar hybrid scoring functions have proven effective in recent multi-objective knapsack formulations [1, 15]. The hybrid value function weights (w₁ = 0.4, w₂ = 0.3, w₃ = 0.3) were determined through consultation with retail domain experts from the Central Java Souvenir Entrepreneurs Association (ASPOO). Based on their operational experience in the Indonesian souvenir retail sector, the 40% weight allocation to price reflects the primary revenue-driven objective in competitive retail markets, where profit margins directly impact business sustainability. The equal 30% allocation to weight efficiency and price-to-weight ratio acknowledges the growing importance of shipping optimization and customer value perception in modern e-commerce environments, while maintaining business practicality over purely theoretical optimality.

2.3 PSO algorithm adaptation

2.3.1 PSO algorithm overview and enhancement framework

Each particle encodes a complete allocation of items across bins using an assignment-based representation. The position vector $\mathrm{X}=\left[w_1, w_2, \ldots, w_n\right]$ specifies the bin assignment for each item, with $w_i=j$ if item $i$ is placed in bin $j$, and $x_i=0$ if unassigned. This discrete encoding ensures direct interpretability for the MCMKPOP.

Particle Swarm Optimization simulates social behavior of bird flocking or fish schooling to solve optimization problems. The algorithm maintains a population (swarm) of candidate solutions (particles) that move through the search space according to both individual experience (personal best) and collective knowledge (global best). Algorithm 1 presents our enhanced PSO framework specifically adapted for MCMKPOP.

Key Enhancement Integration Points: Repair mechanism ensures initial feasibility (in line 4, detailed in Section 2.3.4), Hybrid value function evaluation (in line 5, defined in Section 2.2), Assignment-based position update (in line 12-16 explained in Section 2.3.3).

2.3.2 Enhanced particle representation

Each particle in the swarm represents a complete solution to MCMKPOP using an assignment-based encoding. A particle's position vector $X=\left[x_1, x_2, \ldots, x_n\right]$ where $x_i \in\{0,1,2, \ldots, m\}$ indicates the bin assignment for item i , with $x_i=$ 0 representing non-selection. In the traditional Particle Swarm Optimization (PSO), the search process is conducted in a continuous space where particle positions are represented by real values. In contrast, our proposed enhancement operates within a discrete assignment space, where positions correspond to integer bin indices. This discrete representation enables a more direct modeling of bin allocation decisions, aligning the optimization process more closely with the problem's inherent structure. At the same time, the method preserves the continuous optimization capability of PSO by leveraging velocity-based movement combined with appropriate rounding operations, thereby ensuring both precision in capturing the discrete nature of the problem and efficiency in the optimization process.

2.3.3 Enhanced velocity and position update

The velocity update follows the canonical PSO formulation with discrete adaptations [12]:

$v_i^{(t+1)}=w v_i^t+c_1 r_1\left(\right.$ pbest $\left._i-x_i^{(t)}\right)+c_2 r_2\left(\right.$ gbest $\left.-x_i^{(t)}\right)$     (3)

$x_i^{(t+1)}=\operatorname{round}\left(\max \left(0, \min \left(m, x_i^{(t)}+v_i^{(t=1)}\right)\right)\right)$     (4)

where, $w$ is the inertia weight, $c_1$ and $c_2$ are acceleration coefficients, and $r_1, r_2$ are random numbers uniformly distributed in $[0,1]$. The updated positions are projected onto the discrete domain through rounding and clipping operators [13]. The proposed enhancement introduces several key modifications to the standard PSO framework. First, particle velocities are maintained as continuous values to preserve the exploration capability of the algorithm. Second, particle positions are mapped to discrete values, ensuring that bin assignments remain valid within the problem space. Finally, a boundary-handling mechanism is incorporated to prevent infeasible solutions by restricting assignments to the valid range between 0 and m . Collectively, these enhancements allow the algorithm to effectively capture the discrete characteristics of the bin allocation problem while retaining the search efficiency of continuous PSO dynamics.

2.3.4 Enhanced repair-based constraint handling

To ensure feasibility, we implement a repair mechanism that removes infeasible assignments. If a bin exceeds its weight or budget limit, items are greedily removed based on their lowest value-to-cost efficiency until feasibility is restored [15, 23]. This mechanism avoids premature solution rejection while preserving high-value allocations, an approach recently shown effective in discrete swarm optimization [7, 24].

To maintain solution feasibility, we implement a repair mechanism that addresses constraint violations:

The proposed enhancement offers several advantages that strengthen the effectiveness of PSO in constrained optimization. By removing the least valuable items first, the mechanism preserves high-value components of the solution, thereby maintaining overall quality. Feasibility is ensured through strict constraint satisfaction, while a maximum iteration safety check prevents the occurrence of infinite loops. Furthermore, a greedy repair strategy is employed to balance solution quality and feasibility, providing a systematic approach to handle conflicts. Collectively, this repair mechanism constitutes the primary algorithmic contribution of our work, as it enables PSO to effectively address dual constraints on both weight and budget while preserving solution quality through intelligent item removal strategies.

While the current safety mechanism clears a bin completely if maximum iterations are exceeded, we acknowledge that this coarse strategy may reduce solution quality in rare cases. Alternative approaches, such as adaptive penalties or partial degradation strategies, will be explored in future work to achieve more graceful feasibility restoration without compromising high-value allocations.

2.4 Experimental design

2.4.1 Dataset and problem instances

The experimental evaluation is based on a real-world dataset collected from a retail souvenir shop in Semarang, Indonesia. The dataset includes 213 items with price (in IDR) and weight (grams). Ten bins are defined to represent diverse packaging strategies, ranging from highly constrained “Mini Package” (150,000 IDR, 800g) to large-capacity “Jumbo Package” (800,000 IDR, 4000g). Such heterogeneity reflects realistic multi-constraint environments commonly encountered in retail operations [3], The details of bin configurations are summarized in Table 1.

2.4.2 Baseline algorithms

This research compared the proposed PSO against three baselines, Genetic Algorithm (GA): tournament selection, uniform crossover, mutation rate 0.1. Simulated Annealing (SA): geometric cooling with hybrid neighborhood structures [17]. Random Search (RS): statistical baseline to assess optimization necessity. These baselines represent widely studied metaheuristics for knapsack variants [7, 8].

2.4.3 Statistical validation

Each algorithm is executed 30 times under independent random seeds. We evaluate: best fitness, mean ± standard deviation, utilization ratios, and violation rates. To establish statistical rigor, both parametric tests (Welch’s t-test, effect size by Cohen’s d) and non-parametric tests (Mann-Whitney U) are applied, ensuring robustness regardless of distributional assumptions [17]. Multiple comparisons are corrected using Bonferroni adjustment, consistent with best practices in algorithm performance validation [15].

Table 1. Bin configuration details

2.5 Upper bound estimation

To benchmark algorithmic performance, we compute a theoretical upper bound using a multi-knapsack-aware greedy relaxation. Items are fractionally assigned based on bin-specific efficiency comparative performance metrics of the algorithms are provided in Table 2. This avoids the overestimation caused by double-counting items across bins, a common limitation of naive upper bounds [5, 19]. Fractional relaxation guarantees admissibility and provides a tight, computationally efficient benchmark for evaluating heuristic performance.

Table 2. Algorithm performance comparison

*Comprehensive performance metrics across 30 independent runs for each algorithm. Quality percentage represents performance relative to theoretical upper bound (21.7818). Weight/Budget utilization percentages indicate resource efficiency across the heterogeneous bin configuration. Zero violations confirm effective constraint handling across all metaheuristic approaches.

The bin-specific efficiency calculation in step 6 represents a key innovation:

$e_{i j}=\frac{v_i}{\frac{w_i}{w_j}+\frac{p_i}{B_j}}$     (5)

where,

$v_i$  = value of item i

$w_i$  = weight of item i

$W_j$  = weight capacity of knapsack j

$p_i$  = price (or cost) of item i

$B_j$  = budget (price capacity) of knapsack j

Thus, $e_{i j}$  represents the efficiency score of item i with respect to knapsack j. This formulation normalizes resource consumption relative to bin capacity, ensuring that efficiency assessment adapts to each bin's constraint profile. Items that are efficient for large-capacity bins may exhibit poor efficiency for smaller bins, and vice versa.

Figure 2 illustrates the conceptual process of the multi-knapsack-aware upper bound. Items are first ranked according to bin-specific efficiency, sequentially allocated to bins until capacity is reached, and fractionally relaxed if no full item can be inserted. This visualization clarifies the novelty of our approach compared to traditional single-knapsack relaxations, which often overestimate bounds due to item double-counting.

To complement the preceding mathematical formulation and algorithmic description, a schematic flow diagram is presented to illustrate the sequential steps of the multi-knapsack-aware upper bound estimation. The process begins with sorting bins, followed by computing efficiency values, allocating items, applying fractional relaxation when capacity is insufficient, and repeating the procedure across bins until the final global upper bound is obtained. This visual representation provides an intuitive understanding of the workflow and emphasizes the distinction between the proposed approach and traditional single-knapsack relaxations.

2.png

Figure 2. Conceptual flowchart of the multi-knapsack-aware upper bound estimation process

2.6 Mathematical properties and correctness

The algorithm maintains three critical upper bound properties: (1) Admissibility: UB ≥ OPT where OPT represents the optimal integer solution, guaranteed through fractional relaxation and efficiency-based ordering; (2) Tightness: Minimal overestimation achieved through multi-knapsack awareness and item competition modeling; (3) Computational Efficiency: O (n log n + nm) complexity where sorting dominates for typical problem instances.

Theorem 1 (Upper Bound Validity): Let UB be the value computed by Algorithm 2 and OPT be the optimal integer solution value for MCMKPOP. Then UB ≥ OPT.

Proof Sketch: The algorithm processes bins in decreasing capacity order, ensuring high-capacity bins receive priority access to valuable items. For each bin, items are selected in efficiency order until constraints are violated. Fractional relaxation allows partial item inclusion, relaxing integrality constraints while maintaining feasibility. Since no item is considered for multiple bins (removal in step 12), the bound remains valid. The efficiency-based ordering ensures locally optimal selections per bin, and fractional relaxation provides the tightest possible bound for the remaining capacity. Therefore, UB represents an achievable upper limit for any feasible integer solution.

The multi-knapsack aware methodology ensures tighter bounds compared to naive approaches that independently optimize each bin, providing more accurate performance assessment for MCMKPOP scenarios where resource competition fundamentally influences optimization outcomes. Computational complexity analysis shows O (n log n + nm) performance, significantly more efficient than exact methods (exponential complexity) while maintaining mathematical rigor and practical applicability.

2.7 Implementation details

In this research for all algorithms were implemented in Python 3.8 using NumPy for numerical computation and SciPy for statistical testing. Parameter tuning was performed through preliminary sensitivity analysis. The PSO employed a swarm size of 50 particles and 1000 iterations, following common practice in recent swarm optimization research [13, 25]. Experiments were run on standardized hardware to ensure fair comparison across algorithms.

Table 3. Algorithm parameter configuration

Parameter selection as seen in Table 3 followed an empirical approach based on established PSO literature recommendations and preliminary testing. The inertia weight w = 0.7 provides balanced exploration-exploitation behavior, while equal cognitive and social coefficients (c₁ = c₂ = 1.4) ensure symmetric influence between personal and global search guidance [11-13]. These values fall within optimal ranges reported in recent PSO studies for combinatorial optimization [15, 25]. For baseline algorithms, parameters were selected to ensure fair comparison, with population sizes standardized across all metaheuristics to maintain experimental validity.

The superior performance of the proposed PSO framework for the Multi-Constraint Multi-Knapsack Parcel Optimization Problem (MCMKPOP) is primarily driven by its novel integration of an assignment-based representation, a repair-based constraint mechanism, and a hybrid value function that jointly considers price, weight, and efficiency ratios. This combination enables the algorithm to consistently achieve near-optimal performance under dual-constraint conditions, addressing a gap left by existing studies that typically optimize weight or budget independently [7, 15]. Unlike GA and SA, which either converge prematurely or show inconsistent performance, the swarm-based search dynamics of PSO allow it to balance exploration and exploitation effectively, resulting in higher solution quality and stability. The ability of PSO to attain 100% of the theoretical upper bound while maintaining zero constraint violations and balanced utilization (> 90%) across weight and budget demonstrates its robustness and practical applicability in retail environments, where feasibility is as critical as optimization quality [3]. Beyond algorithmic performance, this study contributes methodological advances by introducing a multi-knapsack-aware upper bound that eliminates item double-counting and by implementing rigorous statistical validation using both parametric and non-parametric testing, thus enhancing confidence in the reproducibility of results [19, 31]. Nevertheless, limitations remain regarding dataset scale and domain specificity, as the current evaluation is based on 213 items from a single retail context in Indonesia. To broaden applicability, future work should test scalability to larger and cross-sectoral datasets, extend the static formulation toward dynamic reallocation under fluctuating demand and capacity, and investigate adaptive weighting schemes to further refine the hybrid value function. Such extensions will strengthen the role of swarm intelligence not only as a powerful optimization tool but also as a practical decision-support system in real-world retail and logistics operations [1].

While the proposed weights reflect authentic retail priorities from Indonesian souvenir businesses, this domain-specific parameterization represents a limitation for broader applicability. The 40%-30%-30% allocation may not be optimal for other retail sectors (e.g., high-volume e-commerce, luxury goods, or international logistics) where operational priorities differ significantly.

Then, in the current parameter selection, while based on literature guidance and empirical validation, represents a limitation in terms of systematic optimization. Future work should employ formal parameter tuning approaches such as grid search, Bayesian optimization, or racing algorithms to identify optimal parameter configurations across diverse problem instances.

4.1 Deployment considerations

From a deployment perspective, the proposed PSO framework demonstrated an average runtime of 12.4 seconds for the 213-item dataset on standard desktop hardware, making it suitable for near real-time decision support. Integration into enterprise systems can be achieved by embedding the Python implementation as a service module in retail ERP or logistics platforms. Scalability analysis further indicates that runtime grows linearly with the number of items, suggesting feasibility for larger datasets when supported by parallelization or GPU acceleration.

Although the current validation is based on retail packaging, the proposed methodology generalizes naturally to other domains. In e-commerce, the model can be adapted for dynamic bundle pricing and personalized packaging. In logistics and warehouse management, it supports multi-bin allocation under heterogeneous storage capacities. In cloud computing, the same dual-constraint framework applies to virtual machine placement with CPU and memory limits. These extensions highlight the broader applicability of the proposed PSO beyond retail, warranting further empirical validation across sectors.