Heurísticas baseadas em relaxação lagrangiana para o problema de roteirização de veículos com restrições operacionais

HEURÍSTICAS BASEADAS EM RELAXAÇÃO LAGRANGIANA PARA O PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM RESTRIÇÕES OPERACIONAIS Claudio Barbieri da Cunha Nicolau D. F. Gualda Departamento de Engenharia de Transportes Escola Politécnica da Universidade de São Paulo RESUMO O problema de roteirização e programação de veículos com restrições de janela de tempo, de duração da jornada e de capacidade dos veículos é do tipo NP-hard. Este trabalho descreve três heurísticas desenvolvidas para resolvê-lo, as quais se baseiam na relaxação Lagrangiana de parte das restrições. O problema relaxado resultante corresponde a um problema de caminho mínimo com janelas de tempo (PCMJT), o qual é ainda NP-hard para frotas com mais de um veículo. As heurísticas a ele aplicadas utilizam uma versão aprimorada do algoritmo de etiquetamento permanente para solução do PCMJT. As heurísticas foram validadas com base em conjuntos de problemas-teste com janelas de tempo apresentados na literatura. As heurísticas desenvolvidas apresentam um desempenho equivalente ou superior, em termos de qualidade das soluções, em comparação aos modelos testados da literatura. As heurísticas foram ainda aplicadas com sucesso a um problema real de distribuição urbana em São Paulo. ABSTRACT The vehicle routing problem with time windows, time duration and vehicle capacity constraints is NP-hard. This paper presents three heuristics developed to solve it, which are based on the Lagrangian relaxation of some constraints. The relaxed problem is still hard to solve for problems with more than one vehicle. For only one vehicle the subproblem results on a shortest path problem with time windows (SPPTW). The heuristics use an improved version of the generalized permanent labeling algorithm to solve the SPPTW. The heuristics were evaluated based on some test-problem sets found in the literature. The results demonstrate that the heuristics perform equal or better than the test models described in the literature for some classes of problems in terms of quality of the solutions obtained. The heuristics have also been sucessfully applied to a real urban distribution problem in São Paulo.

1. INTRODUÇÃO Este trabalho trata da formulação e do desenvolvimento de uma estratégia de solução para o modelo matemático que representa os problemas de roteirização e programação de frotas de veículos, com as restrições de janelas de tempo dos clientes (que definem os horários em que é possível o atendimento), capacidade dos veículos e duração máxima das viagens. Ademais, incorpora a possibilidade de solução de problemas tanto para o caso de frota homogênea quanto para o de frota heterogênea de veículos. Este problema foi objeto da pesquisa de doutorado do primeiro autor, realizada sob orientação do segundo. Diversos aspectos justificam a importância de modelos de otimização de roteiros e da programação de entregas no contexto da distribuição física de produtos. Em particular nos últimos anos, a partir do programa de estabilização da economia (pós Plano Real), podem-se destacar os seguintes aspectos: − A redução da inflação retirou das empresas a oportunidade de auferir lucros através de ganhos financeiros. Consequentemente, a eficiência operacional e a competitividade passaram a ser

