Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos

• Processo: 18/15417-8
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2
• Data de Início da vigência: 01 de maio de 2019
• Data de Término da vigência: 30 de abril de 2024
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Antônio Augusto Chaves
• Beneficiário: Antônio Augusto Chaves
• Instituição Sede: Instituto de Ciência e Tecnologia (ICT). Universidade Federal de São Paulo (UNIFESP). Campus São José dos Campos. São José dos Campos , SP, Brasil
• Pesquisadores associados: Luiz Antonio Nogueira Lorena
• Vinculado ao auxílio: 12/17523-3 - Novos métodos híbridos para resolução de problemas de otimização combinatória, AP.JP
• Auxílio(s) vinculado(s): 25/04599-1 - 34th European Conference on Operational Research (EURO 2025), AR.EXT
• Bolsa(s) vinculada(s): 21/09482-4 - Modelos e métodos de solução para problemas de atribuição de pacientes em leitos e programação de salas de cirurgia, BP.PD; 20/07145-8 - Uma meta-heurística adaptativa aplicada ao problema dial-a-ride e variantes, BP.PD; 20/00198-9 - Desenvolvimento de uma meta-heurística híbrida com parâmetros adaptativos para resolução do problema de escalonamento de técnicos em campo, BP.MS; 20/03408-4 - Uma meta-heurística híbrida aplicada a variantes do problema do caixeiro viajante multiproduto com prioridades, BP.MS
• Assunto(s): Meta-heurística Otimização combinatória Algoritmos genéticos
• Palavra(s)-Chave do Pesquisador: algoritmo genético | Configuração de meta-heurísticas | Heurísticas de busca local | Otimização Combinatória | Meta-heurísticas

Resumo

O estudo de meta-heurísticas eficientes para resolver problemas de otimização tem sido alvo de muitas pesquisas por parte da comunidade científica. Para obter bons resultados em termos de qualidade de soluções e tempo computacional é importante haver uma boa configuração da meta-heurística. Este processo de especificação do fluxo de controle e dos valores dos parâmetros de um método é uma tarefa árdua. Desta forma, este projeto tem como ideia central o desenvolvimento e aperfeiçoamento do método adaptativo Biased Random-key Genetic Algorithm (A-BRKGA) para escolher quais componentes serão utilizados e em qual sequência (fluxo do A-BRKGA) e quais parâmetros utilizar enquanto uma instância de um problema esteja sendo resolvida. Para tal, serão estudadas técnicas de aprendizagem de máquinas e mecanismos adaptativos e reativos para construir um A-BRKGA com configuração on-line de parâmetros e fluxo de controle. O principal objetivo é gerar um algoritmo eficiente para resolver problemas de otimização combinatória e que o código seja fácil de ser reutilizado. Para avaliar o método proposto serão estudados quatro problemas de otimização com aplicações industriais e logísticas: problema de escalonamento de técnicos em campo, problema do caixeiro viajante multiproduto com prioridades, problema de localização de facilidades capacitadas em dois níveis, problema de localização de facilidades com sobreposição de cobertura. Os testes computacionais utilizarão problemas testes disponíveis na literatura e estudos de casos reais. O método será comparado com algoritmos estado-da-arte por meio de análises estatísticas. (AU)

Publicações científicas

(17)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

DA SILVA, TIAGO TIBURCIO; CHAVES, ANTONIO AUGUSTO; YANASSE, HORACIO HIDEKI; LOUREIRO LUNA, HENRIQUE PACCA. The multicommodity traveling salesman problem with priority prizes: a mathematical model and metaheuristics. COMPUTATIONAL & APPLIED MATHEMATICS, v. 38, n. 4, DEC 2019. (18/15417-8)

MAURI, GERALDO REGIS; BIAJOLI, FABRICIO LACERDA; RABELLO, ROMULO LOUZADA; CHAVES, ANTONIO AUGUSTO; RIBEIRO, GLAYDSTON MATTOS; LORENA, LUIZ ANTONIO NOGUEIRA. Hybrid metaheuristics to solve a multiproduct two-stage capacitated facility location problem. International Transactions in Operational Research, v. 28, n. 6, p. 3069-3093, NOV 2021. (18/15417-8)

DA SILVA, TIAGO TIBURCIO; CHAVES, ANTONIO AUGUSTO; YANASSE, HORACIO HIDEKI; LOUREIRO LUNA, HENRIQUE PACCA. The multicommodity traveling salesman problem with priority prizes: a mathematical model and metaheuristics. COMPUTATIONAL & APPLIED MATHEMATICS, v. 38, n. 4, p. 25-pg., 2019-12-01. (18/15417-8)

ARAUJO, ELISEU J.; CHAVES, ANTONIO A.; LORENA, LUIZ A. N.. A mathematical model for the coverage location problem with overlap control. COMPUTERS & INDUSTRIAL ENGINEERING, v. 146, AUG 2020. (18/15417-8, 16/01860-1)

