An experimental study of variable depth search algorithms for the quadratic assignment problem

AUTOR(ES)

Goldbarg, Elizabeth Ferreira Gouvêa, Goldbarg, Marco Cesar

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

03/04/2012

RESUMO

This paper introduces a new variable depth search method for the Quadratic Assignment Problem. The new method considers the cost of edges assignment as the criterion to decide which vertices to exchange during local search moves. It also presents the results of an extensive experimental study that compares the performance of local search and variable depth search algorithms for the Quadratic Assignment Problem. The investigation presented here contributes to a better understanding of the potential of these techniques, which are widely used as intensification tools in more sophisticated heuristic methods, such as evolutionary algorithms. Different algorithms presented in the literature were implemented and compared to the proposed methods. The results of a computational experiment with 161 benchmark instances are reported. Different statistical tests are applied in order to analyze the results provided by the experiments.

Documentos Relacionados

• Combinatorial instruments in the design of a heuristic for the quadratic assignment problem
• An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem
• Problem of Consistent Radiological Diagnosis in Coalminers' Pneumoconiosis: An Experimental Study
• Layout optimization in chemical plants using the problem of quadratic assignment
• Strategies to optimize MEDLINE and EMBASE search strategies for anesthesiology systematic reviews. An experimental study