Proposta de um modelo matemático para o problema de roteamento em arcos capacitado e periódico
Resumo
Resumo: 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. Abstract: 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.
Collections
- Teses & Dissertações [10011]