decisivas para a manutenção e a conquista de mercados, e até mesmo para a sobrevivência das organizações. − As empresas em geral, e em particular as do setor varejista, deixaram de fazer encomendas de em grandes lotes de compras, como ocorria no passado. A estabilidade dos preços e o elevado custo financeiro têm levado à redução dos estoques e ao aumento da freqüência de pedidos, causando impactos diretos no planejamento e na programação de entregas. − As exigências dos clientes recebedores de carga com relação a prazos, datas e horários de entrega têm aumentado. − O aumento dos volumes de tráfego nos grandes centros urbanos e nas rodovias brasileiras agravou o problema de trânsito, circulação e estacionamento de veículos, afetando a produtividade dos veículos e, consequentemente, os custos logísticos. − Novas restrições de acesso, circulação, estacionamento, e carga e descarga de veículos nas áreas mais centrais das grandes metrópoles são impostas, com a finalidade de diminuir o caos no trânsito. Este trabalho está organizado da seguinte forma: no item 2 é apresentada uma revisão da literatura no tocante a problemas de roteirização; o item 3 apresenta o modelo matemático do problema proposto; o item 4 descreve a estratégia geral de solução, baseada no método da Relaxação Lagrangiana, que é utilizado nos três procedimentos heurísticos de solução descritos no item 5. Por fim, o item 6 contém as conclusões e recomendações. 2. REVISÃO DA BIBLIOGRAFIA Bodin et al. (1983) apresentaram o primeiro trabalho abrangente retratando o estado-da-arte da modelagem de problemas de roteirização e programação de veículos e tripulações. Ronen (1988) e Golden e Assad (1988) também trataram de aspectos relacionados à classificação dos diferentes tipos de problemas de roteirização. Trabalhos anteriores relacionados a problemas de roteirização com janelas de tempo abrangem métodos exatos e heurísticas. Os problemas de roteirização de veículos com janelas de tempo em geral são considerado NP-hard, isto é, possuem ordem de complexidade exponencial, conforme foi demonstrado por Lenstra e Rinnooy Kan (1981) e reafirmado por Kolen et al. (1987), Solomon (1987), Solomon e Desrosiers (1988) e Desrosiers et al. (1995). Apesar dos avanços dos métodos exatos e dos computadores, a complexidade dos problemas de roteirização com janelas de tempo ainda impõe soluções heurísticas para a maioria dos problemas reais. Solomon (1987) propôs e avaliou diferentes heurísticas para problemas de roteirização com janelas de tempo. O autor concluiu que uma heurística de inserção sequencial apresentou um bom desempenho e seus resultados até hoje são utilizados para comparação e avaliação de heurísticas desenvolvidas para essa mesma finalidade. Boas revisões sobre problemas de roteirização de veículos com janelas de tempo podem ser encontradas nos trabalhos de Solomon e Desrosiers (1988), Laporte (1992) e Desrosiers et al. (1995) e Cunha (1997).

3. O MODELO MATEMÁTICO DO PROBLEMA PROPOSTO O problema proposto de roteirização e programação de veículos é denominado Problema de Roteirização e Programação de Veículos com Janelas de Tempo (PRPJT). O modelo matemático associado a esse problema visa a minimização do custo total de entrega e/ou coleta de cargas ou passageiros, considerando as restrições de janelas de tempo, de duração máxima da jornada, e de capacidade dos veículos. As quantidades a serem transportadas são determinísticas e conhecidas a priori. A frota pode ser homogênea ou heterogênea (composta de veículos de diferentes tamanhos e capacidades). Seja N o número de pontos ou clientes a serem atendidos. Em cada ponto de atendimento i ∈ {1, 2,..., N} deve ser realizada uma tarefa, que pode ser de coleta ou de entrega de produtos, no caso do transporte de carga; ou de embarque ou de desembarque de pessoas, no caso do transporte de passageiros. A cada ponto i ∈ {1, 2,..., N} estão associados: − um tempo de atendimento (ou de processamento) si 0; − uma janela de tempo [ai , bi ], ai bi , que define, respectivamente, o horário mais cedo e o horário mais tarde em que pode ser iniciado o atendimento; − uma quantidade qi 0 de carga (ou de passageiros) a ser coletada ou entregue. Os pontos 0 e N+1, representam, respectivamente, a base de saída e a de chegada dos veículos. A cada um destes dois pontos estão associados tempos de atendimento e quantidades de carga nulos e janelas de tempo que indicam os horários permitidos de saída e de chegada dos veículos às bases. Para o atendimento dos N pontos dispõe-se de uma frota composta de NV veículos. Para cada v veículo v da frota disponível, v = 1, 2, ..., NV, são definidos: uma capacidade máxima K ; um custo unitário variável com a distância Cvd ; um custo fixo diário total Cvf ; um custo horário Cvh . A duração máxima da jornada, a mesma para todos os veículos, é dada por H. O deslocamento do veículo de um nó i até o nó j requer um tempo de viagem t ij ; da mesma forma, a distância percorrida entre i e j é dada por dij. A formulação matemática do PRPJT compreende as seguintes variáveis de decisão: x

T

v ij

i

  =   

1, se j é atendido após i pelo veículo v;

0, caso contrário. = horário de início de atendimento em i, i ∈ {1, 2,..., N}

O modelo matemático do PRPJT é apresentado a seguir:

[PRPJT]

