Vehicle Routing using Metaheuristic optimization

---

At Ryets Research we provide solutions for our developers to give them a head-start.

One of the interesting problems is determining the most optimum routes for a number of vehicles that needs to go to a list of locations, for example: When a pizza restaurant have a list of locations for delivery, what will be the optimum number of vehicles, and what should be the route for each, in order to achieve maximum utilization.

This business problem describes a well known problem called Vehicle Routing Problem and it becomes complex when taking the following factors into considerations:

Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is one of the most challenging task. Defined more than 40 years ago, this problem consists in designing the optimal set of routes for fleet of vehicles in order to serve a given set of customers. The interest in VRP is motivated by its practical relevance as well as by its considerable difficulty.

Naïve Approach

A Naïve solution for this problem is deciding a random number of vehicles, let’s say 4, then move each of the 4 vehicles to the closest 4 cities, while this solution is guaranteed to find the best route for the given vehicles, it can take longer time, e.g. for 13 cities it will take 6.227 Billions computational calculation to get the best route for the 4 cars. This will take several minutes of computation on iPhone X which is far from the world-class usage.

Thus, the naïve approach is way off-the standards and can’t be used to deliver the daily user needs, also it’s not only about the number of calculations to get the best route, it’s also about the fitness function used to determine which location is better as the next destination for a given city.

In the process of making a route for a truck, we start by initial point or the depot point, then start calculating the best next city, but a one might ask: What is the definition of the best next city? is it the closest city in term of distance? Or is it the best city in term of traffic conjunction? Is there any time constrains? -All of these aspects should be taken into consideration while selecting the best next city, and for this purpose a fitness function is defined. A fitness function is a mathematical function that describes how are the aspects like distance, traffic conjunction should affect our choice for the city, a simple fitness function could be something like this, with (d) is the distance from city (i) to (j).

The problem is that a fitness function is not always as simple, usually calculating the fitness function takes a lot of time and computation, a complex fitness function might involve the calculation of route conjecture which isn’t as simple as calculating the inverse of distance, and in general it’s always better to reduce the number of times we calculate the fitness function as much as possible, and this won’t be achieved if we’ve used the naïve approach.

Metaheurstic optimization

We’ve found that Metaheuristic optimization is the right fit for this kind of problems (combinatorial optimization problem) where nature-Inspired optimization algorithms are used to solve complex problems that has large search space like ours.

Multiple algorithms could be used to solve the problem of VRP like Ant Colony, MIN-MAX, genetics and particle swarm, we chose to use genetic algorithms to solve our problem and will discuss the abstraction and the idea behind genetics algorithms and how we were able to use it to solve the problems.

Genetic Algorithms

After the industrial revolution the skies and environment became darker because of factories exhaust which lead to the survival of the dark butterflies and the death of the light ones.

Genetic algorithms are the earliest, most well-known, and most widely-used metaheuristic techniques, which are the simulations of the natural selection process where the most fit individuals are more likely to survive with their features to the next generation

If you’re familiar with evolution and natural selection you know that most biological organisms reproduce, create an offspring (or children) who reproduce, and so on. Children share the properties of their parents and during the creation of the child there’s a very slight possibility that some of those properties will randomly mutate. Parents die, and the children will start the process again and create a new generation, and so on and so on…

This very slight possibility of mutation is the engine behind biological evolution. You would think that adding random features to an entity is crazy and dangerous, and in most cases it is, for the entity. But every now and then a very useful feature comes along, and that feature is extremely useful for the whole population. Because an entity with useful features has higher chances of reproduction and passing those features to the next generation.

If you think of it, in human timeframe, you might find it difficult to believe. But if you speed the time up, it makes a lot more sense. These tiny mutations is what gave us our eyes, our advanced brains, our intelligence.

Given what we have discussed, we can clearly separate the genetic algorithm into main stages:

Each one of these stages won’t do much. But the five of them working together create a really powerful mechanism that created every living thing on this planet from a single cell.

Let’s see how we can use what we know about evolution and natural selection and apply it to solve our problem.

Individual

An individual is the core element of genetic algorithm, an individual represents the entity we want to evolve and get the best of, in our problem the individual would be a simple route that a truck can take.

for example:

