ALGORITMOS PARA OS PROBLEMAS DE ROTEIRIZAÇÃO ESTÁTICA E

DINÂMICA DE VEÍCULOS COM JANELAS DE TEMPO

Orivalde Soares da Silva Júnior

José Eugenio Leal Departamento de Engenharia Industrial - PUC-Rio

RESUMO

Neste trabalho são propostos diversos algoritmos para resolver as versões estática e dinâmica de roteirização de

veículos com janelas de tempo. Estes problemas têm como objetivo determinar rotas de custo mínimo para uma

frota homogênea, atendendo a demanda de um conjunto de clientes dentro de intervalos de tempo, chamados de

janelas de tempos. Além disto, na versão dinâmica no problema, novos clientes podem ser atendidos durante a

execução das rotas pelos veículos. Para a versão estática do problema propôs-se um algoritmo híbrido utilizando

otimização por colônias de formigas e o método de descida em vizinhança variável aleatória. Para a versão

dinâmica do problema foram propostos seis algoritmos, baseados em métodos de inserção, de otimização por

colônia de formigas e das versões sequencial e aleatória do método de busca em vizinhança variável. Os

resultados computacionais mostram que a maior parte dos algoritmos propostos é competitiva com os algoritmos

propostos na literatura.

ABSTRACT

This paper proposes several algorithms to solve the static and dynamic versions of the vehicle routing problem

with time windows. These problems involve determining minimum cost routes for a homogeneous fleet in order

to meet the demand of a set of customers within specified time intervals popularly called time windows. In

addition, in the dynamic version of the problem, new customers can be assigned to vehicles during the execution

of the routes. For the static version it was proposed a hybrid algorithm using ant colony optimization and the

random variable neighborhood search method. For the dynamic version it was proposed six algorithms, based on

an insertion procedure, ant colony optimization and random and sequential versions of variable neighborhood

search methods. Computational results show that most of the proposed algorithms are competitive regarding the

state of the art.

1. INTRODUÇÃO

O investimento em pesquisas que visam a proposição de novos algoritmos para a resolução de

problemas de roteirização é relevante tanto sob o ponto de vista teórico quando o ponto de

vista prático. Quanto ao ponto de vista teórico, a otimização do problema de roteirização e

suas variantes, pertencem à classe NP-Difícil (Lenstra e Rinnooy Kan, 1981). Desta forma, a

resolução eficiente destes problemas corresponde a um desafio para os pesquisadores, que

precisam desenvolver métodos para obter soluções de boa qualidade no menor tempo

computacional possível. Para tanto, a maioria dos pesquisadores optam pelo desenvolvimento

de heurísticas e meta-heurísticas. No ponto de vista prático, os custos relacionados ao

transporte de pessoas e mercadorias geralmente são elevados e absorvem, em média, a

porcentagem mais elevada de custos do que qualquer outra atividade logística (Ballou, 2006).

Visando a redução destes custos, as empresas procuram ser cada vez mais competitivas no

mercado, buscando por soluções de apoio à decisão às atividades logísticas que atendam as

suas características reais de planejamento. Uma destas características é a possibilidade de

atender novas requisições, ou seja, que são recebidas em tempo real. Neste ambiente, os

gerenciadores da frota frequentemente precisam reconfigurar as rotas dos veículos em tempo

real para melhorar a eficiência e aumentar a qualidade do serviço com o atendimento de novas

requisições. Com os avanços em tecnologias de informação, tornou-se possível o

gerenciamento de frota em tempo real.

Atualmente, muitas empresas possuem sistemas de rastreamento e monitoramento de

veículos, sistemas de comunicação com motoristas, informações sobre o trânsito e sobre o

clima e outras informações obtidas em tempo real. Porém, em geral não possuem softwares de

roteirização que permitam utilizar estas informações para realização de alterações nas rotas

em tempo real.

O presente trabalho realiza o estudo, implementação e avaliação de algoritmos de otimização

(heurísticas e meta-heurísticas) visando à solução do Problema de Roteirização de Veículos

com Janelas de Tempo (Vehicle Routing Problem with Time Windows – VRPTW) e do

Problema de Roteirização Dinâmica de Veículos com Janelas de Tempo (Dynamic Vehicle

Routing Problem with Time Windows – DVRPTW).

O artigo está organizado da seguinte forma: a seção 2 apresenta a definição do VRPTW e do

DVRPTW. Na seção 3, apresenta-se a revisão bibliográfica destes problemas e os métodos já

propostos para resolvê-los. Na seção 4, apresentam-se seis algoritmos propostos para resolver

o VRPTW e o DVRPTW. Na seção 5 são apresentados os resultados computacionais. Por fim,

na seção 6 são apresentadas as conclusões e as contribuições do artigo ao estado da arte.

2. DEFINIÇÕES DOS PROBLEMAS

O VRPTW pode ser descrito por um grafo G(N,A), onde N é um conjunto contendo todos os

nós, e A é um conjunto contendo todos os arcos. Os nós representam os clientes e o depósito,

os quais são representados através dos índices i ou j. O depósito, de onde partem as rotas,

usualmente é representado pelo nó com índice 0. Os arcos representam os caminhos que ligam

estes nós e são acessados através do par ordenado i-j. Considera-se o grafo como sendo

completo, ou seja, existe um arco ij entre todos os nós i e j para ij. Cada arco ij possui um

custo cij associado, que para o Problema do Caixeiro Viajante (Travelling Salesman Problem

– TSP), usualmente representa a distância de cada arco. No caso do VRPTW, este custo

também pode representar o tempo necessário para se percorrer cada arco tij, onde tij=cij.

No depósito, existem V veículos homogêneos à disposição, todos com a mesma capacidade K.

