Figure 1.
An example of solution representation in the WFA for the QAP.
-
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 |
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 & 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] |
Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315 |
| [2] |
R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial & Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173 |
| [3] |
Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211 |
| [4] |
Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129 |
| [5] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
| [6] |
Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control & Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101 |
| [7] |
Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097 |
| [8] |
Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515 |
| [9] |
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 & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 |
| [10] |
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 & Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014 |
| [11] |
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 |
| [12] |
Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 |
| [13] |
Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 |
| [14] |
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 & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 |
| [15] |
Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014 |
| [16] |
K.H. Wong, C. Myburgh, L. Omari. A gradient flow approach for computing jump linear quadratic optimal feedback gains. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 803-808. doi: 10.3934/dcds.2000.6.803 |
| [17] |
Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457 |
| [18] |
Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142 |
| [19] |
Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134 |
| [20] |
Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077 |
2017 Impact Factor: 0.994
Tools
Metrics
Other articles
by authors
[Back to Top]