[minimizar] NV

N

N +1

∑∑∑C d x v =1 i = 0

v

d

j =1

∑ ∑ (T N V N +1

v =1

j=1

i

ij

v ij

NV

N

+ ∑ ∑Cf

+ si + t i , N + 1)

v

v =1 j =1 v

v

h

i, N +1

C x

x

v oj

+ (1)

sujeito a: NV N +1

∑∑ x v =1 j = 1 N +1

∑x j=0

v oj

N

v

=1

ij

=1 N +1

∑x −∑x v

ij

i=0

N +1

∑x i=0

i=1

v i, N +1

v ji

=0

=1

ai ≤ T i ≤ bi T + s +t − T i

i

ij

j

(

i = 0, 1, 2, ..., N ; i ≠ j

(2)

v = 1, 2, ..., NV

(3)

j = 1, 2, ..., N; v = 1, 2, ..., NV

(4)

v = 1, 2, ..., NV

(5)

i = 1, 2, ..., N

(6)

)

≤ 1 − xij M v

i = 1, 2, ..., N

j = 1, 2, ..., N

j≠i

(7)

v = 1, 2, ..., NV N

N

∑∑q x i=0 j=1

j

v ij

≤

K

v

(T + s + t ) x j

j

xij ∈{0, 1} v

j , N +1

v = 1, 2, ..., NV v j, N +1

− ( T i − t 0i ) xvoi ≤ H i = 0, 1, 2, ..., N+1

i = 1, 2, ..., N

(8) j = 1, 2, ..., N

j = 0, 1, 2, ..., N+1

(9) (10)

v = 1, 2, ..., NV A função objetivo (1) representa o custo total a ser minimizado. As restrições (2) impõem que cada um dos pontos seja visitado uma única vez e por um único veículo; já as restrições (3) a (5) descrevem o fluxo no caminho que o veículo v utilizar. Caso o veículo não seja utilizado, ele segue o caminho do arco direto ligando a base de partida (nó 0) à base de chegada (nó N+1). As restrições (6) impõem que o horário de início de atendimento de cada nó ocorra dentro da sua respectiva janela de tempo; já as restrições (7) definem a continuidade e a compatibilidade temporal dos horários de início de atendimento ao longo das rotas. As restrições de capacidade de carga e de duração máxima da jornada dos veículos são dadas pelas restrições (8) e (9), respectivamente. Por fim, as restrições (10) asseguram a integralidade da solução. 4. ESTRATÉGIA DE SOLUÇÃO A estratégia de solução proposta para o PRPJT é baseada na relaxação Lagrangiana das restrições do modelo matemático, relacionadas à obrigatoriedade de atendimento de todos os pontos uma única vez e por um único veículo (restrições (2)). A relaxação Lagrangiana consiste em uma estratégia geral de solução para problemas de programação matemática que permite a decomposição destes, explorando a sua estrutura particular. Para uma caracterização geral do método da relaxação Lagrangiana, recomenda-se consultar os trabalhos de Fisher (1981) e Cunha (1997). Relaxando-se as restrições (3.2), o problema resultante pode ser visto como uma instância especial de um problema de caminho mínimo, em que NV unidades de fluxo devem seguir do nó que corresponde à base de origem (0) ao nó da base de destino (N+1).