Cada cliente i possui uma demanda di≥0 associada, bem como um tempo de serviço si. Além

disso, cada cliente possui também sua janela de tempo; esta janela é dada por [ai, bi], sendo

que ai representa o instante mais cedo para início do atendimento e bi o instante mais tarde

para início do atendimento. O depósito possui demanda e tempo de serviço iguais a zero e

janela de tempo com a0 igual a zero e b0 igual a um valor que indique o horário de fechamento

do depósito. A janela de tempo do depósito é chamada de jornada de trabalho JT.

O objetivo do problema é encontrar rotas de distância total mínima que atendam todos os

clientes, respeitando as restrições de capacidade dos veículos e das janelas de tempo. Além

disso, deseja-se encontrar o número mínimo de veículos necessários para a realização da

tarefa. Na literatura, diversos autores, principalmente aqueles que propõem métodos exatos,

priorizam a minimização da distância total. No entanto, a maioria dos autores hierarquiza os

objetivos de forma que a minimização do número de veículos (NV) é mais importante que a

distância total (DT). Esta hierarquização sugere uma maior aproximação com a realidade, pois

o custo fixo de se alocar um veículo geralmente é bem maior que o custo operacional do

percurso.

No contexto da taxonomia proposta por Psaraftis (1995) e adaptada por Pillac et al. (2013), o

DVRPTW abordado neste trabalho trata problemas que são dinâmicos e determinísticos. Não

são aceitas interrupções do destino atual dos veículos (não-preemptivo) (Gendreau et al.,

1999). Novos veículos podem ser inseridos na solução, deste que estejam disponíveis no

depósito. A restrição que obriga que todos os clientes sejam visitados é relaxada, podendo

existir soluções factíveis com clientes não atendidos. A cada cliente i {1, 2,..., N} são

associados os parâmetros: momento que o cliente é conhecido tai ≥0; estado do cliente ei

{planejado, atribuído, em_trânsito, entregue}. O problema passa a ter um terceiro objetivo,

que é a minimização do número de clientes não atendidos. Os objetivos passam a ser:

minimizar o número de clientes não atendidos (NA), minimizar o número de veículos (NV) e

minimizar a distância total (DT).

3. REVISÃO DA LITERATURA

O VRPTW é um problema clássico que tem sido intensivamente estudado na literatura e

diversos métodos exatos e aproximados têm sido propostos. O trabalho precursor foi

desenvolvido por Solomon (1987), no qual foram estudadas diversas heurísticas e foram

propostas 56 instâncias do problema com 100 clientes, as quais são utilizadas até hoje como

base para avaliação do desempenho dos algoritmos propostos para o VRPTW. Apesar de

serem instâncias relativamente pequenas, é importante ressaltar que apenas no ano de 2012 é

que foram descobertas as soluções ótimas para as 56 instâncias (Ropke, 2013) e (Roberti,

2012). Estas soluções foram obtidas por métodos exatos visando apenas minimizar a distância

total das rotas. Sendo assim, ainda existe uma lacuna para descoberta de novas soluções

considerando como primeiro objetivo a minimização do número de veículos. Outras

instâncias que ainda podem ser exploradas são as instâncias de Homberger e Gehring (1999)

que são extensões das instâncias de Solomon (1987) com 200, 400, 800 e 1000 clientes.

Quanto à versão dinâmica do problema de roteirização, o trabalho precursor é do Psaraftis

(1980), com o desenvolvimento de uma abordagem de programação dinâmica para o

problema de coletas e entregas com janelas de tempo, mais conhecido como Dial-a-Ride-

Problem (DARP) que consiste na procura por uma solução ótima cada vez que um novo

cliente dinâmico é conhecido. O autor também apresenta diversas diferenças entre os

problemas estático e dinâmico (Psaraftis, 1988 e 1995).

Pillac et al. (2013) realizou uma extensa revisão sobre os problemas de roteirização dinâmica.

O autor também propôs uma taxonomia baseando-se nos conceitos de evolução e qualidade da

informação (Psaraftis, 1995), a qual classifica os problemas de roteirização em:

Problemas estáticos e determinísticos: todas as entradas são conhecidas antecipadamente e

as rotas dos veículos não mudam uma vez que estão sendo executadas.

Problemas estáticos e estocásticos: são caracterizados pela entrada parcialmente conhecida

como variáveis aleatórias, as quais seguem, geralmente, uma distribuição de Poisson.

Problemas dinâmicos e determinísticos: também é chamada por outros autores como

roteirização online ou real time (Ichoua et al., 2000). O suporte de tecnologias de

comunicação em tempo real é essencial para comunicação entre os veículos e o tomador de

decisões. Parte ou o total das entradas é desconhecida e é revelada dinamicamente ao longo

do tempo, durante a execução das rotas (Psaraftis, 1995).

Problemas dinâmicos e estocásticos: todas ou parte das entradas são desconhecidas e

reveladas dinamicamente durante a execução das rotas, mas neste caso, a informação

estocástica é disponibilizada dinamicamente.

3.1. Classificação do DVRPTW abordado

O DVRPTW abordado neste trabalho é classificado como um problema dinâmico e

determinístico. Uma abordagem bastante utilizada para resolver este problema é a divisão em

em duas fases: a-priori e a-posteriori. Na fase a-priori, são obtidas rotas para as entradas já

conhecidas e o problema pode ser resolvido com um método de roteirização estática. Na fase

de a-posteriori as rotas são obtidas diversas vezes no decorrer do horizonte de planejamento,

através da re-otimização das rotas, a qual pode ser realizada de modo contínuo ou periódico.

3.1.1. Re-otimização contínua

