Genetic transportation of products

An evolutionary algorithms approach of Artificial Intelligence

Project description

Let's assume that a company has a truck that can ship goods. Each product that is loaded into the truck has a different potential profit whereas other products take up more space than others. The question is: how can we ensure that the truck is loaded with products that maximize the profit? In other words, which products shall the company load in the truck to get the maximum profit?

Possible solutions

The number of possible solutions for this problem are... over a million! For only 10 products, there are about 39.916.800 possible combinations! It is quite exhaustive to iterate all possible combinations and choose the best combination. What if we want to add more products in the future? Every complication will only increase the number of possible solutions.

In this project, we used genetic algorithms which seems to be a perfect fit for this kind of problems!

How it works

  1. You choose the tab "Demostration" above
  2. You define the problem. Specify which products exist in your problem and the capacity of the truck (e.g. 2 TVs of 0.400 cubic meters and a track of 3 cubic meters)
  3. You click "run" and the "Genetic transportation of goods" will give you an optimal solution

Example

Let's assume that company A has a truck of capacity equal to 1m³. In their storage they have the following products available for shipping:

What would you choose in this situation? Obviously you wouldn't add the 5 TVs in the truck just to fill up the truck, right? You would most probably put the notebook first which doesn't take much space and yields the highest income. Then you would have space for 4 more TVs. You can add those too.

Afterwards, you are left with 0.15m³. So what do you do? You obviously add three pairs of shoes that will fill your truck and generate a few more bucks.

As simple as it sounds, it can be quite challenging to do this procedure when you have a warehouse of thousands of products. This is why the automation of such a procedure is needed. In this project, we used genetic algorithms to solve this issue. Click on the demostration tab to try such an example.

Error! Some of the inputs specified are incorrect!

Choose track specifications

Capacity must be between 1 and 10

Specify products in storage

Genetic algorithms tuning

Number of generations must be between 1 and 500

Mutation must be between 0 and 1

Population size must be between 1 and 50

Actions

Configuration used

Truck capacity: m³

No. generations:

Mutation rate: %

Population size:

Best solution

Generation

Score: $

Space used: m³

Products to put in truck

Name Price ($) Space required (m³)

Solutions per generation

Initial population's solution

This is the generation 0, the solution found when the population was initialized. In other words, when the chromosomes where randomly initialized and no mutations or crossovers took place

Score: $

Space used: m³

Products to put in truck

Name Price ($) Space required (m³)

Best scores in each generation

Space used in best solutions

Solution explained

The explanation below assumes that you are familiar with at least the concept of genetic algorithms. If not, perhaps this article is illuminative. Nevertheless, the explanation below is meant for everyone, not just experts.

One of the challenges of genetic algorithms, is to break the problem down to chromosomes, genes and a fitness function. Once you determine that, the rest is quite straightforward (simply put at least). Below, there is a brief explanation on how I defined the gene, the chromosome and the fitness function to solve this problem.

Gene

A gene in this problem is represented as a binary digit.

  • 0 means that the product is not selected to be loaded in the truck
  • 1 means that the product is selected

Chromosome

A chromosome is sequence of genes. Essentially a chromosome represents a solution. For instance, the chromosome 010 below means that the first and thrid products are not selected and the second product is selected to be put inside the truck. In other words, the solution below shows that the TV and the mobile phone will not be put in the truck whereas the Notebook will be.

Representation

Handling quantities

If you already tried the form in the demonstration tab, you might have noticed that in the form you are able to choose more than one instances of the same product (e.g. 3 TVs). Since a chromosome is a binary value representing whether the product is included in the truck... does this mean that the all product instances shall be included?

No. Once the products are specified, the solver creates a list (sequence) of the products. If a product has 2 instances, then the product is represented in the list twice!. Similarly, for every instance of the same product, a new representation will be added. If a product has 0 instances, then obviously the product will not be added to the sequence.

The example below shows how the product "TV" will be represented if the product has quantity equal to two. As you will notice, the product has been added to the chromosome twice.

Representation