A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem

Hameed, A.; Aboobaider, B.; Mutar, M.; Choon, N.

Growing Science » International Journal of Industrial Engineering Computations » A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem

Journals

IJIEC Volumes

Volume 1 (17)
- Issue 1 (9)
- Issue 2 (8)

Volume 2 (68)
- Issue 1 (12)
- Issue 2 (20)
- Issue 3 (20)
- Issue 4 (16)

Volume 3 (76)
- Issue 1 (9)
- Issue 2 (15)
- Issue 3 (20)
- Issue 4 (12)
- Issue 5 (20)

Volume 4 (50)
- Issue 1 (14)
- Issue 2 (10)
- Issue 3 (12)
- Issue 4 (14)

Volume 5 (47)
- Issue 1 (13)
- Issue 2 (12)
- Issue 3 (12)
- Issue 4 (10)

Volume 6 (39)
- Issue 1 (7)
- Issue 2 (12)
- Issue 3 (10)
- Issue 4 (10)

Volume 7 (47)
- Issue 1 (10)
- Issue 2 (14)
- Issue 3 (10)
- Issue 4 (13)

Volume 8 (30)
- Issue 1 (9)
- Issue 2 (7)
- Issue 3 (8)
- Issue 4 (6)

Volume 9 (32)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (7)
- Issue 4 (10)

Volume 10 (34)
- Issue 1 (8)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (8)

Volume 11 (36)
- Issue 1 (9)
- Issue 2 (8)
- Issue 3 (9)
- Issue 4 (10)

Volume 12 (29)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (8)
- Issue 4 (6)

Volume 13 (41)
- Issue 1 (10)
- Issue 2 (8)
- Issue 3 (10)
- Issue 4 (13)

Volume 14 (50)
- Issue 1 (11)
- Issue 2 (15)
- Issue 3 (9)
- Issue 4 (15)

Volume 15 (55)
- Issue 1 (19)
- Issue 2 (15)
- Issue 3 (12)
- Issue 4 (9)

Countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) Quarterly Publication Volume 11 Issue 1 pp. 51-72 , 2020

A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem Pages 51-72 Download PDF

Authors: Asaad Shakir Hameed, Burhanuddin Mohd Aboobaider, Modhi Lafta Mutar, Ngo Hea Choon

DOI: 10.5267/j.ijiec.2019.6.005

Keywords: Combinatorial optimization Problems, Facility Location Problem, Quadratic Assignment Problem, Discrete Differential Evolution Algorithm, Tabu Search Algorithm

Abstract: The Combinatorial Optimization Problem (COPs) is one of the branches of applied mathematics and computer sciences, which is accompanied by many problems such as Facility Layout Problem (FLP), Vehicle Routing Problem (VRP), etc. Even though the use of several mathematical formulations is employed for FLP, Quadratic Assignment Problem (QAP) is one of the most commonly used. One of the major problems of Combinatorial NP-hard Optimization Problem is QAP mathematical model. Consequently, many approaches have been introduced to solve this problem, and these approaches are classified as Approximate and Exact methods. With QAP, each facility is allocated to just one location, thereby reducing cost in terms of aggregate distances weighted by flow values. The primary aim of this study is to propose a hybrid approach which combines Discrete Differential Evolution (DDE) algorithm and Tabu Search (TS) algorithm to enhance solutions of QAP model, to reduce the distances between the locations by finding the best distribution of N facilities to N locations, and to implement hybrid approach based on discrete differential evolution (HDDETS) on many instances of QAP from the benchmark. The performance of the proposed approach has been tested on several sets of instances from the data set of QAP and the results obtained have shown the effective performance of the proposed algorithm in improving several solutions of QAP in reasonable time. Afterwards, the proposed approach is compared with other recent methods in the literature review. Based on the computation results, the proposed hybrid approach outperforms the other methods.

How to cite this paper

 Hameed, A., Aboobaider, B., Mutar, M & Choon, N. (2020). A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem.International Journal of Industrial Engineering Computations , 11(1), 51-72.

Refrences

