Problema de Roteamento com Janelas de Tempo: Uma Abordagem via Geração de Colunas

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

Problema de Roteamento com Janelas de Tempo: Uma Abordagem via Gera¸c˜ ao de Colunas R´ ubia M. Oliveira Universidade Federal de Mato Grosso do Sul - UFMS Departamento de Matem´ atica - DMT 79070-900 Campo Grande-MS, Brasil - [email protected]

Ricardo R. Santos Universidade Cat´ olica Dom Bosco - UCDB Centro de Ciˆencias Exatas e Tecnol´ ogicas - CCET 79117-900 Campo Grande-MS, Brasil - [email protected]

Resumo Um m´etodo para o Problema de Roteamento de Ve´ıculos com Janela de Tempo (PRVJT) ´e apresentado neste artigo. O m´etodo proposto ´e baseado no Algoritmo Simplex com Gera¸c˜ ao de Colunas. A abordagem aqui proposta utiliza um algoritmo de Caminho M´ınimo com Janela de Tempo (CMJT) baseado na generaliza¸c˜ ao de Ford-Bellman-Moore. Esse algoritmo surge como sub-problema no algoritmo Primal Simplex para resolver a relaxa¸c˜ ao linear do problema de parti¸c˜ ao de conjuntos utilizado na modelagem do roteamento com janelas de tempo. O desempenho do algoritmo foi avaliado considerando entradas baseadas nas instˆ ancias de Solomon (R, C e RC) com at´e 100 n´os. O m´etodo proposto obt´em tempos de execu¸c˜ ao compar´ aveis com solu¸c˜ oes heur´ısticas para o mesmo problema. Palavras Chave. Problema de Roteamento de Ve´ıculos, Gera¸c˜ ao de Colunas, Problema de Caminho M´ınimo com Janelas de Tempo. ´ Area principal (Otimiza¸c˜ ao Combinat´ oria, Programa¸c˜ ao Matem´ atica, Metaheur´ıstica) Abstract In this work we present a method for the Vehicle Routing Problem with Time Windows (VRPTW). The method is based on the Simplex algorithm with Column Generation. We have implemented a shortest path algorithm with time windows based on the generalization of the classical Ford-Bellman-Moore algorithm. The algorithm arises as a sub-problem in the Primal Simplex to solve the linear relaxation of the set partitioning problem. The set partitioning problem is used to model the routing problem with time windows. The performance of our method has been evaluated considering Solomon’s instances (R, C, and RC) up to 100 nodes. The proposed method has an execution time comparable to heuristic solutions for the same problem. Keywords. Vehicle Routing Problem, Column Generation, Shortest Path Problem with Time Windows. Main area (Combinatorial Optimization, Mathematical Programming, Metaheuristics)

1802

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

1

Introdu¸c˜ ao