Em particular, se NV = 1, o problema resultante consiste em um problema de caminho mínimo com restrições adicionais de janela de tempo, de duração da jornada e de viabilidade da capacidade do veículo ao longo do roteiro. Para este caso particular existe um algoritmo de etiquetamento permanente (AEP), baseado em programação dinâmica, bastante eficiente (Desrochers e Soumis, 1988 e Cunha, 1991). Uma estratégia de solução baseada no método da relaxação Lagrangiana pressupõe encontrar um algoritmo bastante eficiente para a solução do problema relaxado. Tendo em vista a dificuldade remanescente do problema relaxado para frota superior a um veículo, a estratégia geral de solução do PRPJT é heurística, e utiliza, como sub-rotina, o AEP para o problema de caminho mínimo com restrições de janela de tempo, duração da jornada e capacidade dos veículos (PCMJT). Em decorrência dos resultados da implementação da versão do AEP sugerida por Desrochers e Soumis (1988) para grafos densos, Cunha e Swait (1990) identificaram a potencialidade de se introduzir testes adicionais de dominação, de forma a melhorar o seu desempenho. Na Figura 1 é apresentado o esquema geral de funcionamento do AEP. Outros detalhes sobre o AEP no contexto da relaxação Lagrangiana do PRPJT, bem como os testes adicionais de dominação, podem ser encontrados em Cunha (1997). 5. HEURÍSTICAS DE SOLUÇÃO Neste item pretende-se apresentar uma descrição geral das três heurísticas propostas para a resolução do PRPJT, que são baseadas na relaxação Lagrangiana das restrições de atendimento dos clientes. Duas das heurísticas destinam-se exclusivamente a problemas com veículos idênticos e uma terceira, mais geral, permite tratar problemas em que a frota é heterogênea. Nas três heurísticas são utilizados os procedimentos relativos à relaxação Lagrangiana, incluindo o procedimento de controle, a heurística para a estimativa do limitante superior da função objetivo do problema relaxado e o algoritmo de etiquetamento permanente para o problema de caminho mínimo com janelas de tempo. Maiores detalhes sobre estes e os demais procedimentos que compõem cada uma das heurísticas podem ser encontrados em Cunha (1997). Uma das virtudes das heurísticas propostas é a possibilidade de um veículo ser aproveitado em um novo roteiro, caso retorne à base com a antecedência requerida para tal. O retorno antecipado à base pode ocorrer quando o limite de capacidade do veículo é atingido antes do limite de duração da jornada. 5.1 Problemas com frota homogênea Para instâncias do PRPJT em que a frota é homogênea são propostas duas heurísticas: a Heurística de Alocação Sequencial e a Heurística de Alocação Paralela. Ambas procuram tirar proveito da característica do problema em que não há decisão quanto ao tipo de veículo mais adequado a cada roteiro. 5.1.1. Heurística de Alocação Sequencial A Heurística de Alocação Sequencial consiste em utilizar, de maneira sequencial, o algoritmo para a resolução do subproblema de caminho mínimo com janela de tempo. A estratégia básica desta heurística é considerar todos os clientes como candidatos a serem inseridos em um mesmo veículo.

Passo 1: Inicialização

P

{( 0,0)} i =s = ∅, ∀ i ∈ N , i ≠ s

i

Q = ∅ , ∀i ∈ N ,i ≠ s i

onde: Pi é o conjunto de etiquetas permanentes do nó i. Qi é o conjunto de etiquetas candidatas (não tratadas) do nó i. Passo 2: Encontrar o "bucket" corrente Encontrar F(Q) que corresponde à etiqueta

Q = ∪ (Q − P ) . i ∈N

i

i

Se

Q

(T

k j

)

k , C j de mínimo custo lexicográfico do conjunto

= ∅ , parar.

Passo 3: Selecionar a etiqueta seguinte a ser tratada Selecionar um elemento de B(Q). Se B(Q) = ∅, então vá para passo 2. Passo 4: Tratamento da etiqueta T k , Ck

(

j

j

)

Para todos os sucessores j do nó i faça início se T k + s + t ≤ b (janela de tempo satisfeita) então i i ij j Calcular

(T

k j

k

,C j

)

Adicioná-la ao conjunto Qj caso

(T

k j

)

k , C j não seja dominada

fim

Pi = Pi ∪ {( Ti , Ci )} k

k

volte para o passo 3.

FIGURA 1: Algoritmo de etiquetamento permanente (AEP) para o problema de caminho mínimo com janelas de tempo Após um certo número de iterações, caso não tenha sido possível inserir todos os clientes no mesmo veículo (em decorrência das restrições de janela de tempo, de duração da jornada e de capacidade), mantém-se a melhor solução para o veículo. Os clientes atendidos pelo veículo são excluídos da lista de candidatos a serem programados nos veículos subseqüentes. Em seguida, o procedimento é novamente repetido, considerando apenas os clientes remanescentes, isto é, ainda não atendidos, e assim sucessivamente. Como a frota é homogênea, ou seja, composta de veículos idênticos, não é necessário definir uma ordem de utilização dos mesmos, o que permite esta alocação sequencial dos clientes aos veículos. Deve-se ressaltar que este método proposto é heurístico, o que significa que a convergência para a solução ótima não é assegurada, exceto no caso particular da frota disponível ser de apenas um veículo (NV = 1). Esta heurística busca minimizar o número de veículos utilizados, através do seu máximo aproveitamento e, para cada um dos veículos, obter a solução mais eficiente em termos da distância e/ou tempo de viagem.

