Data science has become an essential tool for solving complex problems in various industries, including logistics. One particular approach that has shown promise in this field is the genetic algorithm. This method is inspired by the principles of natural selection and evolution, and it can be applied to optimize the allocation of resources. In this article, we will explore what is genetic algorithms and how we apply to find an optimum cost for a transportation company.
What is a Genetic algorithm?
A Genetic Algorithm (GA), which is a subclass of the larger class of evolutionary algorithms (EA) in computer science and operations research, is a metaheuristic that takes its cues from the process of natural selection. Genetic algorithms frequently employ biologically inspired operators including mutation, crossover, and selection to produce high-quality solutions to optimization and search issues. Solving optimization and performance-enhancing decision trees are a few examples of GA applications.
What is the concept of genetic algorithm?
The principles of natural evolution form the foundation of genetic algorithms, which are search and optimization tools. By replicating the evolution of species through natural selection, genetic algorithms also carry out the optimization procedures.
Typically, a genetic algorithm consists of two steps. The first step in the process is choosing an individual to produce the next generation, and the second is manipulating the chosen individual using techniques like crossover and mutation to produce the following generation.
Which individuals are chosen for reproduction and how many offspring each selected person produces are determined by the selection mechanism. The fundamental principle of selection strategy is that a person's likelihood of having children increases with their quality.
Problem Statement (Transportation case)
Assume a transportation company who need to send parcels from a depot to their distribution centres with trucks. Parcels may have different size, Trucks can have different capacity and cost.
So, for the Manager in charge need to figure out two things: First, what trucks and how many trucks are used? Second, what are the distribution centres the trucks will visit? Objective being to have a minimum cost.
If we use a simple permutation logic for each Parcel (1: Parcel is in the truck OR 0:parcel is not in the truck) and try all combinations, as the number of items increase, the number of combinations increase exponentially and the time to compute the solution as well. With only 100 items, it might already block a computer for hours, so imagine if you need to perform calculation for 100,000 items!
Genetic algorithms are well-suited for solving logistic problems because they can effectively find optimal solutions in a large, complex search space. Logistics operations often involve many variables and constraints, such as transportation costs, inventory levels, delivery schedules, and so on. The genetic algorithm can handle these complexities by generating a population of potential solutions and then gradually refining them through a process of selection, mutation, and crossover. This allows it to explore a large number of possible solutions, identify the best ones, and converge to an optimal solution in a relatively short amount of time.
Genetic Algorithm applied to transportation problem
For the sake of simplicity, we will simplify our problem as follow: Given a truck with a capacity of 50 m3, what packages with different size can fit in and optimize the usable space.
Study Case: Constraints
The steps of the genetic algorithm that we use are Initialization, Parent Evaluation, Roulette Wheel Selection, Crossover, Mutation, and Repair.
Genetic Algorithm Steps
Step 1: Initialization
During this first step, we generate a number of random solutions of parcel combinations.
Initialization
Step 2: Parent Evaluation
We calculate a Fitness Score to determine the strength of the solution. We can calculate the fitness score by summing up all the parcels that will be loaded into the truck. The solution is for anyone with a fitness score higher than 50 to be given a penalty and their fitness score to be reset to 0.
Parent Evaluation
Step 3: Roulette Wheel Selection
We pass the fitness scores onto a roulette wheel. This roulette wheel determines which solution is going to be a parent. The higher the Fitness score, the larger the area in the roulette wheel, meaning these solutions has a better chance of passing on information to future generations. Note that solution with lower fitness can still be chosen.
Roulette Wheel Selection
Step 4: Crossover
Mutation and crossover are the two most popular operators. By replicating a few selected bits from each parent string, the crossover operator creates two new children from two parent strings. In short, crossover is the step where two solutions exchange information with each other.
Crossover
Step 5: Mutation
The mutation operator modifies the value of a single bit randomly which create a minor change in the bit string.
Mutation
Step 6: Repair
Repair operator checks if the solutions produced by the algorithm are valid, and if not, it modifies them to make them valid. In our case where the capacity of a truck is limited, the repair operation would check if the parcels allocated to the truck exceed its capacity. If so, it would modify the solution by removing or rearranging the parcels until they fit within the capacity constraints.
Repair
Genetic Algorithm in Action!
We took following assumption to demonstrate the capability of Genetic Algorithm:
5 types of Trucks (A: 16 trucks, B: 10 trucks, C: 6 trucks, D: 6 trucks, and E: 4 trucks).
2250 m3 of parcels volume to be delivered.
10 destinations.
100 individual per generation.
3 random data initiations (A, B and C)
We loaded our assumption in the Machine Learning and run the Genetic Algorithm. The animation below is a capture of the Genetic Algorithm in action. You can see that for all random initiations, the cost decreases. This gradual cost optimization is due to the new combinations formed during the crossover and mutation processes, as well as the fact that we only keep the best solutions generation after generation. You can also see that in our case, whatever the random initiation, the solution converges to the same minimum cost.
Chart Animation of Genetic Algorithm
A Powerful Approach for Improved Efficiency
You have now a good understanding of what is Genetic Algorithm and how it can be applied to determine an optimum cost. You already understand that Genetic algorithm can be used to solve a large scope of optimization problem in a wide range of industries.
Contact us Today to schedule a consultation and learn how we can help you optimize your operations and reach new levels of efficiency and productivity.
BI Solusi is your trusted partner for data-driven success in Indonesia, serving companies in the Southeast Asia region and beyond. We specialize in implementing cutting-edge Data Analytics, Business Intelligence platform, and Big Data solution, complemented by expert Data Science services.
We offer flexible nearshore and offshore BI implementation models to meet your specific needs and deliver the highest-quality results.
Our BI Consulting expertise encompasses Data Integration services (ETL), Data Warehousing, and the utilization of Data Visualization tools such as Microsoft Power BI, Qlik Sense, and Tableau for Reports and Dashboards implementation.
Let us help you unlock the full potential of your data and achieve your business goals.