Problemas de roteamento de ve´ıculos desempenham um papel central no gerenciamento da distribui¸c˜ ao de bens e servi¸cos. Sua importˆ ancia ´e refletida na grande variedade de aplica¸c˜ oes, as quais incluem o roteamento de ˆonibus urbano, sistemas de coleta de lixo, entrega de peri´ odicos a assinantes, entre outros (Oliveira, 2001). Dependendo da aplica¸c˜ ao, h´ a necessidade de alterar as restri¸c˜ oes do problema. Algumas restri¸c˜ oes bem conhecidas para o problema de roteamento de ve´ıculos s˜ ao (Cunha, 2000; Oliveira, 2001): restri¸c˜ oes de hor´ ario de atendimento (conhecidas na literatura como janelas de tempo ou janelas hor´ arias), capacidades dos ve´ıculos, frota de ve´ıculos de diferentes tamanhos, dura¸c˜ ao m´ axima dos roteiros dos ve´ıculos (tempo ou distˆ ancia) e restri¸c˜ oes de ve´ıculos que podem atender determinados clientes. Problemas de roteiriza¸c˜ ao de ve´ıculos s˜ao muitas vezes definidos como problemas de m´ ultiplos caixeiros viajantes com restri¸c˜ oes adicionais de capacidade (Cunha, 1997). Sob a ´otica da otimiza¸c˜ ao, os problemas de roteiriza¸c˜ ao de ve´ıculos, incluindo o caso particular do caixeiro viajante, pertencem `a classe de complexidade computacional denominada NP-completo (Garey and Johnson, 1979). Dessa forma, diversas solu¸c˜ oes para o problema de roteamento de ve´ıculos s˜ao baseadas em heur´ısticas de tempo polinomial (Solomon, 1986). Nesse sentido, uma grande quantidade de trabalhos focados no problema de roteamento de ve´ıculos com janelas de tempo tˆem sido desenvolvidos aplicando diferentes t´ecnicas (Boldin and Golden, 1981; Fisher and Jaikumar, 1981; Fisher et al., 1987; Desrochers et al., 1992; Desrosiers et al., 1986; Cunha, 2000; Caramuru, 2006). No entanto, as dificuldades inerentes `a defini¸ca˜o de algoritmos eficientes para o problema tˆem limitado a aplicabilidade dessas solu¸c˜ oes a partir de determinado tamanho do conjunto de instˆ ancias de entrada. Este artigo apresenta um m´etodo para resolu¸c˜ ao do Problema de Roteamento de Ve´ıculos com Janelas de Tempo (PRVJT) baseado no trabalho de (Desrosiers et al., 1983). O algoritmo Simplex com Gera¸c˜ ao de Colunas ´e utilizado em conjunto com o algoritmo de Caminho M´ınimo com Janelas de Tempo (CMJT) baseado na generaliza¸c˜ ao do algoritmo cl´ assico de Ford-Bellman-Moore (Tarjan, 1983; Cormen et al., 1990). A utiliza¸c˜ ao do algoritmo CMJT permite resolver o problema de parti¸c˜ ao de conjuntos, utilizado na modelagem do problema de roteamento com janelas de tempo. A ado¸c˜ ao da t´ecnica de Gera¸c˜ ao de Colunas possibilita obter subproblemas que permanecem com caracter´ısticas combinat´ orias semelhantes ao problema original. Os resultados obtidos com os experimentos computacionais demonstram a aplica¸ca˜o do m´etodo sob instˆ ancias conhecidas para o PRVJT. O desempenho obtido com a aplica¸ca˜o do m´etodo em instˆ ancias de Solomon (Solomon, 1987) com at´e 100 n´ os se mostra atrativo, al´em de apontar para possibilidades de melhoria quando t´ecnicas de paraleliza¸c˜ ao de c´ odigo s˜ ao adotadas. O restante do texto est´ a organizado conforme segue: A Se¸c˜ ao 2 apresenta a modelagem do problema resolvido utilizando a t´ecnica de Gera¸c˜ ao de Coluna. A generaliza¸c˜ ao do algoritmo de Ford-Bellman-Moore e o algoritmo de Caminho M´ınimo com Janela de Tempo ´e abordado na Se¸c˜ ao 3. Os experimentos computacionais e resultados obtidos com a execu¸c˜ ao do algoritmo sob instˆ ancias bem conhecidas para o PRVJT s˜ ao apresentados na Se¸c˜ ao 4. Por fim, a Se¸c˜ ao 5 apresenta as conclus˜ oes e considera¸c˜ oes finais do artigo assim como sugest˜ oes para serem desenvolvidas como trabalhos futuros.

1803

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

2

Descri¸c˜ ao do Problema