5.1.2. Heurística de Alocação Paralela A Heurística de Alocação Paralela visa determinar uma programação que possibilite a utilização da frota total disponível, com uma distribuição mais uniforme dos clientes nos roteiros e, ao mesmo tempo, a minimização das parcelas de custo com a distância e/ou com o tempo de viagem. A principal diferença desta heurística com relação à anterior reside na maneira como são processadas as iterações da relaxação Lagrangiana. Ao invés de tentar inserir todos os clientes não atendidos num mesmo veículo, neste caso a construção dos roteiros dos NV veículos é realizada em paralelo. Assim, em uma iteração da relaxação Lagrangiana são obtidos NV caminhos mínimos com penalidades. O esquema de funcionamento pode ser descrito sucintamente da seguinte forma: a) Inicialmente as penalidades são nulas. O algoritmo de caminho mínimo (com janelas de tempo e demais restrições do problema) é processado NV vezes, gerando sequencialmente NV caminhos de mínimo custo. Estes caminhos passam por nós diferentes, sem repetição, uma vez que são excluídos do grafo os nós que correspondem aos caminhos mínimos para os veículos anteriores ao corrente. b) A cada nova iteração, são calculadas as novas penalidades e processado o algoritmo de caminho mínimo NV vezes. O processo se repete, até que seja atingido o limite do número máximo de iterações da relaxação Lagrangiana, ou haja uma convergência para uma solução parcial, ou ainda que todos os clientes tenham sido atendidos. O usuário pode utilizar esta estimativa da frota caso não tenha sido possível atender a todos os clientes com a frota por ele especificada. Caso se deseje conhecer qual a frota mínima que resolve o problema, basta definir um valor inicial da frota que seja suficientemente elevado, e ir reduzindo sucessivamente o tamanho da frota em uma unidade, até que não seja mais possível atender a todos os clientes. Exemplificando, se ao reduzir a frota de V+1 para V veículos não for possível atender todos a os clientes, a frota mínima necessária, segundo esta heurística, é de V+1 veículos. 5.2. Problemas com frota heterogênea A heterogeneidade da frota aumenta consideravelmente a complexidade do PRPJT. Quando a frota é heterogênea, há de se decidir quais tipos de veículos devem ser utilizados e quantos de cada tipo. Em alguns problemas pode haver limitações quanto ao número de veículos de cada tipo que estão disponíveis para utilização, além da eventual limitação da frota como um todo. Para instâncias que correspondem ao caso mais geral do PRPJT, em que a frota pode ser heterogênea, é proposta a heurística de Agrupamento e Alocação Sequencial. Esta heurística é derivada da Heurística de Alocação Sequencial, para problemas com frota homogênea. A diferença básica é a introdução de um procedimento de agrupamento. Ao invés de se tentar inserir todos os clientes ainda não atendidos em um mesmo veículo, antes é realizado um agrupamento e uma seleção dos clientes que devem estar potencialmente juntos, para então se tentar determinar um roteiro que passe por todos os pontos agrupados. O procedimento da relaxação Lagrangiana é utilizado para resolver instâncias de problemas cujos nós devem potencialmente poder ser atendidos pelo veículo.

