A Metaheurística ILS combinada com a busca ALNS para resolver

o Problema de Coleta e Entrega com Janelas de Tempo

Viviane Junqueira de Moraes

Universidade Federal de Ouro Preto

vivianejmoraes@gmail.com

Gustavo Peixoto Silva

Universidade Federal de Ouro Preto

gustavo@iceb.ufop.br

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 com a metaheurística Iterated

Local Search, que aplica perturbações à solução corrente com o objetivo de fugir de ótimos locais e

aumentar a capacidade de busca no espaço de soluções. A busca local é realizada com a Adaptive Large

Neighborhood Search, que trabalha com múltiplas vizinhanças obtidas pela combinação de diferentes

métodos de destruição e reparo da solução. A metaheurística foi testada com uma série de problemas

benchmark disponíveis na internet e largamente utilizados na literatura.

Keywords: Pick-up and Delivery Problem with Time Windows; Iterated Local Search; Adaptive Large

Neighborhood Search.

1 Introdução

O Problema de Coleta e Entrega com Janelas de Tempo (Pick-up and Delivery Problem with Time

Window - PDPTW), requer que uma frota limitada de veículos atenda os pedidos dos clientes com o

menor custo. Um pedido consiste em coletar uma mercadoria em um determinado local e entregá-lo em

outro. Ambas as operações devem ser iniciadas dentro de determinados intervalos de tempo. Todos os

pedidos devem ser atendidos respeitando a capacidade dos veículos e as janelas de tempo de coleta e

entrega.

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

desenvolveram também um método branch-and-bound, capaz de resolver problemas com até 55 clientes.

Por outro lado, Nanry e Barnes (2000) foi um dos primeiros trabalhos 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, foi capaz de encontrar boas soluções em um tempo computacional relativamente menor.

Li e Lim (2001) usaram uma metaheurística híbrida, combinando a Simulated Annealing e a Busca Tabu.

Para testar o método, desenvolveram 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 mostraram a eficiência do método,

que encontrou bons resultados para todos os dados e a maioria dos resultados perduram até os dias atuais

como a solução ótima para os problemas propostos pelos autores (SINTEF). Lim et al. (2002) aplicaram

otimização local do tipo squeaky wheel e busca local para o PDPTW. Esta heurística também foi testada

no conjunto de problemas propostos por Li e Lim (2001).

No trabalho de Ropke e Pisinger (2006), os autores apresentaram a metaheurística de busca de grande

porte denominada Adaptive Large Neighborhood Search (ALNS) e mostraram 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 exemplo, o problema de roteamento com janelas de

tempo, com múltiplos depósitos e com backhauls.

Recentemente, Zachariadis et al. (2010) trataram o problema de roteamento de veículos com coletas e

entregas simultâneas, problema da área de logística reversa que visa planejar o transporte de produtos aos

clientes, bem como o retorno de produtos utilizados por esses para depósitos especializados. Os autores

utilizaram uma abordagem metaheurística, que introduz um algoritmo de memória adaptativa que guarda

e combina características promissoras da solução para gerar soluções de alta qualidade, conduzindo a

busca para diversas regiões do espaço de soluções. A metaheurística proposta foi testada para instâncias

entre 50 e 400 clientes e foram obtidas soluções de alta qualidade com um esforço computacional

limitado.

O PDPTW é um problema do tipo NP-hard, por se tratar de um caso particular do problema do caixeiro

viajante (ROPKE E PISINGER, 2006). Ele conta com um conjunto de restrições tanto de ordem legal

quanto da operação da empresa, o que o torna de grande complexidade. A necessidade de resolver

problemas reais desta natureza, que na maioria das vezes tem grandes dimensões, em um tempo

computacional razoável, ressalta a importância da utilização de métodos heurísticos eficientes.

Este trabalho está dividido da seguinte maneira: nesta seção o problema é introduzido e as principais

abordagens da literatura para a resolução do mesmo são apresentadas. Na seção 2, apresenta-se a

descrição do problema. Em seguida, na seção 3, é apresentada a metaheurística ILS combinada com a

técnica de busca ALNS que foi utilizada para resolver o problema. Os experimentos computacionais são

