Multi-Agent Decision Support System for Supply Chain Management Yevgeniya Kovalchuk Department of Computing and Electronic Systems University of Essex +44(0)1206 87 3805 yvkova@essex.ac.uk ABSTRACT and ever-changing process, especially nowadays, when This paper presents an extended abstract of the author’s doctoral enterprises move their business on-line. Taking into research project on developing a multi-agent intelligent system consideration market globalisation, companies often run for automatic managing supply chains. Supply chain distributed businesses, having suppliers and customers all over management (SCM) is a very complex and dynamic the world. To deal with their contractors, organisations use the environment. The doctoral work, which started in October 2005, Internet to participate in electronic commerce, where business is dedicated to finding better solutions for successful occurs very fast. To be able to react to all changes quickly, performance in the domain of real-time SCM. companies are looking for applications that can support dynamic strategies and adapt to new conditions in the environment. The development of such an intelligent decision support system for Categories and Subject Descriptors SCM is the main objective of the author’s PhD project. I.2.6 [Artificial Intelligence]: Learning Although the aim is to develop an integrated application for H.4.2 [Information Systems Applications]: Types of Systems – SCM, due to its complexity, it is difficult to address all the decision support issues which can arise in the domain of SCM. To narrow the research scope, the project is mainly focused on the demand part General Terms of the supply chain. In particular, different methods for Economics, Algorithms, Design, Experimentation predicting customer offer prices that could result in customer orders (winning bidding prices) are explored and compared in the system. The motivation is that expected findings not only Keywords can improve a company’s performance while running its supply Supply Chain Management, Trading Agents, Decision Support chains, but could also be applied to financial markets and online Systems, Multi-Agent Systems, Prediction, Learning, Neural auctions where the task of predicting winnings bidding prices is Networks, Genetic Programming. crucial. The TAC SCM game, where software agents developed by different research groups can compete against each other in 1. INTRODUCTION the context of the SCM, is used as a test bed to evaluate the While running their business, enterprises usually deal with a proposed algorithms. This simulated environment was number of activities, such as: procurement, production, implemented by Carnegie Mellon University and the Swedish warehouse management, selling, marketing, and customer Institute of Computer Science (SICS) in 2003 as part of the servicing among others. To help them to manage these activities, International Trading Agent Competition organisations try to automate their business processes. Usually, (http://www.sics.se/tac/). The game is now probably the best independent software and hardware solutions are used for each vehicle for testing SCM systems as it encapsulates many of the of the activities. However in practice, all the activities are highly tradeoffs that could be found in real SCM environments: time- connected and interdependent. To integrate some of them in a constraints, network latency, unpredictable opponents, etc. single process is the task of supply chain management (SCM). The rest of this paper is organized as follows. The description of The SCM is concerned with negotiating with suppliers for raw the TAC SCM scenario and overview of related work are materials, competing for customer orders, managing inventory, provided first. Then, the research approach followed is scheduling production, and delivering goods to customers. In presented. The results achieved so far along with the plans for addition to its complexity, the SCM is also a time-constrained future work are given next. The paper closes with the conclusions. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are 2. THE TAC SCM SCENARIO not made or distributed for profit or commercial advantage and that According to the TAC SCM scenario [4], there are six agents copies bear this notice and the full citation on the first page. To copy competing in the game that act as product manufacturers (Figure otherwise, or republish, to post on servers or to redistribute to lists, 1). Their main tasks are to buy components from suppliers, requires prior specific permission and/or a fee. produce computers and sell them to customers. The behaviour of 10th Int. Conf. on Electronic Commerce (ICEC) ’08 Innsbruck, Austria Copyright 2008 ACM 978-1-60558-075-3/08/08 ...$5.00. both suppliers and customers are simulated by the TAC server. $ Statement of account Bank Expenses: Income: - Component costs + Sales revenue - Inventory costs + Bank interest - Penalties for late delivery + - - Overdraft penalties Competitor Agents 1) Which RFQs to issue 1) Which customer RFQs to which suppliers? to answer, and which Supply 2) Which supplier price to set? Demand Market Offers to accept? 2) Which PCs and when Market Variable Reports to deliver to customers? Reports Variable 1. RFQ Supply 1. RFQ Demand 3. Order 3. Order $$ $ $ 2. Offer 2. Offer Suppliers TAC SCM Agent Reasonable quantity: Reasonable quantity: production needs vs. customers needs vs. Customers inventory cost? inventory cost? Which products to Component Product produce and when? Inventory Inventory Reports Component inventory: Product inventory: Reports + Deliveries from suppliers + Produced PCs - Production needs - Deliveries to Customers Production Delivery Schedule Schedule Component Inventiry Product Inventory Limited Production Capacity Manufacturing Figure 1. TAC SCM environment The game lasts for 220 simulated days, 15 seconds of real time within the SCM domain and develops various methods to tackle each. Each day an agent has to perform the following activities: them. A number of works have been dedicated to the problem of (i) component procurement, (ii) product sales, (iii) production finding optimal prices to offer customers in response to their scheduling, and (iv) delivery scheduling. The aim of each requests. As this problem correlates with the objectives of the participating manufacturer is to maximize their profit: the agent author’s PhD thesis, the overview of these works is presented with the highest bank balance at the end of the game wins. The here. agent spends money on buying components, paying a storage The methods applied by different agents to solve the issue can cost for keeping an inventory of components and PCs, paying be divided into two major categories. The first group of agents penalties for late deliveries of customer orders, and for bank estimates the winning price for each RFQ and assumes that this overdrafts. The income of the agent consists of the revenue from price would result in an order [5, 7, 9]. The second group PCs sales and interest on positive bank balance. predicts for each possible bidding price the probability that it is going to be accepted [1, 10, 11, 12, 14]. 3. RELATED WORK An overview of the strategies applied to the problem of finding The TAC SCM community involves many research groups optimal offer prices up to 2004 is provided in [15]. The paper throughout the world. Each team investigates different issues also presents the comparison of different learning algorithms for accomplishing the task in the context of the TAC SCM 4. RESEARCH APPROACH environment. Specifically, the following methods were To deal with the complexity of the SCM domain, a multi-agent analyzed: neural network with a single hidden layer and using approach is applied to design the system. This allows to break back propagation, M5 regression trees, M5 regression trees the whole system down into separate building blocks, each boosted with additive regression, decision stumps (single-level concentrating on a particular part of the supply chain. By decision trees) boosted with additive regression, J48 decision replacing one building block with another and by combining trees, J48 decision trees boosted with AdaBoost and BoosTexter them in different ways, different versions of the system can be [20, 21], support vector machines, naïve Bayes, and k-nearest created in order to check how separate algorithms affect its neighbours. Their experimental results showed that M5 trees overall performance. The system includes the following agents: and BoosTexter give the minimum root mean squared error. Manager, Demand Agent, Supply Agent, Inventory Agent, In their up-to-date versions in addition to the above mentioned Production Agent, and Delivery Agent. The Manager agent is methods, the TAC SCM agents also use other techniques. In responsible for the communication with the external contractors particular, SouthamptonSCM [7] applies a fuzzy reasoning (suppliers, customers, bank, etc.), as well as managing all other inference mechanism to determine offer prices according to the agents. The Demand Agent decides which customer RFQs to agent’s inventory level, the market demand and the time in the answer and with what price. The remit of the Supply Agent is game. TacTex uses additive regression with decision stumps the procurement of low cost components on time from suppliers; [13]. In the earlier version of the agent, the developers used the agent tracks the supplier market in order to choose the linear regression on six data points to generate a linear function suppliers with lower prices and lower level of suspended which is modified then by the day factor [14]. The day factor deliveries. The Inventory Agent manages the component and measures the effect of the due date on offer acceptance. A PCs stocks in order to satisfy the needs of the Production and similar approach is implemented in Botticelli [3] and CMieux Delivery Agents while at the same time minimising holding [2]. The latter computes a linear least squares fit for the selling costs. The Production Agent is responsible for scheduling prices of each product over the past several game days. current production and projecting production for the future. Additionally, the agent enforces lower and upper bounds on the Finally, the Delivery Agent deals with delivering PCs to predictions to ensure that the prediction remains relatively customers according to their orders and on time to prevent conservative. The agent maintains the probability distribution penalties. for each PC type mapping bidding prices to the likelihood of To model the agents’ behaviour, different techniques are used in winning orders with these prices. The distributions are learned the system, such as: constraint satisfaction, planning, logical off-line using data from previously played games to build a rules, and online adjustments. The majority of the algorithms are regression tree. The developers of the agent showed that under based on simple heuristics. However, testing the system in the certain assumptions this pricing problem can be reduced to the TAC SCM game showed that these algorithms do not perform continuous knapsack problem [1]. Mertacor [12] selected the well against stronger agents developed by other research teams. M5 data mining algorithm applied to historical data from past To improve the performance of the system, a predictive games in order to choose which attributes influence offer prices. approach is required. According to this, a number of predictive It also uses two on-line modelling mechanisms in order to algorithms are implemented in the Demand part of the SCM that handle unexpected circumstances that may arise with regard to deals with selling products to customers. The most crucial selling prices. The agent applies the k-Nearest Neighbours problem here is of predicting customer winning bidding prices. algorithm then to find the probability of offer acceptance for More specifically, a customer sends requests for quotes (RFQs) each bid placed. The probability of winning customer offers is indicating which products, in what quantity and for when he also used in the bidding strategies implemented by MinneTAC wants them. The customer also indicates the reserve price – the [10] and DeepMaize [11]. RedAgent [9] uses an internal highest price he is willing to pay for the product. Competing marketplace structure with competing bidders to set offer prices. agents answer these customer RFQs with their offers specifying The agent computes offer prices as a sum of 3 terms: a base the bidding prices they are willing to offer to the customer. For price of the PC, an estimated discounted profit for the product each RFQ, the customer chooses the lowest price proposed by (the difference between base price and order price, discounted all manufacturers and places an order. So the problem here is to according to the number of days left until the order expires), and set optimal customer offer prices, which should be high enough a discounted penalty. PackaTAC [5] sets prices according to the to allow for profit and at the same time low enough to be market state taking into consideration the lowest and highest accepted by customers. previous day prices and the current demand level. So far, 3 different strategies have been developed to tackle the According to [8] all the aforementioned methods do not take problem. According to the first strategy, the system predicts into consideration market conditions that are not directly bidding prices for each customer RFQ which will more probably observable. The authors propose a clustering based approach to result in customer orders. The predictions are based on the identify the market regime and predict market changes. They use current market situation and also on RFQs’ details. 3 algorithms a Gaussian Mixture Model to represent the probabilities of based on the Neural Network (NN) learning technique are market prices that allows the determination of the probability of implemented to perform the forecasting. In particular, for each receiving an order in different regimes for different prices. The algorithm a set of ensembles of 3-layered NNs for every product authors assume the following factors which correlate with available on the market are constructed; each NN in the product market regimes: the finished goods inventory of other agents; ensemble predicts the probability that the winning bidding price the ratio of offer to demand; and normalized price over time. will be in the price interval assigned to the ensemble. The algorithms differ in the number of inputs they consider and their methods for input normalization. The Back-propagation games played, all of them showed high level of prediction algorithm and sigmoid function as the activation function are accuracy. Both Neural Networks and Genetic Programming used to train the NNs. learning techniques appeared to be appropriate for predicting The second strategy for deciding on offer prices is to predict the order price time series and competitors’ bidding prices. At the lowest order prices for each product based on the time series of same time, NN surpassed GP in terms of complexity of these prices. All TAC SCM competitors get daily market algorithm implementation and time of execution in the case of reports, where the lowest order prices proposed by all agents on predicting competitors’ prices (1 second for NN versus 90 the previous day for each product available on the market are seconds for GP). The disparity in the models’ performance leads specified. Using the previous values of these prices, their values to another conclusion that different models might work better in for one and ten days in the future are predicted. The Neural different market conditions, which, in their turn, depend on the Networks and Genetic Programming (GP) learning techniques strategies applied by competitors. According to this, the task for are used to design 33 different models of predictors. Apart form future work is to develop a meta-model, which can consolidate the difference in the learning technique they use, the models also the results obtained from individual models and find differ in their data transformation and normalization methods dynamically the best solution for the current market applied over inputs, and also the number of observables environment. considered in the time series. The experiments reveal that the prediction of the competitors’ Finally, the third strategy implemented in the Demand Agent is bidding prices themselves is not enough for making optimal to model the competitors’ behaviour and to predict their bidding decisions on offer prices: if the agent with the lowest predicted prices according to the models evolved. Having predicted prices price does not bid for an RFQ, then the winning price will be the of its competitors, the agent can bid just below them and thus lowest among the ones set by the other agents who actually bid. win customer orders. Again, the NN and GP learning techniques Thus, in addition to the prediction of the agents’ bidding prices are used and 4 different algorithms are developed to deal with for every RFQ, the classifiers, that will specify whether the the task. The algorithms differ in their approaches for selecting agent will actually bid for the RFQ at such price level, have to features to model competitors’ behaviour. be introduced. This will help to make decisions on which RFQs to bid for and what price to offer. Another task for future work To evaluate the proposed approaches and algorithms, a number is the problem of Feature Subset Selection. In particular, the of games were played in the TAC SCM simulated environment. experiments showed that the knowledge of the features that the Different combinations of participant agents were used. In some competitors are using for making their decisions, could improve games, the competitors were different versions of own agent. the predictive models of these competitors. The following claim For other games, highly competitive agents developed by other has been proved empirically: if a player knows which features its TAC SCM participants were run. Binary code of these agents is competitor is using for making its bidding decisions, then, even available from the TAC web-site repository. In order to decide without knowing the exact strategy of the competitor, it is on the most successful strategies to follow in each part of the possible to predict its bidding prices more accurately than in the supply chain, the game results were compared in terms of (a) case when these features are not known. Thus, there is a task of overall scores of competing agents, (b) rates of customer offer finding the method for predicting which parameters competitors prices proposed by them, and (c) order winning rates (the ratio are using. between the number of offers send to the number of orders received). To evaluate different algorithms for predicting With regard to the other agents implemented in the proposed customer winning bidding prices implemented in the Demand SCM system, there is plenty of room for improvement of the Agent, the root mean square errors of their predictions were performance of the Supply and Production Agents. Having the calculated to estimate the models’ accuracies. In addition, the limited production capacity, the Production Agents tries to complexity of algorithm implementation and time of their maximize its utility, i.e., the potential profit that might bring the execution were taken into consideration. The last parameter scheduled production. At the moment, the agent schedules (execution time) is important as in the TAC SCM game all the production for 12 days in the future using the following decisions have to be made within 15 seconds. heuristics. For every day in the future, the agent leaves some capacity for future demand (the further production date, the more cycles are reserved), then schedules current and late 5. RESULTS AND FUTURE WORK orders, depending on their due date, profit and availability of The experiment results demonstrated that the agents that track components, and after this, it allocates current RFQs, again the supplier market, plan their production in advance, and/or considering their due date, profit and availability of components. pick only profitable customer RFQs, perform better than those To schedule the production more accurately and to use the that do not support these strategies. The agents that use one of limited production capacity more efficiently, the agent needs to the proposed algorithms for predicting customer winning predict future customer demand, as well as reconsider its bidding prices outperform agents that do not make any planning for the future dynamically, depending on the level of predictions. The strategy of setting customer offer prices orders actually received from the customers. With respect to the according to the algorithms which predict probabilities of the Supply Agent, it places only short-term RFQs at the moment. winning bidding prices to be in a particular price interval On the one hand, this approach gives low holding costs. At the appeared to be less successful than using other predictive same time, the agent takes the risk not to get components on methods (predicting lowest order prices or competitors’ prices). time or to get them at higher rates. Thus, there is the need to find Although the algorithms for predicting lowest order prices and the way to balance short-term and long-term requests for competitors’ prices demonstrated different results across the components. 6. CONCLUSIONS 3. ACM Press, New York, NY, USA, 38-45. DOI= The main objective of the author’s PhD thesis is the http://doi.acm.org/10.1145/1120701.1120707 development and implementation of an intelligent multi-agent [6] Dong, R., Tai, T., Yeung W., and Parkes D.C. 2004. decision support system for supply chain management (SCM). HarTAC – the Harvard TAC SCM ’03 Agent. In The SCM environment is very complex, highly dynamic, and Proceedings of the Trading Agent Design and Analysis with many constraints. It is unresolved issue at the moment on Workshop (New York, NY, 20 July, 2004). TADA-03, 1-8. deciding which strategies to follow and which learning methods [7] He, M., Rogers, A., Luo, X., and Jennings, N.R. 2006. to use in order to perform more successfully in this domain. Designing a Successful Trading Agent for Supply Chain Within the scope of the presented work, the effort is made to Management. In Proceedings of the Fifth International contribute to finding better solutions by developing different Joint Conference on Autonomous Agents and Multi-Agent algorithms and testing them in the TAC SCM simulated Systems (Hakodate, Japan, 8-12 May, 2006). AAMAS-06, environment. In particular, a number of approaches for 1159-1166. predicting customer offer prices that could result in customer orders are explored. To the best of author’s knowledge, the [8] Ketter, W., Collins, J., Gini, M., Gupta A., and Schrater P. proposed strategy of modelling competitors’ selling behaviour is 2005. Identifying and Forecasting Economic Regimes in novel for the TAC community. With respect to the approaches TAC SCM. In Proceedings of the Nineteenth International of predicting winning price probabilities and the lowest order Joint Conference on Artificial Intelligence (Edinburgh, prices, which have been considered by other researchers, new Scotland, UK, 30 July – 5 August, 2005), 53-60. methods to solve the problems are investigated. The results of [9] Keller, W., Dugay, F.-O., and Precup, D. 2004. RedAgent the current research will be valuable for both academia and real – winner of the TAC SCM 2003. ACM SIGecom industries. More specifically, the work is dedicated to applying Exchanges, 4, 3. ACM Press, New York, NY, USA, 1-8. machine learning techniques for forecasting and optimisation DOI= http://doi.acm.org/10.1145/1120701.1120703 problems, which is an open issue within the research [10] Ketter, W., Kryznaya, E., Damer, S., McMillen, C., community. At the same time, the aim of the project is to build Agovic, A., Collins, J., and Gini, M. 2004. MinneTAC up an integrated solution to assist managing supply chains. sales strategies for supply chain TAC. In Proceedings of the Nowadays, enterprises are looking for implementing such Third International Conference on Autonomous Agents and systems to run their businesses. Moreover, various techniques Multi-Agent Systems (New York, NY, July 19-23, 2004). for predicting bidding prices in the context of dynamic AAMAS-04, 1372-1373. competitive environments are explored. Apart from the SCM, the solutions can be used in forecasting financial markets and [11] Kiekintveld, C., Miller, J., Jordan, P.R., and Wellman, participating in on-line auctions. M.P. 2006. Controlling a supply chain agent using value- based decomposition. In Proceedings of the Seventh ACM conference on Electronic commerce, Ann Arbor, Michigan, 7. REFERENCES USA, 208-217. DOI= [1] Benish M., Andrews, J., and Sadeh, N. 2006. Pricing for http://doi.acm.org/10.1145/1134707.1134730 Customers with Probabilistic Valuations as a Continuous Knapsack Problem. In Proceedings of the Eighth [12] Kontogounis, I., Chatzidimitriou, K.C., Symeonidis, A.L., International Conference on Electronic Commerce and Mitkas, P.A. 2006. A Robust Agent Design for (Fredericton, Canada, 2006). ICEC-06, 38-46. DOI= Dynamic SCM Environments. In Proceedings of the Fourth http://doi.acm.org/10.1145/1151454.1151475 Hellenic Joint Conference on Artificial Intelligence (Heraklion, Greece, May, 2006). SETN’06, 18-20. [2] Benish M., Andrews, J., Sardinha, A., and Sadeh, N. 2006. CMieux: Adaptive Strategies for Competitive Supply Chain [13] Pardoe, D. and Stone, P. 2007. Adapting in agent-based Trading. ACM SIGecom Exchanges, 6, 1 (June, 2006). markets: A study from TAC SCM. In Proceedings of the ACM Press, New York, NY, USA, 1-10. DOI= Sixth International Joint Conference on Autonomous http://doi.acm.org/10.1145/1150735.1150737 Agents and Multi-Agent Systems (Honolulu, HI, May, 2007). AAMAS-06, 677–679. [3] Benisch, M., Greenwald, A., Grypari, I., Lederman, R., Naroditskiy, V., and Tschantz, M. 2004. Botticelli: A [14] Pardoe, D. and Stone, P. 2006. Predictive Planning for supply chain management agent. In Proceedings of the Supply Chain Management. In Proceedings of the Third International Conference on Autonomous Agents and Sixteenth International Conference on Automated Planning Multi-Agent Systems (New York, NY, July 19-23, 2004). and Scheduling (Cumbria, UK, June, 2006). ICAPS-06, AAMAS-04, 1174-1181. 21-30. [4] Collins, J., Arunachalam, R., Sadeh, N., Eriksson, J., Finne, [15] Pardoe, D. and Stone, P. 2004. Bidding for Customer N., and Janson, S. 2006. The Supply Chain Management Orders in TAC SCM: A Learning Approach. In Game for the 2007 Trading Agent Competition. Technical Proceedings of the Third International Joint Conference on Report CMU-ISRI-07-100. Carnegie Mellon University. Autonomous Agents and Multi-Agent Systems (New York, NY, July 19-23, 2004). AAMAS-04, 52-58. [5] Dahlgren, E. and Wurman, P. 2004. PackaTAC: A conservative trading agent. ACM SIGecom Exchanges, 4,