Algoritmos Genéticos Aplicados a Programação de

Algoritmos Genéticos Aplicados a Programação de Embarcações de Apoio às Operações “Offshore”

Mayron Rodrigues de AlmeidaPetrobras

Rua Nilo Peçanha, 151 / 7º andar – Centro – Rio de Janeiro - [email protected]

RESUMO

Este trabalho apresenta um caso real do problema de roteamento de veículos que ocorre na programação de embarcações de apoio offshore na Bacia de Campos. O objetivo da solução é construir uma programação de embarcações que maximize o nível de serviço e minimize os custos envolvidos. Algumas das principais características do problema são: a frota heterogênea, múltiplos depósitos, múltiplas viagens, limite de tempo na duração das rotas, transporte de diferentes produtos, priorização de entrega por tipo de produto, restrições entre clientes e veículos e coleta e entrega simultâneas. Para tratar o problema é proposto um algoritmo de solução baseado na técnica de algoritmos genéticos. O algoritmo propõe esquemas de representação indireta baseada em ordem, decodificação e avaliação adequadas às características do problema. São realizados testes considerando 31 cenários de demanda. Os resultados obtidos mostram que o algoritmo proposto fornece soluções ótimas ou quase ótimas com tempos de solução compatíveis com a realidade operacional.

PALAVRAS CHAVE. Programação de embarcações. Algoritmos Genéticos. Exploração e produção de petróleo. AL - Aplicações a Logística e Transportes.

ABSTRACT

This work introduces a real case of the vehicle routing problem experienced at the supply vessel scheduling in offshore support at the Campos Basin. The objective of solution consists in finding a supply vessel scheduling that maximize the service level and minimize the operation costs. Some of the problem main features are: heterogeneous fleet, multiple depots, multiple trips, routing time limit, multiple goods, some goods has priority delivery, client-vessel restrictions and simultaneous pickup and delivery. As solution approach, it is proposed a genetic algorithm to tackle the problem. The algorithm introduces indirect representation, decoding and evaluation strategies suitable to the problem features. Many experiments are executed based on thirty one different scenarios. The results show that the proposed algorithm provides optimum or near optimum solutions within short run times.

KEYWORDS. Vessel Scheduling. Genetic Algorithms. Exploration and Production of Oil. AL – Applications in Logistics and Transportation.

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 1015

1. Introdução

Este trabalho aborda o problema de apoio marítimo nas operações de suprimento de unidades marítimas (plataformas de exploração, plataformas de produção e embarcações especiais) a serviço da Petrobras. O foco principal do trabalho são as unidades atendidas pelo porto de Macaé.

As atividades de exploração e produção offshore de petróleo e gás demandam uma estrutura logística complexa visando o suprimento de alimentação, água, cargas em geral (peças de reposição, equipamentos, tubos, etc.), óleo diesel e outros. O apoio marítimo se configura em um elo importante na cadeia logística que garante o nível de serviço desejado nas operações de suprimento. O atendimento a demanda de produtos das plataformas é realizado principalmente por embarcações do tipo PSV (Platform Suppy Vessel) sob responsabilidade da unidade de serviços de transporte e armazenamento da área de exploração e produção da Petrobras, para as atividades do Sul Sudeste.

Pode-se ter uma dimensão do porte da estrutura logística necessária para atender as demandas envolvidas, através dos dados consolidados para o ano de 2007: 99 pontos de atendimento, 230.000 t/mês de carga transportada e 133 embarcações (Fonte: US-TA 2007).

Considerando-se o cenário apresentado, a utilização de ferramentas de apoio à decisão que permitam definir o perfil e quantidade de embarcações bem como o conjunto de rotas que minimizem o custo operacional, é um diferencial estratégico importante nas operações offshore da Petrobras.

Sendo assim, o objetivo do trabalho consiste em construir um sistema e um módulo de otimização para apoiar a programação das embarcações de suprimento buscando a maximização do nível de serviço exigido pelas unidades marítimas e a minimização dos custos envolvidos na operação de suprimento.

