ALGORITMOS GENÉTICOS APLICADOS EM PROBLEMAS DE
TRANSPORTE
Keila Nogueira ,Kenedy Nogueira, Keiji Yamanaka, Edgard Lamounier
([email protected], [email protected], [email protected], lamounierj@ ufu.br)
Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia
Uberlândia – MG, Brasil
Resumo - Este trabalho apresenta o uso de técnicas de
algoritmos genético com a proposta de auxiliar no
problema de transporte. Será implementado um estudo
de caso de uma fabrica de refrigerantes, com o intuito de
minimizar custos e maximizar lucros.
Palavras-Chave - Algoritmos Genéticos, Otimização de
Rotas.
GENETIC ALGORITHMS APPLIED IN
TRANSPORTATION PROBLEMS
Abstract - This paper presents the use of techniques of
genetic algorithms with the proposal to help the problem
of transport. Will be implemented a case study of a
manufacturing soft drinks in order to minimize costs and
maximize profits.
1
Keywords - Genetic Algorithms, Optimization
I. INTRODUÇÃO
Tradicionalmente para resolução de Problemas de
Otimização (maximização e minimização) são usadas
técnicas como simplex, método gráfico e outros.
(Hermes,2004).
O Problema de Transporte (PT) é talvez o mais
representativo dos Problemas de
Programação Linear. É
um problema de grande aplicação prática, tendo sido
estudado por vários investigadores. (Canavarro, 2003)
O problema geral de transporte consiste em determinar a
forma mais eficiente, isto é, mais econômica de enviar um
bem disponível em quantidades limitadas em determinados
locais para outros locais onde é necessário.
A resolução de um problema de transporte envolve
basicamente três etapas:
1ª consiste em encontrar uma solução básica inicial;
2ª procede-se ao teste para verificar se essa solução é
ótima ou não;
3ª fase consiste na passagem desta solução a outra
melhor, caso exista evidentemente.
Formulação do Problema:
O problema clássico de transporte surge como
necessidade de programar a distribuição ótima de um produto
que:
1.
se encontra disponível em m origens nas
quantidades fixas ai>0 (oferta), com i=1,2,...,m.
2. é necessário em n destinos nas quantidades fixas
bj>0 (procura), com j=1,2,...,n;
3. deve ser enviado diretamente para os destinos,
esgotando as disponibilidades em cada origem e
satisfazendo as necessidades em cada destino, isto é,
a procura total iguala a oferta total;
Tendo por objetivo a minimização do custo total
envolvido no programa de distribuição desse produto, em
que se supõe que os custos unitários de transporte de cada
origem para cada destino, cij, são independentes das
quantidades transportadas, xij.
Figura 1- Problemas de Transporte.
O que são problemas de Transporte?
Figura 2- Esquema Problemas de Transporte.
Para qualquer plano de transporte admissível a soma em
linha dos xij quantidade ai,
e a soma dos xij
.
igualam à quantidade de
O custo do percurso (i,j) é dado por cij X xij, pelo que o
custo total do plano de transporte é dado por
.
B. Obtenção de uma Solução Básica Admissível
(SBA) inicial
Tabela 1- Origem X Destino.
1
Destino
2
...
n
Oferta
Origem
1
2
...
m
Procura
c12
c11
x11
x12
c22
c21
x21
...
x22
...
cm1
xm1
b1
cm2
xm2
b2
...
c1n
a1
c2n
a2
cm3
...
am
x1n
...
x2n
...
...
...
......
bn
xmn
∑
∑
ai= bi
A formalização matemática do problema de transporte
como problema de programação linear vem então:
Como se afirmou, qualquer SBA de um PT tem (m+n-1)
variáveis básicas. A questão que se levanta é como encontrar
uma dessas soluções. Uma forma pouco eficiente consiste em
fixar (mn)-(m+n-1) variáveis com o valor zero e resolver o
sistema em ordem às (m+n-1) restantes. Existem, contudo,
métodos alternativos como, por exemplo, o do Canto do
Noroeste, do Mínimo da matriz de Custos, Método de Vogel,
entre outros.
1- Método do Canto do Noroeste (NW) ou Método do Canto
Superior Esquerdo
Este método é de aplicação muito fácil, mas tem um
grande inconveniente que é o fato de não considerar a matriz
de custos na identificação da SBA inicial. Assim,
considerando o PT na forma de quadro apresentada atrás, a
variável básica escolhida é, em cada quadro, a variável
situada no canto superior esquerdo, donde a designação de
método do canto do NW. No primeiro quadro, a variável a
tomar como básica é sempre
II. OBJETIVO
Está proposta tem por objetivo resolver problemas de
transporte usando Algoritmos Genéticos. Inicialmente serão
mostradas soluções convencionais usando alguns métodos.
A. Usando a solução convencional
·; no segundo quadro a
ou
, consoante
variável básica escolhida será
tenha sido traçada a coluna 1 ou a linha 1, respectivamente, e
assim sucessivamente até terem sido traçadas todas as linhas
e todas as colunas.
Considere-se o exemplo anterior para obter uma SBA
utilizando o método do Canto do Noroeste.
Certa empresa possui dois armazéns, A1 e A2, onde
dispõe de 100 e 50 unidades de determinado produto,
respectivamente, com o que abastece três mercados, M1, M2
e M3, que consomem 80, 30 e 40 unidades. Sabendo que os
custos de transporte são dados no quadro.
Tabela 3 – Origem x Destino
Tabela 2 –Custo1
A1
A2
M1
5
4
M2
3
2
M3
2
1
Atribui-se a
A formalização do problema- minimização do custo total
de transporte – vem:
x o maior valor possível, isto é o mínimo
entre a oferta da origem 1 e a procura no destino 1,
=
min{100,80} =80. O destino 1 vê desta forma satisfeita a
procura respectiva, por isso traça-se o resto da coluna 1, e
ficam ainda disponíveis 100-80=20 unidades na origem 1.
Tem-se um novo quadro.
Quadro 4
Quadro 1
2- Método do Mínimo da Matriz de Custos
A escolha da nova variável recai agora sobre a que está
=min{20,30} =20 ,
no canto mais noroeste, ou seja,
ficando a origem 1 completamente esgotada. Traça-se a linha
1 e ficam por satisfazer 30-20=10 unidades no destino 2.
Repete-se o procedimento no quadro.
·, pelo que, em princípio, fornece soluções iniciais
mais próximas da solução ótima.
Neste método, a escolha da variável a ser básica, é
decidida pelo menor custo em cada quadro (em caso de
empate a escolha é arbitrária).
Este método pode ainda ser particularizado, como
Método do Mínimo de Matriz de Custos em Linha, ou
Método do Mínimo de Matriz de Custos em Coluna. Retomese novamente o exemplo anterior.
O menor dos custos da matriz é
pelo que
={
min 50,40} =40. O destino 3, fica satisfeito, traçando-se a
respectiva coluna, e ficam disponíveis 50-40=10 unidades na
origem 2. Tem-se:
Quadro 2
Tem-se nova variável básica
resultando no quadro:
Ao contrário do método anterior, o algoritmo que agora
se apresenta toma em consideração a matriz de custos,
= min{50,10} =10
Quadro 5
Para escolher a nova variável básica, procura-se outra
Quadro 3
Resta agora, apenas uma quadrícula (2,3), verificando-se
obviamente, a igualdade entre a oferta e a procura, pelo que
=3 , pelo que
=
vez o menor custo que é
min{10,30} =10, ficando assim esgotada a origem 2, e
ficando ainda em falta no destino 2, 30-10=20 unidades.
=40 , esgotando-se assim, em simultâneo origem 2 e
destino
3.
A
SBA
inicial
obtida
é
(m+n-1=4 variáveis básicas) e as restantes, ou seja, as não
básicas iguais à zero.
O valor da FO desta solução é:
z = 5× 80 + 3× 20 + 2 ×10 +1× 40 = 520
A representação da solução no quadro é:
Quadro 6
Resta agora
=min{80,80}= 80 , muito embora
com um custo alto, 5, onde se tem a oferta igual à
procura, pelo que ficam esgotadas as linha e coluna
correspondentes.
A solução que se apresenta é a seguinte:
Quadro 9
Escolhe-se a maior diferença, e de novo há empate
para ambas as linhas. Arbitrariamente escolhe-se a
linha 1 (origem 1), cuja variável de menor custo é
Quadro 7
=min{40,100} =40 , ficando assim esgotado o 3º
destino.
Por coincidência esta solução é igual à obtida pelo
Canto Superior Noroeste, com custo igual a 520.
3- Método de Vogel
Este método tem em geral melhores resultados do
que os dois métodos anteriores, uma vez que a
escolha feita para variável básica, é em cada quadro o
de menor custo da linha ou coluna associada à maior
das diferenças entre os dois menores custos de cada
linha e de cada coluna. Para aplicação deste método é
útil acrescentar uma linha e uma coluna ao quadro
para se escreverem as diferenças entre os dois
menores custos de cada linha e de cada coluna.
Quadro 10
Agora vai-se afetar à variável
={ min 80,20}=,
e restam depois 60 unidades para 11 x
obrigatoriamente.
Quadro 8
Quadro 11
Neste caso há empate em toas as diferenças pelo
que arbitrariamente vou escolher a 2ª coluna, isto é, o
2º destino, e aí, a variável de menor custo
é
=min{30,50}= 30. O 2º destino fica esgotado, e
na origem 2 há ainda 50-30=20 unidades. Voltam a
calcular-se as diferenças para as linhas e colunas,
tendo em atenção às quadrículas que já estão
esgotadas.
Esta solução tem custo igual a 520. Note-se que é
diferente das obtidas pelos outros dois métodos, mas
em termos de custo é exatamente igual.
III. DETALHES DA IMPLEMENTAÇÃO
A proposta do trabalho é desenvolver um estudo de caso
que tenha o problema de transporte, utilizando técnicas de
Algoritmos Genéticos. Será usado um problema real de uma
fabrica de refrigerante.
O sistema ter terá uma única cidade de origem
(Araguari) e n cidades destinos.
O custo é dado de acordo com as distâncias das cidades
a ser percorrida e o peso será a quantidade de refrigerantes a
serem entregues. Com isso será possível minimizar custos e
maximizar lucros.
Existem algumas restrições no sistema, como por
exemplo, a demanda (estoque) tem que ser maior ou igual a
solicitações (vendas).
Abaixo será demonstrado um exemplo utilizando o
método convencional.
Partindo do principio que saía da fabrica dos caminhões
um CAM1 do tipo caminhote e um CAM2 do tipo caminhão.
Estes caminhões irão abastecer três cidades (Monte Carmelo,
Coromandel e Unaí), 400, 400 e 600 pacotes
respectivamente.
400
0
600
200
800
400
400
600
0
X12= min(200,800)=200
400
0
200
0
0
800
600
400
400
200
600
200
X22= min(200,800)=200
Araguari
400
0
200
200
0
600
800
600
400
600
200
400
0
200
X23= min(600,600)=600
Monte Carmelo
400
Coromandel
400
Unaí
600
400
0
200
200
0
600
600
800
600
400
600
200
400
0
200
0
Figura 3- Dados
O valor da FO desta solução é:
Os custos são dados na tabela a seguir:
CAM1
CAM2
Mont.Carm
99
139
Z= 400*99+200*150+200*190+600*459= 383.000
Isso equivale a R$383,00 reais de custo.
Cor.
150
190
Unaí
419
459
2- Método do Mínimo de Custo
Mont
Cor
Unaí
Oferta
Tabela 2 –Custo2
CAM1
Como foi visto anteriormente existem 3 métodos (Canto
do Noroeste, do Mínimo da matriz de Custos, Método de
Vogel). Utilizará somente 2 como exemplo.
99
x11
CAM2
x21
139
400
150
x12
190
x13
419
600
459
800
x22
x23
400
600
1- Canto Noroeste
X11= min(600,400)=400
Mont
Cor
Unaí
Oferta
99
150
419
600
400
459
800
0
99
CAM1
CAM2
x11
x21
139
400
x12
190
x13
x22
x23
400
600
X11= min(600,400)=400
139
400
150
419
190
459
400
600
0
.
X12= min(200,400)=200
600
800
200
99
150
419
200
400
139
190
459
0
400
0
400
200
600
200
800
600
X22= min(200,800)=200
99
400
139
150
200
419
0
190
459
200
0
400
0
600
200
800
600
400
200
600
Como a carga completa dos dois caminhões é 1400, 200
pacotes vão para ser vendidos a pronta entrega.
O cromosso pode ser formado por até 9 genes, sendo que
a posição do gene representa à cidade e o conteúdo a
quantidade de pacotes.
O cruzamento utilizado foi o Partially Mapped Crossover
(PMX).
A Mutação utilizado foi a Mutação Swap(por troca), entre
dois pontos, ou seja, o gene do ponto 1 é trocado com o gene
do ponto 2.
Vamos a um exemplo:
A fabrica tem que fazer entrega para 3 cidades (Monte
Carmelo, Coromandel e Unaí), 400, 400 e 600 pacotes
respectivamente. Com o outro método verificamos que o
custo foi de R$ 383,00 reais. Utilizando Algoritmo Genético
com 10 gerações, 0,1 de mutação e 0,3 de Cross-Over,
obtemos o seguinte resultado:
X23= min(600,600)=600
99
150
400
200
139
0
400
0
419
0
190
459
200
600
400
200
600
200
800
600
600
Z= 400*99+200*150+200*190+600*459= 383.000
Isso equivale a R$383,00 reais de custo.
Utilizando agora Algoritmos Genéticos
Neste estudo de caso a população inicial é a quantidade de
pacotes de guaraná, que podem ser aleatórios ou
inicializados, ou seja, quando um caminhão sai da fabrica já
sai com pedidos para serem entregues, mas, além disso, vai
uma carga excedente para ser vendida a pronta entrega.
Figura 5- Exemplo1
O Caminhão 1 transportou 800 pacotes, 200 para
Coromandel e 600 para Unaí. Já o Caminhão 2, 600 pacotes,
sendo que 400 para Monte Carmelo e 200 para Coromandel.
Figura 4- Pedidos
A figura 4 mostra a quantidade de pacotes que foram
solicitados de acordo com os pedidos Unaí 600, Monte
Carmelo 400 e Coromandel 200, totalizando 1200 pacotes.
Clicando no botão Fabrica Araguari, tem-se a visualização
da fabrica usando o Google Earth.
Figura 8 – Fabrica Araguari
IV. CONCLUSÕES
Figura 6- Rota Percorrida
Neste exemplo o custo final obtido foi de R$ 349,40.
Se aumentar a taxa de mutação para 0,2 o custo será
melhor, sendo que o caminhão 1 transportará 400 pacotes
para Monte Carmelo e 400 para Coromandel, já o caminhão
2 transportará 600 pacotes para Unaí. Neste caso o custo será
de R$ 231,6.
Chegou à conclusão que após vários testes feitos e
apresentado o algoritmo genético conseguiu melhores
resultados dos que os métodos convencionais. Conseguindo
encontrar menores custos de transporte conseqüentemente
obtendo lucros.
Como trabalho futuro pretende-se utilizar mais cidades,
pois a fabrica distribui refrigerantes para mais de 20 cidades.
Visualizar os dados em 3D, utilizando recursos de Realidade
Virtual e Aumentada e traçar as rotas utilizando Google
Earth.
REFERÊNCIAS BIBLIOGRÁFICAS
C.T Canavarro, 2003) http://docentes.esa.ipcb.pt/ccanavarro
(Hermes,2004)http://hermes.ucs.br/ccet/deme/lzsauer/calculo
/restrito/material_de_apoio_pdf
Figura 7- Rota Percorrida 2