American Institute of Mathematical Sciences

Advanced
  • 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

Kien Ming Ng 1, and  Trung Hieu Tran 2,,

1. 

Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 119260
2. 

Laboratory for Urban Complexity and Sustainability, University of Nottingham, Nottingham NG7 2RB, UK

* Corresponding author: Trung Hieu Tran

Received  May 2017 Revised  December 2017 Published  April 2018

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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

A. Blanchard, S. Elloumi, A. Faye and N. Wicker, A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003), 35-49.   Google Scholar

[5]

S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987.  Google Scholar

[6]

E. S. Buffa, G. C. Armour and T. E. Vollmann, Allocating facilities with CRAFT, Harvard Business Review, 42 (1964), 136-158.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998.  Google Scholar

[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.  Google Scholar

[11]

M. Dorigo, Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[18]

J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.  Google Scholar

[19]

L. J. Hubert, Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the ACM, 23 (1976), 555-565.  doi: 10.1145/321958.321975.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

A. Blanchard, S. Elloumi, A. Faye and N. Wicker, A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003), 35-49.   Google Scholar

[5]

S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987.  Google Scholar

[6]

E. S. Buffa, G. C. Armour and T. E. Vollmann, Allocating facilities with CRAFT, Harvard Business Review, 42 (1964), 136-158.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998.  Google Scholar

