1999 | OriginalPaper | Buchkapitel
A Variable Depth Search Algorithm for the Generalized Assignment Problem
verfasst von : Mutsunori Yagiura, Takashi Yamaguchi, Toshihide Ibaraki
Erschienen in: Meta-Heuristics
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 a neighborhood so that it can effectively traverse a 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 the feasible region is not advantageous because the feasible region is very small or is combinatorially complicated to search. Therefore, we allow our algorithm to search within 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.