A re-otimização contínua consiste na otimização ao longo do dia de forma contínua, ou seja,

sempre que forem realizadas alterações nos dados disponíveis, o método de roteirização

obtém imediatamente uma nova solução atual. Nesta abordagem podem ser utilizados os

métodos de re-roteirização ou métodos de operações locais rápidas.

Yang et al. (2004) abordaram o problema de roteirização com coleta e entrega, onde os

pedidos de serviço ponto-a-ponto de transporte chegam de forma dinâmica. Os autores

propõem um algoritmo denominado MYOPT, que é uma abordagem de horizonte rolante com

base em programação linear, que é resolvido sempre que um novo cliente dinâmico é

conhecido.

Lackner (2004) desenvolveu quatro métodos meta-heurísticos. O primeiro e o segundo,

denominados ES1-DVRPTW e ES2-DVRPTW, baseiam-se em Algoritmos Genéticos. O

terceiro, denominado MACS-DVRPTW, baseia-se em Otimização por Colônia de Formigas,

no algoritmo MACS-VRPTW (Gambardella et al., 1999). O quarto, denominado AS-

DVRPTW, baseia-se em Recozimento Simulado (Simulated Annealing). Para comparação dos

resultados, o autor propôs extensões para as 56 instâncias de Solomon (1987) para cinco

diferentes graus de dinamismo, totalizando 280 instâncias. O autor conclui que o método que

apresentou os melhores resultados foi o ES1-DVRPTW, seguido pelo MACS-DVRPTW,

ES2-DVRPTW e AS-DVRPTW.

Hong (2012) desenvolveu um método baseado na Busca em Vizinhança Larga (Large

Neighborhood Search - LNS) proposto por Shaw (1998) e aplicou ao DVRPTW. Este método

trabalha através da destruição (removendo nós) e reparação (inserindo nós) da solução atual,

utilizando operadores de destruir e reparar. A vizinhança é chamada de larga, pois um nó que

é removido pode ser reinserido na mesma rota de origem ou em qualquer outra rota da

solução atual. Além deste processo, são aplicadas buscas locais com diversas vizinhanças. O

autor comparou os resultados com os trabalhos de Lackner (2004) e Yang et al. (2004) e

concluiu que o método proposto apresenta melhores resultados e com menor esforço

computacional.

Pillac et al. (2012) desenvolveu uma versão paralela do ALNS (Adaptive Large

Neighborhood Search), denominada pALNS, que é uma versão adaptativa do LNS proposta

por Pisinger e Ropke (2007). O ALNS adiciona uma camada adaptativa, que seleciona

aleatoriamente os operadores de destruição e remoção dependendo de seu desempenho

passado, ajustando o algoritmo automaticamente para a instância. Os autores compararam os

resultados com os trabalhos de Lackner (2004) e Hong (2012) e concluíram que o pALNS é

capaz de alcançar o estado da arte e traz melhorias de até 12%.

3.1.2. Re-otimização periódica

A re-otimização periódica consiste na otimização ao longo do dia de forma periódica. Este

tempo entre aplicações do método de roteirização pode ser representado por um intervalo de

tempo fixo, também conhecido como épocas de decisão (Chen e Xu, 2006) ou fatias de tempo

(Kilby et al., 1998 e Montemanni et al., 2002).

A vantagem da re-otimização periódica é que ela não requer a execução do método de

roteirização toda vez que algum dado do problema for atualizado. A principal desvantagem é

que o atraso na tomada de uma decisão pode acarretar no aumento da distância total das rotas,

no número de veículos ou na inviabilidade ou atraso de atendimento de um ou mais clientes,

em particular, quando na presença de janelas de tempo.

Seguindo a mesma linha de programação linear, Chen e Xu (2006) desenvolveram um

algoritmo de geração dinâmica de colunas (DYCOL) para o DVRPTW. Os autores propõem o

conceito de épocas de decisão ao longo do horizonte de planejamento, que são as datas em

que o processo de otimização é executado. A novidade de sua abordagem se baseia em na

geração de colunas dinamicamente para um modelo de particionamento de conjuntos, usando

colunas da época de decisão anterior, o que reduziu muito o tempo computacional.

Montemanni et al. (2002) desenvolveram um Sistema de Colônia de Formigas (ACS) para

resolver o DVRP. Semelhante a Kilby et al. (1998), sua abordagem utiliza fatias de tempo, ou

seja, o dia é dividido em períodos de igual duração. Com o decorrer do tempo, novos pedidos

são acumulados. No fim da fatia de tempo é realizada a otimização das rotas utilizando o

método de roteirização estática. Uma característica interessante da sua abordagem é o uso de

uma estratégia que realiza a transmissão dos feromônios da otimização de uma fatia de tempo

para a fatia de tempo seguinte. Uma abordagem semelhante foi também utilizada por Rizzoli

et al. (2007), Gambardella et al. (2003) e Silva Júnior e Leal (2009).

3.1.3. Classificação dos métodos para problemas dinâmicos e determinísticos

Além dos modos contínuo e periódico de re-otimização, uma escolha importante é o tipo de

método a ser utilizado para resolver a fase a-posteriori dos problemas dinâmicos e

determinísticos de roteirização, que podem ser classificados em métodos de re-roteirização e

métodos inserção, também conhecidos como métodos de operações locais rápidas.

3.1.3.1. Métodos de Re-roteirização

Nos métodos de re-roteirização as soluções são construídas, destruídas e reconstruídas várias

vezes. Na fase a-priori, uma solução é construída com objetivo de atender todos os clientes.

Com o avanço do tempo, os clientes são atendidos ou comprometidos (possui um veículo

viajando em sua direção) e surgem novos clientes dinâmicos. Na fase a-posteriori, todos os

