O MÉTODO DE BUSCA ALNS COMBINADO COM AS
METAHEURÍSTICAS ILS E VNS PARA O PROBLEMA
DE COLETA E ENTREGA COM JANELAS DE TEMPO
Viviane Junqueira de Moraes
Gustavo Peixoto Silva
O MÉTODO DE BUSCA ALNS COMBINADO COM AS METAHEURÍSTICAS ILS E
VNS PARA O PROBLEMA DE COLETA E ENTREGA COM JANELAS DE TEMPO
Viviane Junqueira de Moraes
Gustavo Peixoto Silva
Universidade Federal de Ouro Preto
Departamento de Computação
RESUMO
Este trabalho aborda o Problema de Coleta e Entrega com Janelas de Tempo, o qual requer que uma frota de
veículos atenda a um determinado número de pedidos com o menor custo possível. Um pedido consiste em
coletar uma mercadoria em um determinado local e entregá-lo em outro, dentro de um determinado intervalo de
tempo. Todos os pedidos devem ser atendidos respeitando a capacidade dos veículos e as janelas de tempo de
coleta e entrega. O problema é resolvido combinando o método de busca ALNS com as metaheurísticas ILS e
VNS. Os métodos foram testados com uma série de problemas benchmark largamente utilizados na literatura. Os
resultados mostram a eficiência dos mesmos, uma vez que, para a maioria dos problemas testados, foram
encontrados resultados iguais ou muito próximos dos melhores resultados registrados na literatura.
ABSTRACT
This paper explores the Pickup and Delivery Problem with Time Windows (PDPTW), which requires that a fleet
of vehicles try to meet the request of customers at the lowest cost. Each request needs a vehicle to pick up a
number of products in one location and deliver it in another one. All requests must be attended while respecting
vehicle capacity and customer time windows. The problem is solved with the method of search ALNS combined
with metaheuristics ILS and VNS. The methods have been applied to a series of benchmark problems widely
used in the literature. The results show the efficiency of methods once for most of the tested problems, the results
obtained were equal or close to the best results fund in the literature.
1. INTRODUÇÃO
Os setores de logística ligados ao transporte de produtos, matérias-primas, bens e pessoas
lidam constantemente com situações em que os veículos devem ser roteados de modo a
percorrer uma série de locais para a coleta ou entrega de mercadorias ou para a prestação de
serviços. Para isso, procuram constantemente reduzir os custos fixos e variáveis relacionados,
por exemplo, com a aquisição de veículos e manutenção dos mesmos, gastos com
combustíveis, pagamentos de salários de motoristas e de horas extras.
Na literatura existe uma variedade de problemas de roteamento de veículos. O objetivo geral
desses problemas é construir rotas utilizando a mínima distância e o menor número de
veículos e respeitando as características e restrições específicas de cada tipo do problema.
(Ballou, 2001). O Problema de Coleta e Entrega com Janelas de Tempo (Pick-up and Delivery
Problem with Time Windows - PDPTW) é uma variante desta classe de problemas. Aplicações
práticas do PDPTW incluem o problema dial-a-ride, programação de companhias aéreas,
roteamento de ônibus, suporte de helicópteros em plataformas de petróleo e suporte logístico
e de manutenção (Nanry e Barnes, 2000).
O PDPTW requer a construção de um conjunto de rotas de custo mínimo para atender um
determinado número de pedidos, utilizando uma frota limitada de veículos que iniciam e
terminam sua jornada em um depósito. Um pedido consiste em dois clientes: coletar uma
mercadoria em um determinado local, “cliente coleta”, e entregá-lo em outro, “cliente
entrega”.
O PDPTW considera janelas de tempo, que são os prazos para o início da coleta e da entrega e
1
ainda para o veículo sair e retornar ao depósito. Um veículo nunca deve chegar a um local
após o horário final da janela de tempo, mas pode chegar antes do início da janela. Neste caso
ele deve aguardar o horário para iniciar a operação. Tempos de serviço de carga e descarga
também são associados a cada pedido. O local de coleta de um pedido deve ser sempre
visitado antes do local de entrega, garantindo a relação de precedência. Além disso, deve ser
respeitada a relação de acoplamento, ou seja, a coleta e entrega de um pedido devem ser
inseridas na mesma rota. É bom ter em mente que cada rota está associada a um veículo.
Cada veículo tem uma capacidade limitada, e inicia e finaliza sua jornada de trabalho em um
depósito, chamado terminal de início e de fim. O terminal de início pode ser diferente do final
para um veículo e dois veículos podem ter terminais diferentes. Cada veículo possui o horário
determinado para partir do terminal de início e o horário máximo em que deverá chegar ao
terminal de fim. O horário estipulado para início da jornada do veículo deve ser respeitado,
mesmo que introduza um tempo de espera no primeiro local visitado.
Diferentes trabalhos sobre o PDPTW são encontrados na literatura, os quais apresentam
situações reais e métodos de resolução tanto heurísticos quanto exatos. Dumas et al. (1991)
apresentam um algoritmo exato para resolver o PDPTW referente ao transporte de
mercadorias com veículos homogêneos e múltiplos depósitos. O algoritmo proposto é um
método de geração de colunas, o qual utiliza o problema de caminho mínimo com restrição de
recursos para gerar as colunas do problema principal. Os autores desenvolvem também um
método branch-and-bound, capaz de resolver problemas com até 55 clientes. Por outro lado,
Nanry e Barnes (2000) foram os primeiros a apresentar uma Busca Tabu Reativa (BTR) para
o PDPTW. O método combina diferentes movimentos em vizinhanças com o mesmo padrão e
foi aplicado para o PDPTW com frota homogênea e único depósito. Para testar a
metaheurística, os autores criaram instâncias com até 100 clientes a partir de um conjunto
padrão proposto por Solomon (1987). A BTR mostrou-se eficiente para resolver um conjunto
de problemas práticos de tamanho considerável. Quando comparados os seus resultados com
outros resultados da literatura, obtidos até então, foram capazes de encontrar boas soluções
em um tempo computacional relativamente menor.
Li e Lim (2001) usam uma metaheurística híbrida, combinando a Simulated Annealing e a
Busca Tabu. Para testar o método, os autores desenvolvem 56 instâncias, também com base
nos dados propostos por Solomon (1987), com 100 clientes ou mais e com diferentes
distribuições geográficas. Dentre estas instâncias, nove casos são maiores do que os de Nanry
e Barnes (2000). Os resultados mostram a eficiência do método, que encontrou bons
resultados para todos os dados, cuja maioria perdura até os dias atuais como a melhor solução
obtida para os problemas propostos pelos autores (SINTEF). Lim et al. (2002) aplicam
otimização local do tipo squeaky wheel e busca local para o PDPTW. Esta heurística também
é testada no conjunto de problemas propostos por Li e Lim (2001). Xu et al. (2003)
consideram um PDPTW com várias restrições práticas incluindo múltiplas janelas temporais,
compatibilidade e restrições de tempo máximo de condução. O problema é resolvido usando
uma heurística de geração de colunas que foi testada em instâncias com até 500 clientes.
No trabalho de Ropke e Pisinger (2006), os autores apresentam uma metaheurística de busca
em vizinhança de grande porte denominada Adaptive Large Neighborhood Search (ALNS) e
mostram que esta técnica pode ser utilizada para resolver tanto o PDPTW como pode ser
estendida para resolver uma variedade de problemas de roteamento de veículos, como por
2
exemplo, o problema de roteamento com janelas de tempo, com múltiplos depósitos e com
backhauls.
Recentemente, Zachariadis et al. (2010) tratam o problema de roteamento de veículos com
coletas e entregas simultâneas, que considera que os clientes exigem a coleta e a entrega
simultânea de serviços. Os autores utilizam uma abordagem metaheurística, introduzindo um
algoritmo de memória adaptativa que guarda e combina características promissoras da solução
para gerar novas soluções de alta qualidade, conduzindo a busca para diversas regiões do
espaço de soluções. A metaheurística proposta é testada para instâncias entre 50 e 400 clientes
e são obtidas soluções de alta qualidade com um esforço computacional limitado.
O PDPTW é um problema do tipo NP-difícil, por se tratar de um caso particular do problema
do caixeiro viajante (Ropke e Pisinger, 2006b). Em muitos casos reais, o conjunto de
restrições tanto de ordem legal quanto de operação da empresa, tornam o problema de grande
complexidade, e a necessidade de resolver estes problemas em um tempo computacional
razoável, encontrando soluções satisfatórias, ressalta a importância da utilização de métodos
heurísticos eficientes.
Este trabalho apresenta a utilização da busca ALNS combinada com as metaheurísticas VNS e
ILS. As metaheurísticas foram testadas com problemas benchmark, largamente utilizados na
literatura, chegando aos melhores resultados conhecidos para a maioria dos casos. O trabalho
está dividido da seguinte maneira: na seção 2, apresenta-se a modelagem heurística do
problema e os métodos utilizados para a sua resolução. Os experimentos computacionais são
descritos na seção 3 e, finalmente, na seção 4, são apresentadas as conclusões do trabalho.
2. MODELAGEM HEURÍSTICA DO PROBLEMA
O objetivo principal na resolução do PDPTW é minimizar o número de veículos usados e a
distância total percorrida. Para alcançar estes objetivos é necessário construir rotas válidas,
que obedeçam as janelas de tempo, as restrições de capacidade dos veículos, de precedência e
de acoplamento dos pedidos.
2.1 Função Objetivo
O custo associado a uma solução do PDPTW é computado por meio do somatório da distância
total percorrida por todos os veículos utilizados, considerando que para cada veículo é
designada uma rota, ou seja:
tot _ rotas
C PDPTW =
∑ Distância _ Percorrida
i
(1)
i =1
sendo que, Distância_Percorrida representa o somatório da distância do depósito até o
primeiro cliente, deste até ao próximo, e assim sucessivamente até o último cliente e,
finalmente, deste último cliente ao depósito.
2.2 Solução Inicial
O método de geração da solução inicial proposto neste trabalho foi baseado em Li e Lim
(2001). O procedimento constrói uma rota por vez, onde o primeiro pedido da rota é
selecionado utilizando um critério que maximiza a distância do pedido ao depósito, cujas
janelas de tempo finais do pedido ocorrem mais cedo e cujo período das janelas de tempo é
mais curto. Após definido o primeiro pedido da rota, o método seleciona os próximos pedidos
baseado no critério de minimização da distância total percorrida. Para calcular a distância da
3
rota após a inserção de um pedido, o método analisa a melhor posição do pedido na rota. Se
mais nenhum pedido puder ser inserido nesta rota, uma nova rota é criada e o procedimento é
repetido. O método continua até que todos os pedidos tenham sido inseridos em alguma rota.
2.3 Heurística para minimização do número de veículos utilizados
O método para minimização do número de veículos foi baseado no trabalho de Ropke e
Pisinger (2006). O algoritmo recebe uma solução inicial viável, com um determinado número
de veículos. Sorteia-se um veículo e todos os seus pedidos são removidos. Em seguida, um
método guloso tenta reinserir os pedidos deste veículo nas outras rotas existentes. Se todos os
pedidos forem inseridos, o método inicia nova busca a partir desta solução e o número total de
veículos é atualizado. Caso contrário, a busca é realizada a partir da solução viável anterior. O
procedimento é repetido durante um determinado número de iterações sem melhora, que neste
trabalho foi definido empiricamente como 200.
2.4 Adaptive Large Neighborhood Search- ALNS
A heurística ALNS é uma extensão da heurística Large Neighborhood Search (LNS),
introduzida por Shaw (1997), que trabalha com múltiplas vizinhanças definidas
implicitamente através da utilização combinada de diferentes métodos de “destruição” e
“reparo” de uma solução. A cada um dos métodos é atribuído um peso que auxilia na escolha
daqueles que serão utilizados em cada iteração. Os pesos são ajustados dinamicamente a partir
do desempenho dos métodos ao longo do processo de busca.
A pesquisa ALNS é dividida em segmentos. Um segmento equivale a 100 iterações ALNS.
Em cada iteração são aplicadas duas heurísticas: uma de remoção e uma de inserção. A
escolha das heurísticas a serem usadas é feita por uma seleção do tipo roleta (squeaky wheel).
A heurística de inserção é selecionada independentemente da heurística de remoção. O sorteio
é baseado nos pesos atribuídos às heurísticas. A pontuação de ambas as heurísticas aplicadas
são atualizadas pela mesma quantidade, pois não é possível assegurar se foi a heurística de
remoção ou a de inserção que gerou o sucesso. A pontuação é aumentada segundo o seguinte
critério: σ1 quando a última operação resulta em uma solução melhor do que a melhor solução
encontrada até o momento, σ2 quando resulta em uma solução cujo custo ainda não foi
encontrado, é pior que a melhor solução encontrada até o momento mas é melhor do que o da
solução atual, e σ3 quando resulta em uma solução cujo custo ainda não foi encontrado, é pior
que o da solução atual, mas satisfaz o critério de aceitação.
No primeiro segmento, a pontuação de todas as heurísticas é definida como zero e os pesos
são definidos como um. No final de cada segmento são calculados novos pesos usando os
resultados obtidos. Assim, seja wij o peso da heurística i usada no segmento j. Depois de
terminado o segmento j, os pesos são recalculados para cada heurística i, a fim de serem
usados no segmento j + 1 da seguinte maneira:
(2)
1− +
=
,
onde
πi: pontuação da heurística i obtida durante o último segmento;
θi: número de vezes que foi usada a heurística i durante o último segmento;
r : fator reação.
O fator reação controla a influência da pontuação e dos pesos anteriores na definição do peso
para a nova iteração. Se r for igual a zero, não é usada a pontuação do último segmento e o
4
peso anterior é mantido. Se r for igual a um, então, somente a pontuação obtida no último
segmento será utilizada para definir o peso. Além disso, utilizou-se um termo adicional de
diversificação da busca, que consiste em randomizar a operação das heurísticas reconstrutivas,
através de adição de um “ruído” à função objetivo. Desta forma, nem sempre o pedido é
inserido na melhor posição na rota. Todas as vezes que a heurística reconstrutiva calcula o
custo C de inserir o pedido em uma dada rota e em uma dada posição é gerado um “ruído”,
que é um número aleatório no intervalo [–ηmaxi,j∈V(di,j), –ηmaxi,j∈V(di,j)], e calcula-se o custo
modificado C’ = max{0, C + ruído}. Onde η controla a quantidade de ruído que é adicionada
e maxi,j∈V(di,j) é a máxima distância existente entre dois pedidos. Um ruído negativo reduz o
custo do pedido na posição e aumenta a possibilidade do método de inserção optar por essa
posição. Por outro lado, um ruído positivo aumenta o custo da posição tornando menos
provável que o pedido seja inserido naquela posição.
2.4.1 Heurísticas Destrutivas
Foram implementadas as seguintes heurísticas destrutivas: Remoção Randômica, Remoção da
Pior Posição e Remoção Shaw. A heurística de Remoção Randômica simplesmente seleciona
q pedidos de forma aleatória e os remove da solução. A remoção da Pior Posição seleciona os
pedidos que parecem ter sido colocados numa posição errada na solução, gerando um custo
maior. O método calcula o custo de cada pedido e seleciona um determinado número de
pedidos que possuem os maiores custos. Esta seleção é feita segundo o grau de aleatoriedade
dado pelo parâmetro ppior. Isto é feito para evitar situações onde os mesmos pedidos são
removidos várias vezes. A heurística de Remoção Shaw procura remover os pedidos que são
semelhantes, partindo da ideia de que fica razoavelmente fácil embaralhar esses pedidos e,
assim, criar soluções melhores. A similaridade entre dois pedidos é dada pela soma ponderada
da distância entre os pedidos, da conexão temporal, da demanda e do número de veículos que
são capazes de servir os dois pedidos. Quanto menor for este somatório, mais relacionados
são os dois pedidos. Comparando as heurísticas de remoção Shaw e remoção da Pior Posição,
pode-se concluir que a remoção da Pior Posição remove os pedidos mais caros e que podem
ser mais difíceis de serem inseridos e a remoção Shaw seleciona pedidos semelhantes e que,
consequentemente, serão mais fáceis de serem reinseridos na solução.
2.4.2 Heurísticas Construtivas
As duas heurísticas de inserção implementadas recebem as rotas após a remoção e a lista dos
pedidos que foram removidos, e tentam reinseri-los na solução. A heurística de Inserção
Gulosa procura inserir o pedido na posição de menor custo. Primeiro, calcula-se o custo de
inserir cada pedido em cada uma das rotas, na melhor posição, e registra a rota para a qual o
pedido tem menor custo. Então, o pedido a ser inserido será aquele de menor custo. Ela
realiza no máximo q iterações, uma vez que insere um pedido em cada iteração. Um problema
desta heurística é que ela muitas vezes adia a colocação de pedidos difícieis, com custo muito
elevado para as últimas iterações, quando sua inserção se torna mais difícil.
A heurística de Inserção de Arrependimento se baseia na heurística Gulosa, porém tenta
melhorá-la incorporando uma espécie de avaliação do tipo “olhar à frente” quando vai
selecionar um pedido para ser inserido. A heurística pesquisa o custo de inserção de um
pedido nas k melhores rotas e seleciona o pedido cujo somatório das diferenças dos custos
entre inserir na melhor rota e nas k - 1 melhores rotas for maior. O pedido é inserido na rota e
na sua posição de custo mínimo. Os pedidos que só podem ser inseridos em poucas rotas são
inseridos primeiro, para tentar garantir que a heurística sempre alcance uma solução viável.
5
O método para inserção do pedido na sua posição de menor custo foi baseado no método PDRearrange Operator proposto por Li e Lim (2001). A análise é baseada no custo adicional na
FO gerado pela inserção do pedido em determinada posição da rota. Para calcular este custo, o
método primeiro analisa uma posição viável, que não viole as restrições do problema, para o
cliente coleta, a partir do início da rota. Em seguida é feita a análise de todas as posições
possíveis para o cliente entrega, a partir da posição imediatamente seguinte do cliente coleta.
O procedimento é repetido até que todas as posições possíveis sejam testadas, ou seja, até que
seja testada a posição onde o cliente coleta é o penúltimo da rota e o cliente entrega é o
último. Este procedimento é exemplificado na Figura 1.
Figura 1: Exemplo da análise da melhor posição do pedido na rota
Fonte: Adaptado de Li e Lim (2001)
3. A METAHEURÍSTICA ITERATED LOCAL SEARCH PARA O PDPTW
A metaheurística Iterated Local Search (ILS) é baseada na ideia de melhorar um
procedimento de busca local, gerando novas soluções de partida, por meio de perturbações na
solução ótima local corrente. O foco da busca não é o espaço completo de soluções, mas um
pequeno subespaço definido por soluções que são ótimos locais de determinado procedimento
de otimização.
Conforme Lourenço et al.(2003), a ILS explora o espaço de soluções por meio da aplicação
de perturbações à solução corrente. Em linhas gerais, a Figura 2 mostra que o ILS parte de
Função ILS (nível)
1.
gera uma solução inicial s0;
2.
solução smelhor := s0;
3.
aplica Busca Local 1 em s0, gerando s*;
4.
Repita
5.
aplica Perturbação(nível) em s*, gerando s’;
6.
aplica Busca Local 2 em s’, gerando s’’;
7.
se s’’ atende ao Critério de Aceitação;
8.
s*:= s’’;
9.
fim se
10.
se s’’ for melhor smelhor;
11.
smelhor := s’’;
12.
fim se
13. até critério de parada seja satisfeito
14. retorna smelhor;
Figura 2: Pseudocódigo da metaheurística ILS
Fonte: Adaptado de Lourenço et al.(2003)
6
uma solução inicial s0 e a esta aplica a busca local do tipo 1, obtendo s*. Posteriormente, o
método efetua iterativamente os seguintes passos: i) perturba a solução corrente s*, obtendo
s’; ii) realiza uma busca local do tipo 2 a partir de s’, obtendo s’’ que é um ótimo local; iii) se
o critério de aceitação for satisfeito, então retorna s’’ para a nova iteração, senão retorna a
melhor solução conhecida até o momento para que seja efetuada uma nova iteração. Se s’’ for
melhor do que a melhor solução obtida até o momento, então ele atualiza a melhor solução.
Este procedimento é repetido até que um critério de parada seja satisfeito.
3.1 Perturbação da Solução Corrente
De acordo com Lourenço et al. (2003), o sucesso da ILS depende fortemente das perturbações
realizadas. Estas devem ser dosadas de tal maneira que as alterações sejam suficientes para
escapar de ótimos locais e explorar diferentes regiões sem, contudo, causarem a perda de
características do ótimo local corrente. A perturbação utilizada neste trabalho se baseia na
distância média percorrida pelos veículos de uma dada solução. Então, para cada veículo, o
método vai retirando pedidos até que a distância percorrida seja menor ou igual ao nível de
perturbação multiplicado pela distância média da solução. A retirada dos pedidos pode ser
feita de três maneiras: no tipo 1, o método retira os primeiros pedidos da rota; no tipo 2, são
retirados os últimos pedidos da rota; e no tipo 3, a retirada dos pedidos é feita alternadamente,
sendo um do início, um do final. O tipo de remoção é definido aleatoriamente para cada rota.
A inserção dos pedidos removidos é feita da seguinte maneira: em cada iteração um pedido
removido é sorteado e este é inserido de acordo com o critério guloso, ou seja, na rota e na
posição de menor custo. Se algum pedido não puder ser inserido nas rotas existes, o
procedimento é reiniciado a partir da solução viável anterior à perturbação. São feitas cinco
tentativas para encontrar uma solução viável, caso contrário, prossegue-se com aquela
solução. O nível de perturbação varia entre [-10% , 10%]. Ou seja, o método inicia com o
nível igual a 0,9: se a solução encontrada após a iteração ILS for melhor que a melhor solução
conhecida, o nível de perturbação é mantido, caso contrário, ele é aumentado em 0,05.
Quando o nível máximo é atingido, ele retorna para o nível mínimo.
3.2 Métodos de Busca Local
Foram utilizados dois métodos de busca local. A Busca Local 1 consiste em minimizar o
número de veículos utilizados e a Busca Local 2 consiste na aplicação da busca ALNS
seguida pela Busca Local 1.
3.3 Critério de Aceitação e Condição de Parada
O critério de aceitação utilizado foi de soluções correntes até 1% piores do que a melhor
solução encontrada, como forma de diversificar o processo de busca. Quanto ao critério de
parada, definiu-se um número de iterações sem melhora igual a 2.000 como forma de lidar
igualmente com os diferentes problemas resolvidos, uma vez que o tempo computacional de
cada iteração pode variar de um problema para outro.
4. A METAHEURÍSTICA VARIABLE NEIGHBORHOOD SEARCH PARA O PDPTW
A metaheurística Variable Neighborhood Search (VNS) foi proposta por Mladenović e
Hansen (1997). O método parte de uma solução inicial viável, a partir desta gera um vizinho
qualquer, segundo uma estrutura de vizinhança e realiza uma busca local a partir deste
vizinho. Se a busca local gerar uma solução melhor do que a solução corrente, esta é
atualizada e o processo se repete a partir da primeira estrutura de vizinhança. Caso contrário,
7
um novo vizinho é gerado considerando a próxima estrutura de vizinhança e a busca local é
aplicada neste vizinho. Este processo se repete até que a condição de parada seja satisfeita. A
Figura 3 mostra as etapas realizadas pela metaheurística por meio do seu pseudo-código.
4.1 Estruturas de Vizinhança
As estruturas de vizinhança utilizadas neste trabalho são caracterizadas pelo número de
pedidos removidos. Os movimentos realizados para encontrar o melhor vizinho de uma
solução corrente ficam por conta do método ALNS. Ou seja, kmax é igual ao número total de
pedidos do problema. Inicialmente o número de pedidos removidos k é igual 1, a ALNS
Função VNS
1.
gera uma solução inicial s0;
2.
solução smelhor := s0;
3.
seja um conjunto de kmax estruturas de vizinhanças;
4.
repita
5.
k ← 1;
6.
enquanto k ≤ kmax faça:
7.
gere um vizinho qualquer s’ de s na k-ésima vizinhança;
8.
encontre o melhor vizinho s’’ de s’ na vizinhança k;
9.
se s’’ for melhor smelhor;
10.
smelhor := s’’;
11.
fim se
12.
fim enquanto
13. até critério de parada seja satisfeito
14. retorna smelhor;
Figura 3: Pseudocódigo da metaheurística VNS
encontra o melhor vizinho e, se este vizinho for melhor que a melhor solução encontrada até o
momento, então k continua como 1 e a busca é iniciada nesta melhor solução encontrada.
Caso contrário, k é incrementado em 1 unidade e assim sucessivamente, até que k = kmax.
4.2 Critério de Parada
O critério de parada utilizado foi o número de iterações sem melhora igual a 2.000. Este valor
foi obtido empiricamente.
5. EXPERIMENTOS COMPUTACIONAIS
Para testar as metaheurísticas ILS e VNS foram utilizados os 56 problemas construídos por Li
e Lim (2001) com até 100 clientes, disponíveis em SINTEF. Nestes dados os veículos partem
e retornam a um único depósito, e todos os pedidos devem ser obrigatoriamente atendidos.
Além disso, todos os veículos podem atender todos os pedidos. As instâncias propostas por Li
e Lim (2001), são classificativas em 3 tipos: no tipo R, todas as localizações estão distribuídas
uniformemente, no tipo C as localizações estão distribuídas em 10 grupos geográficos e no
tipo RC, 50% das localizações são alocadas em 10 grupos e os outros 50% são distribuídos
uniformemente. A Figura 4 mostra um exemplo da distribuição destes dados. Os
experimentos foram realizados em um computador Intel i7, com 8GB de memória RAM,
Windows 7, linguagem de programação C++ no programa Code::Blocks 12.11.
8
Figura 4: Distribuições dos clientes nos dados dos tipos LC, LR e LRC
Para testar a metaheurística ILS, foram realizadas 5 execuções para cada problema. Em cada
Busca Local 2 foram executados 5 segmentos da heurística ALNS. Os parâmetros da
heurística ALNS utilizados foram aqueles sugeridos por Ropke and Pisinger (2006), quais
sejam, ( , χ, ψ, ω, p, ppior, σ1, σ2, σ3, r, η) = (9, 3, 2, 5, 6, 3, 33, 9, 13, 0.1, 0.025). Para testar a
metaheurística VNS também foram realizadas 5 execuções para cada problema e os
parâmetros ALNS foram os mesmos.
A Tabela 1 apresenta os resultados obtidos pelas metaheurísticas e estes são comparados com
os melhores resultados da literatura, registrados no SINTEF. Os resultados encontrados pelas
metaheurísticas que foram iguais aos da literatura estão em negrito. Os valores que estão
sublinhados correspondem à melhor solução entre ILS e VNS, quando não ocorre o empate
entre elas. São apresentados também os tempos de processamento (TP), em segundos,
necessários para encontrar os resultados. Observa-se que a ILS foi capaz de encontrar o
mesmo resultado da literatura para 45 dos 56 problemas. Para 4 problemas o número de
veículos utilizados foi igual ao da literatura, porém a distância percorrida encontrada é
superior em até 3,45%. Para apenas 5 problemas, tanto o número de veículos quanto a
distância da solução foram superiores aos resultados da literatura. E para 3 problemas, o
número de veículos foi superior em 1 unidade, porém a distância foi inferior ao resultado da
literatura em até 20%.
A metaheurística VNS foi capaz de encontrar o mesmo resultado da literatura para 42 dos 56
dados. Para 3 problemas o número de veículos utilizados foi igual ao da literatura, porém a
distância percorrida encontrada foi superior em até 8,05%. Para apenas 7 problemas, tanto o
número de veículos quanto a distância da solução foram superiores aos resultados da
literatura. E para 4 problemas, o número de veículos foi superior em 1 unidade, porém a
distância foi inferior o resultado da literatura em até 20%.
9
Tabela 1: Resultados obtidos pelas metaheurísticas e comparação com os melhores resultados
da literatura
Problema
LC101
LC102
LC103
LC104
LC105
LC106
LC107
LC108
LC109
LC201
LC202
LC203
LC204
LC205
LC206
LC207
LC208
LR101
LR102
LR103
LR104
LR105
LR106
LR107
LR108
LR109
LR110
LR111
LR112
LR201
LR202
LR203
LR204
LR205
LR206
LR207
LR208
LR209
LR210
LR211
LRC101
LRC102
LRC103
LRC104
LRC105
LRC106
LRC107
LRC108
LRC201
LRC202
LRC203
LRC204
LRC205
LRC206
LRC207
LRC208
Melhor Resultado
Literatura
Veículos
Distância
10
828,94
10
828,94
9
1035,35
9
860,01
10
828,94
10
828,94
10
828,94
10
826,44
9
1000,6
3
591,56
3
591,56
3
585,56
3
590,6
3
588,88
3
588,49
3
588,29
3
588,32
19
1650,80
17
1487,57
13
1292,68
9
1013,39
14
1377,11
12
1252,62
10
1111,31
9
968,97
11
1208,96
10
1159,35
10
1108,90
9
1003,77
4
1253,23
3
1197,67
3
949,40
2
849,05
3
1054,02
3
931,63
2
903,06
2
734,85
3
930,59
3
964,22
2
911,52
14
1708,8
12
1558,07
11
1258,74
10
1128,40
13
1637,62
11
1424,73
11
1230,15
10
1147,43
4
1406,94
3
1374,27
3
1089,07
3
818,66
4
1302,2
3
1159,03
3
1062,05
3
852,76
Resultado ILS
Veículos
10
10
10
9
10
10
10
10
10
3
3
3
3
3
3
3
3
19
17
13
9
14
12
10
9
11
11
10
9
4
4
3
2
3
3
3
2
3
3
3
14
13
11
10
13
11
11
10
4
4
3
3
4
3
3
3
Distância
828,94
828,94
827,86
860,01
828,94
828,94
828,94
826,44
827,82
591,56
591,56
591,17
591,17
588,88
588,49
588,29
588,32
1650,80
1487,57
1292,68
1013,39
1377,11
1252,62
1111,31
968,97
1208,96
1170,59
1108,90
1003,77
1253,23
1250,09
949,40
849,05
1054,02
931,63
930,63
734,85
930,59
964,22
884,29
1708,80
1563,55
1258,74
1128,40
1637,62
1424,73
1230,14
1147,43
1455,54
1390,56
1089,07
818,66
1302,20
1159,03
1062,05
861,86
10
Resultado VNS
TP(s)
0,00
0,00
191,52
337,71
153,33
174,52
0,00
266,20
484,79
0,00
1395,69
2087,92
9551,22
1098,12
1484,04
1482,57
1981,29
585,60
300,75
163,74
1234,00
114,52
149,23
191,60
236,08
327,31
1599,68
213,11
637,55
553,96
2098,78
7105,08
7192,41
2992,36
2041,85
11070,83
5866,85
12665,53
1676,12
15188,27
332,17
125,77
147,62
203,43
108,45
587,81
338,40
343,66
433,96
584,30
1272,73
2393,27
1059,26
902,23
1361,81
5269,65
Veículos
10
10
10
9
10
10
10
10
10
3
3
3
3
3
3
3
3
19
17
13
9
14
12
10
9
11
11
10
9
4
4
3
2
4
3
3
2
3
3
3
15
13
11
10
13
11
11
10
4
4
3
3
4
3
3
4
Distância
TP(s)
0,00
828,94
0,11
828,94
827,86
0,95
861,95
245,30
0,08
828,94
0,19
828,94
0,00
828,94
0,45
826,44
827,82
3,60
0,00
591,56
12,31
591,56
591,17
3,24
638,18
101,09
1,98
588,88
2,23
588,49
10,75
588,29
4,29
588,32
11,45
1650,80
35,15
1487,57
4,06
1292,68
451,59
1013,39
1,36
1377,11
0,45
1252,62
3,85
1111,31
2,09
968,97
37,80
1208,96
1165,83
20,62
55,52
1108,90
82,29
1003,77
27,58
1253,23
1234,00
125,67
256,23
949,40
618,59
849,05
1089,52
295,86
18,03
931,63
957,63
5.004,45
1.047,03
734,85
401,17
930,59
150,76
964,22
884,29
3.702,47
1703,21
30,70
1563,55
40,67
29,48
1258,74
11,33
1128,40
48,98
1637,62
187,47
1424,73
242,63
1230,14
266,59
1147,43
11,87
1406,94
1391,90
163,54
725,95
1089,07
255,80
818,66
100,31
1.302,20
14,49
1.159,03
447,07
1.062,05
946,11
445,32
Comparando o desempenho das duas metaheurísticas, o mesmo resultado foi encontrado para
46 problemas. Para 3 problemas, o número de veículos encontrado pela VNS foi superior em
uma unidade em relaçao ao encontrado pela ILS. Em 4 problemas a VNS encontrou o mesmo
número de veículos que a ILS, porém a distância percorrida é superior em até 7,8%. Em 3
problemas a VNS encontrou o mesmo número de veículos que a ILS, porém a distância
percorrida é melhor em até 3,5% aproximadamente.
Comparando o tempo computacional, em segundos, necessário para a metaheurística
encontrar o melhor resultado apresentado na Tabela 1 na coluna TP(s), pode-se observar que a
VNS foi superior em 98% dos problemas e a economia de tempo variou entre 59,47 e
12.264,36 segundos. Acredita-se que esta diferença acentuada pode estar ligada à heurística
de minimização de veículos que é executada após a ALNS na Busca Local 2, principalmente
para os problemas que são resolvidos utilizando número reduzido de rotas.
6. CONSIDERAÇÕES FINAIS
As metaheurísticas Iterated Local Search e Variable Neighborhood Search combinadas com a
busca local em vizinhança de grande porte Adaptive Large Neighborhood Search mostraramse eficientes para resolver o PDPTW. Para a maioria dos problemas testados, os métodos
foram capazes de encontrar resultados iguais ou muito próximos aos melhores resultados
registrados na literatura. A ILS foi superior à VNS em poucos problemas, porém o tempo
computacional utilizado pela VNS foi consideravelmente menor. Em muitos casos, os
melhores resultados conhecidos podem ser os ótimos o que impossibilita a sua melhoria por
qualquer metaheurística. Este estudo possibilita a utilização das metaheurísticas para a
resolução de problemas maiores e, ainda, abordar problemas correlatos.
Agradecimentos
Os autores agradecem à UFOP, ao CNPq e à FAPEMIG pelo apoio parcial recebido no desenvolvimento deste
trabalho.
REFERÊNCIAS BIBLIOGRÁFICAS
Dumas, Y.; Desrosiers, J. e Soumis, F. (1991) The pickup and delivery problem with time windows. European.
Journal of Operations Research, v. 54. p. 7–22.
Hansen, P. e Mladenovic, N. (1999) An introduction to variable neighborhood search. In: S. Voss et al. (Eds.),
Meta-Heuristics, Advances and Trends in Local Search Paradigms for Optimization, p. 433-458, Kluwer,
Boston.
Li, H. e Lim, A. (2001) A metaheuristic for the pickup and delivery problem with time windows. ICTAI-2001,
13th IEEE Conf. Tools Artificial Intelligence, p. 160-170, Dallas.
Li, H.; Lim, A. e Rodrigues, B. (2002) Solving the pickup and delivery problem with time windows using
“squeaky wheel” optimization with local search. Technical Report, Singapore Management University,
Singapore.
Lourenço, H. R.; Martin, O. C.; Stutzle, T. (2003) Iterated local search. In: Hand-book of Metaheuristics, F.
Glover and G. Kochenberger, Eds. Kluwer Academic Publishers, Boston.
Mladenović, N. e P. Hansen. Variable Neighborhood Search, Computers & Operations Research, v. 24, Issue
11, p. 1097-1100, 1997.
Nanry, W. P. e Barnes, J. W. (2000) Solving the pickup and delivery problem with time windows using reactive
tabu search. Transportation Res. Part B, v. 34, p. 107–121.
Ropke, S. e Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery
problem with time windows. Transportation Science, v. 40, p. 455–472.
SINTEF.
Vehicle
routing
and
travelling
salesperson
problems.
Disponível
em
(www.sintef.no/Projectweb/TOP/PDPTW/Li--Lim-benchmark/100-customers/, 4, 2013.
Shaw, P. (1997) A new local search algorithm providing high quality solutions to vehicle routing problems.
Technical Report, Department of Computer Science, University of Strathclyde, Scotland.
Shaw, P. (1998) Using constraint programming and local search methods to solve vehicle routing problems.
11
Proc. CP-98 Fourth Internat. Conf. Principles Practice Constraint Programming.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window
constraints. Operations Research, v. 35, p. 254–265.
Xu, H.; Z. L. Chen; S. Rajagopal e S. Arunapuram. (2003). Solving a practical pickup and delivery problem.
Transportation Sci. v. 37, p. 347–364.
Zachariadis, E. E.; Christos D. Tarantilis, C. D. e Kiranoudis, C. T. (2010) An adaptive memory methodology
for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of
Operational Research, v. 202, p. 401–411.
Viviane Junqueira de Moraes ([email protected])
Gustavo Peixoto Silva ([email protected])
Departamento de Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto
Campus Universitário, Morro do Cruzeiro, Ouro Preto, MG, Brasil
12