[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.  Google Scholar

[11]

M. Dorigo, Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[18]

J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.  Google Scholar

[19]

L. J. Hubert, Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[31]

S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the ACM, 23 (1976), 555-565.  doi: 10.1145/321958.321975.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

Figure 1.  An example of solution representation in the WFA for the QAP.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The erosion process in exploitation phase of the WFA.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Flow chart of the WFA for the QAP.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Comparison of the WFA with other algorithms on (a). Average percentage difference; and (b). The number of the best known solutions obtained.
Figure Options

Download full-size image

Download as PowerPoint slide

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 $n>30$ effectively or extensive computation time may be required.
Ant system [24] 33 / 44 0.28% 2.79%
(chrxxx instance)		 40 Computation time of local search is rather onerous [24], and thus does not solve instances of size $n>40$ efficiently.
Population based hybrid ant system [28] 80 / 110 0.41% 14.25%
(chrxxx instance)		 100 Population size increases significantly according to instance size [28], leading to difficulty for solving large instances.
Greedy genetic algorithm [2] 58 / 87 0.17% 5.13%
(chrxxx instance)		 100 Although greedy approach improves the quality of individuals, this may affect the overall performance of the genetic algorithm [2]. In addition, using 2-exchange local search could limit the capability for searching better solutions.
Greedy randomized adaptive search procedure [22] 27 / 44 0.69% 4.64%
(chrxxx instance)		 128 The algorithm can be applied only to symmetric QAP instances [2].
Iterated fast local search [29] 72 / 130 0.87% 20.33%
(lipaxxx instance)		 256 2-opt local search of the algorithm could not solve lipaxxx instances of the QAPLIB effectively [29] due to limit in search space.
Hybrid genetic algorithm [23] 84 / 130 0.51% 16.56%
(lipaxxx instance)		 256 2-gene exchange local search could not solve lipaxxx instances of the QAPLIB effectively [23] due to limit in search space.
Table Options

Download as excel

Metaheuristic algorithms No. of best known solutions found / No. of tested instances Average difference Maximum difference Maximum size of instance Drawbacks
Simulated annealing [37] 26 / 40 0.99% 11.51%
(chrxxx instance)		 30 Solving QAP relaxation to construct initial solution for simulated annealing depends on the capability of solvers used [37]. Thus, the algorithm may not solve instances of size $n>30$ effectively or extensive computation time may be required.
Ant system [24] 33 / 44 0.28% 2.79%
(chrxxx instance)		 40 Computation time of local search is rather onerous [24], and thus does not solve instances of size $n>40$ efficiently.
Population based hybrid ant system [28] 80 / 110 0.41% 14.25%
(chrxxx instance)		 100 Population size increases significantly according to instance size [28], leading to difficulty for solving large instances.
Greedy genetic algorithm [2] 58 / 87 0.17% 5.13%
(chrxxx instance)		 100 Although greedy approach improves the quality of individuals, this may affect the overall performance of the genetic algorithm [2]. In addition, using 2-exchange local search could limit the capability for searching better solutions.
Greedy randomized adaptive search procedure [22] 27 / 44 0.69% 4.64%
(chrxxx instance)		 128 The algorithm can be applied only to symmetric QAP instances [2].
Iterated fast local search [29] 72 / 130 0.87% 20.33%
(lipaxxx instance)		 256 2-opt local search of the algorithm could not solve lipaxxx instances of the QAPLIB effectively [29] due to limit in search space.
Hybrid genetic algorithm [23] 84 / 130 0.51% 16.56%
(lipaxxx instance)		 256 2-gene exchange local search could not solve lipaxxx instances of the QAPLIB effectively [23] due to limit in search space.
Table 2.  The parameter sets of the WFA for the QAP benchmark instances.
Benchmarks $n$ Parameter values
MaxCloud MaxPop MaxUIE MinEro
Burkard 26 5 16 10 2
Christofides 12 - 20 10 16 10 2
22 15 16 10 2
25 20 16 10 2
Elshafei 19 10 16 10 2
Eschermann 16, 64 2 8 5 2
32 (a, b) 5 16 10 2
32 (c, e, g) 2 8 5 2
32 (d, h) 2 16 10 2
128 5 16 5 3
Hadley 12 - 20 10 16 10 2
Krarup 30, 32 20 16 10 2
Li & Pardalos 20, 30 10 16 10 2
40, 50, 60 10 24 10 2
70 10 24 15 2
80, 90 20 24 10 2
Nugent 12 - 28 10 16 5 2
30 20 16 10 2
Roucairol 12, 15 5 16 10 2
20 10 24 10 2
Scriabin 12, 15, 20 5 16 10 2
Skorin-Kapov 42 - 64 15 16 10 2
72, 81, 90 10 24 15 2
100 10 16 10 2
Steinberg 36 20 16 10 2
Taillard
 (Taixxxa) 12 5 16 10 2
15, 17 5 24 10 2
20 - 35 20 24 10 2
40, 50 20 24 15 2
60, 80,100 10 24 10 2
 (Taixxxb) 12 - 20 5 8 10 2
25 10 16 10 2
30, 35, 40 20 16 10 2
50, 60, 80 10 16 15 2
100 5 24 10 2
150 5 16 5 2
 (Taixxxc) 64 10 24 10 2
256 2 8 5 2
Thonemann 30 10 24 10 2
40 20 16 10 2
150 5 16 10 2
Wilhelm 50 15 24 10 2
100 10 16 10 2
Table Options

Download as excel

Benchmarks $n$ Parameter values
MaxCloud MaxPop MaxUIE MinEro
Burkard 26 5 16 10 2
Christofides 12 - 20 10 16 10 2
22 15 16 10 2
25 20 16 10 2
Elshafei 19 10 16 10 2
Eschermann 16, 64 2 8 5 2
32 (a, b) 5 16 10 2
32 (c, e, g) 2 8 5 2
32 (d, h) 2 16 10 2
128 5 16 5 3
Hadley 12 - 20 10 16 10 2
Krarup 30, 32 20 16 10 2
Li & Pardalos 20, 30 10 16 10 2
40, 50, 60 10 24 10 2
70 10 24 15 2
80, 90 20 24 10 2
Nugent 12 - 28 10 16 5 2
30 20 16 10 2
Roucairol 12, 15 5 16 10 2
20 10 24 10 2
Scriabin 12, 15, 20 5 16 10 2
Skorin-Kapov 42 - 64 15 16 10 2
72, 81, 90 10 24 15 2
100 10 16 10 2
Steinberg 36 20 16 10 2
Taillard
 (Taixxxa) 12 5 16 10 2
15, 17 5 24 10 2
20 - 35 20 24 10 2
40, 50 20 24 15 2
60, 80,100 10 24 10 2
 (Taixxxb) 12 - 20 5 8 10 2
25 10 16 10 2
30, 35, 40 20 16 10 2
50, 60, 80 10 16 15 2
100 5 24 10 2
150 5 16 5 2
 (Taixxxc) 64 10 24 10 2
256 2 8 5 2
Thonemann 30 10 24 10 2
40 20 16 10 2
150 5 16 10 2
Wilhelm 50 15 24 10 2
100 10 16 10 2
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) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Bur26a 5426670 5426670 30.0 0 30.0 0 11.38 0 21.07 0 235 0 125 0 61.27 - - 0
Bur26b 3817852 3817852 23.0 0 23.0 0 59.45 0 35.03 0 225 0 9.5 0 60.27 - - 0
Bur26c 5426795 5426795 16.0 0 16.0 0 5.16 0 19.09 0 227 0 7.42 0 57.78 - - 0
Bur26d 3821225 3821225 29.0 0 29.0 0 15.12 0 19.40 0 213 0 8.42 0 61.27 - - 0
Bur26e 5386879 5386879 32.0 0 32.0 0 17.63 0 20.53 0 218 0 10.03 0 57.83 - - 0
Bur26f 3782044 3782044 44.0 0 44.0 0 5.05 0 11.23 0 104 0 6.68 0 59.19 - - 0
Bur26g 10117172 10117172 26.0 0 26.0 0 22.58 0 18.67 0 194 0 9.99 0 57.72 - - 0
Bur26h 7098658 7098658 20.0 0 20.0 0 37.58 0 5.67 0 204 0 6.82 0 57.47 - - 0
Chr12a 9552 9552 0.6 0 0.6 - - - - 0 19.6 0 0.54 0 1.09 0 40 0
Chr12b 9742 9742 0.5 0 0.5 - - - - 0 18.4 0 0.42 0 1.11 0 41 0
Chr12c 11156 11156 0.6 0 0.6 - - - - 0 20.2 0 1.29 0 1.02 0.26 38 0.27
Chr15a 9896 9896 3.2 0 3.2 - - - - 0.4 40.6 0 1.50 0 2.97 0 69 0
Chr15b 7990 7990 4.1 0 4.1 - - - - 0 41.8 0 1.31 0 3.08 2.7 72 0
Chr15c 9504 9504 4.0 0 4.0 - - - - 0 44 0 1.30 0 2.64 11.5 69 6.36
Chr18a 11098 11098 9.3 0 9.3 - - - - 0.4 79 0 2.11 5.14 7.23 1.71 103 14.25
Chr18b 1534 1534 10.2 0 10.2 - - - - 0 78.8 0 2.62 0 5.30 0 105 0
Chr20a 2192 2192 32.0 0 32.0 1.82 509 0 331 0 94.6 0.18 3.61 4.38 10.95 0 131 1.82
Chr20b 2298 2298 27.0 0 27.0 5.92 195 2.79 375 5.13 96.4 3.12 3.32 5.40 8.61 0 127 4.96
Chr20c 14142 14142 15.0 0 15.0 0.00 9.23 0 29.49 0 97.8 4.51 1.77 0 13.55 0 140 0
Chr22a 6156 6156 60.0 0 60.0 2.31 201 0 315 0.75 146 0 4.52 0.88 19.11 5.7 164 0.32
Chr22b 6194 6194 58.0 0 58.0 2.58 213 0.97 162 0 152 1.46 5.26 1.68 17.00 8.5 163 0
Chr25a 3796 3796 95.0 0 95.0 2.32 115 0 236 0 194 2.27 5.97 11.17 33.59 0 591 0
Table Options