A introdução de um procedimento de agrupamento decorre do fato de que o número de clientes não atendidos, candidatos a serem inseridos em um veículo, pode ser muito maior do que o número que efetivamente pode ser transportado pelo veículo, em decorrência das restrições do problema. Conseqüentemente, o principal benefício do agrupamento é a redução do esforço computacional do algoritmo de caminho mínimo com janelas de tempo para a resolução do subproblema da relaxação Lagrangiana. O agrupamento proposto nesta heurística pode, potencialmente, possibilitar atenuar o aspecto desfavorável da Heurística de Alocação Sequencial, que é o desequilíbrio entre as rotas geradas para os diferentes veículos. Na medida em que a estratégia procura inserir o maior número possível de nós em uma rota, as rotas geradas correspondentes aos primeiros veículos tendem a englobar um número elevado de tarefas, enquanto que as rotas associadas aos últimos veículos englobam um menor número de atendimentos. Ao contrário da maioria dos procedimentos de agrupamento descritos na literatura, que são sequenciais, o procedimento proposto aqui opera em paralelo, isto é, considera simultaneamente os grupos formados por todos os clientes ainda não atendidos. Os clientes vão sendo agrupados, baseados em um critério de proximidade, que leva em conta a distância entre eles e também a proximidade “temporal”, isto é, definida pelas janelas de tempo. O agrupamento é interrompido quando as restrições de capacidade do veículo ou de duração da jornada tenham sido violadas. Adicionalmente, o procedimento de agrupamento visa racionalizar a alocação dos clientes aos veículos e também reduzir o número de nós candidatos a serem inseridos e roteirizados em um veículo, e não determinar exatamente quais os clientes a serem atendidos pelo veículo. Tendo em vista a complexidade introduzida pelas janelas de tempo, que dificulta a adoção de métodos baseados em critérios espaciais de varredura, bem como a distribuição mais uniforme dos clientes aos veículos, o procedimento de agrupamento baseia-se no problema da árvore de cobertura mínima (“minimum spanning tree”) (Cunha, 1997). Uma árvore de cobertura consiste em um conjunto de nós e arcos tais que não pode haver ciclos; em outras palavras, saindo de qualquer nó i pertencente à árvore e percorrendo os arcos incluídos na árvore, é impossível retornar ao nó i. Na heurística proposta, definiu-se, para a determinação dos custos na árvore de cobertura mínima, a seguinte função de custo f ij entre dois nós quaisquer i e j:

f

ij

= max

{t ,[a − (b + s + t )]} ij

j

i

i

ij

(11)

A função f ij permite determinar a menor proximidade entre dois pontos: a espacial, dada pelo tempo de viagem t ij e a temporal, dada pelo mínimo tempo de espera em j saindo de i o mais tarde possível, em função de ter iniciado o atendimento em i no limite superior da respectiva janela de tempo.

Para a decisão quanto ao tipo de veículo que é utilizado em cada agrupamento foi desenvolvido um procedimento que define a ordem de prioridade na utilização dos veículos da frota segundo uma ordem crescente de custo fixo por unidade de capacidade, isto é, do menor para o maior quociente ( C K ) . Esta regra se baseia na observação de que os veículos maiores apresentam menores v

v

f

custos fixos e variáveis por unidade de capacidade. 6. TESTES COMPUTACIONAIS E ESTUDO DE CASO Os testes foram realizados em um microcomputador PC-compatível, com processador Pentium de 100 Mhz, da marca Intel, memória de acesso randômico (RAM) de 16Mb e disco rígido de 1.28 Gb com tempo de acesso de 15 ms. 6.1. Testes computacionais As três heurísticas foram também avaliadas através dos problemas-teste propostos por Solomon (1987). Na Tabela 1 são apresentados os resultados comparativos das três heurísticas propostas neste trabalho com aqueles obtidos por Solomon (1987), para cada um dos seis conjuntos de problemas. A Heurística de Agrupamento e Alocação Sequencial apresentou, em vários casos, desempenho superior ao da melhor heurística proposta por Solomon (1987), em termos da qualidade das soluções obtidas. As duas outras heurísticas apresentaram resultados de boa qualidade para algumas categorias de problemas. Por outro lado, os resultados não foram totalmente satisfatórios na resolução de alguns problemas com roteiros de maior duração. O desempenho da Heurística de Alocação Sequencial ficou prejudicado pela consideração de todos os clientes não atendidos como candidatos à alocação no veículo correntemente programado. 6.2. Estudo de caso A Heurística de Agrupamento e Alocação Sequencial foi aplicada a um problema real de distribuição física na Grande São Paulo, com cerca de 136 entregas. Trata-se de um problema de uma transportadora localizada na zona oeste de São Paulo (SP). A empresa presta serviços de entregas em supermercados, incluindo as grandes redes de hipermercados, bem como diversos estabelecimentos do comércio varejista (mercearias, cooperativas, etc). Os resultados obtidos foram comparados com aqueles decorrentes da programação manual pelos despachadores da empresa responsável pela distribuição. A Tabela 2 sintetiza os resultados do processamento da heurística proposta, em comparação com a programação realizada pela empresa.