Abdel-Baset, M., Wu, H., Zhou, Y., & Abdel-Fatah, L. (2017). Elite opposition-flower pollination algorithm for quadratic assignment problem. Journal of Intelligent & Fuzzy Systems, 33(2), 901-911.
Abdel-Basset, M., Manogaran, G., Rashad, H., & Zaied, A. N. H. (2018a). A comprehensive review of quadratic assignment problem: variants, hybrids and applications. Journal of Ambient Intelligence and Humanized Computing, 1-24. doi: 10.1007/s12652-018-0917-x.
Abdel-Basset, M., Manogaran, G., El-Shahat, D., & Mirjalili, S. (2018b). Integrating the whale algorithm with tabu search for quadratic assignment problem: a new approach for locating hospital departments. Applied Soft Computing, 73, 530-546.
Abdelkafi, O., Idoumghar, L., & Lepagnot, J. (2015). Comparison of two diversification methods to solve the quadratic assignment problem. Procedia Computer Science, 51, 2703-2707.
Ahmed, Z. H. (2018). A hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem. Cogent Engineering, 5(1), 1423743.
Benlic, U., & Hao, J. K. (2013). Breakout local search for the quadratic assignment problem. Applied Mathematics and Computation, 219(9), 4800-4815.
Cela, E., Deineko, V., & Woeginger, G. J. (2018). New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices. European journal of operational research, 267(3), 818-834.
Czapiński, M. (2013). An effective parallel multistart tabu search for quadratic assignment problem on CUDA platform. Journal of Parallel and Distributed Computing, 73(11), 1461-1468.
Tate, D. M., & Smith, A. E. (1995). A genetic approach to the quadratic assignment problem. Computers & Operations Research, 22(1), 73-83.
Doerner, K., Focke, A., & Gutjahr, W. J. (2007). Multicriteria tour planning for mobile healthcare facilities in a developing country. European Journal of Operational Research, 179(3), 1078-1096.
Duman, E., Uysal, M., & Alkaya, A. F. (2012). Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem. Information Sciences, 217, 65-77.
Taillard, É. (1991). Robust taboo search for the quadratic assignment problem. Parallel computing, 17(4-5), 443-455.
Harris, M., Berretta, R., Inostroza-Ponta, M., & Moscato, P. (2015, May). A memetic algorithm for the quadratic assignment problem with parallel local search. In 2015 IEEE congress on evolutionary computation (CEC) (pp. 838-845). IEEE.
Kaviani, M., Abbasi, M., Rahpeyma, B., & Yusefi, M. (2014). A hybrid tabu search-simulated annealing method to solve quadratic assignment problem. Decision Science Letters, 3(3), 391-396.
Koopmans, T. C., & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, 25(1), 53-76.
Kushida, J. I., Oba, K., Hara, A., & Takahama, T. (2012, November). Solving quadratic assignment problems by differential evolution. In The 6th International Conference on Soft Computing and Intelligent Systems, and The 13th International Symposium on Advanced Intelligence Systems(pp. 639-644). IEEE.
Lim, W. L., Wibowo, A., Desa, M. I., & Haron, H. (2016). A biogeography-based optimization algorithm hybridized with tabu search for the quadratic assignment problem. Computational intelligence and neuroscience, 2016, 27.
Lv, C. (2012, October). A hybrid strategy for the quadratic assignment problem. In 2012 International Conference on Information Management, Innovation Management and Industrial Engineering (Vol. 2, pp. 31-34). IEEE.
Kaviani, M., Abbasi, M., Rahpeyma, B., & Yusefi, M. (2014). A hybrid tabu search-simulated annealing method to solve quadratic assignment problem. Decision Science Letters, 3(3), 391-396.
Pan, Q. K., Tasgetiren, M. F., & Liang, Y. C. (2008). A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 55(4), 795-816.
Pradeepmon, T., Sridharan, R., & Panicker, V. (2018). Development of modified discrete particle swarm optimization algorithm for quadratic assignment problems. International Journal of Industrial Engineering Computations, 9(4), 491-508.
Pradeepmon, T. G., Panicker, V. V., & Sridharan, R. (2016). Parameter selection of discrete particle swarm optimization algorithm for the quadratic assignment problems. Procedia Technology, 25, 998-1005.
Riffi, M. E., Saji, Y., & Barkatou, M. (2017). Incorporating a modified uniform crossover and 2-exchange neighborhood mechanism in a discrete bat algorithm to solve the quadratic assignment problem. Egyptian Informatics Journal, 18(3), 221-232.
Said, G. A. E. N. A., Mahmoud, A. M., & El-Horbaty, E. S. M. (2014). A comparative study of meta-heuristic algorithms for solving quadratic assignment problem. International Journal of Advanced Computer Science and Applications (IJACSA), 5(1), 1–6.
Shariff, S. R., Moin, N. H., & Omar, M. (2012). Location allocation modeling for healthcare facility planning in Malaysia. Computers & Industrial Engineering, 62(4), 1000-1010.
Şahinkoç, M., & Bilge, Ü. (2018). Facility layout problem with QAP formulation under scenario-based uncertainty. INFOR: Information Systems and Operational Research, 56(4), 406-427.
Samanta, S., Philip, D., & Chakraborty, S. (2018). Bi-objective dependent location quadratic assignment problem: Formulation and solution using a modified artificial bee colony algorithm. Computers & Industrial Engineering, 121, 8-26.
Scalia, G., Micale, R., Giallanza, A., & Marannano, G. (2019). Firefly algorithm based upon slicing structure encoding for unequal facility layout problem. International Journal of Industrial Engineering Computations, 10(3), 349-360.
Shukla, A. (2015, May). A modified bat algorithm for the quadratic assignment problem. In 2015 IEEE Congress on Evolutionary Computation (CEC) (pp. 486-490). IEEE.
Da Silva, G. C., Bahiense, L., Ochi, L. S., & Boaventura-Netto, P. O. (2012). The dynamic space allocation problem: Applying hybrid GRASP and Tabu search metaheuristics. Computers & Operations Research, 39(3), 671-677.
Syam, S. S., & Côté, M. J. (2010). A location–allocation model for service providers with application to not-for-profit health care organizations. Omega, 38(3-4), 157-166.
Tasgetiren, M. F., Pan, Q. K., Suganthan, P. N., & Dizbay, I. E. (2013, April). Metaheuristic algorithms for the quadratic assignment problem. In 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS) (pp. 131-137). IEEE.
Van Luong, T., Melab, N., & Talbi, E. G. (2010, July). Parallel hybrid evolutionary algorithms on GPU. In IEEE Congress on Evolutionary Computation (pp. 1-8). IEEE.
Xia, X., & Zhou, Y. (2018). Performance analysis of ACO on the quadratic assignment problem. Chinese Journal of Electronics, 27(1), 26-34.
Zhang, Y., Berman, O., Marcotte, P., & Verter, V. (2010). A bilevel model for preventive healthcare facility network design with congestion. IIE Transactions, 42(12), 865-880.