clientes que não foram atendidos ou comprometidos são removidos da solução (destruição) e

a solução é reconstruída. Na reconstrução, cada rota deve iniciar a partir do depósito ou a

partir do último cliente atendido ou comprometido. Se o método de roteirização utilizado

possuir uma memória das soluções já criadas, esta informação pode ser utilizada de forma a

reduzir o tempo computacional.

Um exemplo desta aplicação é proposto por Taillard et al. (2001), o qual se utiliza de uma

memória adaptativa sobre as boas soluções. Esta memória auxilia na redução do tempo

computacional necessário para obter uma nova solução. No entanto, a implementação deste

método se torna mais complexa. Esta abordagem foi utilizada por Gendreau et al. (1999) para

adaptação da versão paralela do método Busca Tabu (Taillard et al., 1997) para resolver o

DVRPTW aplicado a serviços de expressos de correios. Sua abordagem mantém um conjunto

de boas rotas numa memória adaptativa que é utilizada para gerar soluções iniciais para a

Busca Tabu. Sempre que um novo cliente é conhecido, verifica-se uma possível inserção em

todas as soluções da memória adaptativa para decidir se deve ser aceito ou rejeitado.

3.1.3.2. Métodos de Inserção

Estes métodos se utilizam dos métodos de inserção adaptados para resolverem a fase a-

posteriori do problema. A solução é construída a partir de inserções consecutivas de clientes

dinâmicos na solução atual (encontrada na fase a-priori) à medida que são solicitadas. São

realizadas tentativas de inserção entre todos os possíveis pares de nós e a solução escolhida

será aquela que não viola as restrições do problema e que possui o menor custo. Uma restrição

adicional do problema no caso dinâmico é a proibição de inserções entre clientes já

comprometidos ou atendidos.

4. ALGORITMOS PROPOSTOS

As estratégias e algoritmos utilizados como base para desenvolvimento dos algoritmos

propostos para o VRPTW e DVRPTW são descritos a seguir:

Vizinho Mais Próximo (NN) foi abordado no trabalho de Solomon (1987).

Push Forward Insertion Heuristic (PFIH) foi detalhada por Thangiah et al. (1994) e

proposta por Solomon (1987).

MACS-VRPTW foi proposto por Gambardella et al., (1999) e utiliza-se de duas colônias

de formigas, uma denominada ACS-VEI que busca minimizar o número de veículos e

outra denominada ACS-TIME que busca minimizar o tempo total (ou distância) das rotas.

Descida em Vizinhança Variável Aleatória (Random Variable Neighborhood Descent -

RVND) proposto por Subramanian (2012), utilizando-se de sete estruturas de vizinhança

inter-rota, Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0) e Shift(2,0), e cinco estruturas intra-

rota, Or-Opt1, Or-Opt2, Or-Opt3, 2-opt, Exchange e K-Opt.

Descida em Vizinhança Variável (Variable Neighborhood Descent - VND) proposto por

Mladenović e Hansen (1997), com as mesmas estruturas de vizinhança do RVND.

ECF - Estratégia de Conservação dos Feromônios entre as fases da roteirização dinâmica,

proposta por Guntsch e Middendorf (2001).

RP - Roteirização Periódica proposta por Kilby et al. (1998) e Montemanni et al. (2002).

4.1. O algoritmo proposto para o VRPTW

O primeiro algoritmo proposto para o VRPTW, denominado MACS-RVND é um algoritmo

híbrido que consiste numa extensão melhorada do MACS-VRPTW. As modificações

propostas são descritas em Silva Júnior e Leal (2012).

4.2. Os algoritmos propostos para o DVRPTW

A metodologia aplicada consiste na solução de uma sequência de n problemas estáticos e

determinísticos PEn com várias soluções sn durante a jornada de trabalho tempo_total = bn+1.O

tamanho de n depende da abordagem utilizada na fase a-posteriori. Na re-otimização

contínua, n será igual ao número de novos clientes. Já na re-otimização periódica, n será igual

ao número de faixas de tempo nts de tamanhos iguais f. Este é um processo iterativo, que

evolui em função do tempo e novas entradas devem ser inseridas no procedimento durante sua

execução. Para flexibilizar o uso destas abordagens, propôs-se o Algoritmo 1 (DVRPTW).

Algoritmo 1: DVRPTW 1: Procedimento DVRPTW(estratégia, tipo_método)

2: tempo ← 0 n ← 0

3: PEn ← {depósito e clientes conhecidos, com tai <=tempo}

4: // Obter uma solução inicial utilizando um método de roteirização estática para o VRPTW

5: sn ← obter_solução_inicial(N)

6: Para tempo = 1... tempo_total faça

7: D ← D {novos clientes com tai =tempo}

8: Se D ≠ {} então

9: Se estratégia = contínua OU (estratégia = periódica E tempo MOD f = 0)

10: n ← n + 1

11: PEn ← PEn-1 D

12: D ← {}

13: Se tipo_método = inserção então

14: s’ ← sn-1

15: Senão Se tipo_método = re-roteirização então

16: // Remover de s os clientes com ei {em_trânsito, entregue, atribuído}

17: s’ ← extrair_solução_parcial(sn-1)

18: Fim se

19: // Obter uma solução utilizando um método de roteirização estática adaptado

20: sn ← obter_solução_intermediaria(s’, PEn)

21: Fim se

22: Fim se 23: // Atualizar os estados dos clientes

24: Para r1 = 1...V faça

25: // Para todos os clientes i da rota r1

26: Para i=1 até o tamanho de r1 faça

27: inicio_viagemi ← Ti – ti-1,i

28: Se tempo inicio_viagemi E tempo < Ti então