Download as excel

Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Bur26a 5426670 5426670 30.0 0 30.0 0 11.38 0 21.07 0 235 0 125 0 61.27 - - 0
Bur26b 3817852 3817852 23.0 0 23.0 0 59.45 0 35.03 0 225 0 9.5 0 60.27 - - 0
Bur26c 5426795 5426795 16.0 0 16.0 0 5.16 0 19.09 0 227 0 7.42 0 57.78 - - 0
Bur26d 3821225 3821225 29.0 0 29.0 0 15.12 0 19.40 0 213 0 8.42 0 61.27 - - 0
Bur26e 5386879 5386879 32.0 0 32.0 0 17.63 0 20.53 0 218 0 10.03 0 57.83 - - 0
Bur26f 3782044 3782044 44.0 0 44.0 0 5.05 0 11.23 0 104 0 6.68 0 59.19 - - 0
Bur26g 10117172 10117172 26.0 0 26.0 0 22.58 0 18.67 0 194 0 9.99 0 57.72 - - 0
Bur26h 7098658 7098658 20.0 0 20.0 0 37.58 0 5.67 0 204 0 6.82 0 57.47 - - 0
Chr12a 9552 9552 0.6 0 0.6 - - - - 0 19.6 0 0.54 0 1.09 0 40 0
Chr12b 9742 9742 0.5 0 0.5 - - - - 0 18.4 0 0.42 0 1.11 0 41 0
Chr12c 11156 11156 0.6 0 0.6 - - - - 0 20.2 0 1.29 0 1.02 0.26 38 0.27
Chr15a 9896 9896 3.2 0 3.2 - - - - 0.4 40.6 0 1.50 0 2.97 0 69 0
Chr15b 7990 7990 4.1 0 4.1 - - - - 0 41.8 0 1.31 0 3.08 2.7 72 0
Chr15c 9504 9504 4.0 0 4.0 - - - - 0 44 0 1.30 0 2.64 11.5 69 6.36
Chr18a 11098 11098 9.3 0 9.3 - - - - 0.4 79 0 2.11 5.14 7.23 1.71 103 14.25
Chr18b 1534 1534 10.2 0 10.2 - - - - 0 78.8 0 2.62 0 5.30 0 105 0
Chr20a 2192 2192 32.0 0 32.0 1.82 509 0 331 0 94.6 0.18 3.61 4.38 10.95 0 131 1.82
Chr20b 2298 2298 27.0 0 27.0 5.92 195 2.79 375 5.13 96.4 3.12 3.32 5.40 8.61 0 127 4.96
Chr20c 14142 14142 15.0 0 15.0 0.00 9.23 0 29.49 0 97.8 4.51 1.77 0 13.55 0 140 0
Chr22a 6156 6156 60.0 0 60.0 2.31 201 0 315 0.75 146 0 4.52 0.88 19.11 5.7 164 0.32
Chr22b 6194 6194 58.0 0 58.0 2.58 213 0.97 162 0 152 1.46 5.26 1.68 17.00 8.5 163 0
Chr25a 3796 3796 95.0 0 95.0 2.32 115 0 236 0 194 2.27 5.97 11.17 33.59 0 591 0
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) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Els19 17212548 17212548 15 0 15 - - - - 0 80.6 0 44.46 - - - - 0
Esc16a 68 68 0.1 0 0.1 - - - - 0 47.4 0 5.13 0 3.17 0 61 0
Esc16b 292 292 0.1 0 0.1 - - - - 0 48.2 0 0.19 0 2.75 0 60 0
Esc16c 160 160 0.1 0 0.1 - - - - 0 53.4 0 0.44 0 4.03 0 68 0
Esc16d 16 16 0.1 0 0.1 - - - - 0 53.2 0 0.50 0 3.98 - - 0
Esc16e 28 28 0.1 0 0.1 - - - - 0 46.8 0 0.32 0 2.28 - - 0
Esc16f 0 0 0.1 0 0.1 - - - - 0 46.0 - - 0 1.11 - - 0
Esc16g 26 26 0.1 0 0.1 - - - - 0 49.8 0 0.29 0 2.77 - - 0
Esc16h 996 996 0.1 0 0.1 - - - - 0 48.0 0 0.22 0 2.13 0 65 0
Esc16i 14 14 0.1 0 0.1 - - - - 0 51.6 0 0.16 0 2.05 - - 0
Esc16j 8 8 0.1 0 0.1 - - - - 0 402 0 0.32 0 2.91 - - 0
Esc32a 130 130 190 0 190 1.54 7.03 0 226 0 382 1.52 97.04 0 137 - - 0
Esc32b 168 168 53 0 53 0 2.80 0 40.59 0 400 0 33.61 0 110 - - 0
Esc32c 642 642 1.2 0 1.2 0 0 0 0.08 0 389 0 2.01 0 54.7 - - 0
Esc32d 200 200 11 0 11 0 1.92 0 2.13 0 353 0 2.76 0 74.3 - - 0
Esc32e 2 2 0.8 0 0.8 0 0 0 0.05 0 370 0 0.66 0 46.09 - - 0
Esc32g 6 6 0.9 0 0.9 0 0 0 0.07 0 371 0 1.27 0 28.41 - - 0
Esc32h 438 438 31 0 31 0 3.41 0 2.64 0 349 0 6.54 0 85.75 - - 0
Esc64a 116 116 9.6 0 9.6 - - - - 0 2631 0 194 0 1522 - - 0
Esc128 64 64 1395 0 1395 - - - - - - 0 1631 - - - - 0
Had12 1652 1652 0.7 0 0.7 - - - - - - 0 4.27 0 0.97 0 41 0
Had14 2724 2724 1.5 0 1.5 - - - - - - 0 10.25 0 1.97 0 64 0
Had16 3720 3720 2.2 0 2.2 - - - - - - 0 5.38 0.05 3.64 0 88 0
Had18 5358 5358 4.9 0 4.9 - - - - - - 0 18.54 0 6.52 0 118 0
Had20 6922 6922 11.2 0 11.2 0 2.8 0 159 - - 0 15.26 0 10.58 0 148 0
Kra30a 88900 88900 430 0 430 0 292 0 199 0 301 0.89 71 1.34 106 - - 0
Kra30b 91420 91420 441 0 441 0.32 268 0 140 0 331 0 123 0.13 102 - - 0.08
Kra32 88700 88700 432 0 432 - - - - - - - - 0 172 - - 0
Table Options