O problema estudado é conhecido na literatura como Problema de Roteamento de Veículos (PRV). O PRV e suas variações vêm sendo estudado ao longo das últimas décadas (Cunha, 2000; Goldbarg, 2000) assim como várias técnicas alternativas de resolução (Laporte, 1995; Laporte, 2000). A formulação básica do problema consiste em definir uma rota de mínimo custo onde cada cliente é visitado ao menos uma vez. Os veículos, cuja capacidade é limitada, partem de um depósito e retornam a ele após o término da rota. Algumas formulações consideram problemas com restrições adicionais como janela de tempo (Alvarenga, 2004), frota heterogênea, múltiplas viagens (Brandão, 1997), limite de tempo para o término da rota, múltiplos depósitos (Bondin, 1983), veículos com múltiplos compartimentos, demanda parcialmente atendida, restrições dos clientes a alguns veículos, dentre outras.

O PRV é considerado um problema NP - difícil (Lenstra, 1981). Nestes casos, para alcançar-se boas soluções, sugere-se o uso de métodos heurísticos ou de algoritmos de aproximação. Os métodos heurísticos podem ser classificados como clássicos ou meta heurísticas. Algumas das heurísticas clássicas mais conhecidas para este problema são os algoritmos de Clarke e Wright (1964), o método de melhoramento seqüencial de Mole e Jameson (1976), o algoritmo de setorização seguida de roteirização de Gillet e Miller (1974) e a heurística de melhoramento de Lin e Kernighan (1973). Recentemente, meta heurísticas como Busca Tabu (Gendreau, 1994; Rochat, 1995; Laporte, 2000), Têmpera Simulada (Chiang, 1996; Li, 2003) e Algoritmos Genéticos (Alvarenga, 2004; Ombuki, 2004; Almeida et al, 2007) têm sido largamente usados para a resolução do PRV. A maioria dos algoritmos de aproximação é baseada em relaxação lagrangeana (Khol, 1997) e método de geração de colunas (Larsen, 1999).

O objetivo do trabalho é disponibilizar um modelo de otimização que encontre soluções ótimas ou quase ótimas para este problema. Para a escolha do método de solução do problema, foram considerados os seguintes critérios: o método deve obter soluções melhores que as rotas atuais, alcançando respostas ótimas ou quase ótimas e esta resposta deve ser alcançada em tempo de processamento razoável, visto que este processo pode ser executado várias vezes ao dia.


2. Descrição do Problema

A Figura 1 mostra um esquema resumido do problema tratado e suas entidades principais: porto, embarcações, unidades marítimas, navios-tanque supridores de diesel e cargas a programar.

Considerando um único porto de operação das embarcações, o problema é descrito da seguinte forma. Para cada programação a frota é composta por um número fixo de embarcações que tem características diferentes. As características podem ser físicas: peso máximo total (kg), peso máximo por carga de convés (kg), área útil de convés, volume máximo de água, volume máximo de diesel e velocidade da embarcação; e lógicas: se entregam água, diesel, carga geral, rancho, etc.

A seguir são listados os principais parâmetros das embarcações que são utilizados na otimização:

1. Código: Código da embarcação.2. Expressinho: Indica se embarcação é um expressinho. Exemplo: False3. AlturaUtilConves: Indica a altura (m) máxima permitida na embarcação. Exemplo: 64. CapacidadeCarga: Indica a capacidade (kg) total de carga da embarcação. Exemplo: 10000005. ComprimentoUtilConves: Comprimento (m) útil do convés. Exemplo: 206. CustoFixo: Custo fixo da embarcação. Exemplo: $ 25.0007. CustoVariavelNavegacao: Consumo (litro/dia) de combustível da embarcação quando em

velocidade de serviço. Exemplo: 100008. CustoVariavelParadoUnidade: Consumo (litro/dia) de combustível da embarcação quando

em carga/descarga nas UMs. Exemplo: 59. CustoVariavelParadoPorto: Consumo (litro/dia) de combustível da embarcação quando em

