Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment

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.