New Metaheuristics to Solve the Internet Shopping Optimization Problem with Sensitive Prices

Abstract

In this research, two new methods for solving the Internet shopping optimization problem with sensitive prices are proposed, incorporating adaptive adjustment of control parameters. This problem is classified as NP-hard and is relevant to current electronic commerce. The first proposed solution method corresponds to a Memetic Algorithm incorporating improved local search and adaptive adjustment of control parameters. The second proposed solution method is a particle swarm optimization algorithm that adds a technique for diversification and adaptive adjustment of control parameters. We assess the effectiveness of the proposed algorithms by comparing them with the Branch and Bound algorithm, which presents the most favorable outcomes of the state-of-the-art method. Nine instances of three different sizes are used: small, medium, and large. For performance validation, the Wilcoxon and Friedman non-parametric tests are applied. The results show that the proposed algorithms exhibit comparable performance and outperform the Branch and Bound algorithm.

1. Introduction

Currently, most Internet transactions are primarily due to online purchases, which have become increasingly important because of the COVID-19 pandemic [1]. Customers seek to minimize the cost of their purchases by considering the discounts offered by online stores, since prices change daily depending on the advertised offers. The Internet shopping problem was formally defined by Błażewicz [2]; furthermore, this author shows that this problem corresponds to the NP-hard type by constructing a pseudo-polynomial transformation of the Exact Cover by 3-Sets problem P1.

Currently, metaheuristic algorithms are widely used to solve optimization problems. They are generally used to find optimal solutions or to work towards the optimal value in NP-hard optimization problems [3]. A study by Li [4] identifies the main trends and areas of application of metaheuristic algorithms such as logistics, manufacturing, artificial intelligence, and computer science; the main reason for its popularity is its flexibility in addressing NP-hard problems. Valencia-Rivera [5] presents a complete analysis of trends and the impact of the metaheuristic algorithms that are most frequently used to solve optimization problems today; the review includes particle swarm optimization algorithms, genetic algorithms, and Ant Colony algorithms.

Therefore, developing new solution methods and metaheuristics is essential for identifying which stores offer the best discount to satisfy a shopping list. The described issue is known as the Internet shopping problem with sensitive prices (IShOPwD); related works are described below:

Błażewicz [6] designed the IShOPwD model for the first time, considering only the customer’s perspective. This model explicitly addresses a scenario where a client aims to buy several products from multiple online stores, focusing on minimizing the total cost of all products and incorporating applicable discounts into the overall cost. The solution method developed is a branch-and-bound algorithm (BB).

Musial [7] proposes a set of algorithms (Greedy Algorithm (GA), Forecasting Algorithm (FA), Cellular Processing Algorithm (CPA), MinMin Algorithm, and Branch and Bound algorithm) to solve the problem of IShOPwD optimization. These algorithms are crafted to generate various solutions at different computation times, aiming to achieve results that are close to the optimal solution. The results of these proposed algorithms are compared with the optimal solutions and calculated using a BB.

In the work of Błażewicz et al. [8], the authors define and study some price-sensitive extensions of the IShOP. The study includes the IShOP with price-sensitive discounts and a newly defined optimization problem: the IShOP that includes two discount functions (a shipping cost discount function and a product price discount function). They formulate mathematical programming problems and develop some algorithms (new heuristic: new forecasting), and exhaustive feasibility tests are carried out.

Another related work is that of Chung and Choi [9]. This work aims to introduce an optimal bundle search problem called “OBSP” that allows integration with an online recommendation system (Bundle Search Method) to provide an optimized service considering pairwise discounting and the delivery cost. The results are integrated into an online recommendation system to support user decision-making.

Mahrundinda [10] and Morales [11] analyze the trends and solution methods applied to the IShOP and determine that no solution methods have used non-deterministic metaheuristics to solve the IShOPwD until now. That is why it was decided to adopt the solution methods proposed by Huacuja [12] and García-Morales [13], which are metaheuristic algorithms that provide the best results for the IShOP variant with shipping costs.

In this research, we develop two metaheuristic algorithms (a Memetic Algorithm (MAIShOPwD) and a particle swarm optimization algorithm (PSOIShOPwD)) that allow us to solve the Internet shopping problem with sensitive prices.

The main contributions of the proposed MAIShOPwD algorithm are as follows:

• A novel method for calculating changes in the objective values of the current solution during local search, with a time complexity of $O \left(1\right)$.
• Adaptive adjustment of control parameters.

On the other hand, the contributions of the proposed PSOIShOPwD algorithm are as follows:

• A neighborhood diversification technique and a local search at the end of each iteration.
• Adaptive adjustment of control parameters.

A revised approach derived from the bandit-based adaptive operator selection technique, Fitness-Rate-Rank-Based Multiarmed Bandit (FRRMAB) [14], was used to adjust the control parameters in both proposed algorithms adaptively.

A series of feasibility experiments, including the instances used in [12], were carried out to identify the advantages of the proposed algorithms. Subsequently, the non-parametric tests were applied with a significance level of 5% to establish certain conclusions.

This research comprises the following sections: Section 2 formally defines the problem addressed. Section 3 describes the main components of the proposed algorithms. Section 4 and Section 5 describe the general structure of the MAIShOPwD and PSOIShOPwD algorithms. Section 6 describes the computational experiments carried out to validate the feasibility of the proposed algorithms. Section 7 presents the results obtained through the Wilcoxon and Friedman non-parametric tests. Moreover, Section 8 defines the conclusions obtained and potential areas for future work.

2. Definition of the Problem

The data set $N_j$ includes the available products in each store $j$. Each product $i$ is associated with a cost $c_{ij}$ and a shipping cost $d_i$. The shipping cost is added if the client purchases one or more items in the store $j$.

Formally, the problem considers that a client aims to purchase items from a specified set $N=(1,\dots ,n)$, in a set of online stores $M=(1,\dots ,m)$ with the lowest total cost, including a discount $f_k$, which is applicable in the calculation of the objective function. We calculate the objective value of the solution $I$ using Equation (1):

$$min f_k\left({\sum }_{j=1}^m{\sum }_{i=1\&\&I\left(i\right)=j}^n\left(d_i+c_{ij}\right)\right)$$

(1)

A candidate solution is represented by a vector $I$ of length $N$, which specifies the store from which each product should be purchased. A more detailed description can be found in the work of Błażewicz et al. [6].

Equation (2) below shows the criteria used to select the discount for the total cost of the shopping list for the function $f_k$.