carga/descarga nas UMs. Exemplo: 510. LarguraUtilConves: Largura (m) útil do convés. Exemplo: 2011. Latitude: Posição geográfica. Exemplo: -40,254612. Longitude: Posição geográfica. Exemplo: -22,58413. Transbordo: Indica se embarcação faz operação de transbordo. Exemplo: True14. TransportaAgua: Indica se a embarcação transporta água. Exemplo: False15. TransportaCarga: Indica se a embarcação transporta carga geral. Exemplo: True16. TransportaDiesel: Indica se a embarcação transporta diesel. Exemplo: False17. TransportaRancho: Indica se a embarcação transporta carga de rancho. Exemplo: True18. VazaoDescargaAgua: Vazão (m3/h) de descarga de água. Exemplo: 20019. VazaoDescargaDiese: Vazão (m3/h) descarga de diesel. Exemplo: 10020. VelocidadeServico: Velocidade (nó) de serviço. Exemplo: 2021. VolumeAgua: Volume (m3) de água que a embarcação pode transportar. Exemplo: 100022. VolumeDiesel: Volume (m3) de diesel que a embarcação pode transportar. Exemplo: 150023. FatorOcupacao: Fator de ocupação (%) da área de convés. Exemplo: 7024. TempoCarga: Tempo (h) de carregamento da embarcação. Exemplo: 1025. TransportaBackload: Indica se embarcação faz operação de backload. Exemplo: False26. TransportaTubos: Indica se a embarcação transporta tubos. Exemplo: False

Atualmente, em relação às embarcações que partem do porto, são classificadas como cronogramadas, expressinhos e expressões. As embarcações cronogramadas são aquelas com horário e grupos de unidades pré-estabelecidos, utilizadas para entrega de cargas com quantidade e periodicidade conhecidas; os expressinhos são embarcações menores e mais velozes, geralmente utilizadas para entregas de cargas frágeis e cargas de emergência; os expressões são as demais embarcações. Existem embarcações que não realizam operações no porto, tais como, as exclusivas de transbordo e as de suprimento de diesel.


Figura 1 - Esquema do problema

O conjunto de clientes inclui plataformas de exploração, plataformas de produção e embarcações especiais. Os clientes fazem solicitações de entregas de produtos através de requisições de transporte (RTs). Estas RTs são qualificadas segundo o tipo de carga (rancho, água, diesel, tubos e carga geral), tipo de operação (upload1, backload 2e transbordo3) e criticidade (normal ou emergência) quanto à data mais tarde de entrega. Em relação à ocupação da embarcação as cargas podem se dividir em cargas de convés (rancho, tubos e carga geral) e internas à embarcação (água e diesel).

A seguir são listados os principais parâmetros das unidades marítimas que são utilizados na otimização:

1. Código: Código da unidade marítima. Exemplo: P-502. Latitude: Posição geográfica. Exemplo: -41,25413. Longitude: Posição geográfica. Exemplo: -19,95484. JanelaTempoHoraInicio: Hora de início da janela de tempo. Exemplo: 65. JanelaTempoHoraFim: Hora do fim da janela de tempo. Exemplo: 186. VazaoCargaAgua: Vazão (m3) de carga de água da UM. Exemplo: 2007. VazaoCargaDiesel: Vazão (m3) de carga de diesel da UM. Exemplo: 1008. NivelServico: Nível de serviço (%) desejado pela UM. Exemplo: 959. AtendimentoPrioritario: Indica se a unidade marítima tem prioridade no atendimento.

Exemplo: True