The previous example defines a route for a vehicle where it starts from city 2, then go to city 3, until it reaches city 13, but in real world we have multiple vehicles and we want our individuals to know which vehicle is used so we can modify our individual to:

Where it means that truck one will go to city 2, followed by city 3, then to city 13 and vehicle 2 will go to city 4 followed by 5, then to city 10.

The method used to represent a route is called encoding method, while the current encoding is enough to start making the population, we discovered this would produce infeasible solutions during reproduction because some cities would be visited more than once, while some are not visited at all.

If we have 1 truck and 6 cities, and the following parents:

The child produced might be something like this

Which is infeasible since city #4 would be visited twice and city #5 is not visited at all, to solve this problem we used a new method of encoding for the parents, the idea is to generate random numbers between 0 and 1 or each city in the solution, the order in which the cities are visited is represented by sorting the random number ascendingly.

So, parent #1 will be encoded like this:

Since 0.15 is the 5th index and the smallest one, 5th city will be visited first, then city 1 and so on, by using this method we can produce childes without thinking about the problem of infeasible solutions because numbers will be always sorted ascendingly, which the results will be like this:

The new child solution is now feasible with the order in which cities will be visited, the same could be applied to the truck numbers.

Population

Like the population in real life, we initially construct a large population which is consisted from individuals, and will later reproduce based on their fittest individuals. A generation in our problem is a very large number of random generated routes, the generated routes might not represent the best optimal path, and might have duplicates, we don’t care since all of them will reproduce and the fittest will survive.

Selection

Selecting individuals is one of the crucial parts of the genetic algorithm. We already know that we are interested in the fittest routes, based on our needs and objectives we calculated the fitness function for each individual (for each route), after calculating the functions we were able to get a rank for each route which identify the best routes, Once we have the individuals ranked, various methods could be used to select fit individuals for reproduction, like tournament selection and roulette wheel.

Cross Over

After getting pairs of parents from selection stage we started reproduce the children from the pair, by taking a random point from route #1 and replace what goes after that point in route #1 from route #2 and vice versa, the following video shows the selection stage of two parents, then the reproduction of their child, also the video shows how the selection stage and the cross over stage are applied on the generation, while ignoring truck numbers for simplicity of illustration.

Generation Mutation Factory

Since we have our children from the previous population (parents) we started mutating them, by taking a random routes from the children of new generation, and select random two cities from the route and swap them. Mutation process is mandatory in genetic algorithm because it helps us to avoid local minimum. However, cross overs only won’t be enough to discover new solutions, thus, mutation will help us in discovering new solutions, the number of selected routes to be mutated is governed by the mutation rate, there are multiple ways to mutate a route, the one we’ve used is to select a random two cities from the selected route and swap them.

Implementation Details

Our implementation to solve the problem using genetic algorithm as described was written in Python which is used as backend for the iPad OS and iOS

the implementation contained the following :

And for the parameters of algorithm :

And for iOS integration Beeware software was used to deploy the python code in iOS App, also auto stop was designed in case the algorithm converged to a solution before 500 generation.

Mobile application

After implementing the genetic algorithm mutation, reproduction, and roulette wheel selection, we were able to to design a full-set of APIs so our developers can take advantage of the algorithm without the need to go into further details of implementing.

Case #1

Determination of the best route for various locations while having the ability to change number of trucks:

Case #2

Determination of the best route for 1 truck:

Case #3

Determination of the best route for 1 truck and 20 cities:

Performance

While the current application and usage for our implementation shows a very good results, some heavy tests has to be done, for this big list of locations, which is given to the algorithm where each row represent city number and associated coordinates.

The various lists had 77, 200, 90, 100 Cities respectively, which all resulted in the best routes in a very short time (the longest one took 30.197432041168213 second

Future Enhancements

In this article we discussed the problem of VRP and usage of metaheuristics without digging into the implementation details and the complexity involved for all trucks, while the current solution for VRP is good enough for the basic vehicle routing problem, we are considering supporting other variants of VRP like Multi-Depot Vehicle Routing Problem ( MDVRP), and supporting Multiple Pickup and Multiple Delivery Vehicle Routing with Time Frame which both of them are correlating with our future business needs. For technical enhancements we are considering implementing the algorithm with its interface in Rust because it provides fast and secure memory.

if you like what we are working on, work with us.

---

Share article