$$f_k(x)\left\{\begin{array}{c}x if x\le 25,\\ 0.95x if 25<x\le 50,\\ 0.90x if 50<x\le 100,\\ 0.85x if 100<x\le 200,\\ 0.80x if 200<x\end{array}\right.$$

(2)

3. The General Structure of the Proposed Algorithms

This section describes all the main elements of the proposed solution methods, which are part of the following algorithms: the Memetic Algorithm (MAIShOPwD) and the particle swarm optimization algorithm (PSOIShOPwD).

3.1. Representation of a Candidate Solution

Related state-of-the-art works use a matrix representation of the candidate solutions such that the time complexity of evaluating the objective function for each candidate solution is $O\left(n^2\right)$. This work proposes using a vector representation to reference the solution proposed in [12], in which store $j$ is established and each product i must be purchased. Figure 1 shows the vector representation of a candidate solution.

3.2. Adaptive Parameter Adjustment

The two algorithms proposed in this paper use initial values in their parameters. Later, these values are adjusted based on specific actions taken during the search process. The work in [12] expands the description of the modified FRRMAB [14] method for adaptive tuning of control parameters.

3.2.1. Assignment of Credits

Fialho [15] recommends not using the reward value directly to prove fitness. Because this affects the algorithm’s robustness, the adaptive adjustment method of control uses Fitness Improvement Rates (FIRs) to avoid the problem, as indicated in Equation (3).

$$FI{R}_{i,t}={\displaystyle \frac{p{f}_{i,t}-c{f}_{i,t}}{p{f}_{i,t}}}$$

(3)

where

• ${pf}_{i,t}$ represents the fitness value of the parent.
• ${cf}_{i,t}$ represents the fitness value of the children.

Each $FIR$ value of the actions used is stored in a FIFO (first in, first out) structure of fixed size $W$. This setup enables the latest actions to be retained while the earliest ones are discarded within the sliding window, which stores the stock index and $FIR$ value.

Calculating the reward (${Reward}_i$) for each action, the cumulative sum of FIR values for each action within the sliding window is calculated. They are arranged in descending order based on the rank (${Rank}_i$) of each action i. Finally, a decay factor $D$ within the range of 0 to 1 is applied to modify the ${Reward}_i$ and this allows the best actions to be selected using Equation (4):

$$Deca{y}_i=D^{Ran{k}_i}\times Rewa{rd}_i$$

(4)

Next, each credit is allocated to action $i$ according to Equation (5).

$$FR{R}_{i,t}={\displaystyle \frac{Deca{y}_i}{{\sum }_{j=1}^{K}Deca{y}_j}}$$

(5)

As the decay factor $D$ decreases, the likelihood of selecting the best action increases. Algorithm 1 shows how credits are assigned to an action. The algorithm used is a modified version of the FRRMAB algorithm proposed by Li [14], which was initially used to perform adaptive selection of genetic operators (AOS) but has been adapted to perform adaptive selection of actions. First, the rewards for each operator (${Reward}_i$) are initialized to 0, and the application counter of each action ($n_i$) is also initialized to 0 (lines 1, 2). It is iterated through the sliding window (lines 3–8), which contains a fixed number of recent applications of the actions. For each entry in the window, the index of the action is obtained (line 4). Its corresponding fitness improvement rate (line 5), the improvement rate ($FIR$), is added to the total reward of the action (line 6), and the application counter of the action is incremented (line 7). Once the improvement rates have been added, all rewards are sorted in descending order (line 9). Based on this ranking, each action is given a rank value (${Rank}_i$). A decay factor ($D$) is applied to its reward for each action to adjust for the influence of better-performing actions (lines 10–12). The new adjusted reward (${Decay}_{action}$) is calculated by multiplying the trader’s rank by its total reward (line 11). Finally, the adjusted reward for each action is normalized (lines 14–16) to obtain the final credit value (${FRR}_{action}$), which is subsequently used in the trader selection process.

Algorithm 1. Credit allocation.

1: Initialize each reward $Rewar{d}_i=0$ 2: $\mathrm{Initialize}{n}_i=0;$ 3: $\mathit{f}\mathit{o}\mathit{r} i\leftarrow 1 \mathit{t}\mathit{o} \mathrm{S}\mathrm{l}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}.\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h} \mathit{d}\mathit{o}$ 4:         $action=\mathrm{S}\mathrm{l}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}.\mathrm{G}\mathrm{e}\mathrm{t}\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\left(i\right)$ 5:         $FIR=\mathrm{S}\mathrm{l}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}.\mathrm{G}\mathrm{e}\mathrm{t}\mathrm{F}\mathrm{I}\mathrm{R}\left(i\right)$ 6:         $Rewa{rd}_{action}=Rewar{d}_{action}+FIR$ 7:         $n_{action}++$ 8: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 9: $\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k} Rewar{d}_i \mathrm{i}\mathrm{n} \mathrm{d}\mathrm{e}\mathrm{s}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g} \mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r} \mathrm{a}\mathrm{n}\mathrm{d} \mathrm{s}\mathrm{e}\mathrm{t} Ran{k}_i \mathrm{t}\mathrm{o} \mathrm{b}\mathrm{e} \mathrm{t}\mathrm{h}\mathrm{e} \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} \mathrm{o}\mathrm{f} \mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n} i$ 10: $\mathit{f}\mathit{o}\mathit{r} action\leftarrow \mathit{t}\mathit{o} K \mathit{d}\mathit{o}$ 11:         $Deca{y}_{action}=D^{Ran{k}_{action}}\times Rewar{d}_{action}$ 12: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 13:         $DecaySum={\sum }_{action=1}^{K}Deca{y}_{action}$ 14: $\mathit{f}\mathit{o}\mathit{r} action\leftarrow \mathit{t}\mathit{o} K \mathit{d}\mathit{o}$ 15:         $FR{R}_{action}=Deca{y}_{action}/DecaySum$ 16: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$

3.2.2. Bandit-Based Action Selection

The bandit-based approach utilizes Fitness Rate Rank ($FRR$) values to assess quality for action selection, as depicted in Algorithm 2. Algorithm 2 is used for the action selection based on the multiarmed bandit approach [16] used in the FRRMAB algorithm [14]. The algorithm starts by checking if any actions still need to be selected. If so, one of these operators is chosen uniformly at random (lines 1–3). This mechanism ensures that the algorithm tries to use all possible actions at least once. Suppose all operators have already been selected at least once. In that case, the algorithm selects the operator that maximizes a function, combining the estimated quality of the operator ($FRR$) and further exploration based on the number of times that operator has been selected (line 4); $C$ is a factor that controls the balance between exploitation and exploration.