O processo de suprimento de diesel, transbordo e rancho tem características diferentes em relação às demais. Todas as cargas, exceto transbordo e diesel, tem como origem ou destino o porto. O ponto de abastecimento das embarcações de suprimento de diesel são navios-tanque, representados na Figura 1 pelos dois triângulos pretos com legenda NT. Os navios-tanque podem ser considerados como portos para as embarcações de suprimento de diesel, pois é necessário que haja a coleta do diesel nestes navios-tanque antes da entrega para as unidades maritimas. Na operação de transbordo, as unidades marítimas que são origens no pedido de transbordo podem ser consideradas como porto para as embarcações que fazem transbordo, pois é necessário que haja coleta na origem e entrega no destino. As cargas de rancho, devido à existência de 1 A operação de upload é caracterizada como carga que sai do porto para uma unidade marítima.2 A operação de backload é caracterizada como carga que sai de uma unidade marítima para o porto.3 A operação de transbordo é caracterizada como carga que sai de uma unidade marítima para outra.


containeres não refrigerados, devem ter prioridade de entrega em relação às demais (esta priorização tem impacto relevante nos custos envolvidos).

A seguir são listados os principais parâmetros das cargas que são utilizados na otimização:

1. Codigo: Código da carga. Exemplo: XPTO0004038348482. Altura: Altura (m) da carga. Exemplo: 1,53. Comprimento: Comprimento (m) da carga. Exemplo: 154. Largura: Largura (m) da carga. Exemplo: 55. DataMaisTarde: Data mais tarde de entrega da carga. Exemplo: 05/04/2008 15:00:006. Origem: Local de origem da carga. Exemplo: PMAC7. Destino: Local de destino da carga. Exemplo: P-168. Peso: Peso (kg) da carga. Exemplo: Exemplo: 5009. TipoArmazenagem: Tipo de armazenagem da carga. Exemplo: Convés10. TipoEntrega: Tipo de entrega. Exemplo: Emergência11. TipoTransacao: Tipo de transação. Exemplo: Upload12. Expressinho: Indica se a carga deve ser transportada por embarcação do tipo expressinho.

Exemplo: False 13. NúmeroRTs: Número de RTs unitizado na embalagem. Exemplo: 2014. Volume: Volume (m3) da carga. Exemplo: 112,5

No processo de otimização busca-se a construção de uma programação que maximize o nível de serviço4 e minimize os custos envolvidos na operação, considerando os diversos aspectos reais do problema, tais como: compatibilidade da carga com o peso e dimensões da embarcação, direção da corrente marítima, condições climáticas, compatibilidade entre as embarcações e as unidades marítimas, janela de tempo, disponibilidade do porto, priorização de entrega de rancho, dentre outras.

3. Modelo Proposto

Para tratar o problema de otimização da programação é proposto um algoritmo de solução baseado na técnica de algoritmos genéticos. Algoritmos Genéticos constituem uma técnica de busca e otimização, altamente paralela e adaptativa, inspirada no princípio Darwiniano de sobrevivência dos mais aptos (seleção natural) e reprodução genética. Os princípios da natureza nos quais os Algoritmos Genéticos se inspiram são simples. De acordo com a teoria de Darwin, o princípio de seleção privilegia os indivíduos mais aptos com maior longevidade e, portanto, com maior probabilidade de reprodução. Indivíduos com mais descendentes têm mais chance de perpetuarem seus códigos genéticos nas próximas gerações. Tais códigos genéticos constituem a identidade de cada indivíduo e estão representados nos cromossomos. Estes princípios são imitados na construção de algoritmos computacionais que buscam uma melhor solução para um determinado problema, através da evolução de populações de soluções codificadas através de cromossomos artificiais. Nas subseções seguintes apresenta-se o algoritmo genético proposto mostrando os componentes mais importantes: representação; decodificação e avaliação.

Representação

A representação utilizada neste trabalho é uma representação indireta baseada em ordem (que passará por um processo de decodificação), composta por segmentos de números inteiros: o primeiro segmento representa a ordem de programação das embarcações e os demais segmentos representam a ordem de programação das unidades marítimas para cada embarcação do primeiro segmento. Adicionalmente, existe um segmento de números inteiros (não baseada em ordem), cujo objetivo é decidir em qual navio-tanque será realizado o carregamento de diesel.

