Estratégias de participação em leilões combinatoriais aplicadas em um problema de transporte de derivados de petróleo

Recent researches have shown that approaches based on multi-agent systems (MAS) and market mechanisms like auctions are efficient on the resolution of planning problems in supply chains. This work uses the combinatorial auction-based MAS paradigm and participation strategies in auctions for solving the problem of transporting oil derivatives of PETROBRAS - Petroleo Brasileiro S/A, called Simplified Problem of Transporting Oil Derivatives (SPTOD), which is characterized as a planning problem in supply chains. In combinatorial auctions, the winner determination is a NP-Complete problem without approximation algorithms, whose computational cost increases with the number of bids received by the auctioneer. In this context, this work aims at enlarging the scope of application of combinatorial-auction mechanisms in planning problems by using a heuristic strategy for participation in auctions, besides serving as a support tool for decision-making process by specialists of industrial oil. The results were drawn from several scenarios where the MAS was used with the proposed strategy (global evaluation of needs) and with other strategies for comparison (general – all possible auctions – and greedy – only one auction). The results show that the use of the proposed strategy reduces the processing time when compared to the general strategy and that the quality of the solution is preserved in comparison with the general and greedy strategies. Other contributions of this work are the development of a MAS to realize the planning of transporting oil derivatives between producing and consuming basis having as negotiation model the combinatorial auction-based mechanism and a proposition of a decentralized model where several combinatorial auctions can be run simultaneously.Pesquisas recentes mostram que abordagens baseadas em sistemas multiagentes (SMA) e mecanismos de mercado como leilões são eficazes para encontrar soluções factíveis para problemas de planejamento em cadeias de suprimento. Esta dissertação aborda a utilização do paradigma de SMA baseado em Leilões Combinatoriais e o uso de estratégias de participação em leilões na resolução do problema de transporte de derivados de petróleo em uma rede multimodal da PETROBRAS – Petróleo Brasileiro S/A, denominado Problema de Transporte de Derivados de Petróleo Simplificado (PTDPS), que se caracteriza como um problema de planejamento em cadeias de suprimento. Em leilões combinatoriais, a determinação do vencedor é um problema NP-Completo sem algoritmos de aproximação, cujo custo computacional aumenta com o número de ofertas recebidas pelo leiloeiro. Este trabalho tem por objetivo aumentar o escopo de aplicação de leilões combinatoriais em problemas de planejamento pelo uso de uma estratégia heurística de participação em leilões, além de servir como uma ferramenta de apoio à tomada de decisão por especialistas da indústria petrolífera. Os resultados obtidos a partir da aplicação do SMA desenvolvido em uma série de cenários para a estratégia proposta (avaliação da necessidade global) e outras de referência (geral - todos os leilões possíveis - e gulosa – somente um leilão) foram comparados entre si e demonstram que a utilização da estratégia proposta reduz o tempo de processamento em relação à estratégia geral e sem perda da qualidade da solução em comparação com as estratégias geral e gulosa. Outras contribuições deste trabalho são um SMA para realizar o planejamento do transporte de derivados de petróleo tendo como modelo de negociação o mecanismo de leilões combinatoriais e a proposição de um modelo descentralizado onde diversos leilões combinatoriais podem ser executados simultaneamente