descritos na seção 4 e, finalmente, na seção 5, são apresentadas as conclusões do trabalho.

2 Descrição do Problema

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 em um depósito. O

problema considera janelas de tempo, que são os prazos para o início da coleta e entrega e ainda para o

veículo sair e retornar para o depósito. O objetivo é construir rotas válidas, que satisfaçam os pedidos de

coletar produtos/pessoas em um ponto e entregá-los em outro ponto, satisfazendo as restrições de

capacidade dos veículos, janelas de tempo, acoplamento e precedência dos pedidos.

O PDPTW é inicializado com um conjunto de pedidos e um número de veículos com capacidades iguais.

Cada pedido é constituído por dois clientes, um de “coleta” e outro de “entrega” de uma quantidade de

mercadoria dita “demanda”. Duas janelas de tempo são dadas para cada pedido: uma para a coleta da

mercadoria e outra para a sua entrega. 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. Quando algum pedido não puder ser atendido por nenhum

veículo, ele é colocado no banco de pedidos e, por exemplo, veículos extras são contratados para atendê-

lo (ROPKE E PISINGER, 2006). 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.

A Função Objetivo deste trabalho, que é referenciada no texto como custo, busca minimizar a soma

ponderada por ∝, � e �, da distância total percorrida, do tempo total gasto pelos veículos e do número de

pedidos no banco de pedidos, respectivamente. Para maiores detalhes sobre o modelo matemático para o

problema os autores recomendam a leitura do trabalho de Ropke e Pisinger (2006).

3. Iterated Local Search aplicada ao PDPTW

Conforme Lourenço et al.(2003), 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.

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;

Algoritmo 1 - Pseudocódigo da metaheurística ILS

Fonte: Adaptado de Lourenço et al.(2003)

Em linhas gerais, o Algoritmo 1 mostra que a ILS parte de 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 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 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. 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 seja mais curto. Após definido o primeiro pedido da rota, o

método seleciona os próximos pedidos baseado do critério de minimização da distância total percorrida.

Para calcular a distância da 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 é criada e o procedimento

é repetido. O método continua até que todos os pedidos tenham sido inseridos em alguma rota.

3.2 Perturbação

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 uma rota é criada para alocar o pedido.

O nível de perturbação, definido empiricamente, 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.3 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.

Ambos são descritos a seguir.

3.3.1 Heurística de 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 da solução e a heurística de Inserção Gulosa (subseção

3.3.2.2) tenta reinseri-los 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.

3.3.2 Adaptive Large Neighborhood Search

A heurística ALNS foi proposta por Ropke e Pisinger (2006) e é 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. 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 de remoção ou a de inserção que gerou o sucesso. A pontuação é aumentada em: σ1

quando a última operação resulta em uma solução melhor do que a melhor solução atual, σ2 quando

resulta em uma solução que não foi visitada anteriormente e que é melhor do que a solução atual, e σ3

quando resulta em uma solução ainda não visitada, que é pior que a 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 como segue: ��,� =����1 − �� + � ��

�� . Onde πi é a pontuação da heurística i obtida durante o último segmento e θi é o

número de vezes que foi usada a heurística i durante o último segmento. O fator reação r controla a

influência da pontuação e 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 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ísticas 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 �−� max�,� ∈����,��, � max�,� ∈����,��� e calcula o custo modificado

� = max!0 , � + �#í�%&. Onde, η controla a quantidade de ruído que é adicionada e max�,� ∈����,�� é 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 pela mesma e um ruído positivo, aumenta o custo da

posição tornando-a mais improvável de ser aceita. Esta heurística seguida pela heurística de minimização

de veículos constitui a Busca Local 2, utilizada na ILS.

3.3.2.1 Heurísticas Destrutivas

Foram implementadas três heurísticas destrutivas propostas por Ropke e Pisinger (2006): 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 idéia de que fica

razoavelmente fácil embaralhar esses pedidos e, assim, criar soluções melhores. A similaridade entre dois

pedidos é dada pela soma ponderada por ', χ, ψ, ω, da distância entre os pedidos, da conexão temporal

(dada pela soma dos módulos das diferenças entre os horários das coletas e entre os horários de entrega),

