SOLVING QUADRATIC ASSIGNMENT PROBLEM USING FORWARD AND BACKWARD EXCHANGE ALGORITHM

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

[thumbnail of Fulltext.pdf]
Preview
Text
Fulltext.pdf - Published Version

Download (290kB) | Preview
[thumbnail of Reviewer.pdf]
Preview
Text
Reviewer.pdf - Published Version

Download (355kB) | Preview
[thumbnail of Turnitin.pdf]
Preview
Text
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

Actions (login required)

View Item
View Item