Approximate algorithms for decentralized Supply Chain Formation

Abstract

[eng] Supply chain formation involves determining the participants and the exchange of goods within a production network. Today’s companies operate autonomously, making local decisions, and coordinating with other companies to buy and sell goods along their supply chains. Decentralized decision making is well suited to this scenario since it better preserves the privacy of the participants, offers better scalability on large-scale scenarios, and is more resilient to failure. Moreover, decentralized supply chain formation can be tackled either by means of peer-to-peer communication between supply chain participants or by introducing local markets that mediate the trading of goods. Unfortunately, current approaches to decentralized supply chain formation, both in the peer- to-peer and the mediated scenario, are unable to provide computationally and economically efficient solutions to the supply chain formation problem. The main goal of this dissertation is to provide computationally and economically efficient methods for decentralized supply chain formation both in the peer-to-peer and the mediated scenario. This is achieved by means of two optimized max-sum based methods for supply chain formation. On the one hand, we contribute to peer-to-peer supply chain formation via the so-called Reduced Binarized Loopy Belief Propagation (rb-lbp) algorithm. The rb-lbp algorithm is run by a multi-agent system in which each of the participants in the supply chain is represented by a computational agent. Moreover, rb-lbp’s message computation mechanisms allow the efficient computation of max-sum messages. This results in an algorithm that is able to find solutions to the supply chain formation problem of higher value than the state of the art while reducing the memory, bandwidth and computational resources required by several orders of magnitude. On the other hand, we contribute to mediated supply chain formation via the so-called CHaining Agents IN Mediated Environments (chainme) algorithm. The chainme algorithm is run by a multi-agent system in which each of the participants and each of the goods in the supply chain is represented by a computational agent. In chainme participant agents communicate exclusively with the agents representing the goods who act as mediators. Likewise rb-lbp, chainme is also endowed with a message computation mechanism for the efficient computation of max-sum messages. This results in an algorithm that is able to find economically efficient solutions while requiring a fraction of the computa- tional resources needed by the state-of-the-art methods for both peer-to-peer and mediated supply chain formation. Finally, the design and implementation of both of our contributions to decentralized supply chain formation follow the same methodology. That is, we first map the problem at hand into a local term graph over which max-sum can operate. Then, we assign each max-sum local term to a computational agent. Last, we derive computationally efficient expressions to assess the max-sum messages exchanged between these agents. Although our methodology proved to be valid for the design of SCF algorithms, its generality makes it appear as a promising candidate for other multi-agent coordination problems.