Considere um conjunto de viagens onde cada viagem i ´e especificada por um intervalo de tempo [ai , bi ], no qual a viagem deve ser iniciada. Uma viagem ´e chamada uma “jornada produtiva”. Define-se inter-viagem ou viagem de conex˜ ao como sendo uma “jornada n˜ aoprodutiva” conduzida por um ve´ıculo. Assim, uma inter-viagem ´e representada pelo arco (i, j) que vai do final da viagem i para o in´ıcio da viagem j. A cada inter-viagem (i, j) associamos um tempo de dura¸c˜ ao dado por tij e um custo dado por cij . Uma rota ´e uma seq¨ uˆencia de viagens e inter-viagens conduzida pelo mesmo ve´ıculo. Considere P como sendo o conjunto das viagens, I o conjunto das inter-viagens, A o conjunto de arcos (arestas), A = I ∪ ({s} × P ) ∪ (P × {t}), e N o conjunto de n´ os, N = P ∪ {s, t}. Uma interviagem ´e considerada se e somente se for poss´ıvel realizar a viagem j depois da viagem i, onde a restri¸c˜ ao de intervalo de tempo (ai + tij ≤ bj ) ´e respeitada (Desrosiers et al., 1983; Desrochers and Soumis, 1988; Oliveira, 2001). A formula¸c˜ ao para a defini¸c˜ ao de rotas ´otimas para viagens pode ser definida a partir das seguintes vari´ aveis: ( 1 se o arco (i, j) for usado por um ve´ıculo • xij = , onde (i, j) ∈ A 0 caso contr´ ario • ti : vari´ avel que representa o tempo associado ao in´ıcio de cada viagem i, com i ∈ P . As rotas ´otimas que respeitam as restri¸c˜ oes de hor´ arios s˜ ao as solu¸c˜ oes para o seguinte problema: M inimizar

X

cij xij

(i,j)∈A

sujeito a

X

xij = 1,

i∈P

(1)

xik = 1,

i∈P

(2)

j∈N

X

k∈N

xij ≥ 0,

(i, j) ∈ A

xij > 0 ⇒ ti + tij ≤ tj

(i, j) ∈ N

(3)

i∈P

(4)

ai ≤ ti ≤ bi , xij = {0, 1},

(i, j) ∈ A

A restri¸c˜ ao (1) informa que de algum n´ o j o ve´ıculo chegar´ a ao n´o i e a restri¸c˜ ao (2) indica que o ve´ıculo que chegou ao n´o i ter´ a que partir para algum n´o j. A restri¸c˜ ao (3) descreve a compatibilidade requerida entre as rotas e os hor´ arios e a restri¸c˜ ao (4) estabelece o intervalo de tempo no qual a viagem deve ser iniciada.

2.1

Formula¸c˜ ao por Parti¸c˜ ao de Conjuntos

A nota¸c˜ ao usada para a formula¸c˜ ao do problema de Parti¸c˜ ao de Conjunto ´e apresentada nesta Se¸c˜ ao. Al´em disso, discute-se a relaxa¸c˜ ao feita por programa¸c˜ ao linear que ser´ a resolvida utilizando o m´etodo de gera¸c˜ ao de colunas. Considere as seguintes vari´ aveis : • Ω: conjunto das rotas com os hor´ arios satisfazendo as restri¸c˜ oes 3 e 4;

1804

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

( • yir = ( • δri =

1, se a rota r ´e usada 0, caso contr´ ario.

1, se a rota r inclui a viagem i 0, caso contr´ ario.

• cr : custo da rota r (a soma dos custos dos arcos percorridos pela rota mais o custo fixo por ve´ıculo). O processo de solu¸c˜ ao consiste em construir um conjunto de rotas com o menor custo, satisfazendo as restri¸c˜ oes de hor´ arios e incluindo cada viagem exatamente uma vez. O problema-mestre que define o conjunto ´otimo de rotas ´e formulado como um problema de parti¸c˜ ao de conjuntos dado por: X Minimizar cr yr (5) r∈Ω

sujeito a:

X

δri yr = 1,

i∈P

(6)

r∈Ω

yr = {0, 1}

(7)

Devido ao grande n´ umero de rotas em Ω, a relaxa¸c˜ ao por Programa¸c˜ ao Linear do problema de parti¸c˜ ao de conjuntos ´e resolvido por gera¸c˜ ao de coluna. Uma nova coluna com o menor custo relativo ´e gerada e, a partir da´ı, resolve-se o problema de caminho m´ınimo com restri¸c˜ ao de hor´ ario. Observe que esse ´e um sub-problema do problema original.

2.2

Solu¸c˜ ao do Sub-Problema

A rota de custo m´ınimo satisfazendo as restri¸c˜ oes de hor´ ario, chamada de Caminho M´ınimo com Janela de Tempo (CMJT), ´e encontrada usando uma adapta¸c˜ ao do algoritmo cl´ assico de Ford-Bellman-Moore. O algoritmo de Ford-Bellman-Moore determina para cada n´o uma etiqueta θi representando o custo do caminho de ir da origem s para o destino i. Para problemas de caminho m´ınimo com restri¸c˜ ao de hor´ ario, as rotas tˆem de ser comparadas em termos de seu tempo de chegada at´e os n´ os. Desta forma, o algoritmo CMJT requer um par de etiquetas para cada n´ o (tempo de chegada ao n´ o i, custo da rota).

2.3

Solu¸c˜ ao do Problema-Mestre

O algoritmo simplex ´e usado para solucionar a relaxa¸c˜ ao linear do problema-mestre. Este m´etodo fornece os multiplicadores simplex πi necess´ arios para gera¸c˜ ao de cada coluna e possibilita uma reotimiza¸c˜ ao das novas colunas cada vez que s˜ ao solicitadas. As rotas alternativas com custos relativos negativos s˜ ao disjuntas, isto ´e, n´ os (viagens) inclusos em rotas anteriores ser˜ ao desconsiderados na determina¸c˜ ao de novas rotas. A constru¸c˜ ao de rotas disjuntas favorece o aparecimento de solu¸c˜ oes inteiras. A constru¸c˜ ao de rotas disjuntas reduz o n´ umero de itera¸c˜ oes de modo que o tempo computacional tamb´em ´e reduzido significativamente. A solu¸c˜ ao adotada neste trabalho para obten¸c˜ ao de solu¸c˜ oes inteiras consiste na verifica¸c˜ ao de rotas disjuntas. Al´em disso, foram adotadas de estruturas de dados para acesso e armazenamento r´apido aos n´ os visando determinar rapidamente rotas disjuntas e, com isso, minimizar o tempo de execu¸c˜ ao total do algoritmo.

1805

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

3

Descri¸c˜ ao do Algoritmo Proposto para Resolu¸c˜ ao do SubProblema

Destaca-se a seguir o algoritmo de Ford-Bellman-Moore para o problema de caminho m´ınimo (sem janela de tempo). Esse algoritmo determina para cada n´ o uma etiqueta ci a qual representa o custo de ir da origem s para o n´ o i utilizando a rota de custo m´ınimo. Os r´ otulos s˜ao melhorados recursivamente at´e que os valores ´otimos sejam obtidos.

3.1

Algoritmo de Ford-Bellman-Moore

Seja F (i) = {j : (i, j) ∈ A, j ∈ N} o conjunto de sucessores do n´o i e L o conjunto de n´os que ainda n˜ ao foram explorados. A ´arvore de caminho m´ınimo saindo da origem s para todos os outros n´ os da rede ´e obtida associando-se a cada n´o uma etiqueta que ´e melhorada a cada itera¸c˜ ao do algoritmo. O m´etodo das etiquetas consiste na escolha de um n´o i pertencente ao conjunto L, em seguida retira-se o n´o i do conjunto L e tenta-se melhorar todos os sucessores do n´ o i. O novo n´ o melhorado ´e inserido no conjunto L. Assim, quando o conjunto L for vazio, a etiqueta ci associada ao n´ o i representar´ a o caminho de comprimento m´ınimo saindo da origem s e terminando no n´o i. O Algoritmo 1 apresenta os passos principais do Algoritmo de Ford-Bellman-Moore. Algoritmo 1 Algoritmo de Ford-Bellman-Moore Passo 0: Inicializa¸c˜ ao - o custo na origem s : cs = 0 - o custo nos demais n´ os: ci = ∞, - L = {s}

i 6= s

Passo 1: Explora¸c˜ ao de F (i) - Escolha um n´o i ∈ L - ∀j ∈ F (i) tal que: cj > ci + cij sendo cj = ci + cij L = L ∪ {i} Passo 2: Resolu¸c˜ ao do conjunto L - L = L − {i} - Se L = ∅ ent˜ ao FIM. - Sen˜ ao, retorne ao Passo 1.

3.2

Natureza das Etiquetas

Para resolver o problema de caminho m´ınimo com janela de tempo, as rotas tˆem outro atributo importante: o tempo de chegada at´e o n´o i. Ent˜ ao, para tratar simultaneamente as vari´ aveis de tempo ti e as vari´ aveis de custo ci associadas a cada n´ o i, utiliza-se uma etiqueta formada por (ti , ci ), para rotular cada n´ o i. Uma etiqueta (ti , ci ) ´e atribu´ıda ao n´ o i se e somente se existir um caminho poss´ıvel de custo ci , sa´ıdo da origem s e chegando ao n´ o i no menor tempo ti . Qualquer caminho saindo da origem s e chegando ao n´o i com custo ci e com o tempo pertencente ao intervalo [ti , bi ] n˜ ao tem custo de espera.

1806

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

O algoritmo de Ford-Bellman-Moore associa a cada n´ o uma u ´nica etiqueta que ´e progressivamente melhorada. Quando as restri¸c˜ oes de hor´ arios (janela de tempo) s˜ao adicionadas ao problema, n˜ ao ´e mais poss´ıvel conservar unicamente a etiqueta melhorada para cada n´ o pois 2 o par (ti , ci ) n˜ ao tem ordem total no < . Ent˜ ao, faz-se necess´ ario preservar um conjunto de etiquetas (tαi , cαi ), α ≥ 1. Esse conjunto determina um n´ umero finito de caminhos poss´ıveis saindo da origem s e chegando ao n´o i, e cada caminho produz uma etiqueta. Essas etiquetas formam, para cada n´ o i, uma lista Qi . A lista Qi ´e atualizada seq¨ uencialmente a partir das informa¸c˜ oes em Qi , mais as informa¸c˜ oes encontradas ao considerar os caminhos de s e j, compostas do caminho de s e i do arco (i, j).

3.3

Rela¸c˜ ao de Ordem das Etiquetas

O conjunto de etiquetas Qi , para cada n´ o i, guarda as menores distˆ ancias referentes aos diferentes tempos localizados no intervalo [ai , bi ]. Define-se ent˜ ao a rela¸c˜ ao de ordem parcial ≺ para o n´ o i: (t1i , c1i ) ≺ (t2i , c2i ) ⇔ (t1i ≤ t2i ) e (c1i ≤ c2i ). Uma etiqueta pertencente ao conjunto Qi ´e denominada etiqueta m´ınima se n˜ ao existir um outra etiqueta inferior a ela segundo uma rela¸c˜ ao de ordem. Assim, as etiquetas m´ınimas guardam o comprimento do caminho ´otimo da origem s ao destino i. Um conjunto de etiquetas ´e dito irredut´ıvel se todas as etiquetas s˜ ao m´ınimas. Uma etiqueta m´ınima ´e ´ otima (t∗i , c∗i ) se, quando o princ´ıpio de otimalidade (se os caminhos m´ınimos de todos os predecessores de j s˜ ao conhecidos, ent˜ ao, pode-se determinar o caminho m´ınimo at´e j) ´e aplicado a esta etiqueta, a mesma continua com o menor caminho satisfazendo as restri¸c˜ oes de hor´ ario em rela¸c˜ ao as outras etiquetas do conjunto. O resultado desta aplica¸c˜ ao permite reduzir o conjunto de etiquetas de cada n´o retirando aquelas que n˜ ao s˜ao m´ınimas e conservando o conjunto das etiquetas irredut´ıveis dentro do tempo de atendimento permitido. O conjunto irredut´ıvel associado ao n´ o i ´e ordenado em fun¸c˜ ao da vari´ avel de tempo que ´e estritamente crescente, observando que os comprimentos ci est˜ ao em ordem decrescente. O conjunto irredut´ıvel associado ao n´ o i cont´em α(i) pares de etiquetas: (tαi , cαi ), α = 1, 2, . . . , α(i), com α(i)

ai ≤ t1i < t2i < · · · < ti

3.4

≤ bi

e

α(i)

c1i > c2i > · · · ci

.

Algoritmo de Caminho M´ınimo com Janela de Tempo

Apresenta-se a seguir o algoritmo de caminho m´ınimo com as restri¸c˜ oes de janela de tempo nos n´os, de modo similar ao algoritmo de Ford-Bellman-Moore. O algoritmo armazena em cada n´ o pares de etiqueta (ti , ci ), ou seja, uma rota de custo m´ınimo chegando ao n´o i, no tempo ti . Seja Qi = (tαi , cαi ), α = 1, 2, . . . , α(i), um conjunto irredut´ıvel de etiquetas associadas ao n´ o i. Assim, unindo o arco (i, j) aos caminhos que saem da origem s e chegam em i, obtem-se o conjunto Qj associado ao n´ o j atrav´es da seguinte aplica¸c˜ ao: Fij (Qi ) = ∪α fij {(tαi , cαi )} onde ( fij {(tαi , cαi )} =

(max{[aj , tαi + tij ]}, cαi + cij ), ∅,

se tαi + tij ≤ bj caso contr´ ario

1807

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

A defini¸c˜ ao de fij permite um tempo de espera no n´o j, quando o tempo de chegada for menor que o limitante inferior da janela de tempo. O novo conjunto Fij (Qi ) n˜ ao ´e necessariamente irredut´ıvel, pois etiquetas que n˜ ao sejam m´ınimas podem ser geradas. Denota-se por Fij (Qj ) ∪ Qi a redu¸c˜ ao de Fij (Qi ) ∪ Qj conservando apenas as etiquetas m´ınimas. As etiquetas associadas a um n´ o est˜ ao localizadas dentro de uma lista com os tempos em ordem crescente. Os passos principais do etiquetamento para Problemas de Caminho M´ınimo com Janela de Tempo s˜ao apresentados de acordo com o Algoritmo 2. Algoritmo 2 Algoritmo de Caminho M´ınimo com Janela de Tempo - ACMJT Passo 0: Inicializa¸c˜ ao - Qs = {(t1s = as , c1s = 0)} - Qi = {(t1i = ai , c1i = ∞)} para i 6= s - L = {s} Passo 1: Explorando F (i) - Escolha i ∈ L - ∀j ∈ F (i) tal que Fij (Qj ) ∪ Qi 6= Qj - Qi = Fij (Qj ) ∪ Qi - atualiza¸c˜ ao: L

= L ∪ {j}

Passo 2: Redu¸c˜ ao de L - L = L − {i} - se L = ∅ ent˜ ao FIM - sen˜ ao, retorna ao passo 1.

4

Resultados Computacionais

Os resultados apresentados nesta se¸c˜ ao correspondem aos experimentos realizados com a execu¸c˜ ao do m´etodo proposto sob v´ arios conjuntos de entradas baseados nas instˆ ancias de Solomon (Solomon, 1987). Nesses conjuntos de entradas, foi considerado a mesma quantidade e ordem de n´os das instˆ ancias de Solomon assim como a janela de tempo (READY TIME e DUE DATE). A distˆ ancia entre n´os foi calculada a partir da distˆ ancia euclidiana tomando-se como base a posi¸c˜ ao (XCOORD e YCOORD) de cada n´ o. Al´em disso, a formula¸c˜ ao adotada utiliza apenas um ve´ıculo e n˜ao considera a capacidade dos ve´ıculos. O algoritmo que implementa o m´etodo proposto espera que os conjuntos de entradas estejam organizados como um grafo onde o n´ o fonte possui uma aresta para todos os demais n´ os, assim como todos os n´ os possuem arestas para esse n´o fonte. A Figura 1 apresenta um exemplo de um grafo de rotas. Neste exemplo, h´a cinco n´ os distintos (os dois n´ os “S” representam o n´ o de entrada/fonte do grafo) e dez arestas.

1808

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

Figura 1: Exemplo de grafo de rotas adotado pelo m´etodo.

Os experimentos apresentam resultados da solu¸c˜ ao e tempo computacional obtidos ap´os a execu¸c˜ ao do m´etodo proposto considerando instˆ ancias com 50 n´os (Tabelas 1 e 2), 100 n´os (Tabela 3) e com uma implementa¸ca˜o paralela do m´etodo proposto tamb´em considerando instˆ ancias com 50 n´ os (Tabela 4). Os experimentos apresentados nas Tabelas 1, 2 e 3 foram executados sob uma plataforma computacional composta por um Processador Pentium IV 2.80GHz, 512MB de mem´ oria RAM, 60GB de disco e sistema operacional Linux Fedora Core 6. Nessas tabelas, as colunas I, D e T, representam respectivamente, a instˆ ancia de Solomon que est´ a sendo utilizada, a distˆ ancia obtida pelo m´etodo e o tempo de execu¸c˜ ao (em segundos) do m´etodo. Os experimentos apresentando os resultados com a vers˜ ao paralela do m´etodo (Tabela 4) foram executados em uma plataforma formada por Processador Intel Xeon Quad-Core, 4 GB RAM, 160GB disco e sistema operacional Linux Fedora Core 6. As Tabelas 1 e 2 apresentam os valores correspondentes `a distˆ ancia do caminho m´ınimo (coluna Distˆ ancia) e o tempo computacional (coluna Tempo) de 36 instˆ ancias separadas em 6 classes, cada uma com 6 instˆ ancias, obtidos pela execu¸c˜ ao do m´etodo proposto. A coluna Tempo apresenta os valores em segundos. Tabela 1: Resultados com instˆ ancias de 50 n´os para as classes R1, C1 e RC1. I r101 r102 r103 r105 r106 r109

R1 D 1021,17 1328,81 1256,28 1435,44 1755,25 852,13

T 3 10 46 13 20 19

I c101 c102 c105 c106 c107 c108

C1 D 1511,37 1113,11 840,25 1537,26 1405,24 1479,18

T 10 34 14 6 17 31

I rc101 rc102 rc103 rc105 rc106 rc107

RC1 D 1966,36 1801,29 3514,46 1840,53 3145,61 2854,33

T 25 29 66 37 36 152

Tabela 2: Resultados com instˆ ancias de 50 n´os para as classes R2, C2 e RC2. I r201 r202 r205 r206 r209 r210

R2 D 1589,95 1576,13 1646,31 1741,98 1511,95 1689,53

T 65 81 30 200 111 108

I c201 c202 c205 c206 c207 c208

C2 D 1525,71 1341,96 1184,54 1979,43 3159,48 2765,94

T 10 38 16 36 137 30

I rc201 rc202 rc203 rc205 rc206 rc207

RC2 D 2751,21 2125,79 2520,15 1510,11 1389,35 2140,25

T 19 40 266 40 92 490

1809

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

No experimento apresentado nas Tabelas 1 e 2 ´e interessante observar o desempenho do algoritmo sob a maior parte das instˆ ancias. Deve-se destacar aqui que a discrepˆ ancia para resultados ´otimos, referentes `a distˆ ancia percorrida, encontrados na literatura (Sintef, 2005) ´e devida ao tratamento dado ao n´ umero de ve´ıculos, apenas um ve´ıculo ´e utilizado no m´etodo proposto, e as suas capacidades. A Tabela 3 apresenta os resultados considerando um conjunto de instˆ ancias (sub-conjunto com melhor tempo de execu¸c˜ ao em cada grupo das Tabelas 1 e 2) com 100 n´ os. Tabela 3: Resultados com instˆ ancias de 100 n´os. Classes

R1

R2 C1

C2 RC2

I r101 r102 r105 r106 r109 r205 c101 c105 c106 c107 c201 c205 rc201

D 2048,11 2745,64 2991,45 2714,81 2905,96 3118,00 3848,00 3394,28 5523,44 4213,22 3488,89 4276,10 3218,83

T 640 620 277 1317 689 4477 869 820 2528 1157 3488 378 520

Os resultados apresentados nas Tabelas 1, 2 e 3 demonstram que o m´etodo apresentado neste trabalho pode obter solu¸c˜ oes para problemas de roteamento de grande porte em tempo de execu¸ca˜o aceit´ avel. A Tabela 4 apresenta os valores correspondentes ao tempo de execu¸c˜ ao computacional (em segundos) da vers˜ ao seq¨ uencial (coluna Tempo Seq¨ uencial) e paralela (Tempo Paralelo) do m´etodo proposto. A execu¸c˜ ao das duas vers˜ oes do m´etodo ocorreram sob o mesmo ambiente computacional (computador com quatro n´ ucleos de processamento). A implementa¸c˜ ao da vers˜ ao paralela consiste, basicamente, na paraleliza¸c˜ ao de la¸cos existentes no c´ odigo do algoritmo atrav´es da utiliza¸c˜ ao da biblioteca OpenMP (Chandra et al., 2001) para programa¸c˜ ao paralela. Para este experimento, foram escolhidas 6 instˆ ancias do grupo R2, cada uma com 50 n´ os. Tabela 4: Compara¸c˜ ao entre a Execu¸c˜ ao Seq¨ uˆencial e a Execu¸c˜ ao Paralela do M´etodo. Instˆ ancias r201 r202 r205 r206 r209 r210

Tempo Seq¨ uencial 30 35 27 180 85 102

Tempo Paralelo 28 31 23 132 77 81

Os resultados apresentados na Tabela 4 mostram que a paraleliza¸c˜ ao do algoritmo que implementa o m´etodo proposto gera ganhos significativos com rela¸c˜ ao ao tempo de execu¸c˜ ao. A melhoria no desempenho entre a vers˜ ao paralela e a sequencial variou entre 1.07 − 1.36, o que indica um ganho m´ aximo de 36% sob a vers˜ ao seq¨ uencial.

1810

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

5

Conclus˜ oes

Este artigo apresentou um m´etodo para o Problema de Roteamento de Ve´ıculos com Janela de Tempo (PRVJT). A constru¸c˜ ao do m´etodo ´e baseada no algoritmo Simplex com a t´ecnica de Gera¸c˜ ao de Colunas. Al´em disso, foi implementado um algoritmo de Caminho M´ınimo com Janela de Tempo que surge como sub-problema no algoritmo Simplex para resolver o problema de parti¸c˜ ao de conjuntos. Esse problema ´e utilizado na modelagem do problema de roteamento com janelas de tempo. Experimentos foram executados utilizandos conjuntos de entradas baseados em 36 instˆ ancias de Solomon com at´e 100 n´ os. Os resultados obtidos revelam que o m´etodo proposto pode ser adotado (quanto ao tempo de processamento) para resolu¸c˜ ao de problemas de roteamento com restri¸c˜ oes de janelas de tempo de consider´ avel complexidade. Isso se deve ao fato de obter solu¸c˜ oes em tempo computacional (varia¸c˜ ao de 3-490 segundos entre as 36 instˆ ancias) compar´ avel com heur´ısticas existentes na literatura da ´area. Al´em disso, uma implementa¸c˜ ao paralela do algoritmo se mostrou atrativa pois gerou ganhos de desempenho de 36% sobre a vers˜ ao seq¨ uencial. Alguns trabalhos trabalhos futuros devem focar o aprimoramento da formula¸c˜ ao a fim de melhor comparar as solu¸c˜ oes obtidas pelo m´etodo proposta com solu¸c˜ oes da literatura. H´a tamb´em a possibilidade de aprofundar os estudos em torno da paraleliza¸c˜ ao do algoritmo. Devido `a natureza iterativa do algoritmo Simplex, espera-se que estudos mais aprofundados sobre as possibilidades de paraleliza¸c˜ ao possam gerar ganhos de desempenho ainda mais significativos. Outras possibilidades de trabalhos futuros voltam-se para a formula¸c˜ ao do problema (e implementa¸c˜ ao do algoritmo) considerando m´ ultiplos ve´ıculos e um estudo detalhado sobre as possibilidades de arredondamento a fim de obter solu¸c˜ oes inteiras.

6

Agradecimentos

Os autores agradecem ao CNPq “Conselho Nacional de Desenvolvimento Cient´ıfico e Tecnol´ ogico ” pelo apoio financeiro e ao Prof. Dr. Marcos Nereu Arenales pelas sugest˜ oes dadas a este trabalho.

Referˆ encias L. D. Boldin and B. L. Golden. Classification in Vehicle Routing and Scheduling. Networks, 11:97–108, 1981. M. P. F. Caramuru. Uma Metodologia H´ıbrida Colˆ onia de Formigas-Busca Tabu-Reconex˜ ao por Caminhos para Resolu¸c˜ ao do Problema de Roteamento de Ve´ıculos com Janelas de Tempo. Master’s thesis, CEFET-MG, Belo Horizonte, 2006. R. Chandra, L. Dagum, D. Kohr, D. Maygan, J. Mcdonald, and R. Menon. Parallel Programming in OpenMP. Morgan Kaufman Publishers Inc., 2001. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990. C. B. Cunha. Uma Contribui¸c˜ ao para o Problema de Roteiriza¸c˜ ao de Ve´ıculos com Restri¸c˜ oes Operacionais. PhD thesis, Departamento de Engenharia de Transportes EP/USP, S˜ao Paulo, 1997. C. B. Cunha. Aspectos Pr´ aticos da Aplica¸c˜ ao de Modelos de Roteiriza¸c˜ ao de Ve´ıculos a Problemas Reais. Transportes, 8(2), 2000.

1811

XL SBPO

02 a 05/09/08 João Pessoa, PB

A Pesquisa Operacional e o uso racional de recursos hídricos

M. Desrochers, J. Desrosiers, and M. Solomon. A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operation Research, 40:342–354, 1992. M. Desrochers and F. Soumis. A Generalized Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows. INFOR, 26, 1988. J. Desrosiers, P. Pelletier, and F. Soumis. Plus Court Chemin Avec Constraintes d’Horaires. RAIRO, 17:357–377, 1983. J. Desrosiers, F. Soumis, M. Desrochers, and M. Sauv´e. Methods for Routing with Time Windows. European Journal of Operational Research, 23:236–245, 1986. M. Fisher and R. Jaikumar. A Generalized Assignment Heuristics for Vehicle Routing. Networks, 23:109–124, 1981. M. L. Fisher, K. O. J¨ ornsten, and O. B. G. Madsen. Vehicle Routing with Time Windows: Two Optimization Algorithms. Operations Research, 45:488–492, 1987. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. R. M. Oliveira. A T´ecnica de Gera¸c˜ ao de Colunas Aplicada a Problemas de Roteamento. Master’s thesis, ICMC-USP, S˜ ao Carlos, 2001. Sintef. Best Known Solutions Identified by Heuristics for Solomon’s (1987) Benchmarks Problems. http://www.sintef.no/static/am/opti/projects/top/vrp/bknown.html, 2005. M. M. Solomon. On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling with Time Windows Constraints. Networks, 16:161–174, 1986. M. M. Solomon. Algorithms for Vehicle Routing and Scheduling Problems with Time Windows Constraints. European Journal of Operational Research, 35:254–266, 1987. R. E. Tarjan. Data Structures and Network Algorithms. Conference Series in Applied Mathemathics, 1983.

1812