Download as excel

Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Els19 17212548 17212548 15 0 15 - - - - 0 80.6 0 44.46 - - - - 0
Esc16a 68 68 0.1 0 0.1 - - - - 0 47.4 0 5.13 0 3.17 0 61 0
Esc16b 292 292 0.1 0 0.1 - - - - 0 48.2 0 0.19 0 2.75 0 60 0
Esc16c 160 160 0.1 0 0.1 - - - - 0 53.4 0 0.44 0 4.03 0 68 0
Esc16d 16 16 0.1 0 0.1 - - - - 0 53.2 0 0.50 0 3.98 - - 0
Esc16e 28 28 0.1 0 0.1 - - - - 0 46.8 0 0.32 0 2.28 - - 0
Esc16f 0 0 0.1 0 0.1 - - - - 0 46.0 - - 0 1.11 - - 0
Esc16g 26 26 0.1 0 0.1 - - - - 0 49.8 0 0.29 0 2.77 - - 0
Esc16h 996 996 0.1 0 0.1 - - - - 0 48.0 0 0.22 0 2.13 0 65 0
Esc16i 14 14 0.1 0 0.1 - - - - 0 51.6 0 0.16 0 2.05 - - 0
Esc16j 8 8 0.1 0 0.1 - - - - 0 402 0 0.32 0 2.91 - - 0
Esc32a 130 130 190 0 190 1.54 7.03 0 226 0 382 1.52 97.04 0 137 - - 0
Esc32b 168 168 53 0 53 0 2.80 0 40.59 0 400 0 33.61 0 110 - - 0
Esc32c 642 642 1.2 0 1.2 0 0 0 0.08 0 389 0 2.01 0 54.7 - - 0
Esc32d 200 200 11 0 11 0 1.92 0 2.13 0 353 0 2.76 0 74.3 - - 0
Esc32e 2 2 0.8 0 0.8 0 0 0 0.05 0 370 0 0.66 0 46.09 - - 0
Esc32g 6 6 0.9 0 0.9 0 0 0 0.07 0 371 0 1.27 0 28.41 - - 0
Esc32h 438 438 31 0 31 0 3.41 0 2.64 0 349 0 6.54 0 85.75 - - 0
Esc64a 116 116 9.6 0 9.6 - - - - 0 2631 0 194 0 1522 - - 0
Esc128 64 64 1395 0 1395 - - - - - - 0 1631 - - - - 0
Had12 1652 1652 0.7 0 0.7 - - - - - - 0 4.27 0 0.97 0 41 0
Had14 2724 2724 1.5 0 1.5 - - - - - - 0 10.25 0 1.97 0 64 0
Had16 3720 3720 2.2 0 2.2 - - - - - - 0 5.38 0.05 3.64 0 88 0
Had18 5358 5358 4.9 0 4.9 - - - - - - 0 18.54 0 6.52 0 118 0
Had20 6922 6922 11.2 0 11.2 0 2.8 0 159 - - 0 15.26 0 10.58 0 148 0
Kra30a 88900 88900 430 0 430 0 292 0 199 0 301 0.89 71 1.34 106 - - 0
Kra30b 91420 91420 441 0 441 0.32 268 0 140 0 331 0 123 0.13 102 - - 0.08
Kra32 88700 88700 432 0 432 - - - - - - - - 0 172 - - 0
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) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Lipa20a 3683 3683 14 0 14 0 0.99 0 107 0 74.8 0 0.59 0 16.11 - - 0
Lipa20b 27076 27076 16 0 16 0 0.66 0 0 0 74.4 0 0.39 0 16.78 - - 0
Lipa30a 13178 13178 75 0 75 0 46.43 0 54.85 0 345 0 5.66 0 120 - - 0.99
Lipa30b 151426 151426 73 0 73 0 7.31 0 0 0 337 0 2.78 0 122 - - 0
Lipa40a 31538 31538 655 0 655 1.13 306 1.02 281 0.96 1022 0 19.46 0 490 - - -
Lipa40b 476581 476581 430 0 430 0 6.21 0 0 0 1026 0 9.52 0 486 - - -
Lipa50a 62093 62619 872 0.80 971 - - - - 0.95 1486 0.82 57.32 1.02 1556 - - 0
Lipa50b 1210244 1210244 777 0 777 - - - - 0 1509 0 39.96 0 1462 - - 0
Lipa60a 107218 108103 1337 0.79 2754 - - - - 0.77 3057 0.64 137 0.84 3668 - - 0.81
Lipa60b 2520135 2520135 893 0 893 - - - - 0 3047 0 86.13 0 3724 - - 0
Lipa70a 169755 170956 1714 0.71 1744 - - - - 0.71 6148 0.62 233 0.77 8067 - - -
Lipa70b 4603200 4603200 1771 0 1771 - - - - 0 6123 15.9 196 0 7762 - - -
Lipa80a 253195 254853 2254 0.63 3467 - - - - 0.61 9519 0.61 373 0.67 15220 - - -
Lipa80b 7763962 7763962 2511 0 2511 - - - - 0 9499 16.56 332 20.33 15965 - - -
Lipa90a 360630 362854 2562 0.57 5678 - - - - 0.58 12358 0.54 592 0.63 27909 - - -
Lipa90b 12490441 12490441 5034 0 5034 - - - - 0 12319 0 503 0 27788 - - -
Sko42 15812 15836 1042 0.03 1547 - - - - 0.25 1006 0.35 365 0.30 614 - - 0
Sko49 23386 23510 1098 0.32 1772 - - - - 0.21 1252 0.19 714 0.45 1318 - - 0.05
Sko56 34458 34568 1064 0.20 1742 - - - - 0.02 2976 0.06 907 0.47 2613 - - 0.12
Sko64 48498 48796 1178 0.31 2770 - - - - 0.22 3788 0.09 1399 0.25 4936 - - 0
Sko72 66256 66660 1620 0.47 4096 - - - - 0.29 5078 0.21 1987 0.73 8663 - - 0.03
Sko81 90998 91452 1520 0.50 1655 - - - - 0.20 10964 0.12 2680 0.43 16960 - - 0.05
Sko90 115534 116922 1625 0.91 4053 - - - - 0.27 12698 0.43 3822 0.45 28787 - - 0.02
Sko100a 152002 153426 1905 0.94 1907 - - - - 0.21 16608 0.22 1486 1.30 309 - - 0.19
Sko100b 153890 155288 1494 0.85 1577 - - - - 0.14 14729 0.30 1405 2.34 274 - - -
Sko100c 147862 149628 1525 1.15 1786 - - - - 0.20 20314 0.06 873 1.50 284 - - -
Sko100d 149576 151196 1666 0.97 3978 - - - - 0.17 20302 0.27 863 1.03 293 - - -
Sko100e 149150 151056 2423 0.90 5415 - - - - 0.24 21127 0.33 745 1.55 301 - - -
Sko100f 149036 150510 2038 0.91 2125 - - - - 0.29 21479 0.41 781 0.73 285 - - -
Table Options

