MULTI-AGENT AND MARKET BASED DYNAMIC OPTIMIZATION AND ITS EXTENSIONS TO DISTRIBUTED SUPPLY CHAIN PROCUREMENT PLANNING PROBLEMS
Open Access
- Author:
- Tang, Kaizhi
- Graduate Program:
- Industrial Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- December 15, 2004
- Committee Members:
- Soundar Rajan Tirupatikumara, Committee Chair/Co-Chair
Kalyan Chatterjee, Committee Member
Natarajan Gautam, Committee Member
Ernest Emory Enscore Jr., Committee Member - Keywords:
- double auction
market mechanism
supply chain procurement
transportation planning
multi-agent system
contingency planning
reinforcement learning
meta-heuristic
variable neighborhood search
dynamic optimization
distributed heuristic
multi-stage game
evolutionary method
fictitious playing
evolutionary stable strategy - Abstract:
- This thesis discusses distributed computational methodologies used for solving supply chain procurement planning problems with information systems naturally distributed at different locations. The planning problem is heavily influenced by transportation costs, whose calculation is based on a stochastic environment with random service and travel times. The main contributions of this thesis are the computational methodologies that solve the problem under different conditions. All these methodologies are developed in the context of supply chain procurement planning, but they are not necessarily restricted to this context. They can be modified and adapted to other distributed planning and scheduling problems. The Double Auction Market Mechanism (DAMM) is an innovative distributed negotiation mechanism for supply chain procurement planning. It is developed to achieve a common objective among multiple individual decision makers by modeling their respective interests in a virtual market for trading transportation tasks. The trading mechanism emulates the double auction institutions of a real market. For trading, double auction institutions enable exchange of transportation tasks among a transportation company and its trucks, which are modeled as software agents. An agent's decision making among market interactions is based on a set of stochastic rules, which consider its self-interest with the support of transportation cost evaluation. Iterated task exchange among agents drives the task allocation to Pareto optimality, which is derived from the concept of market equilibrium. DAMM is an any-time negotiation protocol, so it is useful for dynamic ptimization and contingency planning. A Coordinated Reinforcement Learning (CRL) method is developed to refine the distributed transportation plans generated by distributed heuristics based on DAMM. Through analyzing the drawbacks of the distributed double auction heuristic due to its strict market rules, we enable the task agents in the virtual market to return to their previous stages and reconsider their decisions for market trading interactions. This is realized in the framework of reinforcement learning (RL). To be adaptive in the framework of RL, the task allocation derived from the transportation plans is defined as a state; the collective proposals of the task agents are defined as an action; the cost saving during one round of market interaction is defined as a reward; the update of transportation plans resulting from updating task allocation is defined as a state transition. CRL with tabular representations effectively refines the distributed transportation plans generated by DAMM. A meta-heuristic enabled multi-agent optimization architecture is developed for dynamic supply chain procurement planning. This development is based on analyzing drawbacks of DAMM and the curse of dimensionality of CRL. To escape from local optimality towards a higher quality solution, we introduce meta-heuristics over agent interactions to advise agents' searching processes. We mainly propose the variable neighborhood search meta-heuristic (VNS-MH) over the distributed market based heuristic (DMBH), which is based on DAMM. VNS-MH not only performs better on achieving optimality than DMBH, but also requires less memory and computational time than its predecessor -- coordinated reinforcement learning (CRL). A multi-player game with multiple stages is designed to model task delegations among multiple self-interested transportation companies. The delegations are useful for dealing with infeasible or extremely expensive tasks because of transportation companies' limitations on vehicle capacities or restrictions on time windows. Task delegations have to address the self-interests of transportation companies. This turns into a game with multiple stages, each of which incurs a round of double auction interactions. In this game, multiple players, representing a set of transportation companies, aim to maximize their own payoffs summed over multiple stages. By playing the game repeatedly, we develop an evolutionary method, combining reinforcement learning and fictitious playing, to seek a solution. This method is based on the equilibrium concept of evolutionary stable strategy to successfully achieve a solution to the complex game.