TABELA 1:Análise comparativa do desempenho das heurísticas propostas com o das duas melhores heurísticas de Solomon (1987) Grupo

C1

R1

RC1

C2

R2

RC2

Número de problemas

Heurística

Número de veículos da frota

Distância total percorrida

Tempo CPU (s)

9

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

10.0 10.0 10.0 10.0 10.1

935.5 868.5 835.0 951.9 1049.8

11.3 144.9 4.2 25.3 25.3

12

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

14.3 14.6 14.4 13.6 14.5

1674.1 1479.5 1546.9 1436.7 1638.7

145.4 579.1 30.8 24.7 25.5

8

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

14.3 13.9 13.9 13.5 14.2

1830.6 1646.6 1653.5 1596.5 1874.4

129.1 418.4 21.4 23.8 24.4

8

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

3.3 3.5 3.1 3.1 3.4

781.3 743.4 685.7 692.7 921.5

803.6 1051.0 100.8 43.0 44.5

11

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

3.2 3.3 3.1 3.3 3.3

1401.5 1360.6 1365.3 1402.4 1470.7

1417.4 3733.1 1151.9 62.6 71.1

8

Alocação Sequencial Alocação Paralela Agrupam. Alocação Sequenc. Inserção I1 Inserção I2

3.8 4.0 3.8 3.9 4.1

1584.2 1598.6 1777.1 1682.1 1797.6

702.8 2476.7 505.2 51.7 54.0

TABELA 2 - Sumário dos resultados operacionais obtidos para o estudo de caso Segundo Programação da Empresa Total de clientes atendidos Carga total transportada (kg) Número de veículos utilizados Aproveitamento médio dos veículos Distância total percorrida (km) Carga média por veículo (kg) Custo total da programação (R$)

136 152 307 55 53% 3 068.34 2 720 3 722.81

Heurística de Agrupamento e Alocação Sequencial 136 152 307 35 83% 2 360.70 4 353 2 538.23

% diferença 36% 23% 60% 32%

O aproveitamento médio dos veículos utilizados, medido pelo quociente entre a carga total transportada e a capacidade total dos veículos utilizados, subiu de 53% para 83%. Este valor elevado deve-se, em parte, ao aproveitamento de alguns veículos para uma segunda viagem, após o seu retorno antecipado à base. Isto explica ainda a diferença entre as duas programações no tocante à carga média transportada por veículo. A heurística proposta permitiu uma redução na distância total percorrida de cerca de 23%. Mesmo considerando que as distâncias calculadas pelo modelo estão subestimadas, uma vez que foram calculadas com base nas distâncias euclidianas, multiplicadas por um fator de correção, esta diferença é elevada e permite supor, com razoável certeza, que se obteve uma redução da distância total percorrida pela frota. Em síntese, a utilização desta heurística possibilitou uma redução significativa no custo operacional total da programação de entregas daquela data considerada, através da diminuição da distância total percorrida e, principalmente, do melhor aproveitamento da frota da empresa. 7. CONCLUSÕES O esforço para desenvolver heurísticas para o PRPJT foi bem sucedido. As três heurísticas apresentaram um desempenho satisfatório ao longo dos testes. Entretanto, os resultados dos testes demonstraram a superioridade da Heurística de Agrupamento e Alocação Sequencial com relação às demais, tanto em termos de desempenho e qualidade das soluções, como na possibilidade de resolver problemas com frota heterogênea. Note-se que as heurísticas encontradas na literatura não são aplicáveis aos casos em que a frota é heterogênea. Essa pode ser considerada uma contribuição relevante para o estado-da-arte em questão. Os resultados computacionais também demonstraram que, para boa parte dos problemas-teste, a Heurística de Agrupamento e Alocação Sequencial superou a melhor heurística (I2) proposta por Solomon (1987). Os resultados também indicaram um bom desempenho na aplicação ao problema real de distribuição da Região Metropolitana de São Paulo, através da diminuição da distância total percorrida e, principalmente, do melhor aproveitamento da frota da empresa A qualidade das soluções obtidas, assim como o desempenho computacional das heurísticas, em particular da Heurística de Agrupamento e Alocação Sequencial, sugere a possibilidade de sua utilização em conjunto com alguma heurística de melhoria de solução por intercâmbio, como a descrita por Solomon et al. (1988). Pode-se ainda avaliar o potencial de utilização das heurísticas aqui propostas conjuntamente com métodos de melhoria mais sofisticados, tais como, por exemplo, os baseados em busca tabu, conforme proposto por Rochat e Semet (1994), Gendreau et al. (1994).

