Contributions to a supply chain’s overall cost function (such as the bullwhip effect) are sensitive to the different players’ ordering policies. This chapter addresses the problem of developing ordering policies which minimise the overall supply chain cost. Evolutionary Algorithms have been used to evolve such ordering policies. The authors of this chapter extend existing research in a number of ways. They apply two more recent evolutionary algorithms to the problem: Grammatical Evolution (GE), using a standard Genetic Algorithm (GA) search engine; and Quantum Inspired Genetic Algorithm (QIGA), used both as a standalone algorithm, and as an alternative search engine for GE. The authors benchmark these against previous work on the linear Beer Game supply chain, and extend our approaches to arborescent supply chains (without gaming), and capacitated inventory. The ordering-policy-generating grammars investigated range from simple — only using the demand presented at that point — to complex — which may incorporate lagged demands, forecasting approaches such as Moving Average or Simple Exponential Smoothing, conditional statements and other operators. The different grammars and search engines are compared for deterministic demand, and various stochastic demand distributions. Overall, GE outperforms other approaches by discovering more efficient ordering policies. However, its performance is sensitive to the choice of grammar: simple grammars do best on deterministic demand, while grammars using conditionals, information sharing and forecasting do better on stochastic demand. GE with a QIGA search engine has similar performance overall to GE with a standard GA search engine: typically QIGA is better if demand follows a Poisson distribution, with GA better for Normal demand.
TopIntroduction
Supply chains may be linear, with only one player at each tier, or arborescent (tree-like), with multiple players at each tier. The well-known Beer Game (see below) is a linear 4-tier supply chain. Supply chains exhibit the bullwhip effect, where demand variance at the customer end is amplified along the chain upstream. This effect, and the total supply chain cost, are sensitive to the players’ ordering policies.
An example of an ordering policy is the “one for one” policy: the order received from the immediate downstream customer is passed on to the immediate upstream supplier.
The problem this research addresses is to develop ordering policies which minimise the overall cost in the supply chain, and implicitly mitigate the bullwhip effect. For supply chains of very simple stucture, e.g., two tiers, there exist analytical solutions to the optimal order quantity problem, such as the Box-Jenkins ARMA/ARIMA approach Box & Jenkins (1970). However, for more complex supply chains, with multiple tiers, branching, capacitation, or other enrichments, such approaches may fail or simply not exist. Furthermore, such approaches are mathematically involved, and not always understood or adopted by practitioners. There is a need for an approach which is flexible enough to be applicable to a wide range of real situations, while being tunable with a few parameters (and so lending itself to use by practitioners), yet still being accurate enough to perform at least as well as current approaches.
The rise in popularity of Evolutionary Algorithms (EAs) has led researchers to investigate models of the Beer Game incorporating evolution — such as the Genetic Algorithm (GA) and Genetic Programming (GP) — and simulation. These models evolve ordering policies that minimise total supply chain cost. For the supply chain problems so far investigated, EAs appear to be at least competitive with previous approaches.
Our research extends this existing work in several ways. We apply two recent EAs:
- •
Quantum Inspired Genetic Algorithm (QIGA) (the first supply chain use we know of); and
- •
Grammatical Evolution (GE), using as search engine either a standard GA (denoted GE-GA) or QIGA (denoted GE-QIGA). GE (O’Neill & Ryan, 2001, 2003; Brabazon & O’Neill, 2006) is an EA, more specifically, a form of GP using linear genomes. It can evolve complete programs (in our case, ordering policies) in an arbitrary language using a variable-length binary string (genome). The binary string determines which production rules in a Backus-Naur Form (BNF) grammar definition are used in a genotype-to-phenotype mapping process to generate a program.
GE is an intelligent metaheuristic, newly introduced to the supply chain domain. A major motivation for its use here is the capability of encoding the particular supply chain structure in the grammar, so meeting the flexibility requirement above; it is also tunable; and it holds out the hope of being competitive with existing approaches in terms of accuracy, as well as being attractive to practitioners. By hybridising GE with GA and QIGA, we hope to extend recent promising results of hybrid algorithms.
We benchmark QIGA, GE-GA and GE-QIGA against previous work on the Beer Game, and extend our approaches to arborescent supply chains. We investigate stochastic demand distributions, and the effects of capacitated inventory (with resulting additional cost of stockouts).
Our model is sufficiently general for any supply chain configuration that does not involve gaming effects among the players (e.g., in the automotive industry). We apply it not only to the standard Beer Game supply chain (Figure 1) but also to an arborescent supply chain with four players (Figure 2). In each, the manufacturer is merely a source of inventory, and places no orders.
Figure 1. Beer Game supply chain configuration
Figure 2. Example Arborescent supply chain configuration