Ahyaningsih, Faiz (2016) SOLVING QUADRATIC ASSIGNMENT PROBLEM USING FORWARD AND BACKWARD EXCHANGE ALGORITHM. Global Journal of Pure and Applied Mathematics (GJPAM), 12 (06). pp. 4613-4622. ISSN 0973-1768
Fulltext.pdf - Published Version
Download (290kB) | Preview
Reviewer.pdf - Published Version
Download (355kB) | Preview
Turnitin.pdf - Published Version
Download (1MB) | Preview
Abstract
Quadratic assignment problem is one of the combinatorial optimization problems of deciding the placement of facilities in specified locations in such a way as to minimize a nonconvex objective function expressed in terms of flow between facilities, and distance between location. Since QAP is NP-hard problem, and even finding an ε-approximate solution is a difficult problem, therefore to get a ‘good’ starting point is necessary, in order to obtain a better optimal solution. In this paper we propose a random point strategy to get initial starting point and then use forward exchange algorithm and backward exchange algorithm to get ‘optimal’ solution. As a computational experience we solved the problem of Had12, Esc 16b, Esc 16c and Esc 16h from QAPLIB. Finally, we present a comparative study between our proposed algorithm and Data –Guided Lexisearch Algorithm. The computational study shows the effectiveness of our proposed algorithm.
Item Type: | Article |
---|---|
Keywords: | Backward exchange algorithm; Forward exchange algorithm; Quadratic assigment problem; Random point strategy |
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA150 Algebra |
Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika |
Depositing User: | Mrs Harly Christy Siagian |
Date Deposited: | 10 Mar 2021 07:28 |
Last Modified: | 10 Mar 2021 07:28 |
URI: | https://digilib.unimed.ac.id/id/eprint/41444 |