Uma abordagem para a resolução do problema de transporte com custo fixo

Abstract

Resumo: O Problema de Transporte com Custo Fixo (PTCF) é uma classe da Programação Linear (PL), em que o custo total de envio de um produto, de uma origem para um destino, é composto por um custo unitário de transporte, proporcional à quantidade de itens enviados, e um custo fixo, associado à abertura da rota. O PTCF é NP-hard e além disso possui uma característica que à medida que a diferença entre o valor do custo unitário e o do custo fixo aumenta, o tempo computacional sofre alteração, piorando o desempenho. A base de problemas gerada por Sun, em 1998, foi adotada para realizar os testes computacionais. Após revisar alguns métodos da literatura, as heurísticas HEUR-1, HEUR-2, KOWA e HEUR-3 foram desenvolvidas e implementadas, utilizando estrutura de árvores e com otimização em relação ao cálculo das variáveis duais. Após realizar os testes computacionais, os métodos desenvolvidos foram comparados entre si constatando-se a superioridade de HEUR-3. A seguir, HEUR-3 foi comparado com BT, GIP, CORE2 e CORE3, que são métodos da literatura utilizados para resolver o PTCF além de comparar o desempenho com o solver Gurobi. Para todos os testes foi definido como critério de parada o tempo limite de 120 segundos. Cabe ressaltar que HEUR-3 e BT são heurísticas puras enquanto GIP, CORE2 e CORE3 fazem uso de um solver em determinado momento da rotina. Os valores obtidos para o PTCF em cada método da literatura e solver aqui citados, juntamente com HEUR-3, são analisados e discutidos parte a parte. A conclusão dessa tese mostra que HEUR-3 é superior quando comparado ao solver GUROBI e aos métodos BT, CORE2 e CORE3, o que não ocorre apenas com relação à técnica GIP. Palavras-chave: Heurística, implementação computacional, Gurobi.

Abstract: The Fixed Charge Transportation Problem (FCTP) is a Linear Programming (LP) class, whereby the total shipping cost of a product, from a source to a destination, consists of a unit transportation cost, proportional to the amount of sent items and a fixed charge associated with the opening of the route. The FCTP is NP-hard and has a characteristic in which, as far as the difference between the value of the unit cost and the fixed charge increases, the computational time changes, worsening the performance. The base of problems generated by Sun, in 1998, was adopted to perform the computational tests. Following the review of some literature methods, the heuristics HEUR-1, HEUR-2, KOWA and HEUR-3 were developed and implemented, using a tree structure and with optimization in relation to the calculation of dual variables. After executing the computational tests, the developed methods were compared to each other, confirming the superiority of HEUR-3. Next, HEUR-3 was compared to BT, GIP, CORE2 and CORE3, which are literature methods used to solve the FCTP, in addition to compare the performance with the Gurobi solver. For all tests, the timeout of 120 seconds was set as stop criterion. It should be noted that HEUR-3 and BT are pure heuristics while GIP, CORE2 and CORE3 make use of a solver at a given moment of the routine. The values obtained for the FCTP in each of the literature methods and solver listed here, together with HEUR-3, are analyzed and discussed side by side. The conclusion of this thesis shows that HEUR-3 is superior when compared to the GUROBI solver and with BT, CORE2 and CORE3 methods, which does not only occur merely to the GIP technique. Keywords: Heuristic, computational implementation, Gurobi.