Algorithm 2. Bandit-based action selection.

1: $\mathit{i}\mathit{f} \mathrm{T}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e} \mathrm{a}\mathrm{r}\mathrm{e} \mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s} \mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t} \mathrm{h}\mathrm{a}\mathrm{v}\mathrm{e} \mathrm{n}\mathrm{o}\mathrm{t} \mathrm{b}\mathrm{e}\mathrm{e}\mathrm{n} \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d} \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 2:         ${action}_t=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{l}\mathrm{y} \mathrm{s}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t} \mathrm{a} \mathrm{s}\mathrm{e}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{y} \mathrm{f}\mathrm{r}\mathrm{o}\mathrm{m} \mathrm{t}\mathrm{h}\mathrm{e} \mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n} \mathrm{p}\mathrm{o}\mathrm{o}\mathrm{l}$ 3: $\mathit{e}\mathit{l}\mathit{s}\mathit{e}$ 4:         ${action}_t=\underset{i=\{1,\dots ,K\}}{\mathrm{argmax}}\left(FR{R}_{i,t}+C\times \sqrt{{\displaystyle \frac{2\times \mathrm{l}\mathrm{n}({\sum }_{j=1}^K{n}_{j,t})}{n_{i,t}}}}\right)$ 5: $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$

3.3. Actions Pool for the Memetic Algorithm

Below are the six adjustment actions for parameters crossover probability ($pc$) and mutation probability ($pm$) of the MAIShOPwD algorithm: Action 1 increases the values of the crossover and mutation probabilities by one ten-thousandth. Action 2 decreases the values of the crossover and mutation probabilities by one ten-thousandth. Action 3 increases the value of crossover probability by one ten-thousandth. Action 4 increases the value of the mutation probability by one ten-thousandth. Action 5 decreases the value of crossover probability by one ten-thousandth. Finally, action 6 decreases the value of the mutation probability by one ten-thousandth.

(1)

Action 1

$pc=pc+0.0001;$

$pm=pm+0.0001;$

(2)

Action 2

$pc=pc-0.0001;$

$pm=pm-0.0001;$

(3)

Action 3

$pc=pc+0.0001;$

(4)

Action 4

$pm=pm+0.0001;$

(5)

Action 5

$pc=pc-0.0001;$

(6)

Action 6

$pm=pm-0.0001;$

3.4. Actions Pool for the Particle Swarm Optimization Algorithm

Below are the six adjustment actions for the personal learning quotient ($c_1$) and global learning quotient ($c_2$) of the PSOIShOPwD algorithm: Action 1 increases the values of $c_1$ and $c_2$ by one ten-thousandth. Action 2 decreases the values of $c_1$ and $c_2$ by one ten-thousandth. Action 3 increases the value of $c_1$ by one ten-thousandth. Action 4 increases the value of $c_2$ by one ten-thousandth. Action 5 decreases the value of $c_1$ by one ten-thousandth. Finally, action 6 decreases the value of $c_2$ by one ten-thousandth.

(1)

Action 1

$c_1=c_1+0.0001;$

$c_2=c_2+0.0001;$

(2)

Action 2

$c_1=c_1-0.0001;$

$c_2=c_2-0.0001;$

(3)

Action 3

$c_1=c_1+0.0001;$

(4)

Action 4

$c_2=c_2+0.0001;$

(5)

Action 5

$c_1=c_1-0.0001;$

(6)

Action 6

$c_2=c_2-0.0001;$

4. The General Structure of the Memetic Algorithm

Huacuja [12] introduced a Memetic Algorithm to tackle the IShOP with shipping costs. The results obtained by the Memetic Algorithm demonstrate that it could feasibly be used to solve other variants related to IShOP. Considering this contribution as a feasible solution method, the decision was made to improve the local search to allow a significant reduction in the quality and efficiency of the results for the IShOPwD. Additionally, a mechanism that allows adaptive adjustment of some control parameters was added, considering the contribution of García-Morales [17].

4.1. Used Heuristics

The heuristics used to generate candidate solutions are described below. They are called best first and best [12]. These heuristics identify the store where a product can be purchased at the lowest cost, considering the discount associated with the total cost of the shipping list. If more detailed information on the operation of these heuristics is required, please consult the work conducted in [12].

4.1.1. Heuristic: Best First

The best first heuristic changes the stores assigned to a solution vector until the first cost improvement associated with the current product is found. This process is repeated for all products in the shopping list. This heuristic has a time complexity of $O\left(nm\right)$ [12].

4.1.2. Heuristic: The Best

The best heuristic works the same as the best first heuristic. The difference is mainly that this heuristic continues when it finds the first improvement in the cost of each product but continues to search all stores for the lowest cost for each product. The process concludes when all stores have been checked for all products in the solution vector. This process is applied to all products. The best heuristic has a complexity of $O\left(nm\right)$ [12].

4.2. Binary Tournament

A certain number of individuals are randomly selected from the population, and the fittest advance to the next generation. Each individual participates in two comparisons, and the winning individuals form a new population; this ensures that any individual in the population has a maximum of two copies in the new population. A more extensive description of the binary tournament can be found in [12].

4.3. Crossover Mechanism

The crossover mechanism is applied to a certain percentage of the individuals sequentially. This operator selects two solution vectors called parent one and parent two. Both parent vectors are divided in half to generate two children. The first offspring is created by combining the first half of parent 1 with the second half of parent 2. The second offspring is formed by merging the first half of parent 2 with the second half of parent 1.

4.4. Mutation Operator

This operator selects a percentage of elite solutions from the population. Subsequently, it goes through each elite solution and generates a random number. If the value of the mutation probability parameter is less than the heuristic mutation process, the heuristic mutation process will be applied to each selected elite solution. Detailed information on the mutation heuristic can be found in [12].

4.5. Improved Local Search

