Governo Federal

Dados do Trabalhos de Conclusão

UNIVERSIDADE FEDERAL DO PARANÁ
MÉTODOS NUMÉRICOS EM ENGENHARIA (40001016030P0)
PROPOSTA DE UM MODELO MATEMÁTICO PARA O PROBLEMA DE ROTEAMENTO EM ARCOS CAPACITADO E PERIÓDICO
GUILHERME VINICYUS BATISTA
DISSERTAÇÃO
25/04/2014

O Problema de Roteamento em Arcos Capacitado e Periódico (PCARP) é uma das variantes dos Problemas de Roteamento em Arcos em que cada arco tem uma demanda geralmente associada a uma frequência ao longo de um horizonte de tempo bem definido. Para solucioná-lo é necessário fazer um planejamento de modo que todas as demandas sejam atendidas da melhor maneira possível sem exceder a capacidade dos carros que farão os atendimentos. É um problema recente e pouco explorado na literatura, porém com grande aplicabilidade em contextos reais como coleta de lixo, atividades de monitoramento, inspeção e manutenção. O objetivo geral é apresentar uma modelagem matemática capaz de resolver um problema que tem a essência de todo PCARP, mas apresenta características diferenciadas das já propostas na literatura por causa de fatos como: não necessitar voltar a um depósito ao final de um dia e poder atrasar algum atendimento se necessário. Para isso foi feito um levantamento bibliográfico dos problemas que mais se assemelham e analisadas as diferenças entre os mesmos. Finalmente, o modelo proposto foi implementado, alcançando bons resultados com poucos atrasos em diferentes estruturas de grafos.

Problema de Roteamento em Arcos Capacitado e Periódico. Problemas de Roteamento em Arcos. Modelagem Matemática.
The Periodic Capacitated Arc Routing Problem (PCARP) is a class of Arc Routing Problems in that each arc has a demand usually associated to a frequency over a well defined time horizon. To solve it is necessary to do a planning so that it covers all the demands in the best way possible without exceeding the vehicles capacity at service. It is a recent problem and not intensively studied at the literature, though with a large applicability in various real life applications such as waste collection, network monitoring, inspection and maintenance. The main aim is to present a mathematical formulation capable of solving a problem that has the essence of every PCARP, but that presents some distinguished characteristics from those already proposed at the literature. The distinguished characteristics are that the vehicle does not need to come back to the deposit at the end of the day and that the service can be delayed if necessary. For this, it was done a bibliographical research of the nearest problems and analyzed the differences among them. Finally, the proposed model was implemented, reaching good results without delay at several graph structures.
Periodic Capacitated Arc Routing Problem. Arc Routing Problems. Mathematical Formulation.
1
95
PORTUGUES
UNIVERSIDADE FEDERAL DO PARANÁ

Contexto

PROGRAMAÇÃO MATEMÁTICA
ABORDAGEM DE PROBLEMAS DA PESQUISA OPERACIONAL
PESQUISA OPERACIONAL

Banca Examinadora

CASSIUS TADEU SCARPIN
Sim
Nome Categoria
NEIDA MARIA PATIAS VOLPI Docente
LAURO CESAR GALVAO Participante Externo
LEANDRO MAGATAO Participante Externo

Vínculo

CLT
Instituição de Ensino e Pesquisa
Ensino e Pesquisa
Não