Esta representação foi escolhida, pois transformando o problema em um problema baseado em ordem garante que todas as soluções serão viáveis, definindo regras de prioridade que o algoritmo genético irá evoluir e determinar a melhor.4 Nível de serviço representa o percentual de cargas entregues no prazo.


Para exemplificar a representação, considere uma programação com 5 embarcações, 10 unidades marítimas e 2 navios-tanque. Neste caso os indivíduos serão representados por seqüências aleatórias dos códigos das embarcações, das unidades marítimas e dos navios-tanque, como mostra a Tabela 1. A primeira linha representa o segmento com a ordem das n embarcações, as próximas m linhas representam a ordem das unidades marítimas e a última linha qual navio-tanque será utilizado para o carregamento de diesel.

1 3 5 4 22 10 5 1 101 8 6 2 75 7 2 10 17 4 6 4 89 9 9 5 64 5 8 9 43 3 10 7 56 6 7 8 38 2 1 6 2

10 1 4 3 90 1 0 1 1

Tabela 1 - Exemplo de representação da solução

A programação é construída seguindo o processo de decodificação descrito a seguir.

Decodificação

A decodificação dos indivíduos é feita percorrendo-se o segmento de embarcações e para cada elemento deste segmento, percorrendo-se o segmento de unidades marítimas correspondente respeitando todas as restrições do problema. A Figura 3 mostra o fluxograma com os principais passos da decodificação das soluções.

O segmento de embarcações é percorrido 2 vezes. Na primeira passagem, o algoritmo de decodificação não permite programações de entrega prevista para depois da data mais tarde. Na segunda passagem, esta restrição é relaxada e o algoritmo permite que cargas sejam programadas fora do prazo máximo de entrega.

Os segmentos de unidades marítimas também são percorridos 2 vezes. Entretanto, na segunda passagem, ele é percorrido na ordem inversa. Isto tem como objetivo permitir que, quando as cargas de rancho tiverem prioridade, o roteiro de retorno para entrega de outras cargas seja o inverso do roteiro de entrega de rancho como exemplificado na Figura 2.

Figura 2 - Exemplo de priorização de rancho


Selecionar segmento de embarcações

Para cada embarcação do segmento

Selecionar segmento de unidades marítimas

corresponde

Para cada unidade marítima do segmento

Existem cargas a programar

Avaliar solução

NÃO

SIM

Alocar embarcação as

vagas disponíveis no porto

Seleciona tipo de embarcação (sai do

porto, diesel, transbordo exclusivo )

Porto Diesel

Decide navio-tanque

Transbordo

Define se rancho tem prioridade

Embarcação compatível com UM

Vai para próxima UM

SIM

UM tem cargas a programar?

UM pertence ao grupo

atendido pela embarcação?

SIM

Embarcação tem tempo disponível?

SIM

NÃO

SIM

Para cada carga da UM

Tem tempo disponível?

Vai para próxima carga

SIM

Carga é compatível

com a embarcação?

Existe espaço disponível na embarcação

SIM

Data prevista programação menor que data mais

tarde?

SIM

NÃO

SIM

PROGRAMAR

NÃO

Segunda passagem pelo segmento de

embarcações?

FIM

Figura 3 – Fluxograma de decodificação


Outro objetivo, é permitir que a mesma embarcação entregue cargas de transbordo como exemplificado na Figura 4, onde é necessário a coleta da carga 1 na UM1 a entrega UM2 e coleta da carga 2 na UM2 e entrega na UM1.

Figura 4 - Exemplo de transbordo

Operadores de Crossover e Mutação

O modelo permite o uso dos operadores de crossover: partial-mapped crossover (PMX), order crossover (OX) e cycle crossover (CX) e os operadores de mutação: inversion mutation e insertion mutation descritos em Gen e Cheng (1996).

Avaliação da Solução

As soluções são avaliadas considerando os seguintes componentes:1. Maximização do nível de serviço global (percentual de RTs entregues no prazo);2. Maximização do nível de serviço local (menor nível de serviço em relação ao

nível de serviço requerido pela unidade marítima);3. Minimização do custo fixo;4. Minimização do custo variável;