Os resultados também possibilitaram comprovar o potencial da estratégia de relaxação Lagrangiana para a solução de um problema complexo de natureza combinatória, abrindo perspectivas para novas aplicações do método em outros problemas NP-hard.

Agradecimentos Ao CNPq, pelo apoio parcial recebido, para realização da pesquisa da qual resultou este trabalho. REFERÊNCIAS BIBLIOGRÁFICAS Cunha, C.B. (1991) Algoritmos para roteamento e programação de veículos no contexto da distribuição física. São Paulo: EPUSP, Departamento de Engenharia de Transportes. 178p. (Dissertação de Mestrado). Cunha, C.B. (1997) Uma contribuição para o problema de roteirização de veículos com restrições operacionais. São Paulo: EPUSP, Departamento de Engenharia de Transportes. 222p. (Tese de Doutoramento). Bodin, L.D.; B. Golden; A. Assad e M. Ball (1983) Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, vol.10, n.2. Cunha, C.B. e J.D. Swait (1990) New dominance criteria for the generalized permanent labelling algorithm for the shortest path problem with time windows on dense graphs. submetido para publicação no Journal of Operational Research Society. Desrochers, M. e F. Soumis (1988) A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR, 26(3):191-212. Desrosiers, J.; Y. Dumas; M. Solomon e F. Soumis (1995) Time constrained routing and scheduling. Network Routing. In: Ball, M.; T.L.Magnanti; C.L.Monna e G.L.Nemhauser (eds.) Handbooks in Operations Research and Management Science. North Holland, Amsterdam, Países Baixos. Fisher, M.L. (1981) The lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1-17. Gendreau, M.; A. Hertz e G. Laporte (1994) A tabu search heuristic for the routing problem. Management Science, (10):1276-1290 Golden, B.L. e A. Assad (1988) Vehicle routing: methods and studies. North Holland, Amsterdã, Países Baixos. Kolen, A.W.J.; A.H.G. Rinnooy Kan e H.W.J.M. Trienekens (1987) Vehicle routing with time windows. Operations Research, 35(2):266-273. Lenstra, J.K. e A.H.G. Rinnooy Kan (1981) Complexity of vehicle and scheduling problems. Networks, 11(2):221227. Rochat, Y. e F. Semet (1994) A tabu search approach for delivering pet food and flour in Switzerland. Journal of the Operational Research Society, 45(11):1233-1246. Ronen, D. (1988) Perspectives on pratical aspects of truck routing and scheduling. European Journal of Operational Research, 35(2):137-145. Solomon, M.M. (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2):254-265. Solomon, M.M. e J. Desrosiers (1988) Time window constrained routing and scheduling problems. Transportation Science, 22(1): 1-13. Solomon, M.M.; E.K. Baker e J.R. Schaffer (1988). Vehicle routing and scheduling problems with time window constraints: efficient implementations of solution improvement procedures, In: B.L.Golden, A.A.Assad (eds) Vehicle Routing: Methods and Studies, North Holland, Amsterdam, Países Baixos. Claudio Barbieri da Cunha

Nicolau D. F. Gualda

Departamento de Engenharia de Transportes Laboratório de Planejamento e Operação de Transportes Escola Politécnica da Universidade de São Paulo C.P. 61548 - CEP 05424-970São Paulo - SP - Brazil tel.: +55(11) 818-5731/5732 fax: +55(11) 818-5716 email: [email protected]

Departamento de Engenharia de Transportes Laboratório de Planejamento e Operação de Transportes Escola Politécnica da Universidade de São Paulo C.P. 61548 - CEP 05424-970 São Paulo - SP - Brazil tel.: +55(11) 818-5731/5732 fax: +55(11) 818-5716 email: [email protected]