The local search algorithm improves a given vector solution, reducing the total cost. To achieve this goal, we change the assigned store for each product, reducing the solution’s total cost. This procedure improves a given solution, and speeding up the local search algorithm is costly. This procedure was modified to reduce the computational costs and determine the change in the objective value of the current solution. $\mathrm{L}\mathrm{e}\mathrm{t} I=(j_1,j_2,j_3,\dots ,j_n)$ be the current solution and $I’={j^{\prime }}_1,j_2,j_3,\dots ,j_n)$ be the solution we obtain when the store one should buy the product from changes from $j_1$ to ${j^{\prime }}_1$. The change in the objective values of the current solution is given by $\delta =F\left(I^{\prime }\right)-F\left(I\right)$. If this is directly realized using Equation 1, the computational complexity required to determine $\delta$ is $O\left(nm\right)$. The following equation shows how to calculate $\delta$ in $O\left(1\right)$.

Theorem 1. 

$\delta =(d_{{j\prime }_1}+c_{1{j\prime }_1})-(d_{j_1}+c_{1j_1})$.

Proof. 

Let $I=(j_1,j_2,j_3,\dots ,j_n)$ the current solution and $I\prime =({j\prime }_1,j_2,j_3,\dots ,j_n)$ the solution that we obtain when the store one should buy the product from changes from $j_1$ to ${j\prime }_1$.

Then, using Equation (6):

$$F\left(I\right)={\sum }_{i=1}^n{\sum }_{\forall j |I\left(j\right)=i}\left(d_j+c_{ij}\right)=(d_{j_1}+c_{1j_1})+{\sum }_{i=2}^n{\sum }_{\forall j |I\left(j\right)=i}\left(d_j+c_{ij}\right)$$

(6)

$$F(I\prime )={\sum }_{i=1}^n{\sum }_{\forall j |I\prime \left(j\right)=i}\left(d_j+c_{ij}\right)=(d_{{j\prime }_1}+c_{1{j\prime }_1})+{\sum }_{i=2}^n{\sum }_{\forall j |I\prime \left(j\right)=i}\left(d_j+c_{ij}\right)$$

(7)

Therefore, $\delta$ = $F(I\prime )-F(I)=(d_{{j\prime }_1}+c_{1{j\prime }_1})-(d_{j_1}+c_{1j_1})$. □

The local search tries to improve the current solution by changing the stores assigned to the products. For each product, the store that produces the maximal reduction in the objective value is identified. To determine if a change in the store assigned to the product produces a reduction or not, Theorem 1 is applied again in the search process. For this reason, these results significantly impact the local search performance.

4.6. Proposed Memetic Algorithm

Algorithm 3 shows the structure of the proposed MAISHOPwD algorithm. In steps 1 and 2, the values of the initial parameters are defined, and the instance to be used is loaded. From steps 3 to 7, an initial population is generated, the objective value and discount for the entire population are calculated, and the best local and global solution can be identified. In step 9, the binary tournament is applied to the population, and a new population will be generated based on the results obtained. In step 10, a percentage of elite solutions are moved from the new population to an intermediate population. In step 11, the crossover operator affects the new population, and the missing elements of the intermediate population are generated. In steps 12 and 13, the mutation operator and the improved local search are applied to the intermediate population to obtain a population of children. In step 15, the local solution is checked to determine if it is better than the global solution; if so, the global solution is updated. In steps 16 and 17, the entire population is reset, the best global solution is inserted, and all other individuals in the population will be ruled out. In steps 18,19 and 20, the sliding window is updated, and the rewards of the adaptive control parameter adjustment method are ranked. In step 21, the process of each iteration ends, and finally, in step 22, the best solution and the global cost are obtained.

Algorithm 3. MAIShOPwD Algorithm.

Input: $MaxIter$: Maximum number of iterations Instance: m (stores), n (products), cij (product cost), dj (shipping cost) Parameters/Variables$: ps$: initial population size $pc$: crossover probability $pm$: mutation probability $er$: rate elitism $pop$: Initial population BestGlobalSolution, BestGlobalCost: Best overall solution and cost BestLocalSolution, BestLocalCost: Best solution and cost in each generation Functions: BestGlobal(pop, BestGlobalSolution, BestGlobalCost): from pop obtain the BestGlobalSolution and the BestGlobalCost $CrossoverOperator(NewPop,IntermediatePop)$$: \mathrm{among} \mathrm{non}-\mathrm{elite} \mathrm{individuals} \mathrm{in} NewPop$$, \mathrm{the} \mathrm{crossover} \mathrm{operator} \mathrm{is} \mathrm{applied} \mathrm{to} \mathrm{randomly} \mathrm{selected} ps\ast pc$$\mathrm{solutions} \mathrm{and} \mathrm{the} \mathrm{remaining} \mathrm{solutions} \mathrm{are} \mathrm{copied} \mathrm{as}-\mathrm{is} \mathrm{to} IntermediatePop$ $MutationOperator(IntermediatePop, ChildPop)$$: \mathrm{with} \mathrm{probability} pm$, apply the mutation operator to all the solutions in the intermediate population and move the offspring to the population of children $ImprovedLocalSearch(IntermediatePop, ChildPop)$: apply improved LocalSearch to all solutions in IntermediatePop and move the offspring to ChildPop $BestLocal(ChildPop, BestLocalSolution,BestLocalCost)$: obtain the BestLocalSolution and the BestLocalCost in ChildPop $ObjectiveFunction( )$: calculate the objective value $Discount\left(ObjectiveFunction\right( \left)\right)$: apply the discount to the objective value $FRRMAB( )$: obtains the index for executing an action $ExecuteAction\left(indexaction\right)$: performs an action based on an index $SlidingWindow(indexaction,improvement[i\left]\right)$: a sliding window that stores both the frecuency of action execution and the decrease in individual costs $UpgradeRewards\left(SlidingWindow\right)$: enhance the rewards held within the sliding window Output: $BestGlobalSolution$: Best overall solution $BestGlobalCost:$ Best overall cost

$1: \mathrm{Set} \mathrm{initial} \mathrm{parameters}: \mathrm{population} \mathrm{size} \left(ps\right)$$, \mathrm{percentage} \mathrm{of} \mathrm{cross} \left(pc\right)$$, \mathrm{probability} \mathrm{of} \mathrm{mutation} \left(pm\right)$$, \mathrm{Rate} \mathrm{elitism} \left(er\right)$

2:          Load Instance

$3: \mathrm{Randomly} \mathrm{generate} \mathrm{initial} \mathrm{population} \mathrm{of} \mathrm{size} ps$ $4: ObjectiveFunction\left(pop\right)$ $5: Discount\left(ObjectiveFunction\right(pop\left)\right)$

6:         BestGlobal(pop, BestGlobalSolution, BestGlobalCost)

7:         BestLocalSolution = BestGlobalSolution; BestLocalCost = BestGlobalCost;