Download as excel

Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Lipa20a 3683 3683 14 0 14 0 0.99 0 107 0 74.8 0 0.59 0 16.11 - - 0
Lipa20b 27076 27076 16 0 16 0 0.66 0 0 0 74.4 0 0.39 0 16.78 - - 0
Lipa30a 13178 13178 75 0 75 0 46.43 0 54.85 0 345 0 5.66 0 120 - - 0.99
Lipa30b 151426 151426 73 0 73 0 7.31 0 0 0 337 0 2.78 0 122 - - 0
Lipa40a 31538 31538 655 0 655 1.13 306 1.02 281 0.96 1022 0 19.46 0 490 - - -
Lipa40b 476581 476581 430 0 430 0 6.21 0 0 0 1026 0 9.52 0 486 - - -
Lipa50a 62093 62619 872 0.80 971 - - - - 0.95 1486 0.82 57.32 1.02 1556 - - 0
Lipa50b 1210244 1210244 777 0 777 - - - - 0 1509 0 39.96 0 1462 - - 0
Lipa60a 107218 108103 1337 0.79 2754 - - - - 0.77 3057 0.64 137 0.84 3668 - - 0.81
Lipa60b 2520135 2520135 893 0 893 - - - - 0 3047 0 86.13 0 3724 - - 0
Lipa70a 169755 170956 1714 0.71 1744 - - - - 0.71 6148 0.62 233 0.77 8067 - - -
Lipa70b 4603200 4603200 1771 0 1771 - - - - 0 6123 15.9 196 0 7762 - - -
Lipa80a 253195 254853 2254 0.63 3467 - - - - 0.61 9519 0.61 373 0.67 15220 - - -
Lipa80b 7763962 7763962 2511 0 2511 - - - - 0 9499 16.56 332 20.33 15965 - - -
Lipa90a 360630 362854 2562 0.57 5678 - - - - 0.58 12358 0.54 592 0.63 27909 - - -
Lipa90b 12490441 12490441 5034 0 5034 - - - - 0 12319 0 503 0 27788 - - -
Sko42 15812 15836 1042 0.03 1547 - - - - 0.25 1006 0.35 365 0.30 614 - - 0
Sko49 23386 23510 1098 0.32 1772 - - - - 0.21 1252 0.19 714 0.45 1318 - - 0.05
Sko56 34458 34568 1064 0.20 1742 - - - - 0.02 2976 0.06 907 0.47 2613 - - 0.12
Sko64 48498 48796 1178 0.31 2770 - - - - 0.22 3788 0.09 1399 0.25 4936 - - 0
Sko72 66256 66660 1620 0.47 4096 - - - - 0.29 5078 0.21 1987 0.73 8663 - - 0.03
Sko81 90998 91452 1520 0.50 1655 - - - - 0.20 10964 0.12 2680 0.43 16960 - - 0.05
Sko90 115534 116922 1625 0.91 4053 - - - - 0.27 12698 0.43 3822 0.45 28787 - - 0.02
Sko100a 152002 153426 1905 0.94 1907 - - - - 0.21 16608 0.22 1486 1.30 309 - - 0.19
Sko100b 153890 155288 1494 0.85 1577 - - - - 0.14 14729 0.30 1405 2.34 274 - - -
Sko100c 147862 149628 1525 1.15 1786 - - - - 0.20 20314 0.06 873 1.50 284 - - -
Sko100d 149576 151196 1666 0.97 3978 - - - - 0.17 20302 0.27 863 1.03 293 - - -
Sko100e 149150 151056 2423 0.90 5415 - - - - 0.24 21127 0.33 745 1.55 301 - - -
Sko100f 149036 150510 2038 0.91 2125 - - - - 0.29 21479 0.41 781 0.73 285 - - -
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) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Nug12 578 578 0.5 0 0.5 - - - - 0 19 0 6.84 0 1.41 0 36 0
Nug14 1014 1014 0.8 0 0.8 - - - - - - 0 7.71 0.39 3.11 - - 0.2
Nug15 1150 1150 5.8 0 5.8 - - - - 0 41.4 0 8.3 0 4.02 0 73 0
Nug16a 1610 1610 4.1 0 4.1 - - - - - - 0 11.24 0 5.59 - - 0
Nug16b 1240 1240 4.7 0 4.7 - - - - - - 0 11.02 0 5.59 - - 0
Nug17 1732 1732 5.7 0 5.7 - - - - - - 0 11.95 0 7.31 - - 0
Nug18 1930 1930 7.9 0 7.9 - - - - - - 0.31 13.56 0 9.55 - - 0
Nug20 2570 2570 15.7 0 15.7 0 2.53 0 119 0 97.8 0 20.73 0 16.06 0 132 0
Nug21 2438 2438 27.5 0 27.5 - - - - - - 0 29.80 0 20.63 - - 0
Nug22 3596 3596 26.5 0 26.5 - - - - - - 0 43.82 0 25.84 - - 0
Nug24 3488 3488 39.7 0 39.7 - - - - - - 0 33.83 0 39.75 - - 0.06
Nug25 3744 3744 38.5 0 38.5 - - - - - - 0 42.10 0 47.66 - - 0
Nug27 5234 5234 51.8 0 51.8 - - - - - - - - 0 80.56 - - 0
Nug28 5166 5166 57.5 0 57.5 - - - - - - - - 0.12 98.33 - - 0
Nug30 6124 6124 136.1 0 136.1 0.42 523 0 181 0.07 354 0.42 109 2.12 117 0.06 887 0.07
Rou12 235528 235528 0.5 0 0.5 - - - - 0 19.6 0 0.30 0 1.06 0 35 0
Rou15 354210 354210 1.1 0 1.1 - - - - 0 34.6 0 0.56 0 2.95 0.71 71 0
Rou20 725522 725522 12.2 0 12.2 0 165 0 245 0.16 75.2 0 1.43 0.02 11.73 0.06 127 0
Scr12 31410 31410 0.7 0 0.7 - - - - 0 18.8 0 0.44 0 1.11 0 38 0
Scr15 51140 51140 1.0 0 1.0 - - - - 0 35.2 0 0.42 0 3.09 0 78 0
Scr20 110030 110030 5.4 0 5.4 0 157 0 46.1 0 79.6 0 1.57 0 12.69 2.13 137 0
Ste36a 9526 9526 623.5 0 623.5 1.81 276 0.76 295 0.27 710 0 221 0 204 - - -
Ste36b 15852 15852 763.2 0 763.2 0.92 180 0.25 213 - - 0 235 3.43 222 - - -
Ste36c 8239110 8239110 800.4 0 800.4 0.89 142 0.33 321 - - 0 24.07 - - - - -
Tho30 149936 149936 306.2 0 306.2 0 216 0 288 0 396 0 132 0.29 119 - - -
Tho40 240516 240620 823.1 0.04 823.1 1.17 184 0.66 312 0.32 958 0.05 344 0.53 502 - - -
Tho150 8133398 8238058 4590.3 1.29 4590.3 - - - - - - 0.41 729 - - - - -
Wil50 48816 48916 829.8 0.06 2522.3 - - - - 0.07 2115 0 695 0.28 1499 - - -
Wil100 273038 274446 3330.7 0.34 5272.6 - - - - 0.2 20544 0.15 1252 0.27 51121 - - -
Table Options