da demanda e do número de veículos que são capazes de servir os dois pedidos, respectivamente. Quanto

menor for este somatório, mais relacionados são os dois pedidos. A seleção do pedido segue um grau de

aleatoriedade dado pelo parâmetro p. 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 inseridos, ou reinseridos na solução.

3.3.2.2 Heurísticas Construtivas

Todas duas heurísticas de inserção recebem as rotas após a remoção e os 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 o insere na rota

cuja diferença do custo entre inserir na melhor rota e nas k - 1 melhores rotas for maior. O pedido é

inserido 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.

3.4 Critério de Aceitação e de Parada

O critério de aceitação utilizado foi de soluções correntes até 1% piores 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 Experimentos Computacionais

Para testar a metaheurística ILS utilizou-se os 56 dados 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 distribuidas 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. 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.

Para cada problema, foram realizadas 10 execuções. Em cada Busca Local 2 foram executados 5

segmentos da heurística ALNS. Os parâmetros da heurística ALNS utilizados foram os sugeridos por

Ropke e Pisinger (2006), quais sejam, (', χ, ψ, ω, p, ppior, σ1, σ2, σ3, r, η) = (9, 3, 2, 5, 6, 3, 33, 9, 13, 0.1,

0.025). Os parâmetros da função objetivo foram considerados como (∝, �, �) = (1,1,1000), evitando

assim que pedidos fossem colocados no banco de pedidos. O número de pedidos q removidos em cada

iteração ALNS é gerado aleatoriamente no intervalo 4 ≤ * ≤ �0,4 ∗ ,%,-._01�2�%3).

Tabela 1 - Resultados da metaheurística ILS

Resultados ILS

Diferença para

Melhor Resultado Resultados ILS

Diferença para

Melhor Resultado

Problema Veículos Distância

(%)

Veículos Distância

(%)

Problema Veículos Distância

(%)

Veículos Distância

(%)

lc101 10 828,94 0 0,00 lr112 9 1003,77 0 0,00

lc102 10 828,94 0 0,00 lr201 4 1334,01 0 6,45

lc103 10 828,06 1 -20,02 lr202 3 1253,67 0 4,68

lc104 10 844,18 1 -1,84 lr203 3 1006,43 0 6,01

lc105 10 828,94 0 0,00 lr204 2 870,44 0 2,52

lc106 10 828,94 0 0,00 lr205 3 1074,68 0 1,96

lc107 10 828,94 0 0,00 lr206 3 990,78 0 6,35

lc108 10 826,44 0 0,00 lr207 2 906,19 0 0,35

lc109 10 828,94 1 -17,16 lr208 2 765,94 0 4,23

lc201 3 591,56 0 0,00 lr209 3 944,50 0 1,50

lc202 3 591,56 0 0,00 lr210 3 1085,17 0 12,54

lc203 3 591,17 0 0,96 lr211 3 945,16 1 3,69

lc204 3 591,17 0 0,10 lrc101 14 1709,14 0 0,02

lc205 3 588,88 0 0,00 lrc102 12 1585,79 0 1,78

lc206 3 588,49 0 0,00 lrc103 11 1278,84 0 1,60

lc207 3 588,32 0 0,01 lrc104 10 1154,76 0 2,34

lc208 3 595,99 0 1,30 lrc105 13 1640,59 0 0,18

lr101 19 1667,68 0 1,02 lrc106 11 1424,73 0 0,00

lr102 17 1494,29 0 0,45 lrc107 11 1233,59 0 0,28

lr103 13 1297,07 0 0,34 lrc108 10 1154,70 0 0,63

lr104 9 1015,43 0 0,20 lrc201 4 1406,94 0 0,00

lr105 14 1382,15 0 0,37 lrc202 3 1380,34 0 0,44

lr106 12 1254,92 0 0,18 lrc203 3 1258,84 0 15,59

lr107 10 1111,31 0 0,00 lrc204 3 1037,34 0 26,71

lr108 9 980,76 0 1,22 lrc205 4 1351,50 0 3,79

lr109 11 1208,96 0 0,00 lrc206 3 1159,03 0 0,00

lr110 11 1172,83 1 1,16 lrc207 3 1070,41 0 0,79