29: ei ← em_trânsito

30: Senão Se tempo Ti E tempo < Ti + si então

31: ei ← entregue

32: Senão Se estratégia = periódica E inicio_viagemi n.f então

33: ei ← atribuído

34: Senão

35: ei ← planejado

36: Fim se

37: Fim para

38: Fim para

39: Retorne s

O Algoritmo 1 é iniciado com uma estratégia de re-otimização contínua ou periódica e com

um tipo_método que pode ser de inserção ou re-roteirização. No problema PE0 são inseridos

o depósito e os clientes já conhecidos e uma solução inicial s0 é obtida utilizando um método

desejado para resolver o VRPTW. Um procedimento iterativo em função do tempo é iniciado

com tempo=1 até o fim da jornada de trabalho (tempo_total). Novos clientes dinâmicos são

conhecidos e inseridos no conjunto D. Se o conjunto D possuir algum cliente, então é

verificada a abordagem da re-otimização, caso contrário são atualizados os estados dos

clientes. Se a abordagem for contínua ou periódica com tempo igual ao início de uma faixa de

tempo, então é incrementado o contador n. Em seguida é criado um novo problema estático

PEn com a união dos nós de PEn-1 e dos nós do conjunto D. Uma solução parcial s’ é criada.

Se o tipo_método for inserção, então é utilizada sn-1 como solução parcial. Caso contrário é

extraída uma solução parcial de sn-1 com apenas os clientes comprometidos, ou seja, aqueles

que possuem o estado em_trânsito, entregue ou atribuído. Uma nova solução intermediária sn

é obtida para o problema estático PEn, utilizando a solução parcial s’ para iniciar as novas

rotas. Se necessário, novos veículos v podem ser alocados para atender o maior número de

clientes possível. A atualização dos estados dos clientes é realizada em todas as rotas da

solução sn. Se o tempo for maior ou igual ao início da viagem do veículo v na rota r1 para o

cliente i e menor que o tempo de chegada Ti, então o estado ei é atualizado para em_trânsito.

Caso contrário, se o tempo for maior ou igual o tempo de chegada Ti e menor que o tempo de

processamento tpi (Ti + si), então o estado ei é atualizado para entregue. Caso contrário, se a

estratégia for de re-otimização periódica e início da viagem em direção ao cliente i for menor

do que o tamanho da faixa de tempo f multiplicado pelo número da faixa n, então o estado ei é

atualizado para atribuído. Caso contrário, o estado ei é atualizado para planejado. Ao fim da

jornada de trabalho, a solução sn será a solução final para o DVRPTW.

Todos os algoritmos propostos se baseiam no Algoritmo 1. A Tabela 1 mostra os nomes e as

respectivas abordagens de re-otimização, classificação dos algoritmos, métodos para obter a

solução inicial e as soluções intermediárias.

Tabela 1 – Algoritmos propostos para o DVRPTW

Nome do Algoritmo Abordagem de

re-otimização Classificação Solução inicial Solução intermediária

PFIH_PFIH Contínua Inserção PFIH PFIH

PFIH_PFIH-VND Contínua Inserção PFIH PFIH + VND

PFIH-VND_PFIH-VND Contínua Inserção PFIH + VND PFIH + VND

MACS-RVND_PFIH-VND Contínua Inserção MACS-RVND PFIH + VND

MACS-RVND_Re-roteiriza Contínua Re-roteirização MACS-RVND MACS-RVND + ECF

MACS-RVND-Periódico Periódica Re-roteirização MACS-RVND MACS-RVND+ECF+RP

5. RESULTADOS COMPUTACIONAIS

O objetivo desta seção é mostrar o desempenho dos algoritmos propostos para o VRPTW e

DVRPTW. Para execução dos algoritmos utilizou-se de um servidor PowerEdge T110 II com

processador Intel Xeon Quad-Core de 3,4 GHz e 8GB de memória RAM, sob plataforma

Linux, com a distribuição do CentOS 6.3 64 bits.

Para aplicação do algoritmo MACS-RVND aos problemas do VRPTW, foram definidos os

parâmetros ρ=0,1, beta=1, q0=0,9 propostos Gambardella et al. (1999). Cada simulação das

funções ACS-TIME e ACS-VEI foi feita com 20 iterações com k=10 formigas cada uma. O

critério de parada foi definido como sendo o tempo máximo de execução de 5 minutos. Os

problemas adotados para a validação dos algoritmos são as 56 instâncias criadas por Solomon

(1987) e os valores das melhores soluções foram obtidos em Sintef (2013).

Tabela 2 – Comparação com resultados do MACS-RVND com o MACS-VRPTW e com o melhor conhecido

Autores R1 R2 C1 C2 RC1 RC2

SNV

SDT

Melhor conhecido

(diversos autores)

11,92 2,73 10,00 3,00 11,50 3,25 405

1.209,89 951,02 828,38 589,86 1.384,16 1.119,17 57.181

MACS-RVND 12,08 2,82 10,00 3,00 11,63 3,25 409

1.212,38 945,06 828,38 589,86 1.381,08 1.120,15 57.128

Gambardella et al., 1999 12,38 3,00 10,00 3,00 11,92 3,33 418

1.210,83 960,31 828,38 591,85 1.388,13 1.149,28 57.583

Na Tabela 2, são apresentados os valores médios por classe de instância e a soma total de

veículos e tempo total das rotas de todas as instâncias, que foram reportados por diversos

autores. O objetivo primário é minimizar o número total de veículos e objetivo secundário é

minimizar a o tempo total de viagem. A primeira coluna mostra as referências dos trabalhos

que reportaram estes resultados. As colunas R1, R2, C1, C2, RC1 e RC2 mostram o número

