Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment

Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment

0.00 Avg rating0 Votes
Article ID: iaor20012942
Country: United States
Volume: 12
Issue: 3
Start Page Number: 164
End Page Number: 176
Publication Date: Jun 2000
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: heuristics
Abstract:

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for a matrix decomposition problem arising in the context of traffic assignment in communication satellites. We review basic concepts of GRASP: construction and local search algorithms. The local search phase is based on the use of a new type of neighborhood defined by constructive and destructive moves. The implementation of a GRASP for the matrix decomposition problem is described in detail. Extensive computational experiments on literature and randomly generated problems are reported. Moreover, we propose a new procedure Reactive GRASP, in which the basic parameter that defines the restrictiveness of the candidate list during the construction phase is self-adjusted according to the quality of the solutions previously found. The approach is robust and does not require calibration efforts. On most of the literature problems considered, the new Reactive GRASP heuristic matches the optimal solution found by an exact column-generation with branch-and-bound algorithm.

Reviews

Required fields are marked *. Your email address will not be published.