A RANDOM-KEY GRASP FOR COMBINATORIAL OPTIMIZATION

Autor(es)

Chaves, A. A. ; Resende, M. G. C. ; Silva, R. M. A.

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF NONLINEAR AND VARIATIONAL ANALYSIS; v. 8, n. 6, p. 27-pg., 2024-01-01.

Resumo

This paper proposes a problem-independent GRASP metaheuristic by using the random-key tic 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. (AU)

• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 18/15417-8 - Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2