4. Resultados

Foram realizados vários testes considerando cenários reais e diversos tipos de configuração para o algoritmo. Os resultados obtidos mostram que o algoritmo proposto fornece soluções ótimas ou quase ótimas em tempo aceitável de otimização, variando de 5 a 15 minutos de acordo com o tamanho do problema (diretamente relacionado ao número de unidades, de cargas a programar e de embarcações disponíveis para programação) para experimentos realizados com 100 indivíduos, 300 gerações e 3 re-inicializações preservando-se 10% dos melhores indivíduos. Nos testes realizados, a minimização do custo fixo não foi considerada, pois ele é irrelevante para o ambiente de programação, visto que as embarcações devem ser pagas mesmo que não forem utilizadas.

A Tabela 2 mostra os resultados obtidos em 31 cenários diários reais de otimização com custos modificados do período de janeiro de 2006. O principal ponto de destaque foi em relação ao nível de serviço global médio de 97,73%. Atualmente, o nível de serviço5 é de aproximadamente 65% em média. As cargas não programadas são resultado de inconsistências nos dados, implicando em incompatibilidade destas cargas com todas as embarcações disponíveis para a programação. O custo variável é resultado do consumo de combustível das embarcações em velocidade de serviço e operando nas unidades marítimas. O custo fixo é resultado do custo ($/dia) das embarcações multiplicado pelo tempo de programação.

A Figura 5, Figura 6 e Figura 7 mostram exemplos de programação sugerida pelo roteirizador, de embarcações que partem do porto, exclusiva de transbordo e exclusiva de entrega de diesel, respectivamente.

5 Nível de serviço operacional, ou seja, apurado após a entrega das cargas. Não existe informação sobre o nível de serviço da programação nos cenários estudados.


Figura 5 - Programação de embarcação que sai do porto

Figura 6 - Programação de embarcação exclusiva de transbordo

Figura 7 - Programação de embarcação exclusiva de diesel


Resumo dos Dados de Entrada Resumo dos Dados de Saída

CenáriosNúmero

de Cargas

Número de UMs

Número de Embarcações

Cargas Programadas

Cargas Programadas

no Prazo

Nível de Serviço

Global (%)

Nível de Serviço Local 6

Distância Percorrida

(km)

Custo Variável

($)

Custo Fixo ($)

Custo Total ($)

Tempo Otimização

(Seg)1 414 41 15 410 409 98,79 0,98 4332,00 94539,37 209318,47 303857,84 5042 365 42 11 364 360 98,63 1,01 4264,97 102652,05 174757,45 277409,50 3833 164 36 11 161 161 98,17 0,75 3449,51 57629,99 136917,94 194547,93 3244 457 45 14 451 450 98,47 0,95 5170,17 116031,61 263019,36 379050,97 6075 609 48 15 603 600 98,52 0,91 6799,13 167334,74 456550,05 623884,79 8256 547 50 19 541 533 97,44 0,61 8411,83 179067,42 421505,64 600573,06 9127 415 43 15 409 408 98,31 0,52 5102,00 113003,01 218237,52 331240,53 6178 415 43 17 413 410 98,8 0,00 4958,73 92896,67 216631,02 309527,69 5179 562 48 15 557 554 98,58 0,87 5932,21 143645,56 405891,96 549537,52 649

