A Variable Depth Search Algorithm
for the Generalized Assignment Problem
Mutsunori Yagiura, Takashi Yamaguchi and Toshihide Ibaraki
A variable depth search procedure (abbreviated as VDS)
is a generalization of the local search method,
which was first successfully applied by Lin and Kernighan
to the traveling salesman problem
and the graph partitioning problem.
The main idea is to adaptively change the size of neighborhood
so that it can effectively traverse larger search space
while keeping the amount of computational time reasonable.
In this paper,
we propose a heuristic algorithm based on VDS
for the generalized assignment problem,
which is one of the representative combinatorial optimization problems
known to be NP-hard.
To the authors' knowledge,
most of the previously proposed algorithms
(with some exceptions)
conduct the search within the feasible region;
however, there are instances
for which the search within feasible region is not advantageous
because the feasible region is very small
or is combinatorially complicated to search.
Therefore, we allow in our algorithm to search into
the infeasible region as well.
We also incorporate an adaptive use of two different neighborhoods,
shift and swap,
within the sequence of neighborhood moves in VDS.
Computational experiments exhibit good prospects of the proposed
adaptive neighborhood, generalized assignment problem,
local search, metaheuristics, variable depth search procedure
Meta-Heuristics: Advances and Trends in Local Search Paradigms for
Optimization, eds. S. Voss, S. Martello, I.H. Osman and C. Roucairol
(Kluwer Academic Publishers, Boston, 1999) pp. 459-471.
Back to the Paper List