# American Institute of Mathematical Sciences

• Previous Article
A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking
• JIMO Home
• This Issue
• Next Article
Pricing options on investment project expansions under commodity price uncertainty
January  2019, 15(1): 235-259. doi: 10.3934/jimo.2018041

## A parallel water flow algorithm with local search for solving the quadratic assignment problem

 1 Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 119260 2 Laboratory for Urban Complexity and Sustainability, University of Nottingham, Nottingham NG7 2RB, UK

* Corresponding author: Trung Hieu Tran

Received  May 2017 Revised  December 2017 Published  April 2018

In this paper, we adapt a nature-inspired optimization approach, the water flow algorithm, for solving the quadratic assignment problem. The algorithm imitates the hydrological cycle in meteorology and the erosion phenomenon in nature. In this algorithm, a systematic precipitation generating scheme is included to increase the spread of the raindrop positions on the ground to increase the solution exploration capability of the algorithm. Efficient local search methods are also used to enhance the solution exploitation capability of the algorithm. In addition, a parallel computing strategy is integrated into the algorithm to speed up the computation time. The performance of the algorithm is tested with the benchmark instances of the quadratic assignment problem taken from the QAPLIB. The computational results and comparisons show that our algorithm is able to obtain good quality or optimal solutions to the benchmark instances within reasonable computation time.

Citation: Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
##### References:

show all references

##### References:
An example of solution representation in the WFA for the QAP.
The erosion process in exploitation phase of the WFA.
Flow chart of the WFA for the QAP.
Comparison of the WFA with other algorithms on (a). Average percentage difference; and (b). The number of the best known solutions obtained.
A summary of state-of-the-art metaheuristic algorithms for solving the QAP.
 Metaheuristic algorithms No. of best known solutions found / No. of tested instances Average difference Maximum difference Maximum size of instance Drawbacks Simulated annealing [37] 26 / 40 0.99% 11.51% (chrxxx instance) 30 Solving QAP relaxation to construct initial solution for simulated annealing depends on the capability of solvers used [37]. Thus, the algorithm may not solve instances of size $n>30$ effectively or extensive computation time may be required. Ant system [24] 33 / 44 0.28% 2.79% (chrxxx instance) 40 Computation time of local search is rather onerous [24], and thus does not solve instances of size $n>40$ efficiently. Population based hybrid ant system [28] 80 / 110 0.41% 14.25% (chrxxx instance) 100 Population size increases significantly according to instance size [28], leading to difficulty for solving large instances. Greedy genetic algorithm [2] 58 / 87 0.17% 5.13% (chrxxx instance) 100 Although greedy approach improves the quality of individuals, this may affect the overall performance of the genetic algorithm [2]. In addition, using 2-exchange local search could limit the capability for searching better solutions. Greedy randomized adaptive search procedure [22] 27 / 44 0.69% 4.64% (chrxxx instance) 128 The algorithm can be applied only to symmetric QAP instances [2]. Iterated fast local search [29] 72 / 130 0.87% 20.33% (lipaxxx instance) 256 2-opt local search of the algorithm could not solve lipaxxx instances of the QAPLIB effectively [29] due to limit in search space. Hybrid genetic algorithm [23] 84 / 130 0.51% 16.56% (lipaxxx instance) 256 2-gene exchange local search could not solve lipaxxx instances of the QAPLIB effectively [23] due to limit in search space.
 Metaheuristic algorithms No. of best known solutions found / No. of tested instances Average difference Maximum difference Maximum size of instance Drawbacks Simulated annealing [37] 26 / 40 0.99% 11.51% (chrxxx instance) 30 Solving QAP relaxation to construct initial solution for simulated annealing depends on the capability of solvers used [37]. Thus, the algorithm may not solve instances of size $n>30$ effectively or extensive computation time may be required. Ant system [24] 33 / 44 0.28% 2.79% (chrxxx instance) 40 Computation time of local search is rather onerous [24], and thus does not solve instances of size $n>40$ efficiently. Population based hybrid ant system [28] 80 / 110 0.41% 14.25% (chrxxx instance) 100 Population size increases significantly according to instance size [28], leading to difficulty for solving large instances. Greedy genetic algorithm [2] 58 / 87 0.17% 5.13% (chrxxx instance) 100 Although greedy approach improves the quality of individuals, this may affect the overall performance of the genetic algorithm [2]. In addition, using 2-exchange local search could limit the capability for searching better solutions. Greedy randomized adaptive search procedure [22] 27 / 44 0.69% 4.64% (chrxxx instance) 128 The algorithm can be applied only to symmetric QAP instances [2]. Iterated fast local search [29] 72 / 130 0.87% 20.33% (lipaxxx instance) 256 2-opt local search of the algorithm could not solve lipaxxx instances of the QAPLIB effectively [29] due to limit in search space. Hybrid genetic algorithm [23] 84 / 130 0.51% 16.56% (lipaxxx instance) 256 2-gene exchange local search could not solve lipaxxx instances of the QAPLIB effectively [23] due to limit in search space.