médio de veículos e o tempo total médio de viagem para os seus respectivos grupos de

instâncias. A coluna SNV/SDT indica o somatório de número de veículos (SNV) e o

somatório do tempo de viagem (SDT) de todas as 56 instâncias. Observa-se que o método

proposto é competitivo com os métodos propostos por diversos autores, incluindo vários

autores que encontraram algumas das melhores soluções conhecidas para o VRPTW.

Observa-se também que o uso do método RVND combinado com o MACS-VRPTW pode

melhorar consideravelmente o método original proposto por Gambardella et al. (1999).

Os algoritmos propostos para resolver o DVRPTW foram testados com as instâncias

propostas por Lackner (2004), que são extensões das instâncias de Solomon (1987) para o

DVRPTW. Estas extensões utilizaram os graus de dinamismo iguais a 10, 30, 50, 70 e 90.

Para cada instância e para cada grau de dinamismo, o autor criou um novo parâmetro que

indica o momento em que o cliente é conhecido (tai), totalizando 280 instâncias. Nas versões

adaptadas dos algoritmos PFIH, VND e MACS-RVND para resolver os problemas da fase a-

posteriori foram utilizados os mesmo valores para os parâmetros dos algoritmos originais. O

parâmetro de conservação de feromônios foi definido como γr=0,3 para os algoritmos MACS-

RVND_Reroteiriza e MACS-RVND_Periódico, conforme Guntsch e Middendorf (2001).

Nos algoritmos PFIH_PFIH, PFIH_PFIH-VND e PFIH-VND_PFIH-VND o tempo de

execução na fase a-priori não ultrapassa de 10 segundos. Na fase a-posteriori, o tempo de

execução não ultrapassa dos 2 segundos. Por serem algoritmos determinísticos, que retornam

sempre a mesma solução, cada um deles foi executado apenas uma vez para cada instância. Já

para os algoritmos MACS-RVND_PFIH-VND, MACS-RVND_Re-roteiriza e MACS-

RVND-Periódico, o critério de parada para a solução da fase a-priori foi definido como o

tempo máximo de execução de 5 minutos. Na fase a-posteriori, cada subproblema é resolvido

com o tempo máximo de execução de 10 segundos. Por serem algoritmos probabilísticos, que

podem retornar diferentes soluções, foram realizadas cinco execuções para cada instância e

foi obtida a melhor solução.

A Tabela 3 apresenta a soma dos totais médios obtidos em cada um dos algoritmos e

considerando os cinco graus de dinamismo. Avaliando os seis algoritmos propostos e

considerando a hierarquia dos objetivos de minimizar o NA, NV e DT, conclui-se que o

algoritmo que apresentou os melhores resultados é o MACS-RVND_Re-roteiriza. Realizou-se

uma comparação deste algoritmo com outras abordagens propostas na literatura.

Tabela 3 – Comparação dos resultados dos algoritmos propostos para o DVRPTW

Nome do Algoritmo NA NV DT

PFIH_PFIH 5,56 327 70.572

PFIH_PFIH-VND 8,08 257 33.654

PFIH-VND_PFIH-VND 6,39 253 33.450

MACS-RVND_PFIH-VND 8,63 251 32.673

MACS-RVND_Re-roteiriza 5,93 252 32.762

MACS-RVND-Periódico 6,25 258 34.777

A Tabela 4 apresenta os melhores resultados obtidos pelo algoritmo MACS-RVND_Re-

roteiriza e pelo estado da arte da literatura para o DVRPTW, que até o presente momento é

composto pelos trabalhos de Lackner (2004), Hong (2012), Pillac et al. (2012). Estes autores

não publicaram a solução obtida para cada uma das 280 instâncias. Foram publicados apenas

os valores médios por classe de instância e grau de dinamismo. Com base nestes valores,

foram comparados os resultados com o algoritmo MACS-RVND_Re-roteiriza. Observa-se o

algoritmo proposto obteve melhores soluções em termos de distância total média do que as

abordagens propostas Lackner (2004) e Hong (2012). Quanto ao percentual total médio de

clientes não atendidos, o algoritmo proposto apresentou melhores resultados do que Pillac et

al., (2012), Hong, (2012) e Lackner, (2004).

Tabela 4 – Comparação dos resultados do MACS-RVND_Re-roteiriza com o estado da arte para o DVRPTW

MACS-RVND_Re-roteiriza Pillac et al., 2012 Hong, 2012 Lackner, 2004

Grupo δ DT NA DT NA DT NA DT NA

C1 10 891,17 0,00

850,60 0,11

895,80 0,22

996,40 0,00

30 919,83 0,00

874,90 0,11

962,10 0,33

1.066,90 0,00

50 958,85 0,00

903,40 0,11

1.001,20 0,22

1.236,10 0,00

70 998,75 0,00

919,10 0,11

1.031,70 0,22

1.261,30 0,00

90 1.012,84 0,00 929,90 0,11 1.039,80 0,22 1.479,60 0,00

C2 10 598,85 0,00

597,20 0,00

594,70 0,00

629,10 0,00

30 605,39 0,00

597,60 0,00

651,40 0,00

632,30 0,04

50 628,88 0,00

604,00 0,00

605,00 0,00

689,30 0,13

70 621,16 0,00

619,20 0,00

636,50 0,00

743,80 0,21

90 637,45 0,00 625,70 0,00 636,80 0,00 792,50 0,29

R1 10 1.276,10 0,18

1.197,40 0,25

1.257,10 0,17

1.278,10 0,47

30 1.273,95 0,27

1.212,90 0,80

1.286,60 0,58

1.337,90 0,72

50 1.299,77 0,64

1.225,00 1,25

