A Variable Depth Search Algorithm for the Generalized Assignment Problem

Mutsunori Yagiura, Takashi Yamaguchi and Toshihide Ibaraki

Abstract:
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 algorithm.

Key Words: 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.

PS file

Back to the Paper List