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

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.