1.295,80 0,67

1.330,00 0,78

70 1.318,73 1,00

1.237,30 1,71

1.331,30 1,75

1.336,10 0,94

90 1.349,23 1,09 1.230,10 2,55 1.335,90 2,33 1.278,30 0,75

R2 10 973,98 0,00

893,00 0,00

950,00 0,09

1.052,90 0,03

30 985,30 0,00

915,60 0,00

985,50 0,00

1.085,40 0,15

50 1.021,71 0,00

948,60 0,00

1.016,50 0,00

1.138,80 0,21

70 1.023,12 0,00

967,70 0,00

1.032,00 0,09

1.116,90 0,30

90 1.021,69 0,00 981,70 0,00 1.047,80 0,09 1.193,30 0,52

RC1 10 1.438,97 0,25

1.389,40 0,04

1.436,20 1,13

1.426,90 0,46

30 1.480,79 0,25

1.421,50 0,28

1.492,20 1,13

1.439,70 0,42

50 1.511,98 0,50

1.463,40 0,23

1.514,70 1,38

1.448,10 0,46

70 1.507,05 0,63

1.470,10 0,58

1.511,30 1,88

1.488,40 0,58

90 1.555,77 1,13 1.495,50 0,51 1.513,90 2,00 1.475,20 0,42

RC2 10 1.122,49 0,00

1.024,40 0,00

1.103,30 0,00

1.220,90 0,00

30 1.151,20 0,00

1.053,10 0,00

1.166,00 0,25

1.244,90 0,04

50 1.170,26 0,00

1.060,50 0,00

1.190,50 0,13

1.244,90 0,00

70 1.194,84 0,00

1.091,40 0,00

1.239,50 0,00

1.269,30 0,00

90 1.212,11 0,00 1.130,30 0,00 1.257,20 0,13 1.346,80 0,13

TM 32.762,21 5,93 30.930,50 8,75 33.018,30 15,01 35.280,10 8,05

GAP (%) 5,92 -32,21 -0,78 -60,48 -7,14 -26,31

6. CONCLUSÕES

O problema de roteirização de veículos possui um papel muito importante no gerenciamento

da frota das empresas e durante décadas, as aplicações práticas estiveram voltadas apenas ao

problema estático. Com os recentes avanços em tecnologias de informação foram

disponibilizadas as ferramentas necessárias para que as empresas gerenciem suas frotas em

tempo real. No entanto, estas novas tecnologias também introduziram mais complexidade na

gestão da frota, revelando a necessidade do desenvolvimento de sistemas de apoio à decisão

para roteirização dinâmica de veículos.

Para resolver o problema de roteirização de veículos com janelas de tempo foi proposto um

algoritmo híbrido do Sistema de Múltiplas Colônias de Formigas (MACS) com o método de

Descida em Vizinhança Variável Aleatória (RVND). O algoritmo foi apresentado em detalhes

e foram mostradas as modificações propostas nos métodos originalmente propostos. Através

da aplicação do algoritmo a 56 instâncias de benchmark de Solomon (1987) demonstrou-se a

eficiência do algoritmo, pois para 29 delas foram encontradas as melhores soluções

conhecidas, para 23 foram encontradas soluções com o menor número de veículos conhecido

e com GAP de distância total de no máximo 0,62% e apenas para 4 instâncias foram

encontradas soluções com 1 veículo a mais, porém com distância total menor que nas

melhores soluções conhecidas, com uma diferença média de -5,21%.

Para resolver o problema de roteirização dinâmica de veículos com janelas de tempo foi

proposto um algoritmo genérico o qual foi utilizado como modelo para proposta de seis novos

algoritmos. Estes algoritmos foram baseados no algoritmo de Inserção (PFIH), no método de

Descida em Vizinhança Variável (VND) e no Sistema de Múltiplas Colônias de Formigas

com Descida em Vizinhança Variável Aleatória (MACS-RVND). Estes algoritmos foram

aplicados a 280 instâncias de benchmark propostas por Lackner (2004) e foi selecionado o

melhor algoritmo, que por sua vez, foi comparado com os melhores resultados apresentados

na literatura. Por se tratar de um problema relativamente novo, a literatura do problema

dinâmico abordado ainda é escassa e os autores não disponibilizam todos os dados necessários

para realizar uma comparação efetiva e não foi possível comparar o número de veículos

utilizados pelos autores. No entanto, a comparação da distância média total e o percentual

médio total de clientes não atendidos demonstrou que o algoritmo proposto fornece soluções

de ótima qualidade, superando os resultados de todas as abordagens propostas na literatura.

Agradecimento

O presente trabalho foi realizado com apoio do CNPq, Conselho Nacional de Desenvolvimento Científico e

Tecnológico - Brasil.

REFERÊNCIAS BIBLIOGRÁFICAS Ballou, R. H. (2006) Gerenciamento da Cadeia de Suprimentos / Logística Empresarial. São Paulo: Bookman.

Chen, Z.; Xu, H. (2006) Dynamic column generation for dynamic vehicle routing with time windows.

Transportation Science, 40(1):74-88.

Gambardella, L. M.; Taillard, É.; Agazzi, G. (1999) MACS-VRPTW: A Multiple Ant Colony System for vehicle

routing problems with time windows. New Ideas in Optimization. Londres: McGraw-Hill. p. 63-76.

Gambardella, L.; Rizzoli, A.; Oliverio, F.; Casagrande, N.; Donati, A.; Montemanni, R.; Lucibello, E. (2003) Ant

colony optimization for vehicle routing in advanced logistics systems. International Workshop on

Modelling and Applied Simulation (MAS 2003). [S.l.]: [s.n.]. p. 3-9.

