Nova metodologia para resolução de problemas de transporte em casos esparsos

Abstract

Resumo: Entre áreas de estudo da Programação Linear o Problema de Transporte é uma das aplicações de destaque. Os Problemas de Transporte podem ser classificados em densos ou esparsos. O modelo é denominado denso quando existem todas as ligações entre origens e destinos e esparsos quando algumas ou várias destas ligações não existem. O presente trabalho propõe uma alteração no algoritmo de resolução do Problema de Transporte para o caso esparso, que consiste basicamente da inclusão de uma nova origem e um novo destino com elevado custo de transporte para as origens e destinos originais e custo nulo entre a origem e destino acrescentados. O método é demonstrado e testado para instâncias geradas aleatoriamente. Depois de feita a explanação sobre o funcionamento do método e de demonstrar a validade das modificações, os conceitos são implementados computacionalmente. Os testes realizados mostram ganhos significativos no tempo de processamento. Para problemas com densidade 0,05, este tempo chega a ser de somente 25% do necessário para resolver o mesmo problema através do algoritmo tradicional, onde as ligações não existentes são admitidas com custo extremamente elevado. Em problemas com densidade 0,3 este tempo é de aproximadamente 50% daquele necessário pelo tradicional. O método desenvolvido tem desempenho equivalente quando utilizado sobre Problemas Densos. Também é feita uma explanação sobre a utilização de grafos, que são facilitadores na determinação de locais para colocação de variáveis degeneradas e sua aplicação na determinação dos ciclos. Discute-se a importância de utilizar características peculiares de um problema para métodos específicos de resolução. A economia no processamento pode viabilizar a utilização de modelagens deste tipo em processos meta-heurísticos que utilizem iterativamente o problema de transporte.

Abstract: Among the Linear Programming areas, the Transport Problem is one of the highlights applications. The Transport problems may be classified as dense or sparse. The model is named dense if there are connections from every origin to each destinations and sparse when some or several of these connections do not exist. This paper proposes a change in the algorithm of solving the transportation problem for the sparse case which basically consists of adding a new origin and a new demand with high transportation cost to the original sources and demands, and a null cost between the source and demand added. The method is demonstrated and tested for randomly generated instances. After the explanation made on the method operation and demonstrate the validity of the modifications, the concepts are computationally implemented. Tests showed significant gains in processing time. For problems with density 0.05, the time was only 25% of the time necessary to solve the same problem using the traditional algorithm, in which not permitted connections are admitted with extremely high cost. Problems with density 0.3 presented time approximately 50% of that required for the traditional algorithm. The method developed has an equivalent performance when used on dense problems. It's also made an explanation on the use of graphs, which are facilitators in determining locations for degenerate variables allocation and is applied in determining cycles. It is discussed the importance of using the unique characteristics of a specific problem solving methods. The savings in processing time can enable this modeling usage in metaheuristics processes that iteratively uses the transportation problem.