$8: \mathit{while} (not MaxIter)$ do $9: \mathrm{Apply} \mathrm{binary} \mathrm{tournament} \mathrm{in} pop$$\mathrm{to} \mathrm{get} NewPop$

10:                        Move from NewPop to IntermediatePop the elite solutions

$11: CrossoverOperator(NewPop,IntermediatePop)$

$12: MutationOperator(IntermediatePop,ChildPop)$

$13: ImprovedLocalSearch (IntermediatePop, ChildPop)$

$14: BestLocal(ChildPop, BestLocalSolution,BestLocalCost$

$15: \mathbf{if} BestLocalCost$$< BestGlobalCost$ then {BestGlobalCost = BestLocalCost; BestGloblalSolution = BestLocalSolution}

$16: \mathit{pop}=\varphi$$; \mathit{pop}=\mathit{pop} \cup${BestGlobalSolution}

17:                         Randomly generate ps − 1 solutions and add each solution to pop

$18: \mathrm{Add} \mathrm{to} SlidingWindow(indexaction,improvement[i\left]\right)$

$19: UpgradeRewards\left(SlindingWindow\right)$

20:                         Rank Rewards

21:        end while

$22: \mathbf{return} (BestGlobalSolution,BestGlobalCost$)

5. Overview of the Particle Swarm Optimization Algorithm Structure

This section describes the second proposed solution method for the IShOPwD. This method utilizes the PSOIShOPwD algorithm. In this algorithm, two strategies are considered to avoid premature convergence [18]: the first corresponds to the diversification of neighborhoods [13], and the second is an improved local search; both strategies are executed only once per iteration to prevent excessive execution time consumption.

In addition, this proposed algorithm incorporates the adaptive adjustment of control parameters using an adaptation of the FRRMAB method [14].

5.1. Neighborhood Diversification Technique

The diversification technique runs through each particle position in the population [18]. For each position in a particle, it generates a random value $r$ from the interval $[1, M]$. Then, it adjusts the value of the current position based on the following criteria: if the particle’s position is even, the operation subtracts the sum of the best position of the current particle and a random value $r$ from the total number of stores, $M$. If the previous condition is not satisfied, then $M$ is reduced by the difference between the best position of the current particle and the random $r$. Subsequently, the algorithm checks for compliance with minimum and maximum position constraints. Following this, it computes the objective value of the modified particle and assesses if there has been an improvement in its best cost; if so, the best overall particle is modified. The described process concludes once the entire population has been modified and evaluated. The process is detailed in Algorithm 4.

Algorithm 4. Neighborhood diversification technique.

Inputs: Population of solutions Outputs: Updated Population. Variables: $particles$: Population $particles.size$: Population size $N$: Number of products $M$: Number of stores Functions: $random\_number [1,M]:$ Generates a random number in the range [1, $M$]. $ObjectiveFunction\left(particle{s}_i\right):$ Calculate objective value of the particle. $Max\left(particle{s}_i.position\left[j\right],1\right):$ Calculates the maximum value between the $j$ position of a particle and 1. $Min\left(particle{s}_i.position\left[j\right], M\right):$ Calculates the minimum value between the position $j$ of a particle and $M$. $Discount\left(ObjectiveFunction\right( \left)\right)$: Apply the discount to the objective value 1: $\mathit{f}\mathit{o}\mathit{r} i=1 \mathit{t}\mathit{o} Particles.size \mathit{d}\mathit{o}$ 2: $r=random\_number [1,M]$ 3:        $\mathit{f}\mathit{o}\mathit{r} j=1 \mathit{t}\mathit{o} N \mathit{d}\mathit{o}$ 4:               $\mathit{i}\mathit{f} i \% 2==0 \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 5:                         $particle{s}_i.Position\left[j\right]=M-(particle{s}_i.BestPosition[j]+r)$ 6:                         $particle{s}_i.position\left[j\right]=Max\left(particle{s}_i.position\left[j\right],1\right)$ 7:                         $particle{s}_i.position\left[j\right]=Min\left(particle{s}_i.position\left[j\right],M\right)$ 8:               $\mathit{e}\mathit{l}\mathit{s}\mathit{e}$ 9:                         $particle{s}_i.Position\left[j\right]=M-(particle{s}_i.BestPosition\left[j\right]-r)$ 10:                       $particle{s}_i.position\left[j\right]=Max\left(particle{s}_i.position\left[j\right],1\right)$ 11:                       $particle{s}_i.position\left[j\right]=Min\left(particle{s}_i.position\left[j\right],M\right)$ 12:               $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 13:        $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 14:      $Discount\left(ObjectiveFunction\left(particle{s}_i\right)\right)$ 15:      $\mathit{i}\mathit{f} particle{s}_i.Cost<particle{s}_i.bestCost \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 16:            $particle{s}_i.bestPosition=particle{s}_i.position$ 17:            $particle{s}_i.bestCost=particle{s}_i.cost$ 18:            $\mathit{i}\mathit{f} particle{s}_i.bestCost<GlobalBest.cost \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 19:               $GlobalBest=particle{s}_i$ 20:            $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 21:      $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 22:    $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 23: $\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} Particles$

5.2. Local Search

The local search aims to improve the best global particle [18]. The process consists of modifying the particle’s positions and evaluating whether the modifications reduce the particle’s overall cost. This process is repeated in all positions of the particle. Finally, the total cost of the updated particle is calculated and compared with the best cost of the global particle. The newly updated particle will replace the best global particle if the cost is lower than the global particle. The process is detailed in Algorithm 5.

Algorithm 5. Local Search.

Inputs: Best Global solution Outputs: Best Global Solution Updated. Variables: $N$: Number of products $M$: Number of stores $Cost$: Objective value cost Functions: $ObjectiveFunction\left(GlobalBest\right):$ Calculate objective value of the Global Best $Discount\left(ObjectiveFunction\right( \left)\right)$: apply the discount to the objective value 1. $Cost=Discount\left(ObjectiveFunction\left(GlobalBest\right)\right)$ 2. $\mathit{f}\mathit{o}\mathit{r} i=1 \mathit{t}\mathit{o} N \mathit{d}\mathit{o}$ 3.               $\mathit{f}\mathit{o}\mathit{r} j=1 \mathit{t}\mathit{o} M \mathit{d}\mathit{o}$ 4.                   $GlobalBest.Position\left[i\right]=j$ 5.                   $\mathit{i}\mathit{f} Discount\left(ObjectiveFunction\left(GlobalBest\right)\right)<Cost \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 6.                       $Cost=Discount\left(ObjectiveFunction\right(GlobalBest)$) 7.                       $j^{\prime }=j$ 8.                   $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 9.               $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 10.      $GlobalBest.Position\left[i\right]=j\prime$ 11.     $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 12. $Discount\left(Objectivefunction\left(GlobalBest\right)\right)$ 13. $\mathit{i}\mathit{f} \left(GlobalBest.Cost<GlobalBest.bestCost\right) \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 14.           $GlobalBest.bestPosition=GlobalBest.Position$ 15.           $GlobalBest.bestCost=GlobalBest.Cost$ 16. $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 17. $\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} GlobalBest$