10 256 42 8 253 251 98,05 0,68 4044,16 92185,13 236869,14 329054,27 43411 331 44 14 328 326 98,49 0,00 4779,86 97604,24 207645,37 305249,61 79812 707 47 19 701 695 98,3 1,01 8463,09 219189,86 403470,39 622660,25 52513 412 42 9 404 396 96,12 1,01 3977,90 99961,64 261977,18 361938,82 55014 542 46 23 535 532 98,15 0,76 6484,18 158273,94 419041,23 577315,17 72915 504 46 15 499 498 98,81 0,98 5653,04 128634,34 314978,99 443613,33 46416 445 42 12 427 396 88,99 0,00 4978,28 113608,06 252599,05 366207,11 48317 223 39 10 218 218 97,76 0,87 2857,95 49190,88 108437,99 157628,87 21718 566 48 16 557 551 97,35 0,80 5531,04 141880,24 425128,03 567008,27 48019 559 45 16 556 555 99,28 1,01 5638,77 113791,35 261114,10 374905,45 78020 579 48 15 576 572 98,79 0,87 5754,99 112362,53 246214,27 358576,80 65121 364 43 16 361 356 97,8 0,89 6353,25 169448,61 298119,91 467568,52 62622 417 41 15 415 415 99,52 1,01 3826,93 86659,71 238015,48 324675,19 43323 478 44 13 475 470 98,33 1,01 5667,23 126036,34 232931,74 358968,08 49024 286 35 14 282 266 93,01 0,69 3177,72 67330,75 183581,64 250912,39 34725 299 45 11 299 296 99 0,90 3821,05 94956,30 171291,13 266247,43 31026 531 43 18 522 521 98,12 0,74 6448,07 122132,77 325841,28 447974,05 45427 588 46 21 575 573 97,45 0,95 4833,85 106551,63 293493,64 400045,27 52328 475 45 14 446 442 93,05 0,87 4769,51 117112,53 198188,80 315301,33 41029 401 46 13 398 395 98,5 0,70 4275,28 106653,56 202743,41 309396,97 33430 308 41 12 308 308 100 1,01 3088,84 86767,68 211606,33 298374,01 25631 93 22 13 93 93 100 1,01 2164,04 35575,09 73711,86 109286,95 134

Soma 13312,00 1336,00 449,00 13137,00 13010,00 3030,58 24,33 155009,58 3512707,60 8069830,37 11582537,97 15766,00Média 429,42 43,10 14,48 423,77 419,68 97,73 0,78 5000,31 113313,15 260317,11 373630,26 508,58

Tabela 2 - Resultados de Cenários Reais