Download as excel

Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Nug12 578 578 0.5 0 0.5 - - - - 0 19 0 6.84 0 1.41 0 36 0
Nug14 1014 1014 0.8 0 0.8 - - - - - - 0 7.71 0.39 3.11 - - 0.2
Nug15 1150 1150 5.8 0 5.8 - - - - 0 41.4 0 8.3 0 4.02 0 73 0
Nug16a 1610 1610 4.1 0 4.1 - - - - - - 0 11.24 0 5.59 - - 0
Nug16b 1240 1240 4.7 0 4.7 - - - - - - 0 11.02 0 5.59 - - 0
Nug17 1732 1732 5.7 0 5.7 - - - - - - 0 11.95 0 7.31 - - 0
Nug18 1930 1930 7.9 0 7.9 - - - - - - 0.31 13.56 0 9.55 - - 0
Nug20 2570 2570 15.7 0 15.7 0 2.53 0 119 0 97.8 0 20.73 0 16.06 0 132 0
Nug21 2438 2438 27.5 0 27.5 - - - - - - 0 29.80 0 20.63 - - 0
Nug22 3596 3596 26.5 0 26.5 - - - - - - 0 43.82 0 25.84 - - 0
Nug24 3488 3488 39.7 0 39.7 - - - - - - 0 33.83 0 39.75 - - 0.06
Nug25 3744 3744 38.5 0 38.5 - - - - - - 0 42.10 0 47.66 - - 0
Nug27 5234 5234 51.8 0 51.8 - - - - - - - - 0 80.56 - - 0
Nug28 5166 5166 57.5 0 57.5 - - - - - - - - 0.12 98.33 - - 0
Nug30 6124 6124 136.1 0 136.1 0.42 523 0 181 0.07 354 0.42 109 2.12 117 0.06 887 0.07
Rou12 235528 235528 0.5 0 0.5 - - - - 0 19.6 0 0.30 0 1.06 0 35 0
Rou15 354210 354210 1.1 0 1.1 - - - - 0 34.6 0 0.56 0 2.95 0.71 71 0
Rou20 725522 725522 12.2 0 12.2 0 165 0 245 0.16 75.2 0 1.43 0.02 11.73 0.06 127 0
Scr12 31410 31410 0.7 0 0.7 - - - - 0 18.8 0 0.44 0 1.11 0 38 0
Scr15 51140 51140 1.0 0 1.0 - - - - 0 35.2 0 0.42 0 3.09 0 78 0
Scr20 110030 110030 5.4 0 5.4 0 157 0 46.1 0 79.6 0 1.57 0 12.69 2.13 137 0
Ste36a 9526 9526 623.5 0 623.5 1.81 276 0.76 295 0.27 710 0 221 0 204 - - -
Ste36b 15852 15852 763.2 0 763.2 0.92 180 0.25 213 - - 0 235 3.43 222 - - -
Ste36c 8239110 8239110 800.4 0 800.4 0.89 142 0.33 321 - - 0 24.07 - - - - -
Tho30 149936 149936 306.2 0 306.2 0 216 0 288 0 396 0 132 0.29 119 - - -
Tho40 240516 240620 823.1 0.04 823.1 1.17 184 0.66 312 0.32 958 0.05 344 0.53 502 - - -
Tho150 8133398 8238058 4590.3 1.29 4590.3 - - - - - - 0.41 729 - - - - -
Wil50 48816 48916 829.8 0.06 2522.3 - - - - 0.07 2115 0 695 0.28 1499 - - -
Wil100 273038 274446 3330.7 0.34 5272.6 - - - - 0.2 20544 0.15 1252 0.27 51121 - - -
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) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Tai12a 224416 224416 0.3 0 0.3 - - - - - - 0 0.18 0 1.05 0 35 0
Tai12b 39464925 39464925 0.2 0 0.2 - - - - - - 0 0.62 0 1.03 0.03 53 0
Tai15a 388214 388214 2.0 0 2.0 - - - - - - 0 0.69 0 2.99 0.39 73 0.01
Tai15b 51765268 51765268 0.8 0 0.8 - - - - - - 0 0.70 0 3.05 0.47 77 0
Tai17a 491812 491812 4.0 0 4.0 - - - - - - 0.55 0.96 0.38 5.55 0 86 0.56
Tai20a 703482 703482 175.5 0 175.5 0 484 0 160 - - 0.84 1.38 0.47 11.42 0.21 124 0.8
Tai20b 122455319 122455319 4.8 0 4.8 - - - - - - 0 2.70 0 12.52 5.6 167 0
Tai25a 1167256 1169030 236.4 0 1514.3 1.43 355 0.55 206 - - 0.77 3.27 2.00 33.03 - - 1.57
Tai25b 344355646 344355646 70.6 0 70.6 - - - - - - 0 3.77 5.59 35 - - 0
Tai30a 1818146 1832590 437.2 0.57 546.7 1.58 265 1.46 332 - - 1.34 6.72 1.11 83.06 - - 1.37
Tai30b 637117113 637117113 633.8 0 633.8 - - - - - - 0 14.11 2.22 81 - - 0
Tai35a 2422002 2436540 550.9 0.59 1288.4 1.90 531 1.64 232 - - 1.29 12.09 1.24 177 - - 1.3
Tai35b 283315445 283315445 1032.5 0 1032.5 - - - - - - 0 23.90 3.54 186 - - 0.19
Tai40a 3139370 3160484 886.1 0.67 886.1 2.20 325 2.05 253 - - 1.08 18.37 1.85 354 - - 1.7
Tai40b 637250948 637250948 1217 0 1217 - - - - - - 0 36.95 5.60 328 - - 0
Tai50a 4938796 5031472 1113 1.46 2323 - - - - - - 1.31 58.21 2.25 1104 - - 2.48
Tai50b 458821517 458926056 1592 0.02 1592 - - - - - - 0 64.77 0.42 1032 - - 0
Tai60a 7205962 7342990 2165 1.55 3142 - - - - - - 1.79 104 2.75 2740 - - 2.37
Tai60b 608215054 612153786 1866 0.65 1866 - - - - - - 0 148 0.47 2621 - - 0.02
Tai64c 1855928 1855928 1325 0 1325 - - - - - - 0 28.96 0.03 237 - - 0
Tai80a 13511780 13821180 2100 1.87 5707 - - - - - - 1.41 360 2.46 11333 - - 2.37
Tai80b 818415043 827982667 3434 1.17 3434 - - - - - - 0.03 424 2.79 10533 - - 0
Tai100a 21052466 21538854 2450 1.76 8120 - - - - - - 1.29 785 2.33 35781 - - -
Tai100b 1185996137 1198498100 4406 1.05 4406 - - - - - - 0.32 855 0.52 34336 - - -
Tai150b 498896643 508566248 9117 1.94 9117 - - - - - - 0.20 3414 0.38 290186 - - -
Tai256c 44759294 44896638 7539 0.27 12126 - - - - - - 0.16 1956 0.27 73180 - - -
Table Options

