Cargo Load Optimization with a Genetic Algorithm

A few days ago, I came across a problem in an area I had not yet studied, when a friend who owns a fleet of trucks asked me to work out how to distribute deliveries across a region. He wanted to use as much of his trucks' space as possible, carry as much weight as they could support, and maximize his profit on the deliveries, considering that the higher the total value of the cargo, the higher the profit from the deliveries.

So... While researching how to solve this problem, I found an area that I now spend a good part of my time studying, called Genetic Algorithms. This type of computational intelligence algorithm works like the process of species evolution (yes, the one you are thinking of), Darwin's famous theory of evolution, but not quite like the image below, which only considers a sort of "evolutionary leap".

It is more like a genetic explanation, especially of the reproductive process of species, which undergo a phenomenon called crossover that "mixes" part of the DNA of a father and a mother, plus the environmental effects that can cause the famous mutation (but not the X-Men kind). These two phenomena modify the genetics over time, or generations, adapting species to the environment through "survival of the fittest", in which those that survive have an easier time reproducing.

This is exactly the process we simulate when designing a genetic algorithm, and how do we do it? I can tell you it is very simple. All you need is to create a population of individuals whose genes hold binary values indicating whether or not the truck will carry each product.

The whole basic process of a genetic algorithm is essentially defined by the flowchart below, from population creation, fitness and selection all the way to optimization.

Adapted from Eyal Wirsansky, 2020

The products loaded onto the truck were taken from a Kaggle competition called brazilian-ecommerce, which has several separate datasets, so a join between the products was needed to make all the variables required for the load optimization available, as shown in the table below.

Another thing we need for the simulation are our constraints: the maximum volume of the VUC truck (a small urban cargo vehicle), which is 5,544.00 cm³, and a maximum weight load of 4,000,000.00 grams. So the next step is to create the product class in Python and turn the dataset into lists, with the following code.

#Criar Classe do Produto
class Produto():
    def __init__(self, nome, pesos, volume, valores):
        self.nome = nome
        self.pesos = pesos
        self.volume = volume
        self.valor = valor

#Transformar em lista
espacos = list(produtos.volume)
valores = list(produtos.preco)
nome = list(produtos.product_id)
pesos = list(produtos.product_weight_g)

This brings us to one of the trickiest parts of the algorithm, the evaluation function, which assesses which population is best and gives it a score (just like in evolution), thereby giving it priority to reproduce in the next generation. In this case, I used the "biased roulette wheel" evaluation function, considering the truck's weight and space constraints.

#Criar a função de avaliação
def avaliacao(individual):
    nota=0
    soma_espacos=0
    soma_pesos=0

    for i in range(len(individual)):
        if individual[i]==1:
            nota+=valores[i]
            soma_espacos+=espacos[i]
            soma_pesos+=pesos[i]

           if soma_espacos > limtie_espacos and soma_pesos>limtie_peso:
            nota=1
return nota/100000,

With all that done, we just need to call the DEAP evolutionary algorithms framework and create what the framework calls a Toolbox, adding and registering everything in this toolbox, which will be called later to run the optimization.

#Criar a toolbox
toolbox=base.Toolbox()

#Criando parâmetros na toolbox
creator.create("FitnessMax",base.Fitness,weights=(1.0,))creator.create("Individual",list,fitness=creator.FitnessMax)

#Registrando na toolbox
toolbox.register("attr_bool",random.randint,0,1)
toolbox.register("individual",tools.initRepeat,creator.Individual,toolbox.attr_bool,n=len(espacos))
toolbox.register("population",tools.initRepeat,list,toolbox.individual)toolbox.register("evaluate",avaliacao)
toolbox.register("mate",tools.cxOnePoint)
toolbox.register("mutate",tools.mutFlipBit,indpb=0.05)
toolbox.register("select",tools.selRoulette)

With all of that in place, all that is left is to run the algorithm, specifying the statistics to be tracked, the number of individuals in each generation (population), the crossover probability and the number of generations.

#Iniciando a toolbox
if__name__=="__main__":
    population=toolbox.population(n=24)
    probabilidade_crossover=5.0
    probabilidade_mutação=0.03
    numero_gerações=250


    estatisticas = tools.Statistics(key=lambdaindividuo:
            individuo.fitness.values)

    estatisticas.register("max",np.max)
    estatisticas.register("min",np.min)
    estatisticas.register("med",np.mean)
    estatisticas.register("std",np.std)

    populacao,info=algorithms.eaSimple(population,toolbox,
                                         probabilidade_crossover,
                                        probabilidade_mutação,
                                        numero_gerações, estatisticas)

After 250 generations, we arrive at the best individual, with a value of R$ 7968387.8, adding up to 56604 items, some of which you can see in the first five products.

We can also see how the algorithm learned over each epoch by plotting the maximum value of the best individual in each generation.

#Plotando o aprendizado
valores_pop = info.select("max")
plt.figure(figsize = (12,6))
plt.plot(valores_pop)
plt.show()

As we can see, the best individual was found very early in the run, more specifically in generation 23.

So that's it. This was a simple example of using a genetic algorithm, but it showed that with simple programming it is possible to maximize a company's profit, and the approach can be improved and applied to many business problems. You can find the full notebook on my GitHub.

I hope you enjoyed the article; if you did, please share it. :)