6 }/{ ii NSDNSPMin , onde NSP é o nível de serviço programado da unidade marítima i e NSD é o nível de serviço desejado da unidade marítima i.


ConfiguraçãoNível de Serviço Global

ProporçãoNível de Serviço

Local

Distância Percorrida

(km)

Custo Variável Custo Fixo Custo Total

Sem Priorização de Rancho 100 1 7703,82 253723,13 668146,42 921869,55

Com Priorização de Rancho 100 1 8578,97 272544,43 780065,96 1052610,39

Tabela 3 - Resultados comparativos de priorização de rancho

A Tabela 3 mostra os resultados comparativos da execução do algoritmo com e sem a priorização de entrega de rancho em um cenário com 755 cargas, 64 unidades marítimas e 25 embarcações.

5. Conclusões

Foi apresentado neste trabalho, um algoritmo genético com representação indireta baseada em ordem para resolver um problema real de programação de embarcações de apoio às operações Offshore. Adicionalmente, foram desenvolvidas heurísticas de decodificação para atender a necessidade de priorização de rancho e demandas de transbordo com a característica exemplificada na Figura 4.

O processo de apoio marítimo é composto de uma série de atividades interligadas formando uma grande e complexa cadeia logística, onde erros podem ser vitais ao funcionamento do sistema como um todo.

Os níveis de serviço global e local são os objetivos mais importantes no processo de otimização, pois suas maximizações implicam, por exemplo, na redução da possibilidade de paradas de produção. Conforme mostrados na Tabela 2, os resultados em relação ao nível de serviço global estão próximos do nível de serviço possível (igual a 100%). Em relação ao nível de serviço local, os resultados foram satisfatórios (0,78 em média) já que este componente da função objetivo representa a menor relação entre o nível de serviço programado e nível de serviço desejado, ou seja, o pior caso entre as unidades marítimas demandantes.

Conforme os resultados mostrados na Tabela 2, a minimização dos custos (principalmente o custo variável, onde a atuação do roteirizador é mais relevante) envolve valores da ordem de $ 3,5 milhões / mês para custo variável e $ 8 milhões / mês para custo fixo. Estes valores refletem a importância de se obter soluções otimizadas para o problema.

O problema abordado apresenta grande complexidade devido a sua natureza combinatória e seu grande número de restrições. Os resultados obtidos mostram que o algoritmo desenvolvido é capaz de obter soluções otimizadas respeitando-se todas as restrições do problema.

Além de auxiliar as decisões sobre a programação das embarcações, o algoritmo pode ser utilizado em diversos estudos, por exemplo: manter a priorização de rancho ou investir em containeres refrigerados, utilizar ou não janelas de recebimento de cargas nas unidades marítimas, ampliação do porto (inclusão novos píeres), dentre outras.


5. Referências.Almeida, M.R., Mazzini, F.F., Ballesteros, M.L., Ribas, P.C., 2007. Algoritmos Genéticos

Aplicados a um Caso Real do Problema de Roteamento de Veículos. XXXIX SBPO.

Alvarenga, G.B. and Mateus, G.R., 2004. A Two-Phase Genetic and Set Partitioning Approach for the Vehicle Routing Problem with Time Windows. International Conference on Hybrid Intelligent Systems, 428-433

Bondin, L.; Golden, B.; Assad, A. and Ball, M., 1983. Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research V. 10, no. 2, 63-211.

Brandão, J. and Mercer, A., 1997. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operations Research 100, 180-191.

Chiang, W.C. and Russell. R.A., 1996. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63:3-27.

Clarke, G., Wright, J.W., 1964. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12, 568-581.

Cunha, C. B., 2000. Aspectos práticos da aplicação de modelos de roteirização de veículos a problemas reais. Transportes, v.8, n.2, p.51-74.

Gen, M., Cheng, R., 1996. Genetic Algorithms and Engineering Design. Editora John Wiley & Sons.

Gendreau, M.;Hertz, A. and Laporte, G., 1994. A tabu search heuristic to vehicle routing problem. Management Science 40, 1276-1290.

Gillett, B.E., Miller, L.R., 1974. A heuristic algorithm for the vehicle dispatch problem. Operations Research 22, 240-349.

Goldbarg, M.C., Luna, H. P., 2000. Otimização Combinatória e Programação e Linear - Modelos e Algoritmos. Editora Campus. São Paulo/SP.

Kohl, N. and Madsen, O.B.G., 1997. An optimization algorithm for the vehicle routing problem with time windows based on lagrangean relaxation. Operations Research, 45(3):395-406.

Lin, S., Kernighan, B., 1973. An effective heuristic algorithm for the traveling salesman problem. Operations Research 21, 498-516.

Laporte, G and Osmar, I.H., 1995. Routing Problems: A Bibliography. Annals of Operational Research 61, 227-262.

Laporte, G., M. Gendreau, J.Y. Potvin and F. Semet, 2000. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, v.7, n4/5, p.285-300.

Larsen, J., 1999. Parallelization of the vehicle routing problem with time window. Ph.D. Thesis no. 62, DTU Technical University of Denmark.

Lenstra, J.K., and Rinnooy Kan, A.H.G., 1981. Complexity of vehicle routing and scheduling problems. Networks 1 l, 221-227.

Li, H.; Lim, A. and Huang, J., 2003. Local Search with Annealing-like Restarts to Solve the VRPTW. European Journal of Operational Research 150, 115-127.

Mole, R.H., Jameson, S.R., 1976. A sequential route-building algorithm employing a generalized savings criterion. Operational Research Quarterly 27, 503-511.

Ombuki, B.; Ross, B.J. and Hanshar, F., 2004. Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows, Technical Report # CS-04-02, Brock University, Department of Computer Science, St. Catharines, Ontario.

Rochat, Y and Taillard, E.D., 1995. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics 1, 147-167.


Documents

Algoritmos Genéticos Aplicados a Programação de