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

22 Outubro 2021

O webinário desenvolvido pelo Núcleo de Pesquisas Impérios e Lugares no Brasil (ILB/PPGHIS-UFOP) busca divulgar trabalhos científicos produzidos pelo grupo...

Leia mais

20 Outubro 2021

Na última terça-feira (19), a Câmara dos Deputados convidou diversos pesquisadores da área ambiental para debater sobre o Decreto-Lei nº...

Leia mais

5 Outubro 2021

Os professores do Departamento de Física da UFOP Hermano Velten e Júnior Diniz Toniato, em colaboração com o professor Júlio...

Leia mais

5 Outubro 2021

O Conselho Editorial da revista "Além dos Muros da Universidade" (Alemur), da UFOP, abre inscrições para submissão de artigos para...

Leia mais