LORENA, LUIZ H. N.; CHAVES, ANTONIO A.; MAURI, GERALDO R.; LORENA, LUIZ A. N.; IEEE. An Adaptive Biased Random-key Genetic Algorithm for Rank Aggregation with Ties and Incomplete Rankings. 2022 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2022-01-01. (18/15417-8)

DA SILVA, TIAGO TIBURCIO; CHAVES, ANTONIO AUGUSTO; YANASSE, HORACIO HIDEKI. A new multicommodity flow model for the job sequencing and tool switching problem. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, v. 59, n. 12, p. 3617-3632, JUN 18 2021. (16/01860-1, 18/15417-8)

SCHENEKEMBERG, CLEDER M.; CHAVES, ANTONIO A.; COELHO, LEANDRO C.; GUIMARAES, THIAGO A.; AVELINO, GUSTAVO G.. The dial-a-ride problem with private fleet and common carrier. Computers & Operations Research, v. 147, p. 14-pg., 2022-07-13. (18/15417-8, 16/01860-1, 20/07145-8)

SCHENEKEMBERG, CLEDER MARCOS; GUIMARAES, THIAGO ANDRE; CHAVES, ANTONIO AUGUSTO; COELHO, LEANDRO C.. A Three-Front Parallel Branch-and-Cut Algorithm for Production and Inventory Routing Problems. TRANSPORTATION SCIENCE, v. N/A, p. 22-pg., 2023-08-16. (20/07145-8, 18/15417-8, 16/01860-1)

CHAVES, ANTONIO A.; OLIVEIRA, RUDINEI M.; GONCALVES, JOSE F.; LORENA, LUIZ A. N.. An adaptive biased random-key genetic algorithm for the tactical berth allocation problem. 39TH ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING, SAC 2024, v. N/A, p. 8-pg., 2024-01-01. (22/05803-3, 18/15417-8)

DAMM, R. B.; CHAVES, A. A.; RIVEAUX, J. A.; RONCONI, D. P.. Scheduling technicians and tasks through an adaptive multi-objective biased random-key genetic algorithm. ANNALS OF OPERATIONS RESEARCH, v. N/A, p. 36-pg., 2024-10-13. (18/15417-8, 22/06747-0, 22/05803-3, 13/07375-0)

MAURI, GERALDO R.; LORENA, LUIZ H. N.; LORENA, LUIZ A. N.; CHAVES, ANTONIO A.; IEEE. Solving the Point Feature Cartographic Label Placement problem using Jaccard index as a measure of labels intersection. 2022 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2022-01-01. (18/15417-8)

CHAVES, A. A.; RESENDE, M. G. C.; SILVA, R. M. A.. A RANDOM-KEY GRASP FOR COMBINATORIAL OPTIMIZATION. JOURNAL OF NONLINEAR AND VARIATIONAL ANALYSIS, v. 8, n. 6, p. 27-pg., 2024-01-01. (22/05803-3, 18/15417-8)

CHAVES, ANTONIO AUGUSTO; VIANNA, BARBARA LESSA; DA SILVA, TIAGO TIBURCIO; SCHENEKEMBERG, CLEDER MARCOS. A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem. EXPERT SYSTEMS WITH APPLICATIONS, v. 238, p. 16-pg., 2023-10-04. (18/15417-8, 20/07145-8, 20/03408-4, 16/01860-1)

SCHENEKEMBERG, CLEDER M.; CHAVES, ANTONIO A.; GUIMARAES, THIAGO A.; COELHO, LEANDRO C.. Hybrid metaheuristic for the dial-a-ride problem with private fleet and common carrier integrated with public transportation. ANNALS OF OPERATIONS RESEARCH, v. N/A, p. 39-pg., 2024-07-03. (18/15417-8, 20/07145-8, 16/01860-1)

NOGUEIRA LORENA, LUIZ HENRIQUE; CHAVES, ANTONIO AUGUSTO; NOGUEIRA LORENA, LUIZ ANTONIO; IEEE. A Biased Random-key Genetic Algorithm with a Local Search Component for the Optimal Bucket Order Problem. 2021 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC 2021), v. N/A, p. 8-pg., 2021-01-01. (18/15417-8)

DO NASCIMENTO, MARCELO BRANCO; CHAVES, ANTONIO AUGUSTO; IEEE. An Automatic Algorithm Configuration based on a Bayesian Network. 2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2020-01-01. (18/15417-8)

CHAVES, ANTONIO AUGUSTO; NOGUEIRA LORENA, LUIZ HENRIQUE; IEEE. An Adaptive and Near Parameter-Free BRKGA Using Q-Learning Method. 2021 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC 2021), v. N/A, p. 8-pg., 2021-01-01. (18/15417-8)