lr111 10 1109,40 0 0,05 lrc208 3 900,47 0 5,59

Fonte: Elaborado pelos autores

A Tabela 1 apresenta os melhores resultados obtidos para os 56 problemas. Observa-se que a

metaheurística foi capaz de encontrar, para 73% dos casos, resultados iguais ou até 2% além da distância

em relação aos melhores resultados registrados no SINTEF. Para 17,9% dos problemas, a distância variou

em até 7%. E para 3,6% dos problemas a variação da distância foi superior a 12,5%. Apenas para 5

problemas o número de veículos utilizados foi superior aos melhores resultados mas essa diferença foi de

uma unidade. Para dois destes cinco problemas (lc103 e lc109) o número de veículos foi superior ao da

literatura, porém a distância total percorrida foi, em média, 18,6% menor do a melhor distância conhecida

na literatura. Uma comparação em termos de tempos computacionais não foi realizada porque os

resultados da literatura foram obtidos em máquinas distintas.

5 Conclusões

A metaheurística Iterated Local Search combinada com a busca local de grande porte Adaptive Large

Neighborhood Search mostrou-se eficiente para resolver o PDPTW. Para a maioria dos problemas

testados, o método foi capaz de encontrar resultados iguais ou muito próximos aos melhores resultados

registrados na literatura, em um tempo computacional reduzido. Em muitos casos os melhores resultados

conhecidos podem ser os ótimos o que impossibilita a sua melhoria por qualquer metaheurística. Em dois

casos, lc103 e lc109, foi possível reduzir a distância percorrida em aproximadamente 20% da menor

distância conhecida na literatura, ao custo do acréscimo de um veículo. Em termos práticos esta solução

pode ser muito interessante uma vez que uma redução desta magnitude nos custos variáveis justifica

perfeitamente o acréscimo de um veículo nos custos fixos.

Este estudo possibilita ainda a combinação da ALNS com outras metaheurísticas como, por exemplo, o

Variable Neighborhood Search. Pode-se ainda abordar problemas correlatos com a combinação proposta.

Agradecimentos

Os autores agradecem à FAPEMIG, ao CNPq e à UFOP pelo apoio recebido para este trabalho.

Referências

1. Dumas, Y.; Desrosiers, J.; Soumis, F. The pickup and delivery problem with time windows. European. Journal

of Operations Research, v. 54. p. 7–22. 1991.

2. Li, H.; Lim, A. A metaheuristic for the pickup and delivery problem with time windows. ICTAI-2001, 13th

IEEE Conf. Tools Artificial Intelligence, p. 160-170, Dallas, 2001.

3. Li, H.; Lim, A.; Rodrigues, B. Solving the pickup and delivery problem with time windows using “squeaky

wheel” optimization with local search. Technical Report 2002, Singapore Management University, 2002.

4. Lourenço, H. R.; Martin, O. C.; Stutzle, T. Iterated local search. In: Hand-book of Metaheuristics, F. Glover and

G. Kochenberger, Eds. Kluwer Academic Publishers, Boston, 2003.

5. Nanry, W. P.; Barnes, J. W. Solving the pickup and delivery problem with time windows using reactive tabu

search. Transportation Res. Part B, v. 34, p. 107–121, 2000.

6. Ropke, S.; Pisinger, D. An adaptive large neighborhood search heuristic for the pickup and delivery problem

with time windows. Transportation Science, v. 40, p. 455–472, 2006.

7. Shaw, P. A new local search algorithm providing high quality solutions to vehicle routing problems. Technical

Report, Department of Computer Science, University of Strathclyde, Scotland, 1997.

8. Shaw, P. Using constraint programming and local search methods to solve vehicle routing problems. Proc. CP-

98 Fourth Internat. Conf. Principles Practice Constraint Programming, 1998.

9. SINTEF. Vehicle routing and travelling salesperson problems. Disponível em

(www.sintef.no/Projectweb/TOP/PDPTW/Li--Lim-benchmark/100-customers/, 4, 2013.

10. Solomon, M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints.

Operations Research, v. 35, p. 254–265, 1987.

11. Zachariadis, E. E.; Christos D. Tarantilis, C. D. e Kiranoudis, C. T. 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, 2010.