Download as excel

Instances Best known value Random 2-opt WFA Best results of WFA GRASP ANT GGA PGA IFLS MSA PHAS
Best solution Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$ Time (s) $\Delta_{Best}$
Tai12a 224416 224416 0.3 0 0.3 - - - - - - 0 0.18 0 1.05 0 35 0
Tai12b 39464925 39464925 0.2 0 0.2 - - - - - - 0 0.62 0 1.03 0.03 53 0
Tai15a 388214 388214 2.0 0 2.0 - - - - - - 0 0.69 0 2.99 0.39 73 0.01
Tai15b 51765268 51765268 0.8 0 0.8 - - - - - - 0 0.70 0 3.05 0.47 77 0
Tai17a 491812 491812 4.0 0 4.0 - - - - - - 0.55 0.96 0.38 5.55 0 86 0.56
Tai20a 703482 703482 175.5 0 175.5 0 484 0 160 - - 0.84 1.38 0.47 11.42 0.21 124 0.8
Tai20b 122455319 122455319 4.8 0 4.8 - - - - - - 0 2.70 0 12.52 5.6 167 0
Tai25a 1167256 1169030 236.4 0 1514.3 1.43 355 0.55 206 - - 0.77 3.27 2.00 33.03 - - 1.57
Tai25b 344355646 344355646 70.6 0 70.6 - - - - - - 0 3.77 5.59 35 - - 0
Tai30a 1818146 1832590 437.2 0.57 546.7 1.58 265 1.46 332 - - 1.34 6.72 1.11 83.06 - - 1.37
Tai30b 637117113 637117113 633.8 0 633.8 - - - - - - 0 14.11 2.22 81 - - 0
Tai35a 2422002 2436540 550.9 0.59 1288.4 1.90 531 1.64 232 - - 1.29 12.09 1.24 177 - - 1.3
Tai35b 283315445 283315445 1032.5 0 1032.5 - - - - - - 0 23.90 3.54 186 - - 0.19
Tai40a 3139370 3160484 886.1 0.67 886.1 2.20 325 2.05 253 - - 1.08 18.37 1.85 354 - - 1.7
Tai40b 637250948 637250948 1217 0 1217 - - - - - - 0 36.95 5.60 328 - - 0
Tai50a 4938796 5031472 1113 1.46 2323 - - - - - - 1.31 58.21 2.25 1104 - - 2.48
Tai50b 458821517 458926056 1592 0.02 1592 - - - - - - 0 64.77 0.42 1032 - - 0
Tai60a 7205962 7342990 2165 1.55 3142 - - - - - - 1.79 104 2.75 2740 - - 2.37
Tai60b 608215054 612153786 1866 0.65 1866 - - - - - - 0 148 0.47 2621 - - 0.02
Tai64c 1855928 1855928 1325 0 1325 - - - - - - 0 28.96 0.03 237 - - 0
Tai80a 13511780 13821180 2100 1.87 5707 - - - - - - 1.41 360 2.46 11333 - - 2.37
Tai80b 818415043 827982667 3434 1.17 3434 - - - - - - 0.03 424 2.79 10533 - - 0
Tai100a 21052466 21538854 2450 1.76 8120 - - - - - - 1.29 785 2.33 35781 - - -
Tai100b 1185996137 1198498100 4406 1.05 4406 - - - - - - 0.32 855 0.52 34336 - - -
Tai150b 498896643 508566248 9117 1.94 9117 - - - - - - 0.20 3414 0.38 290186 - - -
Tai256c 44759294 44896638 7539 0.27 12126 - - - - - - 0.16 1956 0.27 73180 - - -
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
Table Options

