skip to content

Equipe do PPG em Ciência da Computação é premiada em congresso internacional

Twitter icon
Facebook icon
Google icon
Divulgação
Com: 
Marcelo Afonso de Souza

O doutorando Jonatas Chagas e o professor orientador Marcone Jamilson Freitas Souza foram os vencedores da competição Bi-objective Traveling Thief Problem (Bi-TTP), promovida pelo 10º International Conference on Evolutionary Multi-Criterion Optimization (EMO). A competição analisou trabalhos de pesquisadores de diversas nacionalidades. 

O Bi-TTP é um problema de alta complexidade, pois combina dois problemas clássicos de otimização de natureza combinatória: o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP) e o Problema da Mochila (Knapsack Problem - KP).

O desafio – No Bi-TTP há um conjunto de cidades nas quais existem itens valiosos e pesados. Partindo de um depósito, o mochileiro deve visitar cada cidade uma vez e, ao fim, retornar ao início. Ao longo da rota, o mochileiro pode escolher itens para carregar, desde que seu peso total não exceda a capacidade de carga da mochila. O mochileiro sai do depósito com a sua mochila vazia e consegue se locomover com a sua velocidade máxima. No entanto, à medida que os itens escolhidos são colocados na mochila, seu peso aumenta e a velocidade do mochileiro diminui.

O Bi-TTP tem dois objetivos conflitantes: maximizar o valor total dos itens carregados na mochila e minimizar o tempo total gasto para visitar todas as cidades. 

A competição – Cada equipe participante deveria apresentar soluções para um conjunto de problemas-teste do Bi-TTP. Estes envolviam entre 280 e 33.810 cidades e entre 279 e 338.090 itens. Foram distribuídos pontos para cada problema-teste concluído. A equipe formada por Jonatas e Marcone garantiu o primeiro lugar ao desenvolver um algoritmo heurístico baseado no Biased Random-Key Genetic Algorithm (BRKGA) e no Non-Dominated Sorting Genetic Algorithm II (NSGA-II) para resolver o Bi-TTP. A dupla atingiu 25 dos 27 pontos distribuídos. O segundo e terceiro lugares garantiram 19 e 8 pontos, respectivamente.

Detalhes técnicos do Bi-TTP e da competição, bem como uma análise detalhada dos resultados de todas as equipes participantes podem ser acessados pela página oficial do EMO2019

Veja também

8 Abril 2020

O Sistema de Bibliotecas e Informação (Sisbin) da UFOP disponibilizou uma plataforma com conteúdos voltados para a área da Saúde...

Leia mais

7 Abril 2020

A Liga Acadêmica de Fisiologia Endócrina e Metabolismo (Lafem) da UFOP vai debater o tema "Covid-19 x Endocrinologia", abordando esta...

Leia mais

6 Abril 2020

Os formulários do Projeto Coorte de Universidades Mineiras (Cume) serão enviados para o e-mail pessoal ou institucional dos ex-alunos de...

Leia mais

31 Março 2020

O Laboratório de Análise Experimental e Simulação de Sistemas (Laess) do curso de Engenharia Mecânica da UFOP começa a produzir...

Leia mais