How can genetic algorithms be applied to supply chain optimization?

Genetic Algorithms (GA) are a special set of evolutionary algorithms, these algorithms try to simulate the evolution of the evolution of biology but in the realm of numbers. The genetic algorithm is one of the tools that can be used to apply evolutionary computational methods to find good, sometimes even optimal, solutions to problems that have billions of potential solutions. Implementing this type of progressive algorithm in supply chain management could help solve the complexity of SCM that has increased over time. In this article, we will focus on how genetic algorithm techniques can be applied for optimization in SCM. Here are the topics that would be covered in this article.

Contents

  1. About Genetic Algorithm (GA)
  2. About Supply Chain Management (SCM)
  3. Applications from GA to SCM

About Genetic Algorithm (GA)

A genetic algorithm (GA) is a search algorithm based on the theory of natural evolution. This algorithm works on the natural selection process where these individuals are selected for the processing of who is the ideal person using fitness calculation to extend it to the next generation. Genetic algorithms use important biological characteristics 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. Genotype-phenotype translation determines how the chromosomes should be interpreted to obtain the actual candidate solutions.
  • the aptitude of individuals depends on different factors of the problem so that more adaptable individuals are more likely to survive.
  • A population of individuals develops, in which new individuals enter and others disappear.
  • New individuals appear as a result of the recombination and or mutation previous individuals, so that their physical condition increases steadily.

This explanation is illustrated in a flowchart representation below for a better understanding of the GA calculation steps.

About Supply Chain Management (SCM)

Supply chain management (SCM) involves the management of upstream and downstream relationships with suppliers and customers to deliver high quality, low cost customer value overall. There are a total of five main steps in SCM planning, sourcing, manufacturing, logistics, and defective product return. Here is the organization chart of the SCM.

The main objective of the SCM is to:

  • Make an inventory always ready according to customer requests
  • Get profitable execution and low-cost products
  • Improve response to changes such as economic crisis, changing government directives, etc. for better organizational responsiveness.
  • Build a time-optimized network.
  • Make a profitable business.

Applications from GA to SCM

Over time, a great diversity has been created in supply and demand, which has made supply chain management complex to calculate solutions for the company. To solve this supply chain complexity, a genetic algorithm is implemented, to have an optimized solution on the list of solutions using biological methodology. Let’s take a look at these applications and try to understand the implementation of Genetic Algorithms in SCM.

Inventory analysis using genetic algorithms (GA)

Maintaining inventory based on the supply-demand ratio is a complex problem to solve due to the wide variety of data. The goal is to predict an optimal stock level using the records. Let’s understand the operation flow to solve this problem

Initially, the data relating to the number of stock levels is denominated as follows:

  • the zero (0) refers to the contributor not needing inventory control.
  • the not bad (1,2,3,.. as per requirement) data requires inventory control. It consists of both the excess amount and the shortfall amount.
  • The excess amount is labeled as a positive value and the missing amount is labeled as a negative value.

Then, the labeled data is passed to a clustering algorithm that separates stock levels that are over or under from stock levels that are neither over nor under. This is done simply by grouping the null and non-null values ​​together. The efficient K means that the clustering algorithm is the perfect algorithm for clustering this type of data. After the grouping process, the work begins its work on the genetic algorithm, the heart of the final solution.

Let’s start by defining the chromosome, they are randomly generated initially by having the stock levels in the lower bound and the upper bound for all distributors and contributors in the supply chain and factory. The gene is the stock level of each member of the chromosome. If the supply chain length is n, then the chromosome length is n. In this application, the length of the chromosome is 3 (n=3) since it only uses three members of the chain. Initially, there would be a total of biparental chromosomes and from the next generation only one random chromosome will be produced.

Let’s go to the next step, to check the fitness of each individual in the population. Fitness functions ensure that the evolution is towards optimization by computing the fitness value to evaluate the performance of each individual in the population. It sorts for the best chromosome.

These chromosomes can be represented several times in the following generations, thus leading to a population composed of several copies of the same solution, which also does not guarantee that the initial population contains the globally optimal solution. The genes of each chromosome to the right of the crossover point are reversed, resulting in a crossover operation. Following the crossover operation, two new chromosomes are formed.

This image shows the state of the chromosomes before they crossed during the operation. Since the negative value of 800 should be with a negative chromosome, the implementation of a single crossover could be achieved.

Therefore, the problem was solved by implementing crossover. The newly obtained chromosomes from the crossover operation are then processed for mutation. Mutation is the process of generating a new chromosome that does not resemble the candidate chromosome.

This is done by randomly generating a colon and then performing swaps between the two genes. This process will keep iterating and simultaneously two chromosomes would be selected by the fitness function is going to be the main solution. Each iteration would yield the best chromosome. There must be an optimal number of iterations. Thus, the final selected chromosome 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 served by a set of vehicles. The goal is to schedule carriers so that each customer is visited by exactly one vehicle and the total distance traveled is minimized.

Transporting manufactured products to distributors and planning for them is a difficult task to do with a great 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 transparent and profitable business.

To solve this problem at first, the data must be encrypted, because the encryption algorithm uses the “random key” encryption technique in which it generates a random number between 0 and 1 for each customer in the chromosome . The order in which clients are visited is represented by sorting the random numbers in ascending order. Random keys are used because they prevent the infeasibility of mutation (reproduction).

These chromosomes are then pushed to penalize the infeasibility in other words it is the calculation of aptitude for the chromosomes. Like this, a multi-stop problem requires a cycle crossing method. In this, a gene from one parent will be copied into a child, but it should inherit the position from the other parent. Once the crossover chromosomes that are perfect for the mutation are selected by the test, they are used to generate a new chromosome for the problem.

Therefore, using the genetic algorithm, vehicles are now programmed as carriers in such a way that each customer is visited by exactly one vehicle and the total distance traveled is reduced.

Minimization of production costs

There is a problem with SCM which is a shorter product life cycle due to which there is high demand uncertainty. This is one of the reasons for the increase in the cost of producing a product as manufacturers have to spend more due to this uncertainty. Uncertainty is measured by the frequency of its occurrence and by analyzing the relative contribution and effect of uncertainty on performance. The impact of uncertainty can be quantified as minor or major.

To solve the problem, the data is encoded and the initial chromosomes are initialized using a uniform distribution. Producing successive generations, it is important to give more chances to the “fittest” individuals selected using the calculation of the individual’s suitability score. The fitness score is the assigned probability based on the rank of a truncated geometric distribution.

The initial chromosomes are formed now, there may be a risk of duplication in the future generation to avoid the need to use a single point cross in which the new offspring will inherit the genes from the first parent up to the point cleavage and will inherit non-repeating genes from the beginning of the second parent as shown below.

The new crossed chromosomes will then be used for mutation to produce new chromosomes using iteration to get 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 that helps formulate and optimize solutions. It is widely used in different fields and covers major applications of genetic algorithms in supply chain management.

The references

Sharon D. Cole