Figure 1.
An example of solution representation in the WFA for the QAP.
-
Previous Article
Pricing options on investment project expansions under commodity price uncertainty
- JIMO Home
- This Issue
-
Next Article
A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking
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 |
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.
Keywords:
Combinatorial optimization,
quadratic assignment problem,
nature-inspired optimization,
water flow algorithm,
parallel computing.
Mathematics Subject Classification:
Primary: 90C27, 90B80; Secondary: 68W10.
Citation:
Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization,
2019, 15
(1)
: 235-259.
doi: 10.3934/jimo.2018041
![]()
References:
| [1] |
R. Abbiw-Jackson, B. Golden, S. Raghavan and E. Wasil,
A divide-and-conquer local search heuristic for data visualization, Computers & Operations Research, 33 (2006), 3070-3087.
doi: 10.1016/j.cor.2005.01.020. |
| [2] |
R. K. Ahuja, J. B. Orlin and A. Tiwari,
A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27 (2000), 917-934.
doi: 10.1016/S0305-0548(99)00067-2. |
| [3] |
E. M. Arkin, R. Hassin and M. Sviridenko,
Approximating the maximum quadratic assignment problem, Information Processing Letters, 77 (2001), 13-16.
doi: 10.1016/S0020-0190(00)00151-4. |
| [4] |
A. Blanchard, S. Elloumi, A. Faye and N. Wicker,
A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003), 35-49.
|
| [5] |
S. H. Bokhari,
Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987. |
| [6] |
E. S. Buffa, G. C. Armour and T. E. Vollmann,
Allocating facilities with CRAFT, Harvard Business Review, 42 (1964), 136-158.
|
| [7] |
R. E. Burkard, S. E. Karisch and F. Rendl,
QAPLIB -A quadratic assignment problem library, Journal of Global Optimization, 10 (1997), 391-403.
doi: 10.1023/A:1008293323270. |
| [8] |
R. E. Burkard, E. Cela, G. Rote and G. J. Woeginger, The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, in: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, (1996), 204-218. |
| [9] |
E. Cela,
The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998. |
| [10] |
V. M. Demidenko, G. Finke and V. S. Gordon,
Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices, Journal of Mathematical Modeling and Algorithms, 5 (2006), 167-187.
doi: 10.1007/s10852-005-9013-2. |
| [11] |
M. Dorigo,
Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992. |
| [12] |
E. Duman and I. Or,
The quadratic assignment problem in the context of the printed circuit board assembly process, Computers & Operations Research, 34 (2007), 163-179.
doi: 10.1016/j.cor.2005.05.004. |
| [13] |
B. Eschermann and H. J. Wunderlich, Optimized synthesis of self-testable finite state machines, in: Proceedings of the 20th International Symposium Fault-Tolerant Computing (FTCS 20), Newcastle Upon Tyne, UK, (1990), 390-397.
doi: 10.1109/FTCS.1990.89393. |
| [14] |
H. Eskandar, A. Sadollah, A. Bahreininejad and M. Hamdi,
Water cycle algorithm-A novel metaheuristic optimization method for solving constrained engineering optimization problems, Computers & Structures, 110/111 (2012), 151-166.
|
| [15] |
R. N. Gasimov and O. Ustun,
Solving the quadratic assignment problem using F-MSG algorithm, Journal of Industrial and Management Optimization, 3 (2007), 173-191.
doi: 10.3934/jimo.2007.3.173. |
| [16] |
G. Gutin and A. Yeo,
Polynomial approximation algorithms for TSP and QAP with a factorial domination number, Discrete Applied Mathematics, 119 (2002), 107-116.
doi: 10.1016/S0166-218X(01)00267-0. |
| [17] |
P. M. Hahn, W. L. Hightower, T. A. Johnson, M. Guignard-Spielberg and C. Roucairol,
Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslavian Journal of Operational Research, 11 (2001), 41-60.
|
| [18] |
J. H. Holland,
Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975. |
| [19] |
L. J. Hubert,
Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987. |
| [20] |
J. Kennedy and R. C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, (1995), 1942-1948.
doi: 10.1109/ICNN.1995.488968. |
| [21] |
I. K. Kim, D. W. Jung and R. H. Park,
Document image binarization based on topographic analysis using a water flow model, Pattern Recognition, 35 (2002), 265-277.
doi: 10.1016/S0031-3203(01)00027-9. |
| [22] |
Y. Li, P. M. Pardalos and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems(eds. P. M. Pardalos and H. Wolkowicz), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16 (1994), 237-261. |
| [23] |
M. Lim, Y. Yuan and S. Omatu,
Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems, Computational Optimization and Applications, 23 (2002), 47-64.
doi: 10.1023/A:1019972523847. |
| [24] |
V. Maniezzo and A. Colorni,
The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11 (1999), 769-778.
doi: 10.1109/69.806935. |
| [25] |
P. Merz and B. Freisleben,
Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, IEEE Transactions on Evolutionary Computation, 4 (2000), 337-352.
|
| [26] |
S. Nakrani and C. Tovey,
On honey bees and dynamic server allocation in internet hosting centers, Adaptive Behaviors, 12 (2004), 223-240.
doi: 10.1177/105971230401200308. |
| [27] |
H. H. Oh, K. T. Lim and S. I. Chien,
An improved binarization algorithm based on a water flow model for document image with inhomogeneous backgrounds, Pattern Recognition, 38 (2005), 2612-2625.
doi: 10.1016/j.patcog.2004.11.025. |
| [28] |
A. S. Ramkumar, S. G. Ponnambalam and N. Jawahar,
A population-based hybrid ant system for quadratic assignment formulations in facility layout design, International Journal of Advanced Manufacturing Technology, 44 (2009), 548-558.
doi: 10.1007/s00170-008-1849-y. |
| [29] |
A. S. Ramkumar, S. G. Ponnambalam and N. Jawahar,
Iterated fast local search algorithm for solving quadratic assignment problems, Robotics and Computer-Integrated Manufacturing, 24 (2008), 392-401.
doi: 10.1016/j.rcim.2007.01.004. |
| [30] |
D. F. Rossin, M. C. Springer and B. D. Klein,
New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis, Computers & Industrial Engineering, 36 (1999), 585-602.
doi: 10.1016/S0360-8352(99)00153-9. |
| [31] |
S. Sahni and T. Gonzalez,
P-complete approximation problems, Journal of the ACM, 23 (1976), 555-565.
doi: 10.1145/321958.321975. |
| [32] |
H. Q. Saremi, B. Abedin and A. M. Kermani,
Website structure improvement: Quadratic assignment problem approach and ant colony metaheuristic technique, Applied Mathematics and Computation, 195 (2008), 285-298.
doi: 10.1016/j.amc.2007.04.095. |
| [33] |
A. Shukla, A modified bat algorithm for the quadratic assignment problem, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 15), Sendai, Japan, (2015), 486-490.
doi: 10.1109/CEC.2015.7256929. |
| [34] |
H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231. |
| [35] |
H. Shah-Hosseini,
Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem, International Journal of Intelligent Computing and Cybernetics, 1 (2008), 193-212.
doi: 10.1108/17563780810874717. |
| [36] |
H. Shah-Hosseini,
The intelligent water drops algorithm: A nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computation, 1 (2009), 71-79.
|
| [37] |
S. P. Singh and R. R. K. Sharma,
Two-level modified simulated annealing based approach for solving facility layout problem, International Journal of Production Research, 46 (2008), 3563-3582.
|
| [38] |
E. Taillard,
Comparison of iterative searches for the quadratic assignment problem, Location Science, 3 (1995), 87-105.
doi: 10.1016/0966-8349(95)00008-6. |
| [39] |
T. H. Tran and K. M. Ng,
A water flow algorithm for flexible flow shop scheduling with intermediate buffers, Journal of Scheduling, 14 (2011), 483-500.
doi: 10.1007/s10951-010-0205-x. |
| [40] |
T. H. Tran and K. M. Ng,
A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems, Engineering Optimization, 45 (2013), 483-502.
doi: 10.1080/0305215X.2012.685072. |
| [41] |
K. Y. Wong and P. C. See,
A hybrid ant colony optimization algorithm for solving facility layout problems formulated as quadratic assignment problems, Engineering Computations: International Journal for Computer-Aided Engineering and Software, 27 (2010), 117-128.
|
| [42] |
T. H. Wu, S. H. Chung and C. C. Chang,
A water flow-like algorithm for manufacturing cell formation problems, European Journal of Operational Research, 205 (2010), 346-360.
doi: 10.1016/j.ejor.2010.01.020. |
| [43] |
X. Yang, Q. Lu, C. Li and X. Liao,
Biological computation of the solution to the quadratic assignment problem, Applied Mathematics and Computation, 200 (2008), 369-377.
doi: 10.1016/j.amc.2007.11.016. |
| [44] |
F. C. Yang and Y. P. Wang,
Water flow-like algorithm for object grouping problems, Journal of the Chinese Institute of Industrial Engineers, 24 (2007), 475-488.
|
| [45] |
Y. J. Zheng,
Water wave optimization: A new nature-inspired metaheuristic, Computers & Operations Research, 55 (2015), 1-11.
doi: 10.1016/j.cor.2014.10.008. |
show all references
References:
| [1] |
R. Abbiw-Jackson, B. Golden, S. Raghavan and E. Wasil,
A divide-and-conquer local search heuristic for data visualization, Computers & Operations Research, 33 (2006), 3070-3087.
doi: 10.1016/j.cor.2005.01.020. |
| [2] |
R. K. Ahuja, J. B. Orlin and A. Tiwari,
A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27 (2000), 917-934.
doi: 10.1016/S0305-0548(99)00067-2. |
| [3] |
E. M. Arkin, R. Hassin and M. Sviridenko,
Approximating the maximum quadratic assignment problem, Information Processing Letters, 77 (2001), 13-16.
doi: 10.1016/S0020-0190(00)00151-4. |
| [4] |
A. Blanchard, S. Elloumi, A. Faye and N. Wicker,
A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003), 35-49.
|
| [5] |
S. H. Bokhari,
Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987. |
| [6] |
E. S. Buffa, G. C. Armour and T. E. Vollmann,
Allocating facilities with CRAFT, Harvard Business Review, 42 (1964), 136-158.
|
| [7] |
R. E. Burkard, S. E. Karisch and F. Rendl,
QAPLIB -A quadratic assignment problem library, Journal of Global Optimization, 10 (1997), 391-403.
doi: 10.1023/A:1008293323270. |
| [8] |
R. E. Burkard, E. Cela, G. Rote and G. J. Woeginger, The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, in: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, Vancouver, British Columbia, Canada, (1996), 204-218. |
| [9] |
E. Cela,
The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998. |
| [10] |
V. M. Demidenko, G. Finke and V. S. Gordon,
Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices, Journal of Mathematical Modeling and Algorithms, 5 (2006), 167-187.
doi: 10.1007/s10852-005-9013-2. |
| [11] |
M. Dorigo,
Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992. |
| [12] |
E. Duman and I. Or,
The quadratic assignment problem in the context of the printed circuit board assembly process, Computers & Operations Research, 34 (2007), 163-179.
doi: 10.1016/j.cor.2005.05.004. |
| [13] |
B. Eschermann and H. J. Wunderlich, Optimized synthesis of self-testable finite state machines, in: Proceedings of the 20th International Symposium Fault-Tolerant Computing (FTCS 20), Newcastle Upon Tyne, UK, (1990), 390-397.
doi: 10.1109/FTCS.1990.89393. |
| [14] |
H. Eskandar, A. Sadollah, A. Bahreininejad and M. Hamdi,
Water cycle algorithm-A novel metaheuristic optimization method for solving constrained engineering optimization problems, Computers & Structures, 110/111 (2012), 151-166.
|
| [15] |
R. N. Gasimov and O. Ustun,
Solving the quadratic assignment problem using F-MSG algorithm, Journal of Industrial and Management Optimization, 3 (2007), 173-191.
doi: 10.3934/jimo.2007.3.173. |
| [16] |
G. Gutin and A. Yeo,
Polynomial approximation algorithms for TSP and QAP with a factorial domination number, Discrete Applied Mathematics, 119 (2002), 107-116.
doi: 10.1016/S0166-218X(01)00267-0. |
| [17] |
P. M. Hahn, W. L. Hightower, T. A. Johnson, M. Guignard-Spielberg and C. Roucairol,
Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslavian Journal of Operational Research, 11 (2001), 41-60.
|
| [18] |
J. H. Holland,
Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975. |
| [19] |
L. J. Hubert,
Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987. |
| [20] |
J. Kennedy and R. C. Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, (1995), 1942-1948.
doi: 10.1109/ICNN.1995.488968. |
| [21] |
I. K. Kim, D. W. Jung and R. H. Park,
Document image binarization based on topographic analysis using a water flow model, Pattern Recognition, 35 (2002), 265-277.
doi: 10.1016/S0031-3203(01)00027-9. |
| [22] |
Y. Li, P. M. Pardalos and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems(eds. P. M. Pardalos and H. Wolkowicz), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16 (1994), 237-261. |
| [23] |
M. Lim, Y. Yuan and S. Omatu,
Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems, Computational Optimization and Applications, 23 (2002), 47-64.
doi: 10.1023/A:1019972523847. |
| [24] |
V. Maniezzo and A. Colorni,
The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11 (1999), 769-778.
doi: 10.1109/69.806935. |
| [25] |
P. Merz and B. Freisleben,
Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, IEEE Transactions on Evolutionary Computation, 4 (2000), 337-352.
|
| [26] |
S. Nakrani and C. Tovey,
On honey bees and dynamic server allocation in internet hosting centers, Adaptive Behaviors, 12 (2004), 223-240.
doi: 10.1177/105971230401200308. |
| [27] |
H. H. Oh, K. T. Lim and S. I. Chien,
An improved binarization algorithm based on a water flow model for document image with inhomogeneous backgrounds, Pattern Recognition, 38 (2005), 2612-2625.
doi: 10.1016/j.patcog.2004.11.025. |
| [28] |
A. S. Ramkumar, S. G. Ponnambalam and N. Jawahar,
A population-based hybrid ant system for quadratic assignment formulations in facility layout design, International Journal of Advanced Manufacturing Technology, 44 (2009), 548-558.
doi: 10.1007/s00170-008-1849-y. |
| [29] |
A. S. Ramkumar, S. G. Ponnambalam and N. Jawahar,
Iterated fast local search algorithm for solving quadratic assignment problems, Robotics and Computer-Integrated Manufacturing, 24 (2008), 392-401.
doi: 10.1016/j.rcim.2007.01.004. |
| [30] |
D. F. Rossin, M. C. Springer and B. D. Klein,
New complexity measures for the facility layout problem: An empirical study using traditional and neural network analysis, Computers & Industrial Engineering, 36 (1999), 585-602.
doi: 10.1016/S0360-8352(99)00153-9. |
| [31] |
S. Sahni and T. Gonzalez,
P-complete approximation problems, Journal of the ACM, 23 (1976), 555-565.
doi: 10.1145/321958.321975. |
| [32] |
H. Q. Saremi, B. Abedin and A. M. Kermani,
Website structure improvement: Quadratic assignment problem approach and ant colony metaheuristic technique, Applied Mathematics and Computation, 195 (2008), 285-298.
doi: 10.1016/j.amc.2007.04.095. |
| [33] |
A. Shukla, A modified bat algorithm for the quadratic assignment problem, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 15), Sendai, Japan, (2015), 486-490.
doi: 10.1109/CEC.2015.7256929. |
| [34] |
H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231. |
| [35] |
H. Shah-Hosseini,
Intelligent water drops algorithm: A new optimization method for solving the multiple knapsack problem, International Journal of Intelligent Computing and Cybernetics, 1 (2008), 193-212.
doi: 10.1108/17563780810874717. |
| [36] |
H. Shah-Hosseini,
The intelligent water drops algorithm: A nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computation, 1 (2009), 71-79.
|
| [37] |
S. P. Singh and R. R. K. Sharma,
Two-level modified simulated annealing based approach for solving facility layout problem, International Journal of Production Research, 46 (2008), 3563-3582.
|
| [38] |
E. Taillard,
Comparison of iterative searches for the quadratic assignment problem, Location Science, 3 (1995), 87-105.
doi: 10.1016/0966-8349(95)00008-6. |
| [39] |
T. H. Tran and K. M. Ng,
A water flow algorithm for flexible flow shop scheduling with intermediate buffers, Journal of Scheduling, 14 (2011), 483-500.
doi: 10.1007/s10951-010-0205-x. |
| [40] |
T. H. Tran and K. M. Ng,
A hybrid water flow algorithm for multi-objective flexible flow shop scheduling problems, Engineering Optimization, 45 (2013), 483-502.
doi: 10.1080/0305215X.2012.685072. |
| [41] |
K. Y. Wong and P. C. See,
A hybrid ant colony optimization algorithm for solving facility layout problems formulated as quadratic assignment problems, Engineering Computations: International Journal for Computer-Aided Engineering and Software, 27 (2010), 117-128.
|
| [42] |
T. H. Wu, S. H. Chung and C. C. Chang,
A water flow-like algorithm for manufacturing cell formation problems, European Journal of Operational Research, 205 (2010), 346-360.
doi: 10.1016/j.ejor.2010.01.020. |
| [43] |
X. Yang, Q. Lu, C. Li and X. Liao,
Biological computation of the solution to the quadratic assignment problem, Applied Mathematics and Computation, 200 (2008), 369-377.
doi: 10.1016/j.amc.2007.11.016. |
| [44] |
F. C. Yang and Y. P. Wang,
Water flow-like algorithm for object grouping problems, Journal of the Chinese Institute of Industrial Engineers, 24 (2007), 475-488.
|
| [45] |
Y. J. Zheng,
Water wave optimization: A new nature-inspired metaheuristic, Computers & Operations Research, 55 (2015), 1-11.
doi: 10.1016/j.cor.2014.10.008. |
Figure 2.
The erosion process in exploitation phase of the WFA.
Figure 3.
Flow chart of the WFA for the QAP.
Figure 4.
Comparison of the WFA with other algorithms on (a). Average percentage difference; and (b). The number of the best known solutions obtained.
Table 1.
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 |
| 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 |
| 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 |
| 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 |
| 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. |
Table 2.
The parameter sets of the WFA for the QAP benchmark instances.
| Benchmarks | 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 | 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 | |
Table 3.
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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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 | ||||||||
Table 4.
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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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 | ||||||||
Table 5.
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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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 | - | - | - | ||||||||
Table 6.
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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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 | - | - | - | ||||||||
Table 7.
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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | Time (s) | ||||||||||||||||||
| 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 | - | - | - | ||||||||
Table 8.
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 | |||
Table 9.
The average-value-based comparison results of the WFA and the PGA for all the QAP instances.
| Instances | WFA | PGA | |||
| Time (s) | 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 | |||
| Time (s) | 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 | |
| [1] |
Adrian Korban, Serap Şahinkaya, Deniz Ustun. A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022033 |
| [2] |
Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks and Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315 |
| [3] |
Sen Zhang, Guo Zhou, Yongquan Zhou, Qifang Luo. Quantum-inspired satin bowerbird algorithm with Bloch spherical search for constrained structural optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3509-3523. doi: 10.3934/jimo.2020130 |
| [4] |
R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial and Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173 |
| [5] |
Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003 |
| [6] |
Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial and Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211 |
| [7] |
Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129 |
| [8] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
| [9] |
Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control and Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101 |
| [10] |
Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial and Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515 |
| [11] |
Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097 |
| [12] |
Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 |
| [13] |
Alireza Goli, Hasan Khademi Zare, Reza Tavakkoli-Moghaddam, Ahmad Sadeghieh. Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014 |
| [14] |
Radu C. Cascaval, Ciro D'Apice, Maria Pia D'Arienzo, Rosanna Manzo. Flow optimization in vascular networks. Mathematical Biosciences & Engineering, 2017, 14 (3) : 607-624. doi: 10.3934/mbe.2017035 |
| [15] |
Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 |
| [16] |
Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046 |
| [17] |
Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial and Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 |
| [18] |
Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 |
| [19] |
K.H. Wong, C. Myburgh, L. Omari. A gradient flow approach for computing jump linear quadratic optimal feedback gains. Discrete and Continuous Dynamical Systems, 2000, 6 (4) : 803-808. doi: 10.3934/dcds.2000.6.803 |
| [20] |
Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]