With the advance of technology, when getting one location to another, we can know which direction or path is most efficient by simply typing the names of locations. Well, what would you do in the case that you need to go from not just one place to another but from one place to many, let’s say 10 or 100 places. How would you cope with this situation? Of course, in daily life, factories are trying to solve this routing problem rather than human beings and this article has been written to give information about how to handle route optimization with the nature-inspired artificial intelligence algorithm.
To begin with, let’s define the problem first. The objective is to minimize costs by optimizing the vehicles’ paths meeting customer demand with the work shift, service time, and time window constraints.
This problem can be evaluated as a multiple Traveling Salesman Problem. The complexity of this kind of problem is calculated as such. Let`s say we have n many customers and k many vehicles. Roughly speaking, with brute force, we have 2 to the k many solutions and among those solutions, there is only one optimal solution. So, there are many solving techniques suitable for the problem but here genetic algorithm (GA) has been implemented. So, what is the genetic algorithm then? How does it work? Let’s go deeper into the algorithm.
Genetic algorithm is an algorithm that is based on a biological concept of survival of the fittest. Survival of the fittest is an on-going process and there is a selection part of it. To be able to select something or someone, you need to differentiate it. So, there must be a criterion or a metric for it, which corresponds to fitness function here. This function calculates the total kilometers of a candidate path by using distance time matrix.
At this point, it is good to mention the construction of distance matrix. It keeps the distances from i to j and we use an open-source geographical map called Open Street Map to get it.
So, using the distance matrix, fitness scores of all paths are calculated and the ones with higher fitness values are more likely to be selected in order to generate new offspring. This is the core idea behind the genetic algorithm. To go deep into it, we need to know the components of the algorithm.
Modules of GA needed to know are gene, chromosome, individual, population, mating pool, fitness, mutation, and elitism. Let’s define it one by one and after that, we elaborate on the logic of the algorithm.
· Gene is a city carrying x and y coordinates.
· Chromosome contains genes and the order of gene is defining which city is to visit in which order.
· Individual is made up of chromosome and therefore it is candidate route.
· Population consists of individuals, i.e. possible route samples.
· Parents are two individuals.
· Mating pool is a collection of selected individuals to create new offspring.
· Fitness is a metric describing how short a single route is.
· Mutation is to shift the genes order in an individual.
· Elitism is how many to select from a population.
Initially, a population is generated based on a given city list. So, every individual in the population has a fitness score. Based on a fitness score, the individuals are selected for the mating pool so that they can create better children(individuals) by changing the information by one another. In addition to that, there is a mutation process that shuffles genes in an individual based on a certain probability. Then elitism process comes into view; that is, top X individuals are to be carried to the next iteration. And the process continues until no improvement, as in the figure below.
So, the last thing that is good to be done is sensitivity analysis to find the optimal values of variables. To do that, as in the figure below, you create a grid search of the parameters and after that you look for, using some techniques, which values give the most desired outcome.
So, by implementing GA, we made a ≈ 45% improvement in total distance traveled and ≈ 25% decrease in hours worked and ≈ 30% improvement in the efficiency of use of vehicles, and total contribution to the factory budget is nearly half a million on a year basis.
Other than that, genetic algorithm can be used other areas as well and some of them are: Economics, Neural Networks, Image Processing, Vehicle Routing Problems, Scheduling Applications, Machine Learning, Robot Trajectory Generation, Parametric Design of Aircraft, DNA Analysis, Multimodal Optimization, Traveling salesman problem and its applications.
To sum up, in this paper we can see a real-life example of routing problem, tsp concept, how to deal with this problem with genetic algorithm, and application areas of genetic algorithm. Hope you enjoy reading this article.
Also special thanks to Berat Utkan Menteş giving so much effort for the contribution of the projects and to my team keeping me motivated all the time
Murat Ayvaz — Data Scientist
References
[1]https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_application_areas.htm
[2]Solving the Vehicle Routing Problem with Genetic Algorithm and Simulated Annealing by Ákos Kovács
[3]https://en.wikipedia.org/wiki/Travelling_salesman_problem