5.3. Proposed Particle Swarm Optimization Algorithm (PSOIShOPwD)

Algorithm 6 outlines the fundamental framework of the proposed PSOIShOPwD algorithm. In steps 1 to 4, the initial values of the parameters are defined, a random population of particles is generated, the overall best particle is obtained, and the minimum and maximum particle velocities are calculated. In steps 7 and 8, the algorithm retrieves the index linked to an action and executes that action to adjust the values $c_1$ and $c_2$. From steps 10 to 15, the algorithm adjusts the position and velocity of each particle, ensuring they remain within the permissible range; otherwise, a corrective method is applied. In steps 17, 18, and 19, the algorithm calculates the objective value, applies the discount to each particle, and determines the cost improvement of each particle relative to its best cost. From steps 20 to 27, the algorithm assigns the previously computed objective value to an improvement vector. It then compares the best position of the current particle with the global particle; if it is superior, the global particle’s objective value is replaced with it. In step 28, the sliding window is updated with the action index and the particle cost improvement. In steps 29 and 30, the sliding window rewards are updated, and descending order is applied. In steps 32 and 33, diversification and a local search are applied. Finally, in steps 34 and 35, the inertial weight ($w$) is updated, and the best global solution is obtained.

Algorithm 6. PSOIShOPwD Algorithm.

Inputs: Population. Outputs:  Global Best Solution. Variables/Parameters: $particles$: Population $particles.size$: Population size $N$: Number of products $M$: Number of stores $MaxIt$: Maximum number of iterations $w$: Inertial weight $wdamp$: Inertial weight damping radius $c_1$: Personal learning quotient $c_2$: Global learning quotient $GlobalBest$: Global Best Solution Functions: $random\_number[0,M]:$ Generates a Random number in the range [1, $M]$. $ObjectiveFunction\left(particle{s}_i\right):$ Calculate the objective value of a particle $Max\left(particle{s}_i.{position}_j,1\right):$ Calculates the maximum value between the $j$ position of a particle and 1. $Min\left(particle{s}_i.{position}_j,M\right):$ Calculates the minimum value between the $j$ position of a particle and $M$. $NDT\left(particles\right):$ Applies the neighborhood diversification technique to all particles. $LS\left(GlobalBest\right):$ Apply local search to the best global solution. $FRRMAB\left(\right)$: Gets an index of an action to perform. $executeAction\left(actionIndex\right)$: Execute an action according to an index. $SlidingWindow(actionIndex,improvement[i\left]\right)$: Sliding window that stores the index of action to be performed and the improvement in the cost of the particle. $UpgradeRewards\left(SlidingWindow\right)$: Update the sliding window rewards. $Discount\left(ObjectiveFunction\left(particle{s}_i\right)\right):$ Apply the assigned discount to the total cost of the purchase. 1: Initialize parameters $MaxIt,Particles.size,w,wdamp,c_1,c_2,N,M$. 2: $particles=GeneratePopulation(Particles.size)$ 3: $GlobalBest=getBestGlobal\left(particles\right)$ 4: $velMax=0.2\ast M,velMin=-velMax$ 5: $\mathit{f}\mathit{o}\mathit{r} it=1 \mathit{t}\mathit{o} MaxIt \mathit{d}\mathit{o}$ 6:     $\mathit{f}\mathit{o}\mathit{r} i=1 \mathit{t}\mathit{o} nPop \mathit{d}\mathit{o}$ 7:           $actionIndex=FRRMAB\left(\right)$ 8:           $executeAction\left(actionIndex\right)$ 9:        $\mathit{f}\mathit{o}\mathit{r} j=1 \mathit{t}\mathit{o} d \mathit{d}\mathit{o}$ 10:     $particle{s}_i=w\times particle{s}_i.velocit{y}_j+c1\times random\_number[0,1]\times \left(particle{s}_i.bestPositio{n}_j-particle{s}_i.positio{n}_j\right)+c2\times random\_number[0,1]\times \left(GlobalBest.positio{n}_j-particle{s}_i.positio{n}_j\right);$ 11:             $particle{s}_i.velocit{y}_j=Max\left(particle{s}_i.velocit{y}_j,velMin\right);$ 12:             $particle{s}_i.velocit{y}_j=Min\left(particle{s}_i.velocit{y}_j,velMax\right);$ 13:             $particle{s}_i.positio{n}_j=particle{s}_i.posicion+particle{s}_i.velocit{y}_j;$ 14:             $particle{s}_i.positio{n}_j=Max\left(particle{s}_i.positio{n}_j,1\right);$ 15:             $particle{s}_i.positio{n}_j=Min\left(particle{s}_i.positio{n}_j,M\right);$ 16:        $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 17:        $Objectivefunction(particle{s}_i$) 18:        $Discount\left(Objectivefunction\left(particle{s}_i\right)\right)$ 19:        $fitnessimprovement=(particle{s}_i.bestCost-particle{s}_i.cost)/particles\_i.bestCost$ 20:        $\mathit{i}\mathit{f} particle{s}_i.cost<particle{s}_i.bestCost \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 21:             $improvement\left[i\right]=fitnessimprovement$ 22:             $particle{s}_i.bestPosition=particles{s}_i.position$ 23:             $particle{s}_i.bestCost=particle{s}_i.cost$ 24:             $\mathit{i}\mathit{f} particle{s}_i.bestCost<GlobalBest.cost \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 25:                 $GlobalBest=particle{s}_i$ 26:             $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 27:        $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 28:        Add to $SlidingWindow(actionIndex,improvement[i\left]\right)$ 29:        $Upgrade\_Rewards\left(SlidingWindow\right)$ 30:        Rank Rewards 31:     $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 32:   $NDT\left(particles\right)$ 33:   $LS\left(GlobalBest\right)$ 34:    $w=w\ast wdamp$ 35: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 36: $return GlobalBest$

