Fome e Abundância: Um Paradoxo Brasileiro?
17 a 22 de outubro de 2016
Trabalho 6944
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Teoria e Tecnologia da informação |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Lucas Zago Bissaro |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Métodos exatos e heuristicos para scheduling multicomponentes |
| Resumo | Problemas de otimização muticomponentes são caracterizados pela junção de mais de um problema de otimização combinatória, difíceis de solução isolada, e mais ainda quando devem ser otimizados simultaneamente. A melhor solução de um não necessariamente contém elementos da melhor solução do outro, impedindo que sejam otimizados separadamente. Pela dificuldade em resolvê-los em tempo hábil usando somente métodos exatos, agregam-se métodos heurísticos, que tornam a solução mais rápida, mas perde-se a garantia de se encontrar a melhor solução. A pesquisa tratou dois problemas multicomponentes: i) multiple travelling thief problem, combinação do TSP (caixeiro viajante) e do problema da mochila; ii) close enough ridematching problem, combinação do ridematching com o close enough TSP. No primeiro, têm-se M viajantes que devem passar por N cidades recolhendo itens ao longo do percurso. Cada cidade contém um conjunto de itens com diferentes valores e pesos, que devem ser colocados numa mochila de capacidade limitada. Para cada item pego, o viajante passa a andar mais devagar baseado no peso do item. Ao final eles devem fazer o trajeto no menor tempo possível recolhendo um valor total máximo. Os objetivo são conflitantes, então busca-se otimizar uma função que combina os dois. O trabalho é uma extensão do algoritmo proposto por um mestrando do departamento para o travelling thief problem, que possui apenas um viajante. No segundo, temos M motoristas e N passageiros espalhados em locais diferentes da cidade, e os motoristas devem dar carona aos passageiros. Cada motorista tem um limite de distância que aceita percorrer e um limite de vagas para passageiros. Cada passageiro estabelece a distância que está disposto a andar para a carona. Todos têm um destino final comum, no caso o campus da UFV. O objetivo do problema é atender o máximo de passageiros e minimizar a distância total percorrida pelos motoristas. O objetivo do trabalho foi estudar variações nas heurísticas propostas por um mestrando do departamento, que definiu o problema e métodos de solução. Utilizamos dois métodos para a solução inicial: um busca o passageiro mais próximo de um motorista, o insere em sua rota, repetindo o processo até não ser possível atender mais passageiros; o segundo, proposto deste trabalho, é baseado no primeiro, mas além de observar o passageiro mais perto de cada motorista, busca qual preencheria mais a rota, evitando assim que outro motorista o pegue deixando um mais distante, que não pode ser pego por este motorista. Ajuda assim a atender o máximo de passageiros. Após isso, aplica-se um método heurístico de busca local, que tenta trocar dois passageiros de motoristas e de posições na rota. Se a troca melhora a solução, faz a troca e tenta melhorar a partir dela. O método proposto atinge soluções melhores em alguns casos do problema, contribuindo para reduzir o tempo computacional de um modelo de programação matemática que utiliza tal solução como ponto de partida. |
| Palavras-chave | Roteamento, Heurísticas, Otimização Combinatória |
| Forma de apresentação..... | Painel |