Genetic Algorithms (GA) are a special set of evolutionary algorithms, these algorithms try to simulate the evolution of biology evolution but in the domain of numbers. The genetic algorithm is one of the tools that can be used to apply evolutionary computing methods to find good, sometimes even optimal, solutions to problems that have billions of potential solutions. Implementing this kind of progressive based algorithm in Supply Chain Management could help to solve the complexity of SCM that has been increased over time. In this article, we will put focus on how Genetic Algorithm techniques can be applied for optimization in SCM. Following are the topics that would be covered in this article.
Table of contents
- About Genetic Algorithm (GA)
- About Supply Chain Management (SCM)
- Applications of GA to SCM
About Genetic Algorithm (GA)
A Genetic Algorithm (GA) is a research-based algorithm based on the theory of natural evolution. This algorithm works on the process of natural selection where those individuals are selected for the processing of who is the perfect fit with the help of fitness calculation to expand it to the next generation. Genetic algorithms use important biological features for optimization:
- The environment is defined by the problem to be treated
- Chromosomes represent candidate solutions to the problem.
- The genotypes encode the candidate solutions for the problem. The genotype-phenotype translation determines how the chromosomes should be interpreted to obtain the actual candidate solutions.
- The fitness of individuals depends on different factors of the problem so that more adaptable individuals are more likely to survive.
- A population of individuals develops, into which new individuals enter and others disappear.
- New individuals emerge as a result of the recombination and/or mutation of previous individuals, whereby their fitness increases steadily.
This explanation is shown in a flow chart representation below for a better understanding of the computational steps of GA.
About Supply Chain Management (SCM)
Supply chain management (SCM) involves managing upstream and downstream relationships with suppliers and clients to provide high-quality, low-priced customer value as a whole. There are a total of five major steps in SCM planning, sourcing, manufacturing, logistics and defective product returning. Following is the flow chart for the SCM.
The main purpose of SCM is to:
- Make inventory always ready according to the customer’s demands
- Achieve cost-efficient fulfilment and inexpensive products
- Enhance the response towards the changes like economic crisis, government guideline change, etc for better organisational responsiveness.
- Build a network that gets optimised according to time.
- Make a profitable business.
Applications of GA to SCM
Over time a lot of diversity has been created in the supply-demand which made the supply chain management complex to calculate the solutions for the business. To solve this complexity of the supply chain genetic algorithm is implemented, to have an optimised solution out of the list of solutions with the help of biological methodology. Let’s have a glance over these applications and try to understand the implementation of genetic algorithms in SCM.
Inventory analysis using genetic algorithms (GA)
Maintaining the inventory according to the supply-demand ratio is a complex problem to solve because of a lot of diversity in the data. The objective is to predict an optimum stock level by using the records. Let’s understand the flow of operation to solve this problem
Initially, the data related to the number of stock levels are been labelled as:
- The zero (0) refers to the contributor needing no inventory control.
- The non-zero (1,2,3,.. according to the requirement) data requires inventory control. It consists of both the excess amount and the shortage amount.
- The excess amount is labelled as a positive value and the shortage amount is labelled as a negative value.
Following that, the labelled data is fed to a clustering algorithm that separates the stock levels that are either in excess or shortage from the stock levels that are neither in excess nor shortage. This is done simply by clustering the zero and non-zero values. The efficient K means the clustering algorithm is the perfect algorithm for clustering this kind of data. After the process of clustering, the work starts its proceedings on the Genetic algorithm, the core of the final solution.
Let’s start with defining the chromosome, they are randomly generated initially by having the stock levels within the lower and the upper limit for all the distributors and contributors of the supply chain and the factory. The gene is the stock level of each member of the chromosome. If the length of the supply chain is n then the length of the chromosome is n. In this application, the length of the chromosome is 3 (n=3) since using only three members of the chain. Initially, there would be a total of two-parent chromosomes and from the next generation, a single random chromosome will be produced.
Moving towards the next step, to check the fitness of each individual in the population. The fitness functions ensure that the evolution is toward optimization by calculating the fitness value to evaluate the performance of each individual in the population. It sorts for the best chromosome.
These chromosomes may be represented several times in the next generations, hence leading to a population that is composed of several copies of the same solution which also doesn’t guarantee that the initial population contains the globally optimal solution. Genes on each chromosome that are right of the crossover point are flipped over, which results in a cross-over operation. Following the crossover operation, two new chromosomes are formed.
This image shows the status of the chromosomes before they do crossover in the operation. As the negative 800 value should be with a negative chromosome so implementing a single crossover could be achieved.
Hence the problem has been solved by implementing the cross over. The newly obtained chromosomes from the crossover operation are then processed for mutation. The mutation is the process of generating a new chromosome that doesn’t resemble the candidate chromosome.
This is done by a random generation of two points and then performing swaps between both the genes. This process will keep iterating and simultaneously two chromosomes would be selected by the fitness function are going to be the main solution. Each iteration would give the best chromosome. There should be an optimal number of iterations. Thus, the final chromosome selected would be the solution for inventory control.
The Vehicle Routing Problem (VRP)
The Vehicle Routing Problem (VRP) is a combinatorial optimization problem in which several customers, requiring either pick-ups or deliveries, must be serviced by a set of vehicles. The objective is to schedule the transporters in such a manner that each customer is visited by exactly one vehicle and the total distance travelled is minimised.
Transporting the manufactured goods to the distributors and scheduling those is a tough job to do with a lot of diversity in the market. To solve this problem genetic algorithms are applied. A famous brand of acrylic paints “Asian paints” uses this algorithm to route their vehicles for a seamless and profitable business.
To solve this problem initially the data should be encoded, for the encoding algorithm uses the “random key” encoding technique in which it generates a random number between 0 and 1 for each customer in the chromosome. The order in which the customers are visited is represented by sorting the random numbers in ascending order. Random keys are used because it prevents mutation (reproduction) infeasibility.
These chromosomes are then pushed to penalise the infeasibility in other words it is the calculation of fitness for the chromosomes. Like this, a multi-stop problem there is a need for a cycle cross over method. In this, a gene from one parent will be copied into a child, but it should inherit the position of the other parent. Once the cross over chromosomes that are perfect for the mutation are selected by the test, they are used to generate a new chromosome for the problem.
Hence, using the genetic algorithm now the vehicles are scheduled as the transporters in such a manner that each customer is visited by exactly one vehicle and the total distance travelled is decreased.
Production cost minimization
There is an issue with the SCM which is a shorter product life cycle due to which there is high uncertainty of demand. This is one of the reasons for the increase in the production cost of a product because manufacturers need to spend more due to this uncertainty. Uncertainty is measured by the frequency of its occurrence, and by analysing the relative contribution and effect of the uncertainty on performance. The impact of uncertainty can be quantified as minor or major.
To solve the problem the data is encoded and initial chromosomes are initialised with the help of uniform distribution. Producing successive generations it is important to give more chances to the “fittest” individuals selected with help of calculating the individual’s fitness score. The fitness score is the probability that is assigned based on the rank from a truncated geometric distribution.
The initial chromosomes are formed now there may be a chance of duplication in the future generation so to avoid that need to use a single-point crossover in which the new offspring will inherit genes from the first parent till the cut point and inherit non-repeating genes from the beginning of the second parent as shown below.
The new crossover chromosomes will then be used for the mutation to produce new chromosomes with the help of iteration to achieve an optimal chromosome or the final solution(s).
Nutshell
A Genetic Algorithm is a powerful tool with the concept of evolution as the backbone of the algorithm which helps to formulate and optimise the solutions. It is widely used in different fields and this covers the major applications of genetic algorithms in supply chain management.