6. Computational Experiments

The proposed algorithms are validated using the same instances created in [12], which are presented in

Table 1. Configuration of instance size.

Small Instances	Medium Instances	Large Instances
$3n20m$	$5n240m$	$50n400m$
$4n20m$	$5n400m$	$100n240m$
$5n20m$	$50n240m$	$100n400m$

. This table displays the subgroup sizes of instances used in the computational experiments. Each instance name indicates the number of products denoted by $n$ and the number of stores denoted by $m$. Each algorithm was executed independently 30 times, and the averages of their 30 medians were calculated for the objective value ($OV$) and time execution ($Time$). The time used by the algorithms is measured in milliseconds.

Table 2. Variables and parameters of the proposed algorithms.

Variables/Parameters	MAIShOPwD	PSOIShOPwD
$population.size$	100	100
$pc$	0.6 *	0.6
$pm$	0.01 *	0.01
$er$	0.05
$wdamp$		0.99
$MaxIt$	100	100
$w$		1
$c_1,c_2$		1.5, 2 *

* Start values.

shows the assigned values of variables and parameters utilized in the computational experiments for each analyzed algorithm. These assigned initial values were taken from the state-of-the-art works of Huacuja [12] and García-Morales [18], in which different values for the corresponding parameters were analyzed.

7. Results

Table 3. Comparative performance of BB vs. MAIShOPwD algorithms applying the Wilcoxon test.

Instances	BB	MAIShOPwD	BB	MAIShOPwD	p-Value (OV)	p-Value (Time)
	$\mathit{O}\mathit{V}$	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$
$3n20m$	56.560.04$=$	56.560	0.0846.2×10−5$\uparrow$	1.2222 × 10−50.05	0.625	0.00001
$4n20m$	70.680.21$=$	70.680	0.0484.3×10−5$\uparrow$	6.6667 × 10−60.007	0.625	0.00001
$5n20m$	89.160.62$=$	89.040.004	0.0400.0002$\uparrow$	0.00020.029	0.625	0.00001
$5n240m$	75.701.94$\uparrow$	67.681.67	0.0671.76$\downarrow$	0.2740.1	0.00001	0.00001
$5n400m$	70.562.44$\uparrow$	62.661.68	0.2430.288$\downarrow$	0.7900.2	0.00001	0.00001
$50n240m$	503.4912.83$\uparrow$	434.2917.60	22.507.50$\uparrow$	16.4448.03	0.00001	0.00001
$50n400m$	433.619.78$\uparrow$	389.1424.08	33.1140.10$\downarrow$	48.66125.30	0.00148	0.00001
$100n240m$	992.7215.32$\uparrow$	757.2938.25	50.4939.76$\downarrow$	73.85725.64	0.00001	0.00001
$100n400m$	796.8714.15$\uparrow$	655.7235.04	176.1192.54$=$	181.95295.30	0.00001	0.3843
Total average	343.261	287.007	31.41	35.775

,

Table 4. Comparative performance of BB vs. PSOIShOPwD algorithms applying the Wilcoxon test.

Instances	BB	PSOIShOPwD	BB	PSOIShOPwD	p-Value (OV)	p-Value (Time)
	$\mathit{O}\mathit{V}$	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$
$3n20m$	${56.56}_{0.04}=$	56.640	0.0846.2×10−5$\uparrow$	0.010406.1×10−5	0.625	0.00001
$4n20m$	70.680.21$=$	70.760	0.0484.3×10−5$\uparrow$	0.01030	0.625	0.00001
$5n20m$	89.160.62$=$	89.213.3726×10−14	0.0400.0002$\uparrow$	0.0086.6944×10−5	0.625	0.00001
$5n240m$	75.701.94$\uparrow$	68.212.674×10−14	0.0671.76$\uparrow$	0.01045.85×10−18	0.00001	0.00001
$5n400m$	70.562.44$\uparrow$	64.192.529×10−14	0.2430.288$\uparrow$	0.01105.403×10−18	0.00001	0.00001
$50n240m$	503.4912.83$\uparrow$	463.5212.83	22.507.50$=$	24.554110.18	0.00001	0.24604
$50n400m$	433.619.78$\uparrow$	355.971.3876×10−13	33.1140.10$\uparrow$	0.08942.21×10−7	0.00001	0.00001
$100n240m$	992.7215.32$\uparrow$	712.792.3897×10−13	50.4939.76$\uparrow$	0.0923.1759×10−17	0.00001	0.00001
$100n400m$	796.8714.15$\uparrow$	605.632.0428×10−13	176.1192.54$\uparrow$	0.123964.1404×10−17	0.00001	0.00001
Total average	343.26	276.32	31.41	2.768

and

Table 5. Comparative performance of MAIShOPwD vs. PSOIShOPwD algorithms applying the Wilcoxon test.

Instances	MAIShOPwD	PSOIShOPwD	MAIShOPwD	PSOIShOPwD	p-Value (OV)	p-Value (Time)
	$\mathit{O}\mathit{V}$	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$
$3n20m$	56.560$=$	56.640	1.2222 × 10−50.05	0.01046.1×10−5	0.625	0.00001
$4n20m$	70.680$=$	70.760	6.6667 × 10−60.007	0.01030	0.625	0.00001
$5n20m$	${89.04}_{0.004}=$	89.213.3726×10−14	0.00020.029	0.0086.6944×10−5	0.625	0.00001
$5n240m$	${67.68}_{1.67}\downarrow$	68.212.674×10−14	0.2740.1	0.01045.85×10−18	0.00001	0.00001
$5n400m$	${62.66}_{1.68}\downarrow$	64.192.529×10−14	0.7900.2	0.01105.403×10−18	0.00001	0.00001
$50n240m$	${434.29}_{17.60}\downarrow$	463.5212.83	16.4448.03	24.554110.18	0.00001	0.00016
$50n400m$	389.1424.08$\uparrow$	355.971.3876×10−13	48.66125.30	0.08942.21×10−7	0.00001	0.00001
$100n240m$	757.2938.25$\uparrow$	712.792.3897×10−13	73.85725.64	0.0923.1759×10−17	0.00001	0.00001
$100n400m$	655.7235.04$\uparrow$	605.632.0428×10−13	181.95295.30	0.123964.1404×10−17	0.00001	0.00001
Total average	287.007	276.32	37.775	2.7678

