Formulações matemáticas para o problema de roteamento periódicos em arcos capacitados com janelas de tempo

Abstract

Resumo: Esta tese apresenta o caso não direcionado do Problema de Roteamento Periódico em Arcos Capacitados com Janelas de Tempo. A aplicação real do problema é associada ao problema de planejamento do serviço de coleta de lixo. Além disso, são propostas duas formulações matemáticas para o problema, uma sem e outra com desigualdades válidas. A modelagem foi realizada na transformação do problema de roteamento em arcos em um problema equivalente de roteamento em nós. As duas formulações matemáticas foram validadas sobre um conjunto de 225 instâncias da literatura para o Problema do Carteiro Rural com Janelas de Tempo. As instâncias utilizadas na validação possuem até 60 nós, 90 arestas e 45 arestas requeridas. Para testar as duas formulações matemáticas, foram adaptadas para o Problema de Roteamento Periódico em Arcos Capacitados com Janelas de Tempo, 105 das 225 instâncias utilizadas na validação. As instâncias utilizadas nos testes possuem até 60 nós, 90 arestas, 45 arestas requeridas que necessitam até 142 atendimentos em 5 períodos e 4 veículos. Os resultados computacionais mostram que as formulações matemáticas aqui propostas são capazes de gerar ganhos em comparação com a formulação matemática para o Problema do Carteiro Rural com Janelas de Tempo proposta por Monroy-Licht, Amaya e Langevin (2014). Além disso, os resultados mostram que a formulação matemática com desigualdades válidas é superior à formulação matemática sem desigualdades válidas. Os resultados mais notáveis foram obtidos sobre as instâncias mais complexas, em que o tempo de processamento utilizado pelo solver GUROBI para obtenção de uma solução ótima da formulação matemática com desigualdades válidas, reduziu em média 73,34%, quando comparado ao resultado obtido sobre a formulação matemática sem desigualdades válidas. De modo geral, os resultados que consideram a formulação matemática com desigualdades válidas foram melhores ou iguais aos obtidos com a formulação matemática sem desigualdades válidas, em 84,76% das instâncias. Palavras-chave: Problema de Roteamento Periódico em Arcos Capacitados. Janelas de Tempo. Desigualdades Válidas.

Abstract: This thesis presents the undirected case of the Periodic Capacitated Arc Routing Problem with Time Windows. The real application of the problem is associated with the problem of waste collection planning. Furthermore, two mathematical formulations are proposed for the problem, with and without valid inequalities. The methodology used in the modeling was to transform the arc routing problem into an node routing problem. The two mathematical formulations were validated on a set of 225 instances of the literature for the Rural Postman Problem with Time Windows. The instances used in the validation have up to 60 nodes, 90 edges and 45 required edges. To test the two mathematical formulations, 105 of the 225 instances used in validation were adapted for the Periodic Capacitated Arc Routing Problem with Time Windows. The instances used in the tests have up 60 nodes, 90 edges, 45 required edges the require up to 142 services in 5 periods and 4 vehicles. Computational results show that the mathematical formulations, proposed here, overcame the mathematical formulation for the Rural Postman Problem with Time Windows proposed by Monroy-Licht, Amaya and Langevin (2014). Moreover, the results show that the mathematical formulation with valid inequalities is superior to the mathematical formulation without valid inequalities. The most notable results were obtained on the most complex instances, in which the processing time used by the GUROBI solver to obtain an optimal solution reduced on average 73.34% when compared the results obtained about the mathematical formulation with valid inequalities with that one obtained about the mathematical formulation without valid inequalities. In general, the results presented considering the mathematical formulation with valid inequalities were superior or equal to those obtained with the mathematical formulation without valid inequalities in 84.76% of the instances. Keywords: Periodic Capacitated Arc Routing Problem. Time Windows. Valid Inequalities.