XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
PROBLEMA DE ROTEAMENTO DE
VEÍCULOS COM MÚLTIPLOS
DEPÓSITOS USANDO
METAHEURÍSTICAS
Sibelius Lellis Vieira (PUC GOIAS)
[email protected]
Marcos Vinicios dos Reis (PUC GOIAS)
[email protected]
Murray Evangelista de Souza (PUC GOIAS)
[email protected]
As organizações lidam frequentemente com questões relacionadas à
logística, que abordam problemas de planejamento, implementação e
do controle do fluxo de mercadorias. Um problema importante na
gestão da cadeia de suprimentos é o problema dde roteamento de
veículos em processos de logística. O problema de roteamento de
veículos com múltiplos depósitos (PRVMD) leva em consideração as
variáveis e restrições do problema de localização e roteirização. A
solução deste problema tem como objetivo encontrar as rotas que têm
o menor custo, levando em consideração as restrições do problema,
tais como a capacidade limitada do veículo, o tempo de trabalho do
motorista, a capacidade do depósito, a possibilidade de pontos de
venda serem atendidos por mais de um veículo, entre outras. Neste
trabalho, procura-se formular e analisar a aplicação do Simulated
Annealing ao problema de roteamento de veículos, que utilizam mais
de um depósito para o armazenamento de produtos que devem ser
distribuídos aos ponto de venda, com o objetivo de minimizar o custo
da operação e ao mesmo tempo, obedecer as restrições de recursos
disponíveis. Considera-se que as restrições dos recursos imponham um
custo máximo para as rotas, que espelham o caso prático de entregas
periódicas (normalmente diárias), além de outras restrições adequadas
ao problema. A capacidade dos veículos e dos depósitos não é objeto
de consideração. Diferentes mecanismos de vizinhança e de
estabelecimento da solução inicial são analisados e comparados,
indicando que tal escolha é importante para a eficácia do simulated
annealing.
Palavras-chaves: Roteamento, Logística, metaheurísticas
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM MÚLTIPLOS
DEPÓSITOS USANDO METAHEURÍSTICAS
2
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
1. Introdução
A gestão da cadeia de suprimentos é definida como um sistema pelo qual organizações e
empresas entregam seus produtos e serviços aos consumidores, numa rede de organizações
interligadas (CHOPRA et al, 2011). Uma gestão eficiente, apoiada por processos computacionais que
priorizam o uso de algoritmos adequados para a solução dos problemas de roteamento,
armazenamento e transporte e facilite a tomada de decisão, assegura que estas organizações ofereçam
um serviço diferenciado, garantindo uma liderança no mercado e permitindo que a empresa estabeleça
uma vantagem competitiva sobre os serviços das suas concorrentes, além de maximizar lucros e
minimizar custos (ZAPFEL et alli, 2010).
Neste contexto, as organizações lidam frequentemente com questões relacionadas à logística,
que abordam problemas de planejamento, implementação e do controle do fluxo de mercadorias em
uma organização (TALBI, 2009), bem como questões de armazenamento intermediário e transporte.
Para que a logística funcione de forma adequada, deve atender a alguns critérios: a
mercadoria deve ser entregue na forma que o cliente deseja, com a quantidade esperada, no prazo
correto e com um custo mínimo (BOWERSOX et alli, 2006). O problema de roteamento de veículos
com múltiplos depósitos (PRVMD), que é a base do estudo dessa pesquisa, tem como fundamento a
logística, e leva em consideração as variáveis e restrições do problema de localização e roteirização
(MIRANDA et al, 2010). A solução deste problema tem como objetivo encontrar as rotas que têm o
menor custo, levando em consideração as restrições do problema, tais como a capacidade limitada do
veículo, o tempo de trabalho do motorista, a capacidade do depósito, a possibilidade de pontos de
venda serem atendidos por mais de um veículo, entre outras (SILVA JÚNIOR, 2009).
Uma forma adequada para tratar este tipo de problema é a utilização de metaheurísticas, que
produzem uma solução boa em um curto prazo de tempo (KIRKPATRICK et alli, 1983). Soluções
produzidas por metaheurísticas podem ser avaliadas em um curto intervalo de tempo, permitindo aos
tomadores de decisão compararem as alternativas geradas e garantindo às empresas de logística a
obtenção de rotas eficazes, com um menor custo na entrega.
A técnica de Simulated Annealing é uma das ferramentas que empregam uma metaheurística
de forma flexível e com bons resultados para problemas combinatoriais (MELIÁN et alli, 2003). Neste
trabalho, procura-se formular e analisar a aplicação do Simulated Annealing ao problema de
roteamento de veículos, que utilizam mais de um depósito para o armazenamento de produtos que
devem ser distribuídos aos ponto de venda, com o objetivo de minimizar o custo da operação e ao
mesmo tempo, obedecer as restrições de recursos disponíveis. Considera-se que as restrições dos
recursos imponham um custo máximo para as rotas, que espelham o caso prático de entregas
periódicas (normalmente diárias), além de outras restrições adequadas ao problema. A capacidade dos
veículos e dos depósitos não é objeto de consideração. Diferentes mecanismos de vizinhança e de
estabelecimento da solução inicial são analisados.
No restante do artigo, a descrição do problema de roteamento de veículos com múltiplos
depósitos proposta neste trabalho é apresentada, através do formalismo da programação linear inteira.
O método de Simulated Annealing é descrito a seguir, realçando os parâmetros que devem ser
ajustados para cada tipo de problema. Estes modelos são aplicados em exemplos hipotéticos, para
extrair as informações necessárias no ajuste do método de Simulated Annealing e para explorar os
impactos que as características de vizinhança e de solução inicial podem representar na solução final,
tanto em termos de eficácia como de eficiência. Algumas considerações sobre os desafios correntes e
futuras direções são apresentadas na conclusão.
2. Materiais
Um grande problema na gestão da cadeia de suprimentos é o problema de roteamento de
veículos em processos de logística (MIRANDA et al, 2010). Os problemas reais de roteamento estão
3
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
sujeitos a uma série de fatores tais como uma frota não homogênea de veículos, compartilhamentos de
veículos, produtos incompatíveis, facilidades logísticas diferentes, o tempo de janelas de entregas,
velocidades variadas causadas pelas condições do tráfego, os clientes com prioridades diferentes e
condições de entrega e assim por diante (FISHER, 1995).
A otimização do problema de PRVMD abordado leva em consideração somente as distancias
(custos) entre as cidades (cliente). Fatores tais como a capacidade dos veículos, o tipo de carga e
prioridade de clientes não são levados em consideração. O problema deve respeitar regras
fundamentais das situações práticas, tais como a de que sempre que um determinado veículo faz uma
entrega, ou seja, chega em um determinado nó, o mesmo veículo deve deixar posteriormente (e quase
que imediatamente) o mesmo nó. Os veículos que saem de um determinado depósito devem voltar
para o mesmo depósito e não deve ser ultrapassada um custo máximo de viagem que os veículos
realizam periodicamente.
2.1 Formulação do problema
O objetivo do problema é minimizar o custo total, que inclui o custo de instalação do
depósito, dos veículos usados e os custos das rotas, conforme a apresentação dada na equação (1).
Todos os parâmetros utilizados no problema, os índices e as variáveis de decisão são definidos e
descritos nas Tabelas 1, 2 e 3 respectivamente. A primeira parte da equação (1) representa os custos de
instalação e operação dos depósitos. Neste trabalho, este custo não será considerado. A segunda parte
representa o custo total dos veículos utilizados e a terceira parte representa o custo total de todas as
rotas, ou seja, o somatório dos custos de cada rota, sendo cada uma delas associada a um e apenas um
veículo.
A restrição dada na equação (2) assegura que apenas um veículo chega em uma cidade para
realizar a atividade associada e a restrição dada na equação (3) garante que somente um veículo sai de
cada uma das cidades. Todas as cidades são servidas por algum veículo.
A restrição (4) garante que o veículo que entra em uma cidade é o mesmo a deixar esta
cidade, impedindo a troca de veículos durante o percurso de uma rota.
A restrição (5) assegura que qualquer rota deve incluir um e apenas um dos depósitos
existentes, ou seja, impede a utilização de veículos (rotas) que não passam por nenhum depósito, Um
4
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
veículo apenas existe e é contabilizado se ele sair de algum depósito existente para percorrer uma rota.
Com, isto evita-se a formação de rotas isoladas ou “sub rotas”, que não tem sua associação a nenhum
depósito.
A restrição (6) impede que a rota percorrida não ultrapasse o limite máximo preestabelecido
para qualquer rota, ou seja, o custo de qualquer rota é limitado de acordo com um critério estabelecido
previamente. O critério mais habitual para este tipo de restrição é o que associa às rotas uma
ocorrência periódica, como é o caso de entrega de jornais diários.
Tabela 1 - Parâmetros do modelo.
Parâmetro Descrição
fi
Custo de instalação dos depósito i.
N
Número total de cidades (ou clientes).
M
Número total de veículos.
Q
Número de depósitos (0 e 1).
C
Custo de cada veículo.
cij
L
Índice
i,j
k
Custo de percorrer o percurso i ao j. No caso estudado, este custo está
relacionado ao tempo de distância a ser percorrida de i a j.
Tabela 2 - Índices do modelo.
Custo máximo de uma rota. No caso estudado, este custo está
relacionado ao tempo e distâncias totais percorridas
em uma rota.de
Intervalo
Descrição
Variação
Local de origem e destino de
(0,...,N)
um percurso
Veículo que realizará o
(1,...,M)
percurso
Tabela 3 - Descrição das variáveis de decisão do modelo.
Variável
Tipo
Descrição
5
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
xijk
Binária
zk
Binária
yi
Binária
1: indica que o percurso i para j é feito pelo
veículo k
0: indica que o percurso entre i e j não é feito pelo
veículo k
1: indica que o veículo k existe, ou seja, tem uma
rota associada
0: indica que o veículo k não é utilizado.
1: indica que o depósito i existe
0: indica que o depósito i não existe.
3. Métodos
Do ponto de vista conceitual, as metaheurísticas são um processo que guia uma heurística
subordinada através da combinação de formas inteligentes diferentes que exploram o espaço de busca
e de estratégias de aprendizado usadas para estruturar as informações de modo a encontrar boas
soluções (SARAMAGO, 2003). Entre as metaheurísticas mais utilizadas, temos a busca tabu, o
simulated annealing e a computação evolutiva (BLUM et al, 2003). O Simulated Annealing foi
selecionado neste trabalho por apresentar um bom desempenho na solução de problemas de natureza
combinatorial, tanto linear quanto quadrática (VIEIRA et al, 2004).
3.1 Descrição do Simulated Annealing
A metaheurística de Simulated Annealing emprega uma analogia entre os problemas de física
estatística e problemas combinatoriais (KIRKPATRIC et alli, 1983). O procedimento considera um
sistema em equilíbrio térmico a uma temperatura t com um nível de Energia Ek. A partir daí, uma
perturbação aleatória é aplicada no sistema, correspondendo a uma mudança no nível de energia. Se o
novo nível de energia Ej é menor do que Ek, a perturbação é aceita e o sistema evolui para um novo
estado. Se o nível de energia aumenta, o sistema pode evoluir para um novo estado com uma
probabilidade que é proporcional à exp{(Ej - Ek)/t}. Depois de um número razoavelmente grande de
estados terem sido gerados e avaliados, a temperatura é decrementada e o processo é repetido. A
medida que a temperatura diminui, a probabilidade de aceitar perturbações que aumentem o nível de
energia do estado corrente também diminui. Isto implica em aceitar, depois de um longo tempo,
apenas as perturbações que melhorem a solução. O algoritmo termina com algum critério de parada
determinado, tal como o número de estados avaliados e/ou uma temperatura relativamente baixa.
A temperatura t, com valor inicial tinic, é o parâmetro que controla a evolução do algoritmo.
O valor inicial deve ser relativamente alto para permitir uma boa evolução (diversificação) no espaço
de soluções. Este aspecto permite que o algoritmo evite ficar preso em regiões de ótimos locais, pois
evoluções que não melhorem a solução corrente tem grande probabilidade de serem aceitas. A medida
que a temperatura vai diminuindo, o processo de melhoria em uma região específica vai se
intensificando (intensificação), até que eventualmente convirja para um ótimo global.
A solução inicial é denotada por Xinic e nos referimos à Xmelhor, Xatual e Xnovo para representar a
melhor solução, a corrente e a nova solução obtida a partir da solução corrente. Os valores das funções
objetivo para as soluções inicial, nova, melhor e corrente são denotadas por Zinic, Znovo, Zmelhor e Zatual,
respectivamente. A partir da solução corrente Xatual pode-se obter uma nova solução Xnovo através de
uma busca aleatória na vizinhança da solução corrente, denominada BUSCA(Xatual). A nova solução
será aceita se ∆(Znovo,Zatual) for positivo. Em tal caso, é feita uma verificação para identificar se a nova
solução é a melhor encontrada até o momento. Por outro lado, se ∆(Znovo,Zatual) for negativo, a nova
solução será aceita com uma probabilidade que diminui com a temperatura corrente t. Um número
6
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
uniformemente distribuído no intervalo [0,1) é gerado para decidir se a nova solução será aceita. Na
Figura 1, o método é ilustrado na sua forma algoritmica.
Algoritmo Simulated Annealing (Xinic,Zinic,tinic);
Inicio
Xmelhor ←Xatual ← Xinic
Zmelhor ← Zatual ← Zinic
t ← tinic
Repete
Para i = 1 até REPmax faça
Xnovo ← BUSCA(Xatual)
Se (Zatual,Znovo) > 0
Xnovo ← Xatual
Se Znovo > Zmelhor
Xmelhor ← Xnovo
Zmelhor ← Znovo
Fim-se
Senão
Se exp{∆ (Znovo,Zatual)/t} > Rand[0,1)
Xnovo ← Xatual
Fim-se
Fim-se
Fim-para
t ← rc.t
Até função objetiva inalterada
Retorna Xmelhor, Zmelhor
Fim
Figura 1 – Descrição algoritmica do Simulated Annealing
O mecanismo de decréscimo de temperatura utiliza geralmente uma escala conhecida como
escala geométrica, na qual a temperatura decresce em progressão geométrica ( t = rc.t com 0 < rc < 1).
A cada nível de temperatura, um número normalmente fixo de soluções são geradas e avaliadas. Este
número é denominado fator de repetição e denotado como REPmax. O processo continua até que a
temperatura atinja um valor tão baixo que efetivamente impeça que a solução vai mudar, a menos que
seja para melhor.
3.2 Solução inicial
De acordo com a interpretação da solução do problema, descrita anteriormente na seção 2.1,
todas as cidades devem ser atendidas por um e apenas um veículo, todos os veículos iniciam e
terminam seu trajeto no mesmo depósito, os trajetos são limitados e a soma dos custos dos trajetos
deve ser minimizada, juntamente com os custos dos veículos.
A solução do problema de roteamento de veículos com múltiplos depósitos é iniciada com a
escolha de rotas, tomando como os pontos iniciais os depósitos. Para este trabalho, são avaliadas a
solução inicial aleatória e a solução inicial determinada por uma busca gulosa. Esta busca é
implementada através da escolha da cidade mais próxima, em termos de custo, até o limite de custo
para uma determinada rota que pode ser percorrida por um veículo.
7
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
3.3 Escolha da vizinhança
Como a qualidade das soluções das metaheurísticas pode depender fortemente do tipo da
escolha da vizinhança, uma das características deste trabalho é avaliar a busca pelo tipo de vizinhança
mais adequada para a otimização, a partir das rotas iniciais (gulosas ou aleatórias).
A primeira proposta é a remoção e inserção das cidades de forma aleatória. Essa etapa
consiste na escolha randômica de duas rotas, e duas posições dentro destas rotas. Inicialmente, duas
rotas são escolhidas de forma aleatória, e em cada uma destas rotas, duas posições também aleatórias
são identificadas. Na primeira rota gerada, uma cidade na posição escolhida é retirada, e é feita uma
verificação da factibilidade nessa rota, pois há casos em que ao se retirar uma cidade de uma rota, a
ligação direta entre as cidades anterior e posterior podem geram um custo que ultrapassa o limite de
custo da rota. Se essa retirada tornar a solução não factível, deve-se retornar para o inicio do processo
de escolha, de tal forma a garantir da factibilidade das rotas alteradas. Caso a retirada da primeira
cidade seja factível, ela é inserida na segunda rota escolhida, na posição escolhida aleatoriamente. Esta
inserção só é definitivamente efetivada se a alteração não torna a segunda rota infactível, pois em caso
contrário, uma nova escolha deve ser tentada.
A principal vantagem desse método é que ele permite a retirada de rotas até que a solução
final seja encontrada, ou seja, pode haver exclusão de algumas rotas no processo de escolha do
vizinho. Esse tipo de abordagem gera um balanceamento nas rotas que não são excluídas. Porém, esta
abordagem pode se prender em soluções quando a amostragem de busca é pequena, e o algoritmo
tende a escolher de forma cíclica as mesmas soluções factíveis do problema.
A segunda proposta de vizinhança é uma permuta entre cidades pertencentes à rotas
diferentes. Nesta abordagem, são escolhidas duas rotas e duas cidades aleatoriamente, como no caso
anterior. A primeira cidade escolhida da primeira rota escolhida é trocada com a segunda cidade
escolhida da segunda rota escolhida. A vantagem desse método é que a amostragem de busca é sempre
grande. Entretanto, nesse tipo de abordagem não é possível alterar o número de rotas e portanto, o
custo associado ao veículo da rota, o que é uma grande desvantagem, já que geralmente o custo
associado aos veículos é alto.
4. Resultados e discussão
No sentido de demonstrar a as principais características da técnica de Simulated Annealing
para a solução dos problemas de roteamento de veículos, deve-se investigar experimentalmente quais
as técnicas de vizinhança mais adequadas para o algoritmo de tal forma que ele selecione as melhores
soluções. Além disto, o impacto da escolha da solução inicial na solução final também deve ser
identificado em função das características das soluções encontradas. Para tal, as seguintes questões
devem ser adequadamento respondidas:
1. Como adequar o algoritmo de Simulated Annealing com relação às técnicas de escolha
da vizinhança?
2. Qual o impacto da solução inicial gulosa no desempenho do algoritmo?
Para responder à questão 1), aplica-se o algoritmo de Simulated Annealing a um conjunto de
dados gerados aleatoriamente, tanto para a vizinhança insere-retira quanto para a vizinhança troca e o
resultado tanto na métrica do valor da função objetivo quanto na do tempo necessário para calculá-la é
observado. Para responder a questão 2) aplica-se o algoritmo de Simulated Annealing às mesmas
instâncias anteriores, mas com uma solução inicial aleatória, observando e comparando os valores
anteriormente mencionados.
4.1 Parâmetros básicos do PRVMD no Simulated Annealing
8
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
Para realizar a avaliação do desempenho do Simulated Annealing, considera-se matriz de
custo cij dada através de uma distribuição uniforme de custos entre cidades e destas para os depósitos,
tendo um valor uniformemente distribuído no intervalo [10,100]. O número de cidades é variável,
começando em 28 e aumentando em uma dezena até o número máximo de 98, totalizando um total de
100 pontos (2 depósitos e 98 cidades). O valor para o custo máximo de qualquer rota (L) é de 200 e o
valor de cada veículo (ki) é de 100.
O valor inicial da temperatura foi escolhido de tal forma que possibilite movimentos para
regiões de pior solução e o fator de redução conjuntamente com o número de repetições e o critério de
parada permitem que estes movimentos diminuam ao ponto de inexistirem ao final do algoritmo. Para
os valores típicos do nosso problema, o valor de tinic é escolhido de tal forma que ∆ (Znovo,Zatual)/tinic
seja pequeno, na faixa de [10-2,10-3]. Como critério de parada, um valor de temperatura tfim é escolhido
para que inviabilize qualquer movimento que não seja para melhorar a solução, ou seja, um valor de
tfim substancialmente menor do ∆ (Znovo,Zatual), em geral de 100 a 1000 vezes menor. Para esta variação
de t, o decréscimo da temperatura de forma geométrica com um fator de redução rc , o número de
degraus de temperatura pode ser dado por tfim/tinic .log(rc) . Em cada degrau, com a temperatura
mantida constante, ajusta-se o fator de repetição de tal forma a obter-se um valor para a função
objetivo que aproxima-se da solução ótima.
4.2 Avaliação das vizinhanças e soluções iniciais
Primeiramente, o valor da função objetivo é calculado, levando-se em conta um conjunto de
cenários cujos parâmetros já foram especificados na seção 4.1, partindo de uma solução inicial gulosa,
para as vizinhanças retira-insere e a vizinhança de troca. Cada cenário é executado dez vezes e os
dados analisados são tomadas em relação à média destas 10 observações. Na Figura 2, pode ser
observado que para ambos os casos, a função objetivo aumenta de forma regular com o aumento o
número de cidades ou o custo do sistema. Este aumento não é linear, indicando que após um
determinado número de cidades, o ganho na função objetivo diminui. Isto acontece em particular em
função do aumento das opções de rotas e portanto, da possibilidade de escolha de rotas melhores por
unidade de rota. Também é notado que a vizinhança retira-insere apresenta um resultado melhor e isto
se deve ao fato de este tipo de vizinhança permite a diminuição de rotas, o que não ocorre com a
vizinhança do tipo permuta. A diminuição de rota acaba implicando em um valor menor da função
objetivo, na média.
3700
Valor da funcão objetivo s
3400
3100
2800
2500
Retira insere
2200
Permuta
1900
1600
1300
1000
20
30
40
50
60
70
80
90
100
110
120
Número de cidades
9
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
Figura 2 – Ilustração do valor da função objetivo para as vizinhanças retira-insere e
permuta, com solução inicial gulosa.
700000
Número de tentativas
600000
500000
400000
Retira insere
Permuta
300000
200000
100000
0
20
30
40
50
60
70
80
90
100
110
120
Número de cidades
Figura 3 – Ilustração do número de tentativas para as vizinhanças retira-insere e
permuta, com solução inicial gulosa.
Na Figura 3, verifica-se que o número de tentativas realizadas para obter a solução final é
maior para a vizinhança retira-insere. Com a possível diminuição do número de rotas e o decréscimo
da função objetivo e da temperatura a medida que o algoritmo evolui, o número de vizinhos factíveis
em uma vizinhança também diminui sensivelmente, o que torna a vizinhança retira-insere mais lenta e
aumenta o número de tentativas para encontrar novas soluções factíveis. O aumento do número de
cidades e consequentemente do número de rotas, por outro lado, também influencia este
comportamento, pois aumenta a chance de obter vizinhos factíveis. Entretanto, o desempenho dos
dois tipos de solução é equivalente do ponto de vista de esforço computacional.
Em um segundo grupo de experimentos, a escolha da solução inicial é realizada de forma
aleatória. Pode ser observado, na Figura 4, um aumento não-linear do valor da função objetivo,
consistente com os resultados anteriores apresentados na Figura 2 e já discutidos. A novidade é que o
valor das função objetivo final é bem maior do que o obtido para a solução inicial gulosa, indicando
que a solução inicial tem importância para a convergência adequada da metaheurística, o que tem sido
observado em outros trabalhos.
10
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
Valor da função objetivos
3500
3000
2500
Retira Insere
Permuta
2000
1500
1000
20
30
40
50
60
70
80
90
100
110
120
Número de cidades
Figura 4 – Ilustração do valor da função objetivo para as vizinhanças retirainsere e permuta, com solução inicial aleatória.
5. Conclusão
Neste trabalho procura-se examinar o problema do roteamento de veículos com múltiplos
depósitos, identificando uma formulação adequada para o tratamento do problema e um método de
busca baseado em metaheurísticas capaz de resolver o problema em um tempo aceitável. As propostas
abordadas resultaram em soluções interessantes e se mostraram capazes de contribuir com melhorias
no planejamento das rotas. A solução inicial abordada é uma solução parecida com a solução tomada
por pessoas que planejam essas rotas, que é traçar as rotas para as localidades mais próximas.
Contudo, os resultados mostraram que essa não é uma boa estratégia de roteamento.
As técnicas de otimização com o simulated annealing juntamente com as iterações das
vizinhanças se mostraram melhores em combinação com os algoritmos gulosos. A técnica de inserção
remoção se mostrou cara computacionalmente quando o espaço de busca se reduz com a remoção dos
veículos. Porém, quando o número de cidades aumenta essa técnica se torna muito mais eficaz.
A técnica de permutação de atendimento de cidades entre rotas diferentes se mostrou
equilibrada, embora com menor eficácia em relação à técnica insere remove, em função de não alterar
o número de rotas e portanto, do número e custo dos veículos. Por outro lado, ela não apresenta os
problemas de se prender de forma cíclica em algumas soluções, da forma como pode ocorrer a insere
remove.
Como perspectivas de continuação do trabalho, espera-se investigar novas formulações, que
incluam um número maior de depósitos, os custos dos depósitos e capacidades de entrega e demanda
de recebimento.
Referências
Blum, C. and Roli, A. (2003) Metaheuristics in Combinatorial Optimization: Overview and
Conceptual Comparison. ACM Computing Surveys, 35(3):268-308.
Bowersox, D. J., Closs, D. J. And Cooper, M. B. Gestão Logística de Cadeia de Suprimentos, São
Paulo: Bookman, 2006.
11
XXXII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Desenvolvimento Sustentável e Responsabilidade Social: As Contribuições da Engenharia de Produção
Bento Gonçalves, RS, Brasil, 15 a 18 de outubro de 2012.
Chopra, S. and Meindl, P. Gerenciamento da Cadeia de Suprimentos: Estratégia, Planejamento e
Operação. São Paulo: Prentice Hall, 2011.
Fisher, M. Handbooks in Operations Research and Management Science: Network Routing, chapter
Vehicle Routing, pages 1–33. North-Holland, 1995.
Kirkpatric, S., Gelatt, C. and Vecchi, M. (1983), Optimization by Simulated Annealing. Science,
220:291-307, 1983.
Laporte, G. (1992), The vehicle routing problem: an overview of exact and approximate algoritms.
European Journal of Operations Research, v. 59, n. 3, p 345-358.
Melián, B., Pérez, J. A. M. And Vega, J. M. M. (2003), Metaheuristics: A Global View. In Revista
Iberoamericana de Inteligencia Artificial. Asociación Española de Inteligencia Artificial, v. 2, n. 19.
Miranda, D. M. e Conceição, S. V. (2010). Um Problema de Roteamento Dinâmico, com Tempos de
Viagem Estocásticos, Múltiplos Veículos e Janelas de Tempo. XLII Simpósio Brasileiro de Pesquisa
Operacional, Bento Gonçalves, RS.
Saramago, S. F. Métodos de otimização randômica: algoritmos genéticos e “Simulated Annealing”.
São Carlos, SP: SBMAC, 2003.
Silva Junior, O. S. Roteirização de Veículos de Carga com Múltipos Depósitos em Sistemas de
Informação Geográfica Livre. Rio de Janeiro: Instituto Militar de Engenharia, 2009.
Talbi, E. Metaheuristics: From Design to Implementation, John Wiley and Sons, 2009.
Vieira, S. and Liebeherr, J. (2004), Topology Design of Service Overlay Networks with Bandwidth
Guarantees. Proceedings of the 12th IEEE IWQoS, Toronto, Canada.
Zapfel, G., Braune, R. and Bogl, M. Metaheuristic Search Concepts – A Tutorial with Applications
to Production and Logistics, Springer, 2010.
12