Presentation 2010-03-09
An Application of Lin-Kernighan Algorithm to Quadratic Assignment Problems
Kazuaki SHIBATA, Yoshihiko HORIO,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) A 2-opt local search driven by a chaotic neural network (exponential chaotic tabu search) was proposed for quadratic assignment problems (QAPs). The exponential chaotic tabu search has been demonstrated to have a high ability to solve QAPs. For traveling salesman prolems (TSPs), a chaos driven Lin-Kernighan algorithm was proposed, and further, showed a better performance than chaos driven 2-opt algorithm. Our final goal is to apply the Lin-Kernighan algorithm to the exponential chaotic tabu search for QAPs instead of the 2-opt algorithm. We, however, cannot directly apply the Lin-Kernighan algorithm to QAPs because the algorithm was originally for TSPs. Therefore, in this paper, we propose a technique to solve QAPs based on the Lin-Kernighan algorithm before applying it to the exponential tabu search. We show numerical simulation results to compare the performances of the proposed technique and the 2-opt algorithm. Furthermore, we show simulation results with a different number of exchanges in the Lin-Kernighan algorithm used in the proposed technique.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Quadratic Assignment Problems / Lin-Kernighan Algorithm
Paper # NLP2009-164
Date of Issue

Conference Information
Committee NLP
Conference Date 2010/3/2(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Nonlinear Problems (NLP)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) An Application of Lin-Kernighan Algorithm to Quadratic Assignment Problems
Sub Title (in English)
Keyword(1) Quadratic Assignment Problems
Keyword(2) Lin-Kernighan Algorithm
1st Author's Name Kazuaki SHIBATA
1st Author's Affiliation Graduate School of Engineering, Tokyo Denki University()
2nd Author's Name Yoshihiko HORIO
2nd Author's Affiliation Graduate School of Engineering, Tokyo Denki University
Date 2010-03-09
Paper # NLP2009-164
Volume (vol) vol.109
Number (no) 458
Page pp.pp.-
#Pages 6
Date of Issue