Gendreau, M.; Guertin, F.; Potvin, J. Y.; Taillard, E. (1999) Parallel tabu search for real-time vehicle routing

and dispatching. Transportation Science, Vol. 33 No 4:381-390.

Guntsch, M.; Middendorf, M. (2001) Pheromone modification strategies for ant algorithms applied to dynamic

TSP. In: al., B. E. Application of evolutionary computing: Proceedings of EcoWorkshops. [S.l.]: [s.n.], v.

Lecture Notes in Computer Science 2037. p. 213-222.

Homberger, J.; Gehring, H. (1999) Two evolutionary metaheuristics for the vehicle routing problem with time

windows. Inform. Systems Oper. Res, 37:297-318.

Hong, L. (2012) An improved LNS algorithm for real-time vehicle routing problem with time windows.

Computers & Operations Research, 39(2):151-163.

Ichoua, S.; Gendreau, M.; Potvin, J. Y. (2000) Diversion issues in real-time vehicle dispatching. Transportation

Science, 34(4):426-438.

Kilby, P.; Prosser, P.; Shaw, P. (1998) Dynamic VRPs: a study of scenarios. Strathclyde, U.K..

Lackner, A. (2004). Dynamische Tourenplanung mit ausgewählten Metaheuristiken, volume 47 of Göttinger

Wirtschaftsinformatik. Cuvillier.

Lenstra, J.; Rinnooy Kan, A. H. G. (1981) Complexity of vehicle routing and scheduling problems. Networks,

11:221-227.

Mladenovic, N.; Hansen, P. (1997) Variable Neighbourhood Search. Computers & Operations Research,

24(11):1097-1100.

Montemanni, R.; Gambardella, L. M.; Rizzoli, A. E.; Donati, A. V. (2002) A new algorithm for a Dynamic

Vehicle Routing Problem based on Ant Colony System. Journal of Combinatorial Optimization, Springer

Netherlands, Vol. 10, No 4:327-343.

Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L. (2013) A review of dynamic vehicle routing problems.

European Journal of Operational Research, 225(1):1-11.

Pillac, V.; Guéret, C.; Medaglia, A. L. (2012) A fast re-optimization approach for dynamic vehicle routing. p. 1-

22 École des Mines de Nantes, Nantes, France.

Psaraftis, H. N. (1980) A Dynamic Programming Solution to the Single-Vehicle Many-to-Many Immediate

Request Dial-a-Ride Problem. Transp. Sci., 14:130–154.

Psaraftis, H. N. (1988) Dynamic vehicle routing problems. In: Assad, B. L. G. A. A. A. Vehicle Routing:

Methods and Studies. North-Holland: Elsevier. p. 223–248.

Psaraftis, H. N. (1995) Dynamic vehicle routing: Status and prospects. Ann Oper Res, 61:143–164.

Rizzoli, A.; Montemanni, R.; Lucibello, E.; And Gambardella, L. (2007) Ant colony optimization for real-world

vehicle routing problems. Swarm Intelligence, 1:135-151.

Roberti, R. (2012) Exact Algorithms for Different Classes of Vehicle Routing Problems. Alma Mater Studiorum-

University of Bologna, Bologna.

Pisinger, D.; Ropke, S. (2007) A general heuristic for vehicle routing problems. Computers & Operations

Research, 34(8):2403-2435.

Ropke, S. (2013). Branching decisions in branchand-cut-and-price algorithms for vehicle routing problems.

DTU Transport. Disponível em: http://www.gerad.ca/colloques/ColumnGeneration2012/presentations/

session7/Ropke.pdf. Acesso em 10 de julho de 2013.

Shaw, P. (1998) Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems.

In: Maher, M. P. J. F. Principles and Practice of Constraint Programming - CP98 Lecture Notes in

Computer Science. New York: Springer-Verlag. p. 417-431.

Silva Júnior, O. S.; Leal, J. E. (2009) Roteirização dinâmica de veículos com janelas de tempo usando de um

algoritmo de colônia de formigas. Congresso de Pesquisa e Ensino em Transportes. Vitória, ES: Anais do

XXIII ANPET.

Solomon, M. M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows

Constraints. Operations Research, 35(2):254-265.

Subramanian, A. (2012) Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problem. Tese de

Doutorado. Universidade Federal Fluminense, Niterói.

Taillard, E. D.; Gambardella, L. M.; Gendreau, M.; And Potvin, J.-Y. (2001) Adaptive memory programming: A

unified view of metaheuristics. European Journal of Oper. Research, 135(1):1-16.

Taillard, E.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J. (1997) A tabu search heuristic for the vehicle

routing problem with soft time windows. Transportation Science, 31(2):170-186.

Thangiah, S. R.; Osman, I. H.; Sun, T. (1994) Hybrid Genetic Algorithm Simulated Annealing and Tabu Search

Methods for Vehicle Routing Problem with Time Windows. Technical Report 27, Computer Science

Department, Slippery Rock University.

Sintef (2013) Benchmarks-Vehicle Routing and Travelling Salesperson Problems, Benchmark data sets for

vehicle routing problems with time window. Disponível em: http://www.sintef.no/Projectweb/TOP/

Problems/VRPTW/Solomon-benchmark/100-customers/. Acesso em 06 de junho de 2013.

Yang, J.; Jaillet, P.; Mahmassani, H. (2004) Real-time multivehicle truckload pickup and delivery problems.

Transportation Science, 38(2):135-148.

__________________________________________________________________________________________

Orivalde Soares da Silva Júnior (orivalde@yahoo.com.br)

José Eugênio Leal (jel@puc-rio.br)

Departamento de Engenharia de Produção, PUC-Rio, Rio de Janeiro, RJ, Brasil