Download as excel

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
$\bar{\triangle}$ Time (s) $\bar{\triangle}$ Time (s)
Burkard 0.000 28.14 0.006 22.97
Christofides 0.000 23.65 3.834 2.54
Elshafei 0.000 15.20 2.150 44.46
Eschermann 0.042 91.23 0.586 104.06
Hadley 0.000 4.16 0.002 10.80
Krarup 0.000 441.83 1.190 96.97
Li & Pardalos 1.336 1539.66 5.104 161.72
Skorin-Kapov 0.865 2573.38 0.590 1386.65
Nugent 0.000 29.82 0.259 26.94
Roucairol 0.000 4.78 0.523 0.762
Scriabin 0.000 2.40 0.627 0.808
Steinberg 0.000 745.02 2.090 160.15
Thonemann 0.559 1926.51 0.650 401.51
Wilhelm 0.222 3972.06 0.225 973.44
Taillard 0.890 2514.07 0.920 320.17
Average 0.261 927.46 1.250 247.60
Table Options

Download as excel

Instances WFA PGA
$\bar{\triangle}$ Time (s) $\bar{\triangle}$ Time (s)
Burkard 0.000 28.14 0.006 22.97
Christofides 0.000 23.65 3.834 2.54
Elshafei 0.000 15.20 2.150 44.46
Eschermann 0.042 91.23 0.586 104.06
Hadley 0.000 4.16 0.002 10.80
Krarup 0.000 441.83 1.190 96.97
Li & Pardalos 1.336 1539.66 5.104 161.72
Skorin-Kapov 0.865 2573.38 0.590 1386.65
Nugent 0.000 29.82 0.259 26.94
Roucairol 0.000 4.78 0.523 0.762
Scriabin 0.000 2.40 0.627 0.808
Steinberg 0.000 745.02 2.090 160.15
Thonemann 0.559 1926.51 0.650 401.51
Wilhelm 0.222 3972.06 0.225 973.44
Taillard 0.890 2514.07 0.920 320.17
Average 0.261 927.46 1.250 247.60
[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]

Ji Zhang, Hongxia Lv, Boer Deng, Wenxian Wang. An adaptive genetic algorithm for solving the optimization model of car flow organizat. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020200
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019046
[16]

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
[17]

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
[18]

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
[19]

Cristian Barbarosie, Anca-Maria Toader, Sérgio Lopes. A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019249
[20]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019122

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (98)
  • HTML views (1589)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences