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

Kien Ming Ng; Trung Hieu Tran

doi:10.3934/jimo.2018041

Article Contents

2019, Volume 15, Issue 1: 235-259. Doi: 10.3934/jimo.2018041

This issue Previous Article A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking Next Article Pricing options on investment project expansions under commodity price uncertainty

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
* Corresponding author: Trung Hieu Tran

Received: April 30, 2017

Revised: November 30, 2017

Early access: April 2018

Published: December 2018

Abstract Full Text(HTML) Figure(4) / Table(9) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C27, 90B80; Secondary: 68W10.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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.

Download: Full-size image 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.

| Show Table

DownLoad: CSV

Table 2. The parameter sets of the WFA for the QAP benchmark instances.

Benchmarks	$n$	Parameter values
Benchmarks	$n$	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

| Show Table

DownLoad: CSV

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
Instances	Best known value	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

| Show Table

DownLoad: CSV

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
Instances	Best known value	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

| Show Table

DownLoad: CSV

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
Instances	Best known value	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	-	-	-

| Show Table

DownLoad: CSV

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
Instances	Best known value	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	-	-	-

| Show Table

DownLoad: CSV

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
Instances	Best known value	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	-	-	-

| Show Table

DownLoad: CSV

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
Instances	Best known value	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*

| Show Table

DownLoad: CSV

Table 9. The average-value-based comparison results of the WFA and the PGA for all the QAP instances.

Instances	WFA		PGA
Instances	$\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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	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.
	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.
	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.
	A. Blanchard , S. Elloumi , A. Faye and N. Wicker , A cutting algorithm for the quadratic assignment problem, INFOR, 41 (2003) , 35-49.
	S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, Boston, MA, 1987.
	E. S. Buffa , G. C. Armour and T. E. Vollmann , Allocating facilities with CRAFT, Harvard Business Review, 42 (1964) , 136-158.
	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.
	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.
	E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, Combinatorial Optimization (eds. D. Z. Du and P. Pardalos), Kluwer Academic Publishers, London, 1998.
	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.
	M. Dorigo, Optimization, Learning and Natural Algorithms, Ph. D thesis, Politecnico di Milano, Italie, 1992.
	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.
	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.
	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.
	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.
	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.
	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.
	J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
	L. J. Hubert, Assignment Methods in Combinatorial Data Analysis, Marcel Dekker Inc., New York, 1987.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	S. Sahni and T. Gonzalez , P-complete approximation problems, Journal of the ACM, 23 (1976) , 555-565. doi: 10.1145/321958.321975.
	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.
	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.
	H. Shah-Hosseini, Problem solving by intelligent water drops, in: Proceedings of IEEE Congress on Evolutionary Computation (CEC' 07), Singapore, (2007), 3226-3231.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.
	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.