Asymptotic analysis of endemic equilibrium to a brucellosis model

1.   Introduction

The winner determination problem (WDP) in combinatorial auction aims to determine a bid-winning scheme according to the combination of items submitted by various bidders as well as their bids. The object of WDP is to maximize the revenue of auctioneers, where the revenue is measured by the total price of the selected bids. Compared with traditional auction mechanisms, WDP can improve the efficiency of the auction process and reduce the number of failure bids ^[1]. WDP is widely used in cloud computing ^[2], online reverse auctions ^[3,4], spectrum license sales by America's Federal Communications Commission (FCC)^*, e-commerce ^[5], wireless network ^[6], production management ^[7], game theory ^[8], and multi-agent system resource allocation ^[9,10], etc. Solving the winner determination problem effectively can improve the utilization of items, which is conducive to sustainable development. However, the process of determining the winning criterion is NP-hard problem ^[11]. How to solve WDP effectively has become a hot topic in the field of combinatorial optimization.

^*http://wireless.fcc.gov/auctions

Nowadays, the memetic algorithm which integrates the population-based method and the heuristic or meta-heuristic method performs well on many combinatorial optimization problems ^{[12,13,14,15]}. The population-based methods, which can expand the search space of the problem, include genetic algorithm ^[16], ant colony algorithm ^[17], bee colony algorithm colony ^[18], and so on.

Among the population-based methods, the ant colony algorithm (ACO), which uses the pheromone model and heuristic information of the problem to construct solutions in a probabilistic way ^[19]. Pheromone trails are the result of a learning mechanism that tries to identify the solution components that, when appropriately combined, lead to high-quality solutions. However, as well known, ACO and other population-based methods have strong robustness, but its convergence speed is slow and is easy to fall into the local optima.

Therefore, in many combinatorial problems, the heuristic or meta-heuristic methods are essential for obtaining competitive solutions, which can be used to prevent the search from premature convergence, including local search ^[20], tabu search ^[21], and simulated annealing ^[22], etc. Tabu search (TS) is a widely studied heuristic method for its distinguishing features of adaptive memory and responsive exploration ^[23]. This method maintains a short-term memory of the specific changes in some recent moves within the search space, and prevent future moves from undoing those changes. Due to its capacity of searching effectively, TS has been applied to solve various combinatorial problems, such as minimum weight vertex independent dominating set problem ^[24], the multi-compartment vehicle routing problem ^[25], and multi-AGV routing problem ^[26].

Consequently, in this paper, we focus on improving the basic ACO by blending an effective local search procedure for solving WDP. To be specific, a hash tabu method is proposed to prevent the revisiting of those crucial solutions marked in the search history. As the searching direction is guided by the scoring function of the local search, we further propose a deep scoring strategy, which not only considers the environment of incumbent solutions, but also takes subsequent operations into account. We present the computational results of the proposed algorithm on 44 basics and 13 extended benchmark instances commonly used in the literature, and compare our results with those of the state-of-the-art algorithms for WDP. The results indicate that DHS-ACO is quite efficient on basic benchmark instances and outperforms other competitors on extended test suits. Furthermore, the verification experiments on different components of DHS-ACO are conducted to verify the effectiveness of the hash tabu strategy, the deep scoring strategy, the local search, and the ant colony algorithm.

The remainder of this paper is organized as follows. In the next section, we introduce the related work of practical algorithms for solving the WDP. In Section 3, we introduce some preliminary knowledge about both DHS-ACO and WDP. Section 4 describes the details of the components in the local search. Based on the above, DHS-ACO is presented. Then, we carry out comparison and verification experiments to evaluate DHS-ACO in Section 5. In the last section, we conclude the paper and introduce some future work.

2.   Related work

In recent years, WDP and its variants have been well studied due to their extensive applications. Vangerven et al. ^[27] adapted the winner determination problem for geometrical combinatorial auctions. Then, a new subclass of WDP, i.e., the network winner determination problem (NWDP), was proposed in ^[28], which characterized different problems in NWDP class and analyzed their computational complexity. Afterwards, Remli et al. ^[29] addressed the winner determination problem for TL transportation procurement auctions under uncertain shipment volumes and uncertain carriers' capacity. It extended an existing two-stage robust formulation proposed for WDP with uncertain shipment volumes. In the same year, Qian et al. ^[30] conducted a research on winner determination of loss-averse buyers with incomplete information in multi-attribute reverse auctions for clean energy device procurement. It was the same team that further studied a revised winner determination problem with disruption risk of bidders for a fourth party logistics (4PL) provider to purchase transportation services via combinatorial reverse auction ^[31]. In 2020, Lee et al. ^[32] resolved the integration difficulty between scheduling and routing aspects of the multiple automated guided vehicle (AGV) problem that were modelled by the winner determination problem.

For the WDP studied in this work, a number of exact algorithms have been proposed. Fujishima et al. ^[33] proposed a method, which is guaranteed to be optimal, to reduce the running time by structuring the search space. Nisan ^[34] suggested an approach based on linear programming (LP) and proved that the LP approach finds an optimal allocation if and only if prices can be attached to single items in the auction. Leyton-Brown et al. ^[35] proved the correctness of a branch-and-bound algorithm, which incorporates a specialized dynamic programming procedure. Sandholm and Suri ^[36] presented a more sophisticated search algorithm, including several technologies, for determining winners in many generalizations. Günlük and Ladányi ^[37] presented a column generation-based algorithm to solve the WDP given in the XOR-of-OR language and a methodology to generate realistic test problems. Escudero et al. ^[38] proposed a new and tighter formulation of WDP and new valid inequalities; then they presented a branch-and-cut algorithm which shows its efficiency in a big number of instances.

However, the exact methods can obtain the optimal solution of WDP, while they may fail to return a high-quality solution within a reasonable time or for large-scale of instances. Therefore, Hoos and Boutilier ^[39] proposed a stochastic local search algorithm (named Casanova), which added a bid to the current solution by considering bids' scores and history information. Based on the basic framework of the simulated annealing algorithm, Guo et al. ^[40] introduced the SAGII algorithm with three hybrid moving operators, i.e., the branch-and-bound move, the greedy local search move and the exchange move. Experimental results showed that SAGII performed better than Casanova algorithm. A new strategy was proposed in ^[41], in which a bid was added randomly with probability $p$ at each local iteration, and the bid with maximum profits was added into the solution with probability $1-p$. Experimental results showed that this strategy had a remarkable effect on the improvement of the algorithm. Wang ^[42] proposed a new super-heuristic algorithm (named SHH) by combining the selection function and random strategy. Based on the framework of the ant colony algorithm, Dowlatshahi et al. ^[43] performed a multi-neighborhood local search algorithm. By combining a stochastic local search component with a specific crossover operator, Boughaci et al. ^[44] presented a memetic algorithm for the winner determination problem. An efficient local search algorithm (named abcWDP) was proposed in ^[45], which used a pattern monitoring strategy to guide the search. Experimental results illustrated that this algorithm was the state-of-the-art heuristic algorithm for WDP. In addition, Lin et al. ^[46] raised to transform the combinatorial auction optimization problem into an unconstrained integer programming problem, and proposed a DCM algorithm to solve it.

3.   Preliminaries

3.1.   Definition and notations

Before we give the formulation of WDP, some notations are firstly introduced. Suppose that the collection of items auctioned is $MS = \{M_{1}, M_{2}, ..., M_{t}\}$, where $t$ is the quantity of items. The set of bids provided by all bidders is $BS = \{B_{1}, B_{2}, ..., B_{n}\}$, where $n$ is the number of bids. Each bid $B_{j} = \{S_{j}, P_{j}\}$ has two properties: $S_{j}$ is a non-empty subset of $MS$ that represents the combination of items to bid $B_{j}$, while $P_{j}$ is the bid price of $B_{j}$ and $P_{j} \geq 0$. Assume that a Boolean array $X = \{x_{1}, x_{2}, ..., x_{n} \}$ is a feasible solution of WDP, where $x_{j} \in \{0, 1\}$. $x_{j} = 1$ means that the bid $B_{j}$ is selected by the auctioneer, i.e., $B_{j}$ is the winning bid, i.e., $B_{j}$ is selected in the solution; otherwise, $x_{j} = 0$ indicates that $B_{j}$ is not selected by the auctioneer, i.e., it is a losing bid. Given above, the constraint of WDP is described as follows:

where $a_{ij} = 1$ represents $M_{i} \in S_{j}$, otherwise, $M_{i} \notin S_{j}$, $i \in [1, t]$. Constraint 3.2 guarantees that each item can be allocated at most once. Therefore, Eq (3.1) aims to maximize the auctioneer's revenue by selecting a set of winning bids.

In order to make the auction process clearly, Figure 1 shows the composite auction scene. Note that two bids containing at least a same item are considered as conflicting bids, which cannot exist simultaneously in the solution. For example, in this scene, $B_{2}$ and $B_{3}$ conflict with each other as they both contain $M_{1}$. All feasible solutions of WDP are composed of different non-conflicting bids. Therefore, all feasible solutions in this example are : $C_{1} = \{\{B_{1}\}, 12\}$, $C_{2} = \{\{B_{2}\}, 6\}$, $C_{3} = \{\{B_{3}\}, 8\}$, $C_{4} = \{\{B_{4}\}, 6\}$, $C_{5} = \{\{B_{2}, B_{4}\}, 12\}$, $C_{6} = \{\{B_{3}, B_{4}\}, 14\}$. Among all feasible solutions, $C_{6}$ is the optimal solution, as it brings maximum benefit to the auctioneer. That is, when the auctioneer selects $B_{3}$ and $B_{4}$, the auctioneer will get the highest income ＄14.

3.2.   Ant colony algorithm

Ant colony algorithm (ACO) constructs the solution step by step in the way of selecting probability. For WDP, the specific calculation method of selection probability can be calculated as follows. An initial solution $C$ is given to store all winning bids. Let $FB = \{B | CB(B) \cap C = \emptyset\} \cap \{BS \backslash C\}$ collect all bids without any conflict bids in $C$, where $CB(B)$ represents all bids that conflict with $B$ in $BS$. Given the candidate bid set $FB$, the chosen probability of bid $B_{j}\in FB$ is:

where $\alpha$ and $\beta$ represent the influence factors of pheromone and heuristic information of the ant colony algorithm respectively, and $\eta_{j}$ is the heuristic factor for solving WDP. Considering the goal of WDP, which is to maximize the auctioneer's revenue, we use the bid price $P_{j}$ to replace the heuristic factor $\eta_{j}$.

The basic process of ACO for solving WDP is as follows: firstly, initialize the pheromone vector of each element $\tau_{j} = pvi$, where $pvi$ is the initial pheromone concentration. Then, the algorithm enters the search phase. At each iteration, every ant chooses bids from $FB$ according to Eq (3.3). Then, the colony pheromones are updated as Eq (3.4) shows.

where $\rho \in \left[0, 1\right]$ represents the volatility of the pheromone. $\Delta$ is defined as:

where $Fitness(C)$ represents the fitness of solution $C$, calculated as:

After the pheromone updating process is completed, ACO judges whether the stop condition is met. If not, the algorithm enters the next iteration. Otherwise, ACO ends in outputting the best solution ever found.

4.   Hybrid ant colony algorithm for WDP

In this section, the proposed algorithm named DHS-ACO is introduced. Firstly, the main strategies of the local search are described with detailed explanations. Then, the whole profile of the local search is introduced. Finally, the framework of DHS-ACO is given.

4.1.   Local search procedure

Local search is an effective method to enhance the quality of the newly generated solutions by exploiting their surroundings. In this section, two key methods for the local search are introduced, including the hash tabu method and the deep scoring strategy. Then, the description of the move operator used in the local search is given. Finally, the local search framework is summarized.

4.1.1.   Hash tabu method

To avoid the repeated visiting of the same solution in the local search procedure, the hash tabu strategy is designed to efficiently determine whether the current solution has been visited. Given a solution $C$ and a prime number $pr$, the hash value corresponding to solution $C$ is defined as:

The hash tabu strategy employs a Boolean hash table $HT$, whose length is $pr$. The larger the $pr$ value is, the longer the hash table length is, and the less the possibility of hash clash is. Specifically, the method uses a hash table to judge whether the algorithm returns to the visited solution again. In other words, $HT_{h} = 1$ indicates that the solution with a hash value of $h$ has been marked in the search history, while $HT_{h} = 0$ indicates that the solution has not been marked. At the beginning of the algorithm, each element in $HT$ is set to 0, and a hash secondary array $H$ with length $n$ ($n$ is the number of bids) is created, in which each element $H_{i} = 2^{i-1}\mod pr$. In the initialization, we first set $H_{1} = 2^{0} \pmod{pr} = 1$, and the subsequent elements are calculated according to the following equation:

When adding or removing the bid $B_{i}$ to the solution $C$, the corresponding hash value of $C$ is updated according to the following equations:

Then, the specific usage of the hash tabu strategy is introduced. In the local search procedure, if the quality of the local search solution decreases in the previous step, while improved in the current step, one of the following situations which will be executed determined by the value of $HT_{h}$, and $h = hash(C)$.

$1)$If $HT_{h} = 1$, the last move will be cancelled with probability $ph$. In this case, the selected bid $B_{win}$ will be removed and prohibited from being added to the current solution until any of its conflicted bids are removed from $C$. With probability $1 - ph$, the algorithm will rebuild $C$ according to Eq (3) and restart the local search to avoid repeated visiting.

$2)$ Otherwise, the algorithm will set $HT_{h} = 1$ and continue to search.

4.1.2.   Deep scoring strategy

The deep scoring strategy is applied in the bid selection of the local search. The main idea of this mechanism is that if $FB \ne \emptyset$, then a bid with the largest $SScore$ value is selected from $FB$ to be added to the current solution. $FB$ stores those bids that are not conflicted with the current solution and $SScore$ is calculated as follows:

where $Score()$ reflects the fitness value change of $C$ after $B_{i}$ is added:

Clearly, if $B_{i} \in FB$ and $CB(B_{i}) = \emptyset$, the time complexity of the Eq (4.6) will reduce to $\mathcal{O}$(1). The $Score()$ reflects the greedy degree of the local search, because it only considers the impact of adding one bid to the current solution and does not consider the impact on subsequent local search operators. Regarding this, we introduce the $Subscore()$ evaluation function to estimate the loss of $FB$ set after adding one bid to $C$, which is calculated as follows:

On the one hand, the deep scoring strategy ensures that the local search can choose those bids in $FB$ first. Since there are no conflict bids between $FB$ and $C$, it is unnecessary to conduct conflict detection process and remove the conflicting bid when a bid in $FB$ is added. Therefore, giving priority to select bids in $FB$ will significantly reduce the selecting time. On the other hand, when selecting bids in $FB$, the deep scoring strategy uses $SScore()$ to comprehensively consider the impact on the solution and the impact on $FB$ loss, which makes the bid selection more reasonable.

4.1.3.   Move operator

The local search procedure exploits the neighborhoods of the current solution by performing the move operator, whose pseudo-code is shown in Algorithm 1.

In algorithm 1, the input data includes the current solution $C$ and the configuration checking vector $CC$. $CC$ was proposed by ^[45], whose updating method is as follows: at the beginning of the local search, all elements of $CC$ are initialized to 1. When a bid is removed from the current solution $C$, the bid $CC$ value is set to 0, and all bids that conflict with the bid $CC$ value are set to 1.

The algorithm first detects whether FB is empty. If $FB \ne \emptyset$, the bid with the largest $SScore$ will be selected into $C$. Otherwise, the following steps are executed:

$1)$ In the case of probability $p$, the algorithm puts the bid with $CC = 1$ into a temporary set $L$ and calls $OldestGoodBid()$. The $OldestGoodBid()$ function performs the following operations: if $L = \emptyset$, then the bid to be added into $C$ will be randomly selected from $BS \backslash C$. Otherwise, c $T = \{B|{B \in L} \cap {Score^{*}-Score(B) \leq \delta \cdot std_{B}}\}$, where $Score^{*}$ is the maximum score of all bids in $L$, $\delta$ is the parameter that controls the scale of $T$, and $std_{B}$ is the standard deviation of all bids' prices. Finally, the bid with the longest iterations outside $C$ will be selected into $C$.

$2)$ Randomly select a bid from $BS \backslash C$ with probability $1-p$ and add it into $C$ to enhance the diversity of the algorithm.

After completing any of the above cases, the algorithm removes all bids that conflict with $B_{pick}$ in $C$ and returns $C$.

Based on the ideas proposed above, the pseudo-code of the local search is given in Algorithm 2. At the beginning, the local search procedure initializes the best solution $C^{*}$ as the current solution $C$, the non-improved number of the fitness $N = 0$, and the boolean variable $lastStepImproved = 1$, presenting the condition that the fitness of $C$ has been improved after the last move (line 1). Moreover, all elements in $CC$ are initialized to 1 to allow the case that all bids are enabled to be added (line 2). Then, the algorithm iterates until $N$ reaches the limit $max\_no\_improved$ (lines 3–25). At each iteration of the loop, the $Move$ operator is applied to exploit the neighborhood of $C$ (line 5). If the $Move$ operator failed to find a better solution, the algorithm will set $N = N+1$ and mark $lastStepImproved$ as 0 (lines 6–8). Otherwise, the algorithm will refresh $N = 0$ (line 10), and attempt to update $C^{*}$ (line 11). Afterwards, the hash tabu strategy described in Section 4.1.1 is executed (lines 12–23). Finally, the best solution $C^{*}$ found during the search will be returned (line 25).

4.2.   The DHS-ACO algorithm

In this section, we design a hybrid ant colony algorithm called DHS-ACO to solve WDP. The pseudo-code of the DHS-ACO algorithm is given in Algorithm 3.

At the start of the algorithm, DHS-ACO initializes the pheromone vector $\tau$, the hash table $HT$, the hash auxiliary array $H$ and the best solution $bestC$ (lines 1–2). In each subsequent iteration, the algorithm firstly builds each ant by using the pheromone (line 5). Then, the local search procedure is adopted to exploit the neighborhood of the new ant (line 6). After all ants have finished the local search, DHS-ACO updates the pheromone vector $\tau$ (line 8). The loop will end when the running time exceeds the time limit (line 3). Finally, DHS-ACO outputs the best solution $bestC$ (line 9).

4.3.   Time complexity of DHS-ACO

In this section, the complexity of the key components of DHS-ACO are calculated, including the ant construction, the pheromone updating, and the local search procedure. For a brief instruction, some notations are recalled: $AntNum = p_a$, $|FB| = s_f$.

The ant construction process builds an ant by selecting bids from $FB$ one by one until $FB = \emptyset$. The selected bids are determined within $O(s_f)$ time. Since $|C| \le n$ and $s_f \le n$, the time complexity of constructing one ant is no more than $O(n^2)$. As for the pheromone updating, all $n$ elements of $\tau$ are updated according to the fitness of all $p_a$ ants. Therefore, it takes $O(np_a)$ time. In the local search procedure, it takes $O(n)$ for the Move operator in each iteration. Besides, at most $O(n^2)$ time would be taken if the hash tabu strategy decides to rebuild the current solution. Thus, the worst case time complexity of one iteration of the local search is $O(n+n^2)$, i.e., $O(n^2)$.

5.   Experimental evaluation

To show the efficiency of the proposed algorithm, we carry out extensive experiments in this section. Firstly, the benchmarks used in the experiments are introduced. Then, we compare DHS-ACO against a number of state-of-the-art competitors, including abcWDP ^[45], DCM ^[46], MA ^[44] and HBHSA ^[47], to show the algorithmic efficiency. Furthermore, the strategy verification experiments are performed to verify the effectiveness of the hash tabu method, the deep scoring strategy, the ant colony framework and the local search procedure proposed in this paper.

5.1.   Benchmarks

The benchmarks used in this work are selected from a set of LG benchmarks proposed in ^[48]. As shown in Table 1, it contains 500 instances and is divided into five classes according to the number of bids and items. All classes are named as $REL\_X\_Y$, where $X$ represents the number of bids and $Y$ is the number of items. Each class contains 100 examples. We refer to ^{[44,45,46,47]} and only select 44 samples from them as the basic benchmarks.

In addition, due to the small performance gap between DHS-ACO and other competitors on the basic benchmarks, we use the CATS platform ^[49] to generate a larger set of 13 extended instances, to further compare the performance of DHS-ACO and the state-of-the-art solvers on large-scale instances. Compared with the basic benchmarks, the number of bids and items increases significantly, which will become the obstruction for algorithms. Note that abcWDP performs best among the competitors and thus is chosen as the comparison on extended benchmarks. The extended benchmarks are listed in Table 2. All instances used in this work can be found on the website^†.

^†https://github.com/wujunzero/WDP

5.2.   Experiments and analysis

The DHS-ACO is implemented in C++. For DHS-ACO and abcWDP, all experiments are conducted 10 times on a computer with Intel(R) Xeon(R) CPU E7-4820 v4 @ 2.00 GHz, 64 GB. The experimental results of DCM and MA are taken from ^[46], while the results of HBHSA are taken from ^[47]. The operating environment is Intel i3-2330@2.2 GHz, Intel Pentium IV@2.8 GHz and 3.4 GHz AMD processors, respectively. Obviously, their CPU base frequency is higher than that of the experimental environment in this paper (2.00 GHz).

5.3.   Parameter settings

We use the automatic tuning tool irace ^[50] to tune the parameters. We randomly select 50 examples from all the examples as the training set. The parameter tuning process is budgeted to run 2,000 times, each with a budgeted run time of 1000 seconds. The final values obtained by irace are shown in Table 3. The results of each experiment will be introduced and analyzed in the following part.

5.4.   Comparison with state-of-the-art competitors

The experimental results of DHS-ACO and its competitors on basic benchmarks are presented in Tables 4–8. The columns named $f$ and $t$ stand for the average fitness and the average convergence time, respectively. Table 9 summarizes the average of the fitness ("$avg\_f$") and the total time ("$total\_t$", in seconds) of all algorithms in each class of basic benchmarks shown in Tables 4–8. Figure 2 shows the average convergence time ("$avg\_t$") and the number of reaching the optimal fitness among all reference algorithms ("$best\_num$") of the best solution obtained by each compared algorithm on all 44 basic instances.

Since the performance gap between DHS-ACO and abcWDP is small on basic benchmarks, we use the extended benchmarks to compare the performance of DHS-ACO and abcWDP. As shown in Table 10, compared with abcWDP algorithm, DHS-ACO algorithm is superior to abcWDP on the average objective function values obtained, which demonstrates that DHS-ACO performs better than abcWDP in solving large-scale instances. "Total" in the last row means the execution time of the tested instances in seconds.

