A random-key GRASP for combinatorial optimization
A.A. Chaves, M.G.C. Resende, R.M.A. Silva · Journal of Nonlinear and Variational Analysis · 2024
This paper proposes a problem-independent GRASP metaheuristic by using the random-key optimizer (RKO) paradigm.GRASP (Greedy Randomized Adaptive Search Procedure) is a metaheuristic for combinatorial optimization that repeatedly applies a semi-greedy construction procedure followed by a local search procedure.The best solution found over all iterations is returned as the solution of the GRASP.Continuous GRASP (C-GRASP) is an extension of GRASP for continuous optimization in the unit hypercube.A random-key optimizer (RKO) uses a vector of random keys to encode a solution to a combinatorial optimization problem.It uses a decoder to evaluate a solution encoded by the vector of random keys.A random-key GRASP is a C-GRASP where points in the unit hypercube are evaluated employing a decoder.We describe random key GRASP consisting of a problem-independent component and a problem-dependent decoder.As a proof of concept, the random-key GRASP is tested on five NPhard combinatorial optimization problems: traveling salesman problem, tree of hubs location problem, Steiner triple covering problem, node capacitated graph partitioning problem, and job sequencing and tool switching problem.