The parameter sets of the WFA for the QAP benchmark instances.
 Benchmarks $n$ Parameter values MaxCloud MaxPop MaxUIE MinEro Burkard 26 5 16 10 2 Christofides 12 - 20 10 16 10 2 22 15 16 10 2 25 20 16 10 2 Elshafei 19 10 16 10 2 Eschermann 16, 64 2 8 5 2 32 (a, b) 5 16 10 2 32 (c, e, g) 2 8 5 2 32 (d, h) 2 16 10 2 128 5 16 5 3 Hadley 12 - 20 10 16 10 2 Krarup 30, 32 20 16 10 2 Li & Pardalos 20, 30 10 16 10 2 40, 50, 60 10 24 10 2 70 10 24 15 2 80, 90 20 24 10 2 Nugent 12 - 28 10 16 5 2 30 20 16 10 2 Roucairol 12, 15 5 16 10 2 20 10 24 10 2 Scriabin 12, 15, 20 5 16 10 2 Skorin-Kapov 42 - 64 15 16 10 2 72, 81, 90 10 24 15 2 100 10 16 10 2 Steinberg 36 20 16 10 2 Taillard (Taixxxa) 12 5 16 10 2 15, 17 5 24 10 2 20 - 35 20 24 10 2 40, 50 20 24 15 2 60, 80,100 10 24 10 2 (Taixxxb) 12 - 20 5 8 10 2 25 10 16 10 2 30, 35, 40 20 16 10 2 50, 60, 80 10 16 15 2 100 5 24 10 2 150 5 16 5 2 (Taixxxc) 64 10 24 10 2 256 2 8 5 2 Thonemann 30 10 24 10 2 40 20 16 10 2 150 5 16 10 2 Wilhelm 50 15 24 10 2 100 10 16 10 2
 Benchmarks $n$ Parameter values MaxCloud MaxPop MaxUIE MinEro Burkard 26 5 16 10 2 Christofides 12 - 20 10 16 10 2 22 15 16 10 2 25 20 16 10 2 Elshafei 19 10 16 10 2 Eschermann 16, 64 2 8 5 2 32 (a, b) 5 16 10 2 32 (c, e, g) 2 8 5 2 32 (d, h) 2 16 10 2 128 5 16 5 3 Hadley 12 - 20 10 16 10 2 Krarup 30, 32 20 16 10 2 Li & Pardalos 20, 30 10 16 10 2 40, 50, 60 10 24 10 2 70 10 24 15 2 80, 90 20 24 10 2 Nugent 12 - 28 10 16 5 2 30 20 16 10 2 Roucairol 12, 15 5 16 10 2 20 10 24 10 2 Scriabin 12, 15, 20 5 16 10 2 Skorin-Kapov 42 - 64 15 16 10 2 72, 81, 90 10 24 15 2 100 10 16 10 2 Steinberg 36 20 16 10 2 Taillard (Taixxxa) 12 5 16 10 2 15, 17 5 24 10 2 20 - 35 20 24 10 2 40, 50 20 24 15 2 60, 80,100 10 24 10 2 (Taixxxb) 12 - 20 5 8 10 2 25 10 16 10 2 30, 35, 40 20 16 10 2 50, 60, 80 10 16 15 2 100 5 24 10 2 150 5 16 5 2 (Taixxxc) 64 10 24 10 2 256 2 8 5 2 Thonemann 30 10 24 10 2 40 20 16 10 2 150 5 16 10 2 Wilhelm 50 15 24 10 2 100 10 16 10 2
Comparison results of the WFA with other algorithms for Burkard's and Christofides' instances
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Bur26a 5426670 5426670 30.0 0 30.0 0 11.38 0 21.07 0 235 0 125 0 61.27 - - 0 Bur26b 3817852 3817852 23.0 0 23.0 0 59.45 0 35.03 0 225 0 9.5 0 60.27 - - 0 Bur26c 5426795 5426795 16.0 0 16.0 0 5.16 0 19.09 0 227 0 7.42 0 57.78 - - 0 Bur26d 3821225 3821225 29.0 0 29.0 0 15.12 0 19.40 0 213 0 8.42 0 61.27 - - 0 Bur26e 5386879 5386879 32.0 0 32.0 0 17.63 0 20.53 0 218 0 10.03 0 57.83 - - 0 Bur26f 3782044 3782044 44.0 0 44.0 0 5.05 0 11.23 0 104 0 6.68 0 59.19 - - 0 Bur26g 10117172 10117172 26.0 0 26.0 0 22.58 0 18.67 0 194 0 9.99 0 57.72 - - 0 Bur26h 7098658 7098658 20.0 0 20.0 0 37.58 0 5.67 0 204 0 6.82 0 57.47 - - 0 Chr12a 9552 9552 0.6 0 0.6 - - - - 0 19.6 0 0.54 0 1.09 0 40 0 Chr12b 9742 9742 0.5 0 0.5 - - - - 0 18.4 0 0.42 0 1.11 0 41 0 Chr12c 11156 11156 0.6 0 0.6 - - - - 0 20.2 0 1.29 0 1.02 0.26 38 0.27 Chr15a 9896 9896 3.2 0 3.2 - - - - 0.4 40.6 0 1.50 0 2.97 0 69 0 Chr15b 7990 7990 4.1 0 4.1 - - - - 0 41.8 0 1.31 0 3.08 2.7 72 0 Chr15c 9504 9504 4.0 0 4.0 - - - - 0 44 0 1.30 0 2.64 11.5 69 6.36 Chr18a 11098 11098 9.3 0 9.3 - - - - 0.4 79 0 2.11 5.14 7.23 1.71 103 14.25 Chr18b 1534 1534 10.2 0 10.2 - - - - 0 78.8 0 2.62 0 5.30 0 105 0 Chr20a 2192 2192 32.0 0 32.0 1.82 509 0 331 0 94.6 0.18 3.61 4.38 10.95 0 131 1.82 Chr20b 2298 2298 27.0 0 27.0 5.92 195 2.79 375 5.13 96.4 3.12 3.32 5.40 8.61 0 127 4.96 Chr20c 14142 14142 15.0 0 15.0 0.00 9.23 0 29.49 0 97.8 4.51 1.77 0 13.55 0 140 0 Chr22a 6156 6156 60.0 0 60.0 2.31 201 0 315 0.75 146 0 4.52 0.88 19.11 5.7 164 0.32 Chr22b 6194 6194 58.0 0 58.0 2.58 213 0.97 162 0 152 1.46 5.26 1.68 17.00 8.5 163 0 Chr25a 3796 3796 95.0 0 95.0 2.32 115 0 236 0 194 2.27 5.97 11.17 33.59 0 591 0
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Bur26a 5426670 5426670 30.0 0 30.0 0 11.38 0 21.07 0 235 0 125 0 61.27 - - 0 Bur26b 3817852 3817852 23.0 0 23.0 0 59.45 0 35.03 0 225 0 9.5 0 60.27 - - 0 Bur26c 5426795 5426795 16.0 0 16.0 0 5.16 0 19.09 0 227 0 7.42 0 57.78 - - 0 Bur26d 3821225 3821225 29.0 0 29.0 0 15.12 0 19.40 0 213 0 8.42 0 61.27 - - 0 Bur26e 5386879 5386879 32.0 0 32.0 0 17.63 0 20.53 0 218 0 10.03 0 57.83 - - 0 Bur26f 3782044 3782044 44.0 0 44.0 0 5.05 0 11.23 0 104 0 6.68 0 59.19 - - 0 Bur26g 10117172 10117172 26.0 0 26.0 0 22.58 0 18.67 0 194 0 9.99 0 57.72 - - 0 Bur26h 7098658 7098658 20.0 0 20.0 0 37.58 0 5.67 0 204 0 6.82 0 57.47 - - 0 Chr12a 9552 9552 0.6 0 0.6 - - - - 0 19.6 0 0.54 0 1.09 0 40 0 Chr12b 9742 9742 0.5 0 0.5 - - - - 0 18.4 0 0.42 0 1.11 0 41 0 Chr12c 11156 11156 0.6 0 0.6 - - - - 0 20.2 0 1.29 0 1.02 0.26 38 0.27 Chr15a 9896 9896 3.2 0 3.2 - - - - 0.4 40.6 0 1.50 0 2.97 0 69 0 Chr15b 7990 7990 4.1 0 4.1 - - - - 0 41.8 0 1.31 0 3.08 2.7 72 0 Chr15c 9504 9504 4.0 0 4.0 - - - - 0 44 0 1.30 0 2.64 11.5 69 6.36 Chr18a 11098 11098 9.3 0 9.3 - - - - 0.4 79 0 2.11 5.14 7.23 1.71 103 14.25 Chr18b 1534 1534 10.2 0 10.2 - - - - 0 78.8 0 2.62 0 5.30 0 105 0 Chr20a 2192 2192 32.0 0 32.0 1.82 509 0 331 0 94.6 0.18 3.61 4.38 10.95 0 131 1.82 Chr20b 2298 2298 27.0 0 27.0 5.92 195 2.79 375 5.13 96.4 3.12 3.32 5.40 8.61 0 127 4.96 Chr20c 14142 14142 15.0 0 15.0 0.00 9.23 0 29.49 0 97.8 4.51 1.77 0 13.55 0 140 0 Chr22a 6156 6156 60.0 0 60.0 2.31 201 0 315 0.75 146 0 4.52 0.88 19.11 5.7 164 0.32 Chr22b 6194 6194 58.0 0 58.0 2.58 213 0.97 162 0 152 1.46 5.26 1.68 17.00 8.5 163 0 Chr25a 3796 3796 95.0 0 95.0 2.32 115 0 236 0 194 2.27 5.97 11.17 33.59 0 591 0
Comparison results of the WFA with other algorithms for Elshafei's, Eschermann's, Hadley's, and Krarup's instances.
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Els19 17212548 17212548 15 0 15 - - - - 0 80.6 0 44.46 - - - - 0 Esc16a 68 68 0.1 0 0.1 - - - - 0 47.4 0 5.13 0 3.17 0 61 0 Esc16b 292 292 0.1 0 0.1 - - - - 0 48.2 0 0.19 0 2.75 0 60 0 Esc16c 160 160 0.1 0 0.1 - - - - 0 53.4 0 0.44 0 4.03 0 68 0 Esc16d 16 16 0.1 0 0.1 - - - - 0 53.2 0 0.50 0 3.98 - - 0 Esc16e 28 28 0.1 0 0.1 - - - - 0 46.8 0 0.32 0 2.28 - - 0 Esc16f 0 0 0.1 0 0.1 - - - - 0 46.0 - - 0 1.11 - - 0 Esc16g 26 26 0.1 0 0.1 - - - - 0 49.8 0 0.29 0 2.77 - - 0 Esc16h 996 996 0.1 0 0.1 - - - - 0 48.0 0 0.22 0 2.13 0 65 0 Esc16i 14 14 0.1 0 0.1 - - - - 0 51.6 0 0.16 0 2.05 - - 0 Esc16j 8 8 0.1 0 0.1 - - - - 0 402 0 0.32 0 2.91 - - 0 Esc32a 130 130 190 0 190 1.54 7.03 0 226 0 382 1.52 97.04 0 137 - - 0 Esc32b 168 168 53 0 53 0 2.80 0 40.59 0 400 0 33.61 0 110 - - 0 Esc32c 642 642 1.2 0 1.2 0 0 0 0.08 0 389 0 2.01 0 54.7 - - 0 Esc32d 200 200 11 0 11 0 1.92 0 2.13 0 353 0 2.76 0 74.3 - - 0 Esc32e 2 2 0.8 0 0.8 0 0 0 0.05 0 370 0 0.66 0 46.09 - - 0 Esc32g 6 6 0.9 0 0.9 0 0 0 0.07 0 371 0 1.27 0 28.41 - - 0 Esc32h 438 438 31 0 31 0 3.41 0 2.64 0 349 0 6.54 0 85.75 - - 0 Esc64a 116 116 9.6 0 9.6 - - - - 0 2631 0 194 0 1522 - - 0 Esc128 64 64 1395 0 1395 - - - - - - 0 1631 - - - - 0 Had12 1652 1652 0.7 0 0.7 - - - - - - 0 4.27 0 0.97 0 41 0 Had14 2724 2724 1.5 0 1.5 - - - - - - 0 10.25 0 1.97 0 64 0 Had16 3720 3720 2.2 0 2.2 - - - - - - 0 5.38 0.05 3.64 0 88 0 Had18 5358 5358 4.9 0 4.9 - - - - - - 0 18.54 0 6.52 0 118 0 Had20 6922 6922 11.2 0 11.2 0 2.8 0 159 - - 0 15.26 0 10.58 0 148 0 Kra30a 88900 88900 430 0 430 0 292 0 199 0 301 0.89 71 1.34 106 - - 0 Kra30b 91420 91420 441 0 441 0.32 268 0 140 0 331 0 123 0.13 102 - - 0.08 Kra32 88700 88700 432 0 432 - - - - - - - - 0 172 - - 0
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Els19 17212548 17212548 15 0 15 - - - - 0 80.6 0 44.46 - - - - 0 Esc16a 68 68 0.1 0 0.1 - - - - 0 47.4 0 5.13 0 3.17 0 61 0 Esc16b 292 292 0.1 0 0.1 - - - - 0 48.2 0 0.19 0 2.75 0 60 0 Esc16c 160 160 0.1 0 0.1 - - - - 0 53.4 0 0.44 0 4.03 0 68 0 Esc16d 16 16 0.1 0 0.1 - - - - 0 53.2 0 0.50 0 3.98 - - 0 Esc16e 28 28 0.1 0 0.1 - - - - 0 46.8 0 0.32 0 2.28 - - 0 Esc16f 0 0 0.1 0 0.1 - - - - 0 46.0 - - 0 1.11 - - 0 Esc16g 26 26 0.1 0 0.1 - - - - 0 49.8 0 0.29 0 2.77 - - 0 Esc16h 996 996 0.1 0 0.1 - - - - 0 48.0 0 0.22 0 2.13 0 65 0 Esc16i 14 14 0.1 0 0.1 - - - - 0 51.6 0 0.16 0 2.05 - - 0 Esc16j 8 8 0.1 0 0.1 - - - - 0 402 0 0.32 0 2.91 - - 0 Esc32a 130 130 190 0 190 1.54 7.03 0 226 0 382 1.52 97.04 0 137 - - 0 Esc32b 168 168 53 0 53 0 2.80 0 40.59 0 400 0 33.61 0 110 - - 0 Esc32c 642 642 1.2 0 1.2 0 0 0 0.08 0 389 0 2.01 0 54.7 - - 0 Esc32d 200 200 11 0 11 0 1.92 0 2.13 0 353 0 2.76 0 74.3 - - 0 Esc32e 2 2 0.8 0 0.8 0 0 0 0.05 0 370 0 0.66 0 46.09 - - 0 Esc32g 6 6 0.9 0 0.9 0 0 0 0.07 0 371 0 1.27 0 28.41 - - 0 Esc32h 438 438 31 0 31 0 3.41 0 2.64 0 349 0 6.54 0 85.75 - - 0 Esc64a 116 116 9.6 0 9.6 - - - - 0 2631 0 194 0 1522 - - 0 Esc128 64 64 1395 0 1395 - - - - - - 0 1631 - - - - 0 Had12 1652 1652 0.7 0 0.7 - - - - - - 0 4.27 0 0.97 0 41 0 Had14 2724 2724 1.5 0 1.5 - - - - - - 0 10.25 0 1.97 0 64 0 Had16 3720 3720 2.2 0 2.2 - - - - - - 0 5.38 0.05 3.64 0 88 0 Had18 5358 5358 4.9 0 4.9 - - - - - - 0 18.54 0 6.52 0 118 0 Had20 6922 6922 11.2 0 11.2 0 2.8 0 159 - - 0 15.26 0 10.58 0 148 0 Kra30a 88900 88900 430 0 430 0 292 0 199 0 301 0.89 71 1.34 106 - - 0 Kra30b 91420 91420 441 0 441 0.32 268 0 140 0 331 0 123 0.13 102 - - 0.08 Kra32 88700 88700 432 0 432 - - - - - - - - 0 172 - - 0
Comparison results of the WFA with other algorithms for Li & Pardalos' and Skorin-Kapov's instances.
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Lipa20a 3683 3683 14 0 14 0 0.99 0 107 0 74.8 0 0.59 0 16.11 - - 0 Lipa20b 27076 27076 16 0 16 0 0.66 0 0 0 74.4 0 0.39 0 16.78 - - 0 Lipa30a 13178 13178 75 0 75 0 46.43 0 54.85 0 345 0 5.66 0 120 - - 0.99 Lipa30b 151426 151426 73 0 73 0 7.31 0 0 0 337 0 2.78 0 122 - - 0 Lipa40a 31538 31538 655 0 655 1.13 306 1.02 281 0.96 1022 0 19.46 0 490 - - - Lipa40b 476581 476581 430 0 430 0 6.21 0 0 0 1026 0 9.52 0 486 - - - Lipa50a 62093 62619 872 0.80 971 - - - - 0.95 1486 0.82 57.32 1.02 1556 - - 0 Lipa50b 1210244 1210244 777 0 777 - - - - 0 1509 0 39.96 0 1462 - - 0 Lipa60a 107218 108103 1337 0.79 2754 - - - - 0.77 3057 0.64 137 0.84 3668 - - 0.81 Lipa60b 2520135 2520135 893 0 893 - - - - 0 3047 0 86.13 0 3724 - - 0 Lipa70a 169755 170956 1714 0.71 1744 - - - - 0.71 6148 0.62 233 0.77 8067 - - - Lipa70b 4603200 4603200 1771 0 1771 - - - - 0 6123 15.9 196 0 7762 - - - Lipa80a 253195 254853 2254 0.63 3467 - - - - 0.61 9519 0.61 373 0.67 15220 - - - Lipa80b 7763962 7763962 2511 0 2511 - - - - 0 9499 16.56 332 20.33 15965 - - - Lipa90a 360630 362854 2562 0.57 5678 - - - - 0.58 12358 0.54 592 0.63 27909 - - - Lipa90b 12490441 12490441 5034 0 5034 - - - - 0 12319 0 503 0 27788 - - - Sko42 15812 15836 1042 0.03 1547 - - - - 0.25 1006 0.35 365 0.30 614 - - 0 Sko49 23386 23510 1098 0.32 1772 - - - - 0.21 1252 0.19 714 0.45 1318 - - 0.05 Sko56 34458 34568 1064 0.20 1742 - - - - 0.02 2976 0.06 907 0.47 2613 - - 0.12 Sko64 48498 48796 1178 0.31 2770 - - - - 0.22 3788 0.09 1399 0.25 4936 - - 0 Sko72 66256 66660 1620 0.47 4096 - - - - 0.29 5078 0.21 1987 0.73 8663 - - 0.03 Sko81 90998 91452 1520 0.50 1655 - - - - 0.20 10964 0.12 2680 0.43 16960 - - 0.05 Sko90 115534 116922 1625 0.91 4053 - - - - 0.27 12698 0.43 3822 0.45 28787 - - 0.02 Sko100a 152002 153426 1905 0.94 1907 - - - - 0.21 16608 0.22 1486 1.30 309 - - 0.19 Sko100b 153890 155288 1494 0.85 1577 - - - - 0.14 14729 0.30 1405 2.34 274 - - - Sko100c 147862 149628 1525 1.15 1786 - - - - 0.20 20314 0.06 873 1.50 284 - - - Sko100d 149576 151196 1666 0.97 3978 - - - - 0.17 20302 0.27 863 1.03 293 - - - Sko100e 149150 151056 2423 0.90 5415 - - - - 0.24 21127 0.33 745 1.55 301 - - - Sko100f 149036 150510 2038 0.91 2125 - - - - 0.29 21479 0.41 781 0.73 285 - - -
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Lipa20a 3683 3683 14 0 14 0 0.99 0 107 0 74.8 0 0.59 0 16.11 - - 0 Lipa20b 27076 27076 16 0 16 0 0.66 0 0 0 74.4 0 0.39 0 16.78 - - 0 Lipa30a 13178 13178 75 0 75 0 46.43 0 54.85 0 345 0 5.66 0 120 - - 0.99 Lipa30b 151426 151426 73 0 73 0 7.31 0 0 0 337 0 2.78 0 122 - - 0 Lipa40a 31538 31538 655 0 655 1.13 306 1.02 281 0.96 1022 0 19.46 0 490 - - - Lipa40b 476581 476581 430 0 430 0 6.21 0 0 0 1026 0 9.52 0 486 - - - Lipa50a 62093 62619 872 0.80 971 - - - - 0.95 1486 0.82 57.32 1.02 1556 - - 0 Lipa50b 1210244 1210244 777 0 777 - - - - 0 1509 0 39.96 0 1462 - - 0 Lipa60a 107218 108103 1337 0.79 2754 - - - - 0.77 3057 0.64 137 0.84 3668 - - 0.81 Lipa60b 2520135 2520135 893 0 893 - - - - 0 3047 0 86.13 0 3724 - - 0 Lipa70a 169755 170956 1714 0.71 1744 - - - - 0.71 6148 0.62 233 0.77 8067 - - - Lipa70b 4603200 4603200 1771 0 1771 - - - - 0 6123 15.9 196 0 7762 - - - Lipa80a 253195 254853 2254 0.63 3467 - - - - 0.61 9519 0.61 373 0.67 15220 - - - Lipa80b 7763962 7763962 2511 0 2511 - - - - 0 9499 16.56 332 20.33 15965 - - - Lipa90a 360630 362854 2562 0.57 5678 - - - - 0.58 12358 0.54 592 0.63 27909 - - - Lipa90b 12490441 12490441 5034 0 5034 - - - - 0 12319 0 503 0 27788 - - - Sko42 15812 15836 1042 0.03 1547 - - - - 0.25 1006 0.35 365 0.30 614 - - 0 Sko49 23386 23510 1098 0.32 1772 - - - - 0.21 1252 0.19 714 0.45 1318 - - 0.05 Sko56 34458 34568 1064 0.20 1742 - - - - 0.02 2976 0.06 907 0.47 2613 - - 0.12 Sko64 48498 48796 1178 0.31 2770 - - - - 0.22 3788 0.09 1399 0.25 4936 - - 0 Sko72 66256 66660 1620 0.47 4096 - - - - 0.29 5078 0.21 1987 0.73 8663 - - 0.03 Sko81 90998 91452 1520 0.50 1655 - - - - 0.20 10964 0.12 2680 0.43 16960 - - 0.05 Sko90 115534 116922 1625 0.91 4053 - - - - 0.27 12698 0.43 3822 0.45 28787 - - 0.02 Sko100a 152002 153426 1905 0.94 1907 - - - - 0.21 16608 0.22 1486 1.30 309 - - 0.19 Sko100b 153890 155288 1494 0.85 1577 - - - - 0.14 14729 0.30 1405 2.34 274 - - - Sko100c 147862 149628 1525 1.15 1786 - - - - 0.20 20314 0.06 873 1.50 284 - - - Sko100d 149576 151196 1666 0.97 3978 - - - - 0.17 20302 0.27 863 1.03 293 - - - Sko100e 149150 151056 2423 0.90 5415 - - - - 0.24 21127 0.33 745 1.55 301 - - - Sko100f 149036 150510 2038 0.91 2125 - - - - 0.29 21479 0.41 781 0.73 285 - - -
Comparison results of the WFA with other algorithms for Nugent's, Roucairol's, Scriabin's, Steinberg's, Thonemann's, and Wilhelm's instances.
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Nug12 578 578 0.5 0 0.5 - - - - 0 19 0 6.84 0 1.41 0 36 0 Nug14 1014 1014 0.8 0 0.8 - - - - - - 0 7.71 0.39 3.11 - - 0.2 Nug15 1150 1150 5.8 0 5.8 - - - - 0 41.4 0 8.3 0 4.02 0 73 0 Nug16a 1610 1610 4.1 0 4.1 - - - - - - 0 11.24 0 5.59 - - 0 Nug16b 1240 1240 4.7 0 4.7 - - - - - - 0 11.02 0 5.59 - - 0 Nug17 1732 1732 5.7 0 5.7 - - - - - - 0 11.95 0 7.31 - - 0 Nug18 1930 1930 7.9 0 7.9 - - - - - - 0.31 13.56 0 9.55 - - 0 Nug20 2570 2570 15.7 0 15.7 0 2.53 0 119 0 97.8 0 20.73 0 16.06 0 132 0 Nug21 2438 2438 27.5 0 27.5 - - - - - - 0 29.80 0 20.63 - - 0 Nug22 3596 3596 26.5 0 26.5 - - - - - - 0 43.82 0 25.84 - - 0 Nug24 3488 3488 39.7 0 39.7 - - - - - - 0 33.83 0 39.75 - - 0.06 Nug25 3744 3744 38.5 0 38.5 - - - - - - 0 42.10 0 47.66 - - 0 Nug27 5234 5234 51.8 0 51.8 - - - - - - - - 0 80.56 - - 0 Nug28 5166 5166 57.5 0 57.5 - - - - - - - - 0.12 98.33 - - 0 Nug30 6124 6124 136.1 0 136.1 0.42 523 0 181 0.07 354 0.42 109 2.12 117 0.06 887 0.07 Rou12 235528 235528 0.5 0 0.5 - - - - 0 19.6 0 0.30 0 1.06 0 35 0 Rou15 354210 354210 1.1 0 1.1 - - - - 0 34.6 0 0.56 0 2.95 0.71 71 0 Rou20 725522 725522 12.2 0 12.2 0 165 0 245 0.16 75.2 0 1.43 0.02 11.73 0.06 127 0 Scr12 31410 31410 0.7 0 0.7 - - - - 0 18.8 0 0.44 0 1.11 0 38 0 Scr15 51140 51140 1.0 0 1.0 - - - - 0 35.2 0 0.42 0 3.09 0 78 0 Scr20 110030 110030 5.4 0 5.4 0 157 0 46.1 0 79.6 0 1.57 0 12.69 2.13 137 0 Ste36a 9526 9526 623.5 0 623.5 1.81 276 0.76 295 0.27 710 0 221 0 204 - - - Ste36b 15852 15852 763.2 0 763.2 0.92 180 0.25 213 - - 0 235 3.43 222 - - - Ste36c 8239110 8239110 800.4 0 800.4 0.89 142 0.33 321 - - 0 24.07 - - - - - Tho30 149936 149936 306.2 0 306.2 0 216 0 288 0 396 0 132 0.29 119 - - - Tho40 240516 240620 823.1 0.04 823.1 1.17 184 0.66 312 0.32 958 0.05 344 0.53 502 - - - Tho150 8133398 8238058 4590.3 1.29 4590.3 - - - - - - 0.41 729 - - - - - Wil50 48816 48916 829.8 0.06 2522.3 - - - - 0.07 2115 0 695 0.28 1499 - - - Wil100 273038 274446 3330.7 0.34 5272.6 - - - - 0.2 20544 0.15 1252 0.27 51121 - - -
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Nug12 578 578 0.5 0 0.5 - - - - 0 19 0 6.84 0 1.41 0 36 0 Nug14 1014 1014 0.8 0 0.8 - - - - - - 0 7.71 0.39 3.11 - - 0.2 Nug15 1150 1150 5.8 0 5.8 - - - - 0 41.4 0 8.3 0 4.02 0 73 0 Nug16a 1610 1610 4.1 0 4.1 - - - - - - 0 11.24 0 5.59 - - 0 Nug16b 1240 1240 4.7 0 4.7 - - - - - - 0 11.02 0 5.59 - - 0 Nug17 1732 1732 5.7 0 5.7 - - - - - - 0 11.95 0 7.31 - - 0 Nug18 1930 1930 7.9 0 7.9 - - - - - - 0.31 13.56 0 9.55 - - 0 Nug20 2570 2570 15.7 0 15.7 0 2.53 0 119 0 97.8 0 20.73 0 16.06 0 132 0 Nug21 2438 2438 27.5 0 27.5 - - - - - - 0 29.80 0 20.63 - - 0 Nug22 3596 3596 26.5 0 26.5 - - - - - - 0 43.82 0 25.84 - - 0 Nug24 3488 3488 39.7 0 39.7 - - - - - - 0 33.83 0 39.75 - - 0.06 Nug25 3744 3744 38.5 0 38.5 - - - - - - 0 42.10 0 47.66 - - 0 Nug27 5234 5234 51.8 0 51.8 - - - - - - - - 0 80.56 - - 0 Nug28 5166 5166 57.5 0 57.5 - - - - - - - - 0.12 98.33 - - 0 Nug30 6124 6124 136.1 0 136.1 0.42 523 0 181 0.07 354 0.42 109 2.12 117 0.06 887 0.07 Rou12 235528 235528 0.5 0 0.5 - - - - 0 19.6 0 0.30 0 1.06 0 35 0 Rou15 354210 354210 1.1 0 1.1 - - - - 0 34.6 0 0.56 0 2.95 0.71 71 0 Rou20 725522 725522 12.2 0 12.2 0 165 0 245 0.16 75.2 0 1.43 0.02 11.73 0.06 127 0 Scr12 31410 31410 0.7 0 0.7 - - - - 0 18.8 0 0.44 0 1.11 0 38 0 Scr15 51140 51140 1.0 0 1.0 - - - - 0 35.2 0 0.42 0 3.09 0 78 0 Scr20 110030 110030 5.4 0 5.4 0 157 0 46.1 0 79.6 0 1.57 0 12.69 2.13 137 0 Ste36a 9526 9526 623.5 0 623.5 1.81 276 0.76 295 0.27 710 0 221 0 204 - - - Ste36b 15852 15852 763.2 0 763.2 0.92 180 0.25 213 - - 0 235 3.43 222 - - - Ste36c 8239110 8239110 800.4 0 800.4 0.89 142 0.33 321 - - 0 24.07 - - - - - Tho30 149936 149936 306.2 0 306.2 0 216 0 288 0 396 0 132 0.29 119 - - - Tho40 240516 240620 823.1 0.04 823.1 1.17 184 0.66 312 0.32 958 0.05 344 0.53 502 - - - Tho150 8133398 8238058 4590.3 1.29 4590.3 - - - - - - 0.41 729 - - - - - Wil50 48816 48916 829.8 0.06 2522.3 - - - - 0.07 2115 0 695 0.28 1499 - - - Wil100 273038 274446 3330.7 0.34 5272.6 - - - - 0.2 20544 0.15 1252 0.27 51121 - - -
Comparison results of the WFA with other algorithms for Taillard's instances.
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Tai12a 224416 224416 0.3 0 0.3 - - - - - - 0 0.18 0 1.05 0 35 0 Tai12b 39464925 39464925 0.2 0 0.2 - - - - - - 0 0.62 0 1.03 0.03 53 0 Tai15a 388214 388214 2.0 0 2.0 - - - - - - 0 0.69 0 2.99 0.39 73 0.01 Tai15b 51765268 51765268 0.8 0 0.8 - - - - - - 0 0.70 0 3.05 0.47 77 0 Tai17a 491812 491812 4.0 0 4.0 - - - - - - 0.55 0.96 0.38 5.55 0 86 0.56 Tai20a 703482 703482 175.5 0 175.5 0 484 0 160 - - 0.84 1.38 0.47 11.42 0.21 124 0.8 Tai20b 122455319 122455319 4.8 0 4.8 - - - - - - 0 2.70 0 12.52 5.6 167 0 Tai25a 1167256 1169030 236.4 0 1514.3 1.43 355 0.55 206 - - 0.77 3.27 2.00 33.03 - - 1.57 Tai25b 344355646 344355646 70.6 0 70.6 - - - - - - 0 3.77 5.59 35 - - 0 Tai30a 1818146 1832590 437.2 0.57 546.7 1.58 265 1.46 332 - - 1.34 6.72 1.11 83.06 - - 1.37 Tai30b 637117113 637117113 633.8 0 633.8 - - - - - - 0 14.11 2.22 81 - - 0 Tai35a 2422002 2436540 550.9 0.59 1288.4 1.90 531 1.64 232 - - 1.29 12.09 1.24 177 - - 1.3 Tai35b 283315445 283315445 1032.5 0 1032.5 - - - - - - 0 23.90 3.54 186 - - 0.19 Tai40a 3139370 3160484 886.1 0.67 886.1 2.20 325 2.05 253 - - 1.08 18.37 1.85 354 - - 1.7 Tai40b 637250948 637250948 1217 0 1217 - - - - - - 0 36.95 5.60 328 - - 0 Tai50a 4938796 5031472 1113 1.46 2323 - - - - - - 1.31 58.21 2.25 1104 - - 2.48 Tai50b 458821517 458926056 1592 0.02 1592 - - - - - - 0 64.77 0.42 1032 - - 0 Tai60a 7205962 7342990 2165 1.55 3142 - - - - - - 1.79 104 2.75 2740 - - 2.37 Tai60b 608215054 612153786 1866 0.65 1866 - - - - - - 0 148 0.47 2621 - - 0.02 Tai64c 1855928 1855928 1325 0 1325 - - - - - - 0 28.96 0.03 237 - - 0 Tai80a 13511780 13821180 2100 1.87 5707 - - - - - - 1.41 360 2.46 11333 - - 2.37 Tai80b 818415043 827982667 3434 1.17 3434 - - - - - - 0.03 424 2.79 10533 - - 0 Tai100a 21052466 21538854 2450 1.76 8120 - - - - - - 1.29 785 2.33 35781 - - - Tai100b 1185996137 1198498100 4406 1.05 4406 - - - - - - 0.32 855 0.52 34336 - - - Tai150b 498896643 508566248 9117 1.94 9117 - - - - - - 0.20 3414 0.38 290186 - - - Tai256c 44759294 44896638 7539 0.27 12126 - - - - - - 0.16 1956 0.27 73180 - - -
 Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Tai12a 224416 224416 0.3 0 0.3 - - - - - - 0 0.18 0 1.05 0 35 0 Tai12b 39464925 39464925 0.2 0 0.2 - - - - - - 0 0.62 0 1.03 0.03 53 0 Tai15a 388214 388214 2.0 0 2.0 - - - - - - 0 0.69 0 2.99 0.39 73 0.01 Tai15b 51765268 51765268 0.8 0 0.8 - - - - - - 0 0.70 0 3.05 0.47 77 0 Tai17a 491812 491812 4.0 0 4.0 - - - - - - 0.55 0.96 0.38 5.55 0 86 0.56 Tai20a 703482 703482 175.5 0 175.5 0 484 0 160 - - 0.84 1.38 0.47 11.42 0.21 124 0.8 Tai20b 122455319 122455319 4.8 0 4.8 - - - - - - 0 2.70 0 12.52 5.6 167 0 Tai25a 1167256 1169030 236.4 0 1514.3 1.43 355 0.55 206 - - 0.77 3.27 2.00 33.03 - - 1.57 Tai25b 344355646 344355646 70.6 0 70.6 - - - - - - 0 3.77 5.59 35 - - 0 Tai30a 1818146 1832590 437.2 0.57 546.7 1.58 265 1.46 332 - - 1.34 6.72 1.11 83.06 - - 1.37 Tai30b 637117113 637117113 633.8 0 633.8 - - - - - - 0 14.11 2.22 81 - - 0 Tai35a 2422002 2436540 550.9 0.59 1288.4 1.90 531 1.64 232 - - 1.29 12.09 1.24 177 - - 1.3 Tai35b 283315445 283315445 1032.5 0 1032.5 - - - - - - 0 23.90 3.54 186 - - 0.19 Tai40a 3139370 3160484 886.1 0.67 886.1 2.20 325 2.05 253 - - 1.08 18.37 1.85 354 - - 1.7 Tai40b 637250948 637250948 1217 0 1217 - - - - - - 0 36.95 5.60 328 - - 0 Tai50a 4938796 5031472 1113 1.46 2323 - - - - - - 1.31 58.21 2.25 1104 - - 2.48 Tai50b 458821517 458926056 1592 0.02 1592 - - - - - - 0 64.77 0.42 1032 - - 0 Tai60a 7205962 7342990 2165 1.55 3142 - - - - - - 1.79 104 2.75 2740 - - 2.37 Tai60b 608215054 612153786 1866 0.65 1866 - - - - - - 0 148 0.47 2621 - - 0.02 Tai64c 1855928 1855928 1325 0 1325 - - - - - - 0 28.96 0.03 237 - - 0 Tai80a 13511780 13821180 2100 1.87 5707 - - - - - - 1.41 360 2.46 11333 - - 2.37 Tai80b 818415043 827982667 3434 1.17 3434 - - - - - - 0.03 424 2.79 10533 - - 0 Tai100a 21052466 21538854 2450 1.76 8120 - - - - - - 1.29 785 2.33 35781 - - - Tai100b 1185996137 1198498100 4406 1.05 4406 - - - - - - 0.32 855 0.52 34336 - - - Tai150b 498896643 508566248 9117 1.94 9117 - - - - - - 0.20 3414 0.38 290186 - - - Tai256c 44759294 44896638 7539 0.27 12126 - - - - - - 0.16 1956 0.27 73180 - - -
Improved results of the WFA variants for the QAP instances that have not been optimally solved by 2-opt WFA.
 Instances Best known value Random 2-opt WFA Systematic generator 2-opt WFA Random 2-opt mirror WFA WFA-3-opt Best solution Time (s) Best solution Time (s) Best solution Time (s) Best solution Time (s) Lipa50a 62093 62619 872 62703 1158 62666 1507 62593 971 Lipa60a 107218 108103 1337 108172 2508 108070 2754 108070 2529 Lipa80a 253195 254853 2254 254840 3965 254800 3467 254800 3930 Lipa90a 360630 362854 2562 362906 4423 362673 5678 362673 5680 Sko42 15812 15836 1042 15816 1547 15830 1071 15816 1618 Sko49 23386 23510 1098 23460 1772 23474 1868 23460 1897 Sko56 34458 34568 1064 34528 1742 34558 2454 34528 2134 Sko64 48498 48796 1178 48648 2770 48758 2954 48648 3429 Sko72 66256 66660 1620 66570 4096 66820 3425 66570 3702 Sko90 115534 116922 1625 116968 4385 116632 4491 116590 4053 Sko100b 153890 155288 1494 155728 4388 155398 4942 155204 1577 Sko100c 147862 149628 1525 149862 3972 149990 4830 149564 1786 Sko100d 149576 151196 1666 151186 4230 151022 3978 151022 3897 Sko100e 149150 151056 2423 151140 4162 150588 5515 150498 5415 Sko100f 149036 150510 2038 151032 4060 150794 4893 150390 2125 Tai25a 1167256 1169030 236 1169030 570 1167256 1514 1167256 1817 Tai30a 1818146 1832590 437 1828576 547 1830918 2571 1828576 640 Tai35a 2422002 2436540 551 2436458 1288 2443826 2147 2436458 1508 Tai50a 4938796 5031472 1113 5010798 2323 5026322 3595 5010798 2520 Tai60a 7205962 7342990 2165 7317694 3142 7353798 3910 7317694 3074 Tai80a 13511780 13821180 2100 13790286 2647 13764720 5707 13764720 4123 Tai100a 21052466 21538854 2450 21577638 3897 21422344 8120 21422344 6220 Tai256c 44759294 44896638 7539 44879868 12126 44881948 13280 44879868 15916 Wil50 48816 48916 830 48856 3365 48846 2522 48846 2892 Wil100 273038 274446 3331 274244 4278 274608 4234 273980 5273
 Instances Best known value Random 2-opt WFA Systematic generator 2-opt WFA Random 2-opt mirror WFA WFA-3-opt Best solution Time (s) Best solution Time (s) Best solution Time (s) Best solution Time (s) Lipa50a 62093 62619 872 62703 1158 62666 1507 62593 971 Lipa60a 107218 108103 1337 108172 2508 108070 2754 108070 2529 Lipa80a 253195 254853 2254 254840 3965 254800 3467 254800 3930 Lipa90a 360630 362854 2562 362906 4423 362673 5678 362673 5680 Sko42 15812 15836 1042 15816 1547 15830 1071 15816 1618 Sko49 23386 23510 1098 23460 1772 23474 1868 23460 1897 Sko56 34458 34568 1064 34528 1742 34558 2454 34528 2134 Sko64 48498 48796 1178 48648 2770 48758 2954 48648 3429 Sko72 66256 66660 1620 66570 4096 66820 3425 66570 3702 Sko90 115534 116922 1625 116968 4385 116632 4491 116590 4053 Sko100b 153890 155288 1494 155728 4388 155398 4942 155204 1577 Sko100c 147862 149628 1525 149862 3972 149990 4830 149564 1786 Sko100d 149576 151196 1666 151186 4230 151022 3978 151022 3897 Sko100e 149150 151056 2423 151140 4162 150588 5515 150498 5415 Sko100f 149036 150510 2038 151032 4060 150794 4893 150390 2125 Tai25a 1167256 1169030 236 1169030 570 1167256 1514 1167256 1817 Tai30a 1818146 1832590 437 1828576 547 1830918 2571 1828576 640 Tai35a 2422002 2436540 551 2436458 1288 2443826 2147 2436458 1508 Tai50a 4938796 5031472 1113 5010798 2323 5026322 3595 5010798 2520 Tai60a 7205962 7342990 2165 7317694 3142 7353798 3910 7317694 3074 Tai80a 13511780 13821180 2100 13790286 2647 13764720 5707 13764720 4123 Tai100a 21052466 21538854 2450 21577638 3897 21422344 8120 21422344 6220 Tai256c 44759294 44896638 7539 44879868 12126 44881948 13280 44879868 15916 Wil50 48816 48916 830 48856 3365 48846 2522 48846 2892 Wil100 273038 274446 3331 274244 4278 274608 4234 273980 5273
The average-value-based comparison results of the WFA and the PGA for all the QAP instances.
 Instances WFA PGA $\bar{\triangle}$ Time (s) $\bar{\triangle}$ Time (s) Burkard 0.000 28.14 0.006 22.97 Christofides 0.000 23.65 3.834 2.54 Elshafei 0.000 15.20 2.150 44.46 Eschermann 0.042 91.23 0.586 104.06 Hadley 0.000 4.16 0.002 10.80 Krarup 0.000 441.83 1.190 96.97 Li & Pardalos 1.336 1539.66 5.104 161.72 Skorin-Kapov 0.865 2573.38 0.590 1386.65 Nugent 0.000 29.82 0.259 26.94 Roucairol 0.000 4.78 0.523 0.762 Scriabin 0.000 2.40 0.627 0.808 Steinberg 0.000 745.02 2.090 160.15 Thonemann 0.559 1926.51 0.650 401.51 Wilhelm 0.222 3972.06 0.225 973.44 Taillard 0.890 2514.07 0.920 320.17 Average 0.261 927.46 1.250 247.60
 Instances WFA PGA $\bar{\triangle}$ Time (s) $\bar{\triangle}$ Time (s) Burkard 0.000 28.14 0.006 22.97 Christofides 0.000 23.65 3.834 2.54 Elshafei 0.000 15.20 2.150 44.46 Eschermann 0.042 91.23 0.586 104.06 Hadley 0.000 4.16 0.002 10.80 Krarup 0.000 441.83 1.190 96.97 Li & Pardalos 1.336 1539.66 5.104 161.72 Skorin-Kapov 0.865 2573.38 0.590 1386.65 Nugent 0.000 29.82 0.259 26.94 Roucairol 0.000 4.78 0.523 0.762 Scriabin 0.000 2.40 0.627 0.808 Steinberg 0.000 745.02 2.090 160.15 Thonemann 0.559 1926.51 0.650 401.51 Wilhelm 0.222 3972.06 0.225 973.44 Taillard 0.890 2514.07 0.920 320.17 Average 0.261 927.46 1.250 247.60

2018 Impact Factor: 1.025