show the outcomes obtained from the computational experiments carried out, and subsequently, the non-parametric Wilcoxon test is applied with a significance level of 5%. For each table, the first column corresponds to the evaluated instance. The second and fourth columns show the $OV$ and the $Time$ achieved by the reference algorithm and, as a subindex, the standard deviation. Correspondingly, the third and fifth columns show these values for the comparison algorithm. Columns six and seven, however, represent the $p-value$ obtained by the Wilcoxon test for the objective value and shortest time, respectively. The cells shaded in gray represent the lowest $OV$ or the shortest time when the best solution is found according to each column. The symbol ↑ indicates a significant difference in favor of the reference algorithm. The symbol ↓ indicates a significant difference in favor of the comparison algorithm, and the symbol = indicates no significant differences.

Based on the Wilcoxon test results, Table 3 illustrates that the proposed MAIShOPwD algorithm outperforms the state-of-the-art algorithm regarding the objective value in six out of nine instances. Regarding the shortest time metric, the MAIShOP algorithm performs better in four out of nine instances evaluated.

The results obtained by the Wilcoxon test shown in Table 4 indicate that the proposed PSOIShOPwD algorithm outperforms the state-of-the-art algorithm in six out of nine instances when evaluating the objective value. Regarding the shortest time metric, this algorithm outperforms the others in eight out of nine instances.

The results obtained by the Wilcoxon test shown in Table 5 indicate that the two proposed algorithms perform similarly to the objective value, since the MAIShOPwD algorithm performs better in medium instances. In contrast, the PSOIShOPwD algorithm performs better in large instances.

Table 6. Comparative performance of the BB vs. MAIShOPwD vs. PSOIShOPwD algorithms applying the Friedman test.

Instances	BB		MAIShOPwD		PSOIShOPwD		p-Value (OV)	p-Value (Time)
	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$	$\mathit{O}\mathit{V}$	$\mathit{T}\mathit{i}\mathit{m}\mathit{e}$
$3n20m$	56.560.04$=$	0.0846.2×10−5$\downarrow$	56.560	1.2222 × 10−50.05	56.640	0.01046.1×10−5	0.97531	0.00001
$4n20m$	70.680.21$=$	0.0484.3×10−5$\downarrow$	70.680	6.6667 × 10−60.007	70.760	0.01030	0.97531	0.00001
$5n20m$	89.160.62$=$	0.0400.0002$\downarrow$	89.040.004	0.00020.029	89.213.3726×10−14	0.0086.6944×10−5	0.97531	0.00001
$5n240m$	75.701.94$\downarrow$	0.0671.76$\downarrow$	67.681.67	0.2740.1	68.212.674×10−14	0.01045.85×10−18	0.00001	0.00001
$5n400m$	70.562.44$\downarrow$	0.2430.288$\downarrow$	62.661.68	0.7900.2	64.192.529×10−14	0.01105.403×10−18	0.00001	0.00001
$50n240m$	503.4912.83$\downarrow$	22.507.50$\downarrow$	434.2917.60	16.4448.03	463.5212.83	24.554110.18	0.00001	0.00001
$50n400m$	433.619.78$\downarrow$	33.1140.10$\downarrow$	389.1424.08	48.66125.30	355.971.3876×10−13	0.08942.21×10−7	0.00001	0.00001
$100n240m$	992.7215.32$\downarrow$	50.4939.76$\downarrow$	757.2938.25	73.85725.64	712.792.3897×10−13	0.0923.1759×10−17	0.00001	0.00001
$100n400m$	796.8714.15$\downarrow$	176.1192.54$\downarrow$	655.7235.04	181.95295.30	605.632.0428×10−13	0.123964.1404×10−17	0.00001	0.00001
Total average	343.261	31.41	287.007	35.775	276.32	2.768

contains the results obtained from the evaluation of the Friedman test at a 5% significance level; the first column lists the instances, while the second and third columns show the results for the $OV$ and the $Time$ achieved by the state-of-the-art algorithm. The fourth and fifth columns present equivalent data but for the MAIShOP algorithm. The sixth and seventh columns display results similar to those in the second and third columns, but specifically for the PSOIShOPwD algorithm. The last two columns contain the results of the $p$-value for each instance evaluated by the Friedman test.

The results obtained by the Friedman test indicate that in small instances concerning the objective value, the performances of the three algorithms are the same. For medium-sized instances, the algorithm that performs the best is MAIShOPwD. In the case of large instances, the best algorithm is PSOIShOPwD. The time analysis reveals that the two proposed algorithms outperform the state-of-the-art algorithm.

8. Conclusions and Future Work

This research addresses the IShOPwD, a variant of the IShOP that has become very relevant for buyers in the current electronic commerce scenario because online stores offer endless benefits for customers acquiring their products. This variant allows us to identify the most economical cost of a shopping list, considering a discount associated with the total cost. In this article, two main metaheuristic algorithms that have not yet been considered are proposed to solve IShOPwD. The first is a MAIShOPwD algorithm that incorporates an improved local search that contains a method used to calculate the change in the objective value of the current solution with a time complexity of $O\left(1\right)$, thus avoiding excessive expenditure of computing time and adaptive adjustment of control parameters that, during the execution of the algorithm, adjust the best values of the crossover and mutation probability. The second is a PSOIShOPwD algorithm that, unlike the state-of-the-art algorithms, also uses a vector representation of the candidate solutions. It includes neighborhood diversification to avoid local stagnation of the algorithm and incorporates the adaptive adjustment of control parameters that directly benefit the personal and global learning parameters. These parameters allow better positioning of the particles in the search space. The proposed algorithms are validated using the non-parametric Wilcoxon and Friedman tests, which were utilized to assess the results obtained from both the proposed algorithms and the state-of-the-art BB. According to the results obtained in the Wilcoxon test, the MAIShOPwD algorithm achieves a better performance compared to the BB; however, in inefficiency, the BB is better, and in the case of the PSOIShOPwD algorithm, it is better in terms of both quality and efficiency compared to the BB. This same test concludes that the two proposed algorithms have similar performance. The Friedman test indicates that the two proposed algorithms exhibit superior performances in both quality and efficiency when compared to the state-of-the-art algorithm.

Finally, in future work related to the IShOPwD variant, all the control parameters used by the algorithms could be incorporated into the adaptive adjustment, adding the restriction of being able to purchase more than one product of the same type and being able to use other types of discount such as coupons and lightning offers.