Therefore, according to the results in Tables 4–9 and Figure 2, DHS-ACO algorithm is obviously superior to HBHSA, DCM and MA regarding the performance on each group of the basic benchmarks. Compared with the reference algorithms, DHS-ACO can obtain the same fitness values on all basic benchmarks, owing to the exploration of the heuristic method. And the average convergence time of DHS-ACO is faster and performs 1–2 orders of magnitude faster than the competitors, which reflects the effectiveness and efficiency of DHS-ACO on basic benchmarks. Moreover, for the extended benchmarks (the results of the comparison are shown in Table 10), due to the large-scale of these benchmarks, it is difficult for DCM, MA and HBHSA to solve them, while DHS-ACO obtains the better solutions by reducing the convergence time in each search iteration. Note that DHS-ACO can also find the better solutions on all extended benchmarks than abcWDP, although it requires more execution time than abcWDP in total. It is because of DHS-ACO explored enlarged feasible search space, benefited of the population-based framework.

5.5.   Validation experiment

In order to verify the effectiveness of each key component of DHS-ACO, we compare DHS-ACO with its four variants, which are introduced as follows:

● DHS-ACOnoh: DHS-ACO algorithm without using the hash tabu strategy.

● DHS-ACOnofbs: DHS-ACO algorithm without using the deep scoring strategy.

● DHS-ACOnols: DHS-ACO algorithm without local search.

● DHS-ACOnoaco: DHS-ACO algorithm without ant colony framework. This means DHS-ACOnoaco only uses the local search to solve the benchmarks. When the hash tabu strategy decides to rebuild the solution, the solution will be initialized randomly rather than use the construction method of ACO.

Since the comparison experiment shows that DHS-ACO algorithm can solve all basic test cases stably, we select all extended cases in Table 2 to test the effectiveness of each key component. The comparisons between DHS-ACO and its variants are listed in Table 11 to Table 14.

Table 11 shows that DHS-ACOnoh algorithm gains lower $f$ values than DHS-ACO on 11 instances, while obtains higher values on the remaining 2 instances. It can be seen that the intervention of the hash tabu strategy of the local search shows a negative effect, because the local search selects bids with randomness, which means the subsequent searches for those solutions marked by hash tabu strategy have little chance to find better solutions. However, in general, the hash tabu strategy makes DHS-ACO avoid repeated visiting efficiently and improve the local search significantly.

As can be seen from Table 12, DHS-ACO outperforms DHS-ACOnofbs on 10 out of 13 instances. One can see that the deep scoring strategy is counterproductive in a few test cases, because it focuses too much on the selection and maintenance of $FB$, and ignores the bids outside $FB$. Nevertheless, the deep scoring strategy improves the performance of DHS-ACO from an overall perspective.

According to Table 13, DHS-ACOnols obtains worse solutions on all instances without using the local search. Meanwhile, its convergence time is greatly reduced compared with DHS-ACO. It is clear that the proposed local search provides a powerful neighborhood search capability for DHS-ACO, which makes DHS-ACO effective in exploiting the solution space.

Table 14 indicates the effectiveness of the ant colony algorithm framework of DHS-ACO. Without the new solutions generated by the ant colony framework, DHS-ACOnoaco performs significantly worse than DHS-ACO on all test cases. It demonstrates the necessary of using the ant colony framework to provide high-quality solutions for DHS-ACO based on pheromones and heuristics.

6.   Conclusions

In this paper, we propose a new swarm algorithm called DHS-ACO, which can effectively deal with the WDP on a wide instances. Based on the ant colony framework, the algorithm combines an effective local search with a hash tabu method and a deep scoring strategy. Extensive computational evaluations of the algorithm on two set of benchmarks demonstrated its competitiveness compared to the state-of-the-art methods. In particular, the algorithm can find the same best solutions on all basic benchmarks with less time reported in the literature and the best solutions on all extended benchmarks.

Furthermore, owing to the random nature of the swarm intelligent algorithms, DHS-ACO need more time than its competitor abcWDP on large-scale benchmarks, although it can give better solutions. It would be interesting to reduce the consumption time on the large-scale benchmarks in the future.

Acknowledgments

This work is supported by the Fundamental Research Funds for the Central Universities 2412018QD022, NSFC (under Grant No.61976050, 61972384) and Jilin Provincial Science and Technology Department under Grant No. 20190302109GX.

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this paper.