ads:
Pontifícia Universidade Católica
do Rio de Janeiro
RENATA SARMENTO LEAL
Heurística para elaboração de Plano de Estivagem de
placas de aço em navio
Dissertação de Mestrado
Dissertação apresentada como requisito parcial para
obtenção do título de Mestre pelo Programa de Pós-
Graduação em Engenharia de Produção da PUC-
Rio.
Orientador: Prof. José Eugênio Leal
Rio de Janeiro, julho de 2005.
PUC-Rio - Certificação Digital Nº 0312525/CA
ads:
Pontifícia Universidade Católica
do Rio de Janeiro
Renata Sarmento Leal
Heurística para elaboração de Plano de Estivagem de
placas de aço em navio
Dissertação apresentada como requisito parcial para
obtenção do título de Mestre pelo Programa de Pós-
Graduação em Engenharia de Produção da PUC-Rio.
Aprovada pela Comissão Examinadora abaixo assinada.
Prof. José Eugênio Leal
Orientador
Departamento de Engenharia Industrial - PUC-Rio
Prof. Luiz Felipe Roris Rodriguez Scavarda do Carmo
Departamento de Engenharia Industrial - PUC-Rio
Prof. Elias Silva de Oliveira
Universidade Federal do Espírito Santo - UFES
Daniella Gonçalves de Barros S. de Queiroz
Companhia Siderúrgica de Tubarão
Prof. José Eugênio Leal
Coordenador Setorial do Centro Técnico Científico - PUC-Rio
Rio de Janeiro, 25 de julho de 2005.
PUC-Rio - Certificação Digital Nº 0312525/CA
Todos os direitos reservados. É proibida a reprodução total ou
parcial do trabalho sem autorização da universidade, do autor
e do orientador.
Renata Sarmento Leal
Graduou-se em Engenharia Civil pela Universidade Federal
do Espírito Santo (UFES).
Ficha Catalográfica
Leal, Renata Sarmento
Heurística para elaboração de plano de estivagem de
placas de aço em navio / Renata Sarmento Leal; orientador:
José Eugênio Leal. – Rio de Janeiro : PUC-Rio,
Departamento de Engenharia Industrial, 2005.
91 f. ; 30 cm
Dissertação (mestrado) – Pontifícia Universidade
Católica do Rio de Janeiro, Departamento de Engenharia
Industrial .
Inclui referências bibliográficas
1. Engenharia Industrial – Teses. 2. Plano de estivagem.
3. Logística. 4. Heurística. 5. Problema de empacotamento. I.
Leal, José Eugênio. II. Pontifícia Universidade Católica do
Rio de Janeiro. Departamento de Engenharia Industrial . III.
Título.
CDD: 658.5
PUC-Rio - Certificação Digital Nº 0312525/CA
ads:
Ao meu avó Helio (in memorian) e minha avó Dedé por sempre estarem presentes
em minha vida
PUC-Rio - Certificação Digital Nº 0312525/CA
Agradecimentos
Superar mais um desafio não foi uma das tarefas mais fáceis. Chegar ao final seria
praticamente impossível sem o apoio da família e dos amigos. Pretendo aqui
demonstrar meus sinceros agradecimentos a estas pessoas:
A Deus que iluminou meu caminho durante essa jornada;
Aos meus pais, Jorge e Darcilana, aos meus irmãos Aninha, Renato e Jorgeana, a
Gugu, tia Nara, tio Duda, tia Ana, vovó Dalva e vovô Jasson por terem me
apoiado durante o curso e principalmente por agüentaram minhas constantes
crises nervosas e de mau-humor.
A tia Maria do Carmo pelo carinho e atenção;
As amigas Fernadinha, Maris, Rochely por terem sido realmente AMIGAS nesses
últimos meses de dissertação;
A Alba e família pelo carinho, amizade e companheirismo durante a estada no Rio
de Janeiro;
Ao meu professor e orientador José Eugênio, pela calma e paciência nos meus
momentos de pânico!
Aos colegas de PUC, Natasa, Alessandra, Dudu e Fabio por terem tornado as
horas de estudo na “favelinha” menos estressantes;
A CST por viabilizar o desenvolvimento dessa dissertação, em especial a Daniella
e Custódio, pelo apoio, interesse e otimismo em relação ao desenvolvimento do
trabalho e por terem colocado seus preciosos tempos a minha disposição para
esclarecimento de dúvidas e troca de idéias;
A Niltinho e Bartira pelas palavras de consolo nos momentos difíceis e pelo
incentivo. Sem vocês essa dissertação poderia não ter terminado!!!!
As amigas Aline, Débora, Braga, Andréia, Marilia, D’ros, Sara, Danielly,
Adriana, Bob e Fabis que de certa forma contribuíram para a finalização deste
trabalho.
Aos funcionários, professores e colegas da PUC pelo apoio e confiança;
À CAPES pelo apoio financeiro concedido.
PUC-Rio - Certificação Digital Nº 0312525/CA
Resumo
Leal, Renata Sarmento; Leal, José Eugenio. Heurística para elaboração de
Plano de Estivagem de placas de aço em navio. Rio de Janeiro, 2005. 91p.
Dissertação de Mestrado – Departamento de Engenharia Industrial,
Pontifícia Universidade Católica do Rio de Janeiro
Essa dissertação aborda o problema da elaboração de Plano de Estivagem
de Placas de Aço, em navios, para o mercado externo. O Plano de Estivagem é
muito importante para agilizar o processo de carregamento de navios e reduzir o
laytime utilizados por esses no porto. O estudo de caso é na Companhia
Siderúrgica de Tubarão (CST). A partir do levantamento dos procedimentos
atualmente utilizados, foi desenvolvida uma heurística para elaboração de Planos
de Estivagem no Terminal de Produtos Siderúrgicos do Porto de Praia Mole. A
heurística desenvolvida foi dividida em duas etapas. Na primeira etapa, as placas
de aço são distribuídas pelos porões do navio respeitando a capacidade do mesmo
e, na segunda etapa, é determinado o layout das placas em cada porão. A
heurística proposta foi implementada em um ambiente de programação C.
Palavras-chave
Plano de Estivagem, logística, heurística, problema de empacotamento.
PUC-Rio - Certificação Digital Nº 0312525/CA
Abstract
Leal, Renata Sarmento; Leal, José Eugenio. Heuristic for Slabs Stowage
Plan elaboration in ships. Rio de Janeiro, 2005. 91p. MSc. Dissertation –
Departamento de Engenharia Industrial, Pontifícia Universidade Católica do
Rio de Janeiro
This thesis considers the problem of elaborating Slabs Stowage Plan
elaboration in ships, for international markets. The stowage plan is very important
for shipment agility and reduction of the laytime used by the ships in the port. A
case study was developed at Companhia Siderúrgica de Tubarão (CST). Based on
the procedure used today, a heuristic solution is proposed for Slab Stowage Plan
on the Steel Products Terminal (TPS) located at the port of Praia Mole. The
heuristic was divided in two parts. In the first part, respecting holds capacities,
slabs are distributed along the holds and in the second part the slabs layout in each
hold is determinate. The proposed heuristc was implemented in a C programming
language.
Keywords
Stowage Plan, logistics, heuristic, packing problem
PUC-Rio - Certificação Digital Nº 0312525/CA
Sumário
1 INTRODUÇÃO......................................................................................12
1.1. Introdução ......................................................................................12
1.2. Conceituação do problema ............................................................13
1.3. Objetivos ........................................................................................13
1.4. Delimitação do problema ...............................................................14
1.5. Composição da dissertação...........................................................14
ESTUDO DE CASO .................................................................................15
2.1. A empresa......................................................................................15
2.2. Produção de placas e bobinas.......................................................15
2.3. Etapas do processo de vendas......................................................16
2.4. Transporte de placas e bobinas.....................................................18
2.5.
Afretamento de navios ...................................................................19
2.6.
Estivagem das placas de aço em navios .......................................21
3 REVISÃO BIBLIGRÁFICA....................................................................25
3.1. Carregamento de pallets................................................................26
3.2. Carregamento de contêiner ...........................................................35
3.3. Carregamento de contêineres em navio ........................................45
4 MÉTODO HEURÍSTICO PARA ELABORAÇÃO DE PLANO DE
ESTIVAGEM DE PLACA DE AÇO ..........................................................55
4.1. Definições importantes...................................................................55
4.2. Dados de entrada do algoritimo.....................................................56
4.3. Distribuição dos itens pelos porões ...............................................57
4.3.1. Agrupamento dos itens ...........................................................57
4.3.2. Distribuição dos itens pelos porões.........................................57
4.4.
Determinação do layout das placas no porão................................57
4.4.1.Ranqueamento dos itens .........................................................57
4.4.2. Determinação das dimensões das camadas a serem carregadas
..........................................................................................................58
4.4.3. Lastreamento do porão ...........................................................61
4.4.3.1. Distribuição dos itens nas extremidades do porão............61
4.4.3.2. Carregamento do restante do lastro do porão ..................63
4.4.4. Carregamento da parte central do porão ................................67
4.4.4.1. Pré-carregamento das regiões A e C................................68
4.4.4.2. Pré-carregamento da região B..........................................69
4.4.4.3. Carregamento do 2º lastro................................................70
4.4.4.4. Procedimento para carregamento da parte central do porão70
4.5.
Resumo da heurística ....................................................................80
4.6. Teste da heurística ........................................................................82
5 CONCLUSÕES E RECOMENDAÇÕES ...............................................83
6 REFERÊNCIAS BIBLIOGRÁFICAS.....................................................85
APÊNDICE A ...........................................................................................86
PUC-Rio - Certificação Digital Nº 0312525/CA
Lista de figuras
Figura 1 – Etapas do processo de vendas ...............................................17
Figura 2 – Modais utilizados no transporte de placas e bobinas para o
Mercado Interno e Externo.......................................................................18
Figura 3 – Terminal de Produtos Siderúrgicos do Porto de Praia Mole....19
Figura 4 – Empilhadeiras utilizadas no carregamento das placas de aço nos
navios.......................................................................................................19
Figura 5 – Estivagem das placas pelo método convencional em um porão
intermediário.............................................................................................21
Figura 6 – Estivagem das placas pelo método convencional em um porão de
extremidade (popa/proa) ..........................................................................22
Figura 7 – Estivagem das placas pelo método vertical ............................22
Figura 8 – Peação das placas utilizando calços e roletes ........................23
Figura 9 – Processo padrão de geração para dois blocos .......................27
Figura 10 – Exemplo de carregamento com 2 tipos de caixa...................28
Figura 11– Exemplo de carregamento com 1 tipo de caixa com orientação
diferente ...................................................................................................29
Figura 12 – Vista superior e lateral do carregamento com 2 tipos de caixa 30
Figura 13 – Geração de superfície de carregamento ...............................30
Figura 14 – Flixograma da heurística de Bischoff ....................................32
Figura 15 – 1ª e 2ª etapas da heurística de Steudel ................................33
Figura 16 – Layout gerado pela heurística de Smith e de Cani................33
Figura 17– Divisão do pallet em 5 regiões ...............................................34
Figura 18 – Carregamento do contêiner por camada...............................36
Figura 19 – Largura Flexível.....................................................................39
Figura 20 – Os novos espaços para carregamento..................................40
Figura 21– Versão arranjo da Heurística de George e Robinson.............43
Figura 22 – Versão camada da heurística de George e Robinson...........44
Figura 23 – Composição das bays ...........................................................46
Figura 24 – Arranjo das bays do navio Columbus Olivos.........................47
Figura 25 – Formação de blocos de carga...............................................47
Figura 26 – Blocos de espaço de carga ...................................................49
Figura 27 – Alocação de contêineres nos respectivos slots.....................50
Figura 28 – Sentido de preenchimento das cells de uma determinada bay 52
Figura 29 – Definições .............................................................................55
Figura 30 – Vista superior das Regiões da “boca” e do “fora de boca” do
porão ........................................................................................................56
Figura 31 – Inclinação de 45º no lado do porão no sentido popa-proa ....58
Figura 32 – Seção transversal do porão ..................................................59
Figura 33 – Alocação das placas nos cantos do porão no sentido anti-horário
.................................................................................................................63
Figura 34 – Cálculo de P..........................................................................63
Figura 35 – Carregamento do lastro.........................................................66
Figura 36 – Divisão da parte central do porão em regiões.......................67
Figura 37 – Pré-carregamento e Carregamento Definitivo........................68
Figura 38 – Vista lateral do carregamento de duas pilhas de placas nas
Regiões A e C .........................................................................................69
PUC-Rio - Certificação Digital Nº 0312525/CA
Figura 39 – Vista lateral de duas pilhas de placas carregadas na Região C
.................................................................................................................69
Figura 40 – Cálculo de MI ........................................................................70
Figura 41 – Carregamento da região B ....................................................72
Figura 42 – Cálculo de x ..........................................................................73
Figura 43 – Divisão do 2º lastro do porão em 2 regiões nos casos em que
z > 1 e a camada de carregamento é ímpar ............................................75
Figura 44 – Divisão do 2º lastro do porão em 2 regiões nos casos em que
z > 1 e a camada de carregamento é par.................................................75
Figura 45 – Definição das distâncias D1 e D2..........................................76
Figura 46 – y > lp .....................................................................................77
Figura 47 – y < lp .....................................................................................77
Figura 48 – Alocação das placas no 2º lastro do porão para z=2 ............78
Figura 49 – Posição final das placas da região paralela a Proa...............79
Figura 50 – Resumo da heurística ...........................................................81
PUC-Rio - Certificação Digital Nº 0312525/CA
Lista de tabelas
Tabela 1 – Dimensões das placas ...........................................................15
Tabela 2 – Custo de estiva por período ...................................................24
Tabela 3 – Critérios de desempate ..........................................................37
Tabela 4 – Cálculo do “espaço que sobra”...............................................74
Tabela 5 – Distância de deslocamento ....................................................79
PUC-Rio - Certificação Digital Nº 0312525/CA
1
Introdução
1.1. Introdução
O comércio exterior tem sido um dos grandes responsáveis pelo
crescimento da economia do Estado do Espírito Santo (ES). O Estado é
privilegiado pela sua localização geográfica ficando perto dos principais centros
consumidores, produtores e distribuidores do país.
O Estado conta com um complexo portuário constituído pelos Portos de
Vitória, Tubarão, Praia Mole, Regência, Ubu e Barra do Riacho. Além disso, o
Estado conta com uma malha ferroviária (Estrada de Ferro Vitória-Minas e
Ferrovia Centro-Atlântica) e com duas rodovias federais (BR-101 e BR-262). Tais
características levaram o ES a funcionar como um corredor logístico tanto para o
mercado interno quanto para o mercado externo.
Dentre as empresas exportadoras do Estado, destacam-se a Companhia
Siderúrgica de Tubarão (CST), a Companhia Vale do Rio Doce (CVRD), a
Samarco Mineração e a Aracruz Celulose.
A CST aparece no mercado como grande exportadora de placas de aço.
Das 1.107 mil toneladas de placas de aço e bobinas a quentes comercializadas no
1º trimestre de 2005, 60% destinam ao mercado internacional, sendo os EUA o
maior consumidor.
As placas de aço da CST são distribuídas no mercado externo via
transporte marítimo. Dentre as despesas que influenciam no valor do custo de
embarque das placas no Terminal de Produtos Siderúrgicos do Porto de Praia
Mole, podemos citar: despesas com estivadores/conferentes, transporte entre a
usina e o porto, peação, empilhadeiras, Demurrage/Despatch, entre outros.
O fator responsável pelo aumento dos custos de embarque das placas de
aço no Porto de Praia Mole é o custo de demurrage não orçado. O demurrage é
uma multa paga pelo Afretador ao Armador devido à retenção do navio no porto
além do prazo estabelecido para embarque e desembarque de carga. Um dos
fatores que pode reduzir o tempo de permanência dos navios no porto e
consequentemente, reduzir os custos de estadia do navio, é a elaboração do Plano
de Estivagem que possa tornar o processo de estivagem mais rápido.
PUC-Rio - Certificação Digital Nº 0312525/CA
13
1.2. Conceituação do problema
Esta dissertação aborda o problema da elaboração de Plano de
Estivagem de Placas de Aço, em navios, da Companhia Siderúrgica de Tubarão
(CST). A proposta deste estudo é desenvolver uma heurística para elaboração de
Plano de Estivagem, a partir do conhecimento adquirido junto aos profissionais da
empresa. Deseja-se que a elaboração do Plano de Estivagem se torne uma tarefa
rápida e de fácil execução quando comparada com o método atual utilizado pela
CST.
A motivação da pesquisa se deve ao fato de que, atualmente, o Plano de
Estivagem é feito manualmente por uma empresa terceirizada tornando o processo
uma tarefa difícil e demorada (cerca de 4 horas) devido às restrições que devem
ser obedecidas. Por ser um serviço terceirizado, a CST confia nos planos
elaborados, sem ter uma idéia clara da metodologia utilizada para elaboração dos
mesmos. Além disso, não foram encontrados, na literatura, estudos abordando o
tema de Estivagem de placas de aço em navios, sendo os estudos existentes
limitados ao carregamento de caixas em pallets (Bischoff et al. (1995) e Bischoff
e Dowsland (1982)), caixas em contêineres (George e Robinson (1980)) e
contêineres em navio (Wilson el al. (2001) e Gifford et al. (1988)).
1.3. Objetivos
O objetivo deste projeto é auxiliar a empresa com a criação de um
procedimento para elaboração do Plano de Estivagem de placas de aço no Porto
de Praia Mole, de forma a agilizar o processo, ou seja, gerar Planos de Estivagem
de uma forma rápida, confiável e transparente. Para isso, será desenvolvida uma
heurística para elaboração de Planos de Estivagem de placas de aço obedecendo-
se às restrições que serão apresentadas no Capítulo 4. A heurística proposta deve
evitar a mistura de itens (placas diferentes) no porão, levando em consideração a
forma de carregamento do mesmo.
A heurística proposta foi implementada em um ambiente de programação
C e os dados de teste foram coletados junto ao Departamento de Logística da
CST.
PUC-Rio - Certificação Digital Nº 0312525/CA
14
1.4. Delimitação do problema
O presente estudo está focado no caso de Estivagem Convencional de
placas de aço com mesma espessura (200, 225 ou 250mm). Os porões do navio
serão considerados com seção horizontal retangular. Para a elaboração do Plano
de Estivagem deverá ser usado o Plano de Carga, que funcionará como restrição
de capacidade do porão. A ordem de carregamento dos porões é estabelecida pelo
comandante do navio, porém a forma de carregamento de cada porão é
determinada pela heurística desenvolvida. Pode-se ter em um navio apenas carga
de um cliente. Além disso, considera-se que todas as placas do pedido do cliente
estão armazenadas no Terminal de Produtos Siderúrgicos (TPS).
1.5. Composição da dissertação
A dissertação está estruturada como se segue:
No capítulo 2 é apresentado o Estudo de Caso da CST onde são explicadas
as etapas que antecedem a elaboração do Plano de Estivagem.
No capítulo 3 é feita uma revisão bibliográfica mais relevante sobre o
assunto de Problemas de Empacotamento.
No capítulo 4, propõe-se a heurística para elaboração do Plano de
Estivagem.
No capítulo 5, são feitas as considerações finais sobre o trabalho,
comentários sobre os resultados encontrados e sugestões para trabalhos futuros.
PUC-Rio - Certificação Digital Nº 0312525/CA
2
ESTUDO DE CASO
2.1.
A empresa
A Companhia Siderúrgica de Tubarão (CST) está localizada na região da
Grande Vitória, Estado do Espírito Santo. A empresa fabrica e comercializa
Placas de Aço e Bobinas de Aço Laminadas a Quente cuja a previsão de produção
até o final do ano de 2005 é de 2.588.530t de Placas e 2.327.420t de Bobinas.
As Placas são produtos semi-manufaturados para posterior laminação em
produtos planos. Dentre as diversas áreas de utilização das Placas de Aço
podemos citar: Indústria Automobilística, Eletrodomésticos, Indústria Naval,
Construção Civil, entre outros.
As dimensões das placas produzidas na empresa são apresentadas na
Tabela 01:
Tabela 01: Dimensões das placas
Espessura 200, 225 ou 250mm
Comprimento 5000 a 12.500mm
Largura 800 a 2.100mm
2.2.
Produção de Placas e Bobinas
Resumidamente, podemos descrever a fabricação das placas de aço e
bobinas da seguinte forma:
O carvão mineral é transformado em coque na Coqueria e o minério de
ferro é transformado em sinter na Sinterização. O coque, o sinter, o minério de
ferro em pelota, entre outros materiais, são levados ao alto-forno para a produção
do ferro gusa (ferro líquido). O ferro gusa é transportado por meio de carro-
torpedo, onde sofre o processo de pré-refino conhecido como Dessulfuração.
Após este processo, o carro torpedo transporta esse material até o convertedor na
Aciaria. No convertedor, inicia-se o processo de transformar o ferro-gusa em aço,
também conhecido como Refino Primário. Entre o convertedor e o Lingotamento,
existe uma etapa denominada Refino Secundário, onde é feito o ajuste de
composição química e da temperatura do aço líquido. A próxima etapa ocorre na
PUC-Rio - Certificação Digital Nº 0312525/CA
16
Máquina de Lingotamento Contínuo (MLC), onde ocorre o processo de
resfriamento controlado do aço líquido, vazado em molde, solidificando-o em
forma e dimensões previamente definidas, de forma totalmente automatizada. Da
MLC, as placas seguem via modal rodoviário para o Terminal de Produtos
Siderúrgicos (TPS) do Porto de Praia Mole onde são embarcadas para o mercado
externo. As placas de aço que serão utilizadas para fabricação de bobinas são
encaminhadas para o Laminador de Tiras a Quente (LTQ), na qual as placas são
transformadas em bobinas de aço com pequenas espessuras. Do LTQ, as bobinas
seguem para a Linha de Acabamento onde passam por um processo de
acabamento e sofrem a inspeção de qualidade superficial. Após esse processo, as
bobinas estão prontas para serem despachadas para os clientes no mercado externo
e interno.
2.3.
Etapas do processo de vendas
O cliente solicita ao Departamento de Vendas uma proposta de venda para
um determinado pedido. Este por sua vez solicita ao Departamento de Logística
uma estimativa do valor do frete. O Departamento de Logística contacta os
representantes dos Armadores
A
(brokers) para a realização da cotação de preço do
frete e analisa as proposta para posterior encaminhamento da melhor oferta a
Vendas que repassa ao cliente.
As etapas do processo de vendas podem ser resumidas conforme a figura 01:
A
É a pessoa física/jurídica que coloca a embarcação nas condições necessárias para
que possa ser carregada em sua finalidade comercial, e que opera comercialmente,
pondo a embarcação ou a retirando da navegação por sua conta.
PUC-Rio - Certificação Digital Nº 0312525/CA
17
As vendas são realizadas de duas maneiras:
· CRF-FO – A CST é responsável pela contratação do transporte, ou
seja, é ela quem paga os custos e o frete relativos ao transporte da
mercadoria até seu destino. Porém, a partir do embarque da
mercadoria no navio, o cliente é responsável por eventuais custos
de perda ou avaria da mercadoria. O custos referentes a descarga da
mercadoria também são de responsabilidade do cliente;
· FOB – O cliente é responsável pela contratação do transporte
enquanto que a CST fica responsável pelo embarque da carga no
navio. Ao término do carregamento, o comando do navio emite
uma documentação atestando o embarque da mercadoria. A partir
deste momento a responsabilidade pela carga não é mais do
vendedor.
CLIENTE
V
ENDAS
LOGISTICA
Solicita proposta de
venda
Solicita cota
ç
ão de
frete
Contacta
pre
ç
o
Repassa melhor pre
ç
o
Enviar
p
ro
p
osta
BROKERS
Figura 01 – Etapas do processo de vendas
PUC-Rio - Certificação Digital Nº 0312525/CA
18
2.4.
Transporte de Placas e Bobinas
As placas e bobinas são transportadas dos pátios da CST para o Porto de
Praia Mole por meio de caminhões com capacidade de 100t.
Os clientes de placas de aço no Mercado Externo recebem a carga via
transporte marítimo de longo curso. Essa comercialização é feita principalmente
com a América do Norte e Ásia.
Os clientes de bobinas, no Mercado Interno, recebem a carga via
cabotagem, modal rodoviário e ferroviário.
A figura 02 ilustra os modais utilizados no transporte de placas e bobinas
para o Mercado Interno e Externo.
O Terminal de Produtos Siderúrgicos (TPS) do Porto de Praia Mole é
administrado por um condomínio e é de propriedade da CST, Gerdau, Açominas e
Usiminas. O TPS é constituído por um cais de 638m de extensão e 14.5m de
profundidade, sendo dividido em 3 berços para atracação. Dispõe de 8
equipamentos para embarque da carga no navio sendo: 5 guindastes com
capacidade para 42t e 3 guindastes para capacidade de 25 t. Além disso, conta
com uma retro-área portúaria de 400.000m
2
e um pool de 32 empilhadeiras
V
ITÓRIA
CST
SÃO PAULO
SÃO FRANCISCO DO SUL
RS
SC
PR
SP
MG
RJ
BELO
HORIZONTE
Oceano Atlântico
ES
CVRD/FCA
MRS
ALL
Rodovia
CAMPINAS
ARAUCÁRIA
VEGA
GVSP
CDSP
CDM
Ponta
Rodoviária
Exportação
Cabotagem
Barcaças
Figura 02 – Modais utilizados no transporte de placas e bobinas para o Mercado Interno e Externo
Fonte: CST
PUC-Rio - Certificação Digital Nº 0312525/CA
19
contratadas. O Terminal de Produtos Siderúrgicos e as empilhadeiras contratadas
são apresentados nas figuras 03 e 04.
2.5.
Afretamento de navios
Normalmente, a CST afreta navios tipo “Hand Size” ou “Panamax” na
categoria Bulk Carrier (navios projetados para o transporte de carga geral) ou
Figura 03 – Terminal de Produtos Siderúrgicos do Porto de Praia Mole
Fonte: CST
Figura 04 – Empilhadeiras utilizadas no carregamento das placas de
aço nos navios
Fonte: CST
PUC-Rio - Certificação Digital Nº 0312525/CA
20
Graneleiro (navios voltados para o carregamento de granéis). Os navios “Hand
Size” são aqueles com DWT
B
até ±50.000t e comprimento total do navio (LOA) =
200m. Os navios “Panamax” são navios com DWT até 75.000t, geralmente com
LOA acima de 220m.
Os navios são afretados por viagem e, para isso, a CST entra em contato
com os representantes dos armadores (Broker) para solicitar a cotação. É
necessário informar ao Broker, o porto de carregamento e o porto de destino da
carga, bem como a tonelagem a ser transportada com sua respectiva tolerância e o
período que o navio tem que chegar ao porto. A tolerância da carga define os
limites superior e inferior de um carregamento. Por exemplo, um carregamento de
50.000ton ± 5% significa que o navio deverá carregar no máximo 52.500 e no
mínimo 47.500ton. Se o carregamento for inferior a 47.500t, o embarcador deverá
pagar um valor relativo à diferença entre a carga mínima e a carga carregada. Esse
valor é conhecido como frete morto. As condições para o transporte marítimo da
carga são estabelecidas através do contrato denominado Charter Party.
Após a contratação do navio, este tem um prazo, em dias, estipulado
durante as negociações do afretamento para chegar ao porto de carregamento. Este
prazo é conhecido como laydays. Ao chegar ao porto, o agente do navio entrega
ao Afretador um documento chamado de Notice of Readiness (NOR) no qual o
Afretador é notificado de que o navio se encontra no porto e está pronto para
atracar e executar o carregamento/descarregamento da carga. Assim que o
Afretador aceitar o NOR, inicia-se a contagem do Laytime. Entende-se por
Laytime o tempo acordado entre o Afretador e o Armador, no qual o navio estará
disponível para carregamento e descarregamento. Caso o Afretador ultrapasse o
prazo estipulado pelo Laytime para o carregamento/descarregamento da carga, ele
paga ao Armador uma “multa” denominada Demurrage, que é proporcional ao
tempo de atraso. Caso o carregamento/descarregamento, tenha sido realizado em
um tempo inferior ao Laytime, o Afretador recebe do Armador um “prêmio”
denominado Despatch, proporcional ao tempo de adiantamento. O Laytime é
calculado conforme o total de carga a ser carregado e a prancha de carregamento
(quantidade de carga a ser embarcada em um determinado período,
B
Denominação dada ao peso total que pode ser colocado no navio (peso da carga
transportada + combustível + tripulação que o navio pode carregar até o máximo
permitido para sua segurança).
PUC-Rio - Certificação Digital Nº 0312525/CA
21
frequentemente estabelecida em tonelagem/dia). Por exemplo, um navio que é
contratado para carregar 50.000t com uma prancha diária de 5.000t, terá um
laytime igual a 50.000/5.000 = 10 dias.
Ao final do embarque/desembarque da carga, o comandante do navio
apresenta um documento denominado Statement of Facts que inclui um histórico
completo sobre a chegada, estadia e saída do navio no porto.
2.6.
Estivagem das placas de aço em navios
A partir da atracação do navio em um dos 3 berços dos Porto de Praia
Mole, inicia-se o processo de carregamento da carga no navio. O comandante do
navio fornece à CST um Plano de Carga (Pré-stowage plan) no qual fica
determinado a quantidade de carga, em toneladas, que deverá ser colocada em
cada porão. Respeitando essa restrição, a CST elabora o Plano de Estivagem, que
consiste em distribuir as placas pelos porões e determinar o layout das mesmas no
porão.
Atualmente, a CST utiliza dois tipos de estivagem: Convencional e
Vertical.
ü Convencional: Consiste em colocar as placas em camadas
horizontais, lastreando toda a área do porão. É utilizada na maioria
dos casos. As figuras 05 e 06 ilustram este tipo de estivagem.
Figura 05 - Estivagem das placas pelo método convencional em um porão intermediário
PUC-Rio - Certificação Digital Nº 0312525/CA
22
ü Vertical: Consiste em estivar as placas em pilhas. É utilizada
somente para a Califórnia Steel nos Estados Unidos. A figura 07
ilustra este tipo de estivagem.
Conforme citado anteriormente, o embarque das placas no navio é feito de
acordo com o Plano de Estivagem. Porém, o comandante do navio é quem
determina a ordem de carregamento dos porões. Geralmente, carrega-se dois
Figura 06 - Estivagem das placas pelo método convencional em um porão
de extremidade (popa/proa)
Figura 07 - Estivagem das placas pelo método vertical
Fonte: CST
PUC-Rio - Certificação Digital Nº 0312525/CA
23
porões simultaneamente. Essa medida é tomada para evitar que a movimentação
da carga afete a estabilidade do navio.
A peação
C
das placas no navio é feita utilizando-se calços (entre placa e
piso) e roletes (entre placas) de madeira, conforme a figura 08.
Dentre os componentes que influenciam o Custo de Embarque das Placas
no Porto de Praia Mole, podemos citar:
ü Estiva/conferência – trabalhadores avulsos que manuseiam a
carga dentro do porão do navio;
ü Peação – amarração das cargas dentro do porão do navio;
ü Equipamentos – empilhadeiras para manuseio das placas;
ü Serviços de doqueiros – trabalhadores que preparam a carga em
terra para ser içada para dentro do navio.
C
Fixação da carga nos porões a fim de evitar a varia da carga.
Calço
Rolete Rolete
Figura 08 – Peação das placas utilizando calços e roletes
Fonte: CST
PUC-Rio - Certificação Digital Nº 0312525/CA
24
O custo de Estiva/conferência é o mais representativo. Ele varia conforme
a tabela abaixo:
Tabela 02: Custo de Estiva por período
Dia Período Valor
07 – 19h Normal Segunda/Sexta
19 – 07h Normal * 1,25
07 – 19h Normal Sábado
19 – 07h Normal * 1,875
07 – 19h Normal * 1,875 Domingo
19 – 07h Normal * 2,344
07 – 19h Normal * 2 Feriado
19 – 07h Normal * 2,5
Fonte: CST
O Plano de Estivagem é de fundamental importância para aumentar a
velocidade de embarque da carga, e consequentemente, diminuir a permanência
do navio em operação, o que acarreta menores custos de estadia do próprio navio
e dos demais navios que aguardam para atracar. O aumento do índice de
carregamento
D
do navio significa um maior planejamento operacional de
embarque, que permite que os navios trabalhem sem interrupção de carga. Para
isso, independente da chegada do navio ao porto, as cargas devem ser transferidas
da área de produção da Usina para o Pátio do porto tão logo os lotes sejam
concluídos.
O próximo capítulo apresentará a Revisão Bibliográfica sobre os
Problemas de Corte e Empacotamento que nesta dissertação são tratados como
Problemas de Estivagem.
D
Compreende a tonelagem embarcada dividido pelo tempo de permanência do navio no
cais do porto.
PUC-Rio - Certificação Digital Nº 0312525/CA
3
REVISÃO BIBLIOGRÁFICA
Problemas de Corte e Empacotamento (PCE) são, em geral, problemas de
otimização combinatória cujo objetivo é achar o arranjo ótimo de unidades
menores (itens) dentro de unidades maiores (objetos). Os PCE aparecem na
literatura com diferentes nomes, tais como: carregamento de pallet, carregamento
de contêiner, Problema da Mochila, Bin Packing, Problema de corte de materiais,
entre outros (Dyckhoff, 1990).
O Problema de Bin Packing consiste em empacotar objetos de diferentes
tamanhos ou pesos, no menor número possível de bins (caixas) com capacidade
fixa (C). Considera-se que os bins são indexados (1, 2, 3, 4,...) conforme a ordem
de criação dos mesmos.
Coffman et al (1998) considera que os algoritmos utilizados para resolver
os Problemas de Bin Packing são classificados como:
· On-line – os objetos são empacotados na ordem que chegam, sem o
conhecimento dos demais objetos que serão empacotados;
· Off-line – todos os objetos a serem empacotados são conhecidos
antes de se iniciar o processo de empacotamento e são
armazenados em uma lista L.
Existem quatro algoritmos clássicos para o Problema de Bin Packing, que
são os seguintes:
· Next Fit (NF) – o primeiro objeto da lista é alocado em um bin. Os
demais objetos são empacotados nesse mesmo bin até a capacidade
do mesmo ser alcançada. Assim que a restrição de capacidade (C) é
atingida, esse bin é fechado e um novo bin é aberto continuando-se
o empacotamento dos objetos;
· First Fit (FF) – os bins são considerados parcialmente cheios e o
próximo objeto da lista é alocado no primeiro bin que comporta o
objeto sem ultrapassar a capacidade (C) do mesmo. Um novo bin
só é aberto quando o objeto não couber em nenhum outro bin que
está sendo utilizado;
· Best Fit (BF) – o objeto é colocado no bin mais cheio onde ele
cabe. Se não houver nenhum bin aberto que comporte o objeto, um
PUC-Rio - Certificação Digital Nº 0312525/CA
26
novo bin é aberto. Se houver empate entre bins, o critério de
desempate é feito escolhendo o bin de menor indexação;
· Worst Fit (WF) – o objeto é colocado no bin mais vazio onde ele
cabe. O critério de desempate utilizado é feito escolhendo o bin de
menor indexação. Se não houver nenhum bin aberto que comporte
o objeto, um novo bin é aberto.
Ao invés de empacotarmos os objetos na ordem que eles aparecem na
lista, podemos ordená-los em ordem decrescente de peso ou tamanho e
assim, realizar o empacotamento dos mesmos. Utilizando essa regra, os
procedimentos acima se transformam em NFD (Next Fit Decreasing), FFD
(First Fit Decreasing), BFD (Best Fit Decreasing) e WFD (Worst Fit
Decreasing).
O objetivo deste capítulo é apresentar alguns métodos utilizados em
problemas de Empacotamento que nessa dissertação serão tratados como
Problemas de Estivagem. Foram estudados três tipos de Estivagem:
· Pallets;
· Contêineres;
· Contêineres em navios.
3.1.
Carregamento de pallets
Bischoff et all. (1995) consideraram o Problema de Carregamento de
Pallet do Distribuidor, ou seja, empacotar n tipos diferentes de caixas retangulares
com dimensões l
i
(comprimento) x w
i
(largura) x h
i
(altura) e quantidade m
i
(i =
1,..., n) em um pallet de dimensão L (comprimento) x W (largura). O objetivo do
carregamento é maximizar o volume empacotado respeitando a altura limite do
carregamento (H).
O procedimento proposto consiste em carregar o pallet em camadas
horizontais, de baixo para cima e com, no máximo, dois tipos de caixas por
camada.
Inicialmente, a heurística proposta gera todos os carregamentos possíveis
da superfície do pallet, escolhendo o arranjo que apresentar maior ocupação
superficial. Os carregamentos possíveis são formados por carregamentos gerados
PUC-Rio - Certificação Digital Nº 0312525/CA
27
por um único tipo de caixa ou pela combinação de dois tipos de caixa. Não existe
restrição quanto a orientação da caixa.
CARREGAMENTO DA SUPERFÍCIE
A figura 09 ilustra umas das possíveis formas de carregamento da
superfície do pallet com dois tipos diferentes de caixas. O processo de geração em
questão é para dois blocos que particionam o comprimento L do pallet. Os blocos
são formados por caixas do tipo j e do tipo k. Os lados referentes ao comprimento
das caixas (S
L
e T
L
comprimento das caixas j e k, respectivamente) são paralelos
ao comprimento do pallet. Considerando que S
L
≥ T
L
, as alternativas de
carregamento podem ser geradas a partir da expansão do Bloco 1 e com o
preenchimento da superfície restante (Bloco 2) com caixas do tipo k, respeitando a
quantidade existente deste tipo de caixa.
Se l representa a quantidade de caixas do tipo j que podem ser colocadas
lado a lado no Bloco 1 com comprimento paralelo L (comprimento da superfície),
então l pode assumir valores inteiros entre 0 e o menor valor entre
þ
ý
ü
î
í
ì
÷
ø
ö
ç
è
æ
-
L
j
S
L
m ,
E
onde mj representa o número de caixas do tipo j. Sendo l > 0, o número de caixas
que podem ser alocadas na outra direção é dado pelo menor valor entre
E
-
÷
ø
ö
ç
è
æ
L
S
L
retorna o próximo menor valor inteiro ao se arredondar o valor para baixo
W
Tipo j
Tipo k
S
L
S
W
T
W
T
L
L
Bloco 1 Bloco 2
Figura 09 – Processo padrão de geração para dois blocos
Fonte:
Bischoff (1995)
PUC-Rio - Certificação Digital Nº 0312525/CA
28
ï
þ
ï
ý
ü
ï
î
ï
í
ì
÷
ø
ö
ç
è
æ
÷
ø
ö
ç
è
æ
-
-
W
j
S
W
l
m
,
F
. Um bloco de
()
-
þ
ý
ü
î
í
ì
÷
ø
ö
ç
è
æ
*
ú
û
ù
ê
ë
é
*-
WL
L
T
W
T
SlL
G
caixas do tipo k
podem ser colocadas na área restante.
Exemplo 1: Carregamento com dois tipos de caixa (figura 10)
Dimensões do Pallet
W 120cm
L 160cm
Caixas do tipo j
m
j
30
S
L
35cm
S
W
30cm
Caixas do tipo k
m
k
25
T
L
20cm
T
W
30cm
F
-
-
÷
ø
ö
ç
è
æ
÷
ø
ö
ç
è
æ
W
j
S
W
l
m
,
retorna o próximo menor valor inteiro ao se arredondar o valor para
baixo
G
()
-
þ
ý
ü
î
í
ì
÷
ø
ö
ç
è
æ
*
ú
û
ù
ê
ë
é
*-
WL
L
T
W
T
SlL
retorna o próximo menor valor inteiro ao se arredondar o valor
para baixo
(L/S
L
)
-
= 4
l = min {30; 4} = 4
l pode assumir valores inteiros entre [0, 4]
Assumindo l = 4, ou seja, 4 caixas com
comprimento paralelo a L, calcularemos a
quantidade de caixas na direção W.
(m
j
/l)
-
= 7
(W/ S
W
)
-
= 4
A quantidade de caixas com a largura
paralela a W é 4.
A quantidade de caixas tipo k no bloco 2 é
de [(160-4*35)/20]*[120/30]
-
= 4
Figura 10 – Exemplo de carregamento com 2 tipos de caixa
j
k
S
w
S
l
T
w
T
l
W
L
PUC-Rio - Certificação Digital Nº 0312525/CA
29
No caso da camada ser carregada pelo mesmo tipo de caixa porém com
orientação diferente, a única diferença em relação ao processo do carregamento
com 2 caixas é que temos que subtrair de m
k
a quantidade de caixas que foram
alocadas no Bloco 1 e assim sucessivamente.
Exemplo 2: Carregamento com um tipo de caixa com orientação diferente (figura
11)
Dimensões do Pallet
W 100cm
L 120cm
Caixas do tipo j
m
j
50
S
L
30
S
W
20
Caixas do tipo k
m
j
’ -
T
L
20
T
W
30
(L/S
L
)
-
= 4
l = min {50; 4} = 4
l pode assumir valores inteiros entre [0,
4]
Assumindo l = 2, ou seja, 2 caixas com
comprimento paralelo a L, calcularemos
a quantidade de caixas na direção W.
(m
j
/l)
-
= 25
(W/ S
W
)
-
= 5
A quantidade de caixas com a largura
paralela a W é 5.
O total de caixas do tipo j é igual a 10.
Atualizando o nº de caixas do tipo j
temos: m
j
’= 50-10 = 40
A quantidade de caixas tipo k no bloco 2
é de [(120-2*30)/20]*[100/30]
-
= 9
Figura 11 – Exemplo de carregamento com 1 tipo de caixa com orientação diferente
j
k
S
w
S
l
T
w
T
l
L
W
PUC-Rio - Certificação Digital Nº 0312525/CA
30
SUPERFÍCIES DE CARREGAMENTO
Novas superfícies de carregamento são criadas assim que uma camada é
carregada. Essas superfícies são armazenadas na lista de superfícies potenciais de
carregamento. Quando o carregamento é feito com dois tipos de caixa, podem ser
geradas até 2 novas superfícies de carregamento. Essas superfícies são mais altas
do que a anterior. Além disso, existe a necessidade de se gerar superfícies de
carregamento a partir de áreas não-utilizadas no carregamento anterior. A figura
12 exemplifica a geração de superfícies potencias de carregamento.
A heurística proposta por Bischoff procura evitar a formação de
superfícies longas e finas devido à dificuldade para carregar esse tipo de
superfície. No caso ilustrado na figura 13, a heurística escolheria como superfície
de carregamento A e B ao invés de C e D pois C é uma superfície longa e fina a
qual a heurística tende a evitar.
Figura 13 – Geração de superfícies de carregamento
1ª nova
superfície de
carregamento
2ª nova
superfície de
carregamento
Superfície de
carregamento
anterior
Figura 12 - Vista superior e lateral do carregamento com 2 tipos de caixa
Superfície carregada
Superfície carregada
Superfície carregada
A
B
D
C
PUC-Rio - Certificação Digital Nº 0312525/CA
31
Além de evitar a formação de superfícies longas e finas, a heurística busca
a estabilidade do carregamento, priorizando o carregamento das superfícies mais
baixas.
Quando a superfície selecionada para carregamento não comportar
nenhuma das caixas que ainda podem ser empacotadas, essa superfície é
descartada.
A desvantagem da heurística de Bischoff é a possibilidade de ocorrência
da fragmentação das superfícies de carregamento nas etapas iniciais do algoritmo.
Quando é utilizado o padrão de geração por dois blocos, duas novas superfícies
(menores ou iguais à original) são geradas acima dos blocos atuais e assim
sucessivamente, gerando uma fragmentação das superfícies de carregamento, o
que dificulta o carregamento de caixas maiores.
Para minimizar o problema, o algoritmo verifica a possibilidade de unir as
superfícies facilitando assim o carregamento da mesma. Duas superfícies só
podem ser unidas se apresentarem a mesma altura e se forem adjacentes.
O algoritmo termina quando não existem superfícies a serem carregadas ou
quando não existem caixas para serem empacotadas.
A figura 14 resume a heurística proposta por Bischoff.
.
PUC-Rio - Certificação Digital Nº 0312525/CA
32
Bischoff e Dowsland (1982) propuseram uma heurística para carregamento
de pallets do produtor baseado na heurística proposta por Smith e De Cani (1980)
e Steudel (1979).
O Problema de Carregamento de Pallet do Produtor consiste em arranjar
ortogonalmente e sem sobreposição caixas com comprimento a e largura b sobre
pallet com comprimento A e largura B.
Atualizar a lista das superfícies
potenciais de carregamento, retirando
da lista a superfície utilizada no último
carregamento
Definir lista de caixas não empacotadas
Definir o fundo do pallet como
superfície inicial de carregamento
Checar a lista de caixas não
empacotadas
Checar a lista de superfícies potenciais
de carregamento
Selecionar para carregamento a
superfície mais baixa
Determinar a máxima utilização da
superfície com, no máximo, dois tipos
de caixa
Empacotar a superfície com as caixas
escolhidas no passo anterior
Atualizar a lista das caixas não
empacotadas, retirando da lista as
caixas utilizadas no passo anterior
Final
Final
Excluir a
superfície da
lista
Lista estiver
vazia
Lista estiver
vazia
Util = 0
Figura 14 – Fluxograma da heurística de Bischoff
Fonte: Bischoff (1995)
PUC-Rio - Certificação Digital Nº 0312525/CA
33
A heurística proposta por Steudel divide o pallet em até quatro regiões
retangulares ou blocos. Dentro de cada bloco, as caixas possuem orientação pré-
fixada. A dimensão desses blocos é determinada em duas etapas. O objetivo da
primeira etapa é maximizar a utilização do perímetro do pallet e na 2ª etapa são
feitas modificações nas dimensões dos blocos a fim de tentar o preenchimento da
parte central do pallet. A heurística escolhe o layout gerado com o maior número
de caixas como o padrão. As etapas da heurística são ilustradas na figura 15.
A heurística proposta por Smith e De Cani também divide o pallet em até
quatro regiões retangulares e a orientação das caixas dentro de cada região é pré-
fixada. A heurística avalia todas as possibilidades de variação das dimensões dos
blocos, inclusive a possibilidade de dimensão nula e retorna o padrão que tiver o
maior número de caixas carregadas. As restrições existentes nessa heurística
impedem a geração de layouts com sobreposição de caixas. A figura 16 ilustra um
layout gerado pela heurística.
B1
B
2
B
3
B
4
B4
B1
B2
B3
Figura 15 – 1ª e 2ª etapas da Heurística de Steudel
Fonte: Bischoff e Dowsland (1982)
Figura 16 – Layout gerado pela Heurística de Smith e de Cani
Fonte: Bischoff e Dowsland (1982)
PUC-Rio - Certificação Digital Nº 0312525/CA
34
Baseado nas heurísticas descritas anteriormente, Bischoff e Dowsland
propuseram uma heurística que divide o pallet em até 5 regiões aproveitando a
região, que, pelas heurísticas anteriores, ficava vazia.
As dimensões das áreas 1, 2, 4 e 5 da figura 17 determinam a dimensão da
área 3.
Na 1ª etapa da heurística, são calculadas partições eficientes do
comprimento A e da largura B do pallet. Essas partições são definidas como uma
combinação (n, m) (números inteiros não negativos) de caixas de comprimento a e
largura b que devem satisfazer as seguintes condições:
na + mb ≤ S
S - na - mb ≤ b
onde:
· S é a dimensão do lado do pallet que está sendo considerada;
· b é a menor dimensão da caixa;
· n é a quantidade de caixas em uma área do pallet com
comprimento paralelo ao lado do pallet;
· m é a quantidade de caixas em uma área do pallet com largura
paralela ao lado do pallet.
Na 2ª etapa da heurística, são gerados os layouts a partir das partições
eficientes dos quatro lados do pallet gerado na etapa anterior.
A
1
A
4
Área 5
Área 2
Área 4
Área 1
Área 3
A
5
A
2
B
2
B
1
Área 2
a
Figura 17 – Divisão do pallet em 5 regiões
Fonte: Bischoff e Dowsland (1982)
A
B
B
5
B
4
b
PUC-Rio - Certificação Digital Nº 0312525/CA
35
O autor denominou (n
L
, m
L
) e (n
R
, m
R
) as partições eficientes do lado
esquerdo e do lado direito do pallet, respectivamente. Os lados de cima e de baixo
foram denominados de (n
T
, m
T
) e (n
B
, m
B
).
As áreas 1, 2, 4 e 5 da figura 17 são alocadas nos cantos do pallet e tem
suas dimensões definidas por:
A1 = n
L
a B1 = m
T
b
A2 = m
R
b B2 = n
T
a
A4 = m
L
b B4 = n
B
a
A5 = n
R
a B5 = m
B
b
A região 3 é a região restante do pallet. A heurística calcula quantas caixas
e em que posição (horizontal ou vertical) as caixas serão dispostas na Região 3.
As seguintes condições devem ser evitadas a fim de não ocorrer a
sobreposição de áreas:
A– A
1
- A
5
< 0 e B– B
1
- B
5
< 0
ou
A– A
2
- A
4
< 0 e B– B
2
- B
4
< 0
3.2
Carregamento de Contêiner
George e Robinson (1980) consideraram o Problema de Carregamento de
Contêiner cujo objetivo é carregar i tipos de caixas diferentes com dimensões l
i
(comprimento) x w
i
(largura) x h
i
(altura) e quantidade conhecida (b
i
) dentro de
um contêiner dimensão com
L (comprimento) x W (largura) x H (altura). O
problema consiste em achar uma ordem de carregamento e a posição das caixas
dentro do contêiner de forma a otimizar o aproveitamento do espaço do contêiner.
Mesmo que a soma dos volumes das caixas seja menor que o volume do
contêiner, é possível que alguma(s) caixa(s) não seja(m) empacotada(s) devido ao
arranjo geométrico das mesmas.
Nesta heurística, as caixas são empilhadas em camadas verticais ao longo
da largura do contêiner (W) e a partir de uma das paredes do mesmo, conforme a
figura 18. Não é feita nenhuma restrição em relação à quantidade de caixas que
podem ser empilhadas umas sobre as outras. É desejável que caixas do mesmo
tipo sejam colocadas próximas uma das outras.
PUC-Rio - Certificação Digital Nº 0312525/CA
36
O contêiner é preenchido camada por camada e uma nova camada só é
criada quando a camada atual estiver carregada.
A Heurística proposta por George e Robinson pode ser dividida em cinco
etapas:
1ª etapa: Achar o primeiro tipo de caixa a ser carregada em uma nova
camada e o tamanho da profundidade da camada;
2ª etapa: Definir a altura e a largura da caixa que será utilizada e a
quantidade de caixas empacotadas;
3ª etapa
: Criar novos espaços de carregamento;
4ª etapa
: Escolher o novo espaço de carregamento;
5ª etapa
: Achar o tipo de caixa para preencher os espaços vazios já
existentes nas camadas e o tamanho da profundidade.
Antes de explicarmos passo-a-passo a heurística proposta, iremos
introduzir o conceito de “ranqueamento das caixas” que será utilizado em alguns
passos da heurística. O ranqueamento das caixas é feito da seguinte forma:
primeiramente, escolhe-se a caixa com a maior entre as menores dimensões.
Havendo empate neste critério, escolhe-se o tipo de caixa de maior quantidade. E
como último critério de desempate, escolhe-se a caixa com maior dimensão. O
exemplo ilustrado na tabela 03 esclarece os critérios de desempate:
Figura 18 – Carregamento do contêiner por camada
PUC-Rio - Certificação Digital Nº 0312525/CA
37
Caixas Quantidade
(b
i
)
Comprimento
(l
i
)
Largura
(w
i
)
Altura
(h
i
)
Menor
dimensão
1 12 7 3 4 3
2 12 6 3 3 3
3 14 5 4 5 4
4 16 5 5 6 5
Neste caso, a primeira caixa a ser empacotada é a caixa 4, seguida pela
caixa 3. As caixas 1 e 2 ficaram empatadas tanto em relação ao critério caixa com
maior entre as menores dimensões quanto em relação ao critério quantidade. O
desempate entre as caixas ocorre em relação ao critério caixa com maior dimensão
devendo a caixa 1 ser empacotada antes da caixa 2. Portanto, a ordem de
carregamento
é:
Passo-a-passo da heurística:
1ª etapa: Achar o primeiro tipo de caixa a ser carregada em uma nova camada e o
tamanho da profundidade da camada.
Entende-se por camada de carregamento uma seção do comprimento do
contêiner (L) na sua completa altura H e largura W. A seção do comprimento do
contêiner utilizada é denominada profundidade da camada.
Os tipos de caixas podem ser classificados como
“aberta” (quando um
determinado tipo de caixa já foi utilizado no carregamento) ou como “
fechada”
(quando um tipo de caixa ainda não foi utilizado no carregamento).
Para iniciar o carregamento de uma nova camada, verifica-se se existe
alguma caixa classificada como “aberta”.
ü Se existir mais de um tipo de caixa classificada como “aberta”, a
heurística sugere dois critérios para desempate: escolher o tipo de
caixa com maior quantidade de caixas ou escolher a caixa melhor
ranqueada conforme os critérios descritos anteriormente;
4, 3, 1, 2
Tabela 03 – Critérios de desempate
PUC-Rio - Certificação Digital Nº 0312525/CA
38
ü Caso só existam caixas classificadas como “fechadas”, escolhe-se a
caixa com melhor posição no ranking das caixas.
Em cada camada, a maior dimensão da primeira caixa a ser carregada
determina a profundidade da camada. As outras dimensões da caixa (altura e
largura) devem ser menores do que as dimensões do contêiner.
As caixas que ainda não foram empacotadas são armazenadas na “Lista de
Caixas não Empacotadas”.
2ª etapa: Definir a altura e a largura da caixa que será utilizada e a quantidade de
caixas empacotadas.
Definido o tipo de caixa que será utilizado e a dimensão da profundidade,
o algoritmo verifica a dimensão da altura e da largura e a quantidade de caixas que
serão empacotadas.
ü Se a quantidade de caixas for suficiente para preencher mais do que
uma coluna inteira utilizando quaisquer dos dois posicionamentos
possíveis (trocando a altura com a largura), então define-se o
posicionamento das caixas procurando minimizar a perda na altura;
ü Caso contrário, o algoritmo escolhe a maior dimensão como sendo
a largura a fim de facilitar o posterior carregamento das caixas.
Definido o posicionamento da caixa, verifica-se a possibilidade de
empacotar uma coluna inteira com esse tipo de caixa.
ü Se não for possível o empacotamento de uma coluna inteira,
carrega-se toda a quantidade disponível da caixa;
ü No caso da viabilidade do carregamento em mais de uma coluna,
torna-se necessário o cálculo da Largura Flexível.
George e Robinson introduziram o conceito de Largura Flexível a fim de
combinar espaços não ocupados entre camadas para aumentar a utilização do
mesmo. Na figura 19, após o carregamento de 1 cria-se o espaço BCGF como
espaço de carregamento na largura do contêiner (W). Porém, verificamos que é
possível unir o espaço vazio da camada anterior ABFE com o espaço da camada
atual formando então uma região de carregamento ACGE. Ao criar essa nova
região de carregamento, percebemos que o espaço IDEH ficaria vazio. Para não
ocorrer esse tipo de problema, a heurística calcula a Largura Flexível AD. Pela
PUC-Rio - Certificação Digital Nº 0312525/CA
39
figura, a próxima região a ser carregada terá sua profundidade aumentada de BC
para AC.
Calculada a Largura Flexível, o algoritmo verifica se o número (dimensão)
de colunas que serão carregadas é maior que a Largura Flexível.
ü Se for, então carrega-se uma coluna a mais do que a permitida pela
Largura Flexível, conforme figura 19.
ü Se não, empacota-se o maior número possível de colunas
completas.
Após essa etapa, o algoritmo atualiza a quantidade de caixas e a
classificação (“aberta” ou “fechada”).
O carregamento da região ACGE é feito até exceder em no máximo uma
coluna a largura flexível AD. Agora, a heurística tentará aumentar a profundidade
do carregamento aproveitando o espaço vago IDEH.
3ª etapa: Criar os novos espaços de carregamento.
Os novos espaços para carregamento são criados conforme a figura 20:
Camada de
carregamento atual
Camada carregada
anteriormente
A
B
C
D
E
F
G
Região já
carregada
Largura
Flexível
1
I
H
Figura 19 – Largura Flexível
PUC-Rio - Certificação Digital Nº 0312525/CA
40
Primeiramente, gera-se os novos espaços de carregamento “a frente” e
coloca-se esses espaços na “Lista de Espaços a serem Carregados”. A seguir, cria-
se o espaço “ao lado” e verifica-se se a largura do espaço é maior ou igual a
menor dimensão das caixas que ainda não foram empacotadas. Se a largura for
maior ou igual, então adiciona-se esse espaço a “Lista de Espaços a serem
Carregados”. Caso contrário, descarta-se esse espaço. O último espaço gerado é o
“acima”. Gerado esse espaço, verifica-se se a altura dele é maior que a menor
dimensão das caixas que ainda não foram empacotadas. Se a altura for maior,
adiciona-se esse espaço à “Lista de Espaços a serem Carregados”. Caso contrário,
descarta-se o espaço.
Independente da dimensão do espaço gerado “a frente”, esse nunca é
descartado uma vez que o algoritmo tenta unir esses espaços através do cálculo da
Largura Flexível.
Os espaços gerados são armazenados na “Lista de Espaços a serem
Carregados” de forma que, carrega-se primeiro o espaço gerado “acima”, seguido
do “ao lado” e finalmente do “a frente”.
4ª etapa: Escolher o novo espaço de carregamento.
Nessa etapa, o algoritmo verifica se existe alguma caixa que ainda não foi
empacotada e se existir espaços não carregados.
ü Verifica-se a existência de alguma caixa na “Lista de Caixas não
Empacotadas”;
Figura 20 – Os novos espaços para carregamento
Espaço de
carregamento “a
frente”
Espaço de
carregamento
“ao lado”
Espaço de
carregamento
“acima”
PUC-Rio - Certificação Digital Nº 0312525/CA
41
Ø Se existir, então verifica-se a existência de espaços a serem carregados
na “Lista de Espaços a serem Carregados” e escolhe-se o espaço que
estiver no topo da lista.
§ Verifica-se a viabilidade de unir o espaço atual de
carregamento com algum espaço da “Lista de Espaços
Rejeitados” definido na 5ª etapa da heurística. Para unir
os espaços é necessário que a altura e a largura do
espaço da “Lista de Espaços a serem Carregados” sejam
menor ou igual a altura e a largura do espaço rejeitado,
respectivamente.
· Se for viável, une-se os espaços e verifica-se
novamente a possibilidade de unir a esse espaço
criado um outro espaço da “Lista de Espaços
Rejeitados”;
· Se não for viável unir os espaços, calcula-se a
Largura Flexível.
Ø Se não existir significa que todas as caixas foram empacotadas.
Se o espaço a ser carregado for considerado uma nova camada o algoritmo
volta para a 1ª etapa. Caso contrário, vai para a 5ª etapa.
5ª etapa: Achar o tipo de caixa para preencher os espaços vazios já existentes nas
camadas.
Os novos espaços de carregamento possuem suas dimensões
(profundidade, largura e altura) definidas. Para o carregamento desses espaços, o
algoritmo verifica se algum tipo de caixa cabe no espaço.
Ø Se couber, verifica-se se algum tipo de caixa preenche mais de
uma coluna.
§ Se sim, então escolhe-se a caixa que melhor preencha a
profundidade e a heurística volta para a 2ª etapa.
§ Caso contrário, escolhe-se o tipo de caixa que melhor
preencha a área da base e a heurística volta para a 2ª etapa.
PUC-Rio - Certificação Digital Nº 0312525/CA
42
Ø Se o algoritmo verificar que nenhuma caixa cabe no espaço
vazio, ele armazena o espaço na “Lista de Espaços Rejeitados”.
A heurística volta para a 4ª etapa.
Cecilio e Morabito (2003) desenvolveram novas heurísticas para o
problema carregamento de contêineres baseadas em refinamento e extensões da
heurística de George e Robinson.
O refinamento proposto consiste em, na 5ª etapa da heurística de George e
Robinson descrita anteriormente, ao invés de escolhermos o tipo de caixa que
preenche a maior área da base do espaço, verificar se pode ser feita uma
combinação de caixas de mesmo tamanho no comprimento desse espaço. A
combinação de caixas que apresentar uma maior utilização da área da base do
espaço é escolhida.
As duas extensões da heurística desenvolvidas foram denominadas de
versão Arranjo e versão Camada.
Para essas novas extensões da heurística, foram acrescentados mais dois
critérios para o ranqueamento das caixas, além dos critérios estabelecidos por
George e Robinson.
Agora, os cincos critérios utilizados para o ranqueamento das caixas são:
ü caixa com a maior entre as menores dimensões;
ü caixa de maior quantidade;
ü caixa com maior dimensão;
ü caixa com maior volume;
ü caixa com a maior razão dada por (maior dimensão/menor
dimensão).
Vale ressaltar que o ranqueamento das caixas é utilizado para a escolha da
primeira caixa da camada.
VERSÃO ARRANJO
Nessa versão são utilizados cada um dos arranjos de três dos cinco
critérios descritos anteriormente, o que resulta em 60
H
possibilidades de
H
A
m,n
= m! / (m – n)!
A
5,3
= 5! /2! = 120/2 = 60
PUC-Rio - Certificação Digital Nº 0312525/CA
43
combinação dos critérios. Isso significa que a heurística de George e Robinson
será executada 60 vezes sendo que em cada vez, um arranjo diferente de três
critérios de ranqueamento das caixas será utilizado e um novo padrão de
empacotamento do contêiner é gerado. O padrão que obtiver maior volume
empacotado é o escolhido. O fluxograma da figura 21 resume a Versão Arranjo.
VERSÃO CAMADA
Nessa versão também são utilizados arranjo de três dos cinco critérios
descritos anteriormente, o que resulta em 60 possibilidades de combinação dos
critérios. Nessa versão será determinado o padrão de empacotamento de cada
camada do contêiner. Isso significa que serão geradas 60 possibilidades de
carregamento para cada camada do contêiner. A iteração que apresentar menos
espaço vazio é escolhida como padrão para a camada. O fluxograma da figura 22
resume a Versão Camada.
Figura 21 – Versão Arranjo da Heurística de George e Robinson
Fonte: Cecílio e Morabito (2003)
PUC-Rio - Certificação Digital Nº 0312525/CA
44
Com base no refinamento e nas duas novas extensões da heurística de
George e Robinson, Cecílio e Morabito definiram 5 métodos de solução para o
problema de carregamento de contêineres. São eles:
ü Heurística de George e Robinson original + refinamento proposto;
ü Heurística de George e Robinson original + versão arranjo;
ü Heurística de George e Robinson original + refinamento proposto +
versão arranjo;
ü Heurística de George e Robinson original + versão camada;
ü Heurística de George e Robinson original + versão camada +
refinamento.
Figura 22 – Versão Camada da Heurística de George e Robinson
Fonte: Cecílio e Morabito (2003)
PUC-Rio - Certificação Digital Nº 0312525/CA
45
3.3.
Carregamento de contêineres em navio
Antes dos artigos referentes ao carregamento de contêineres em navios,
serão introduzidos alguns termos técnicos importantes nesse tipo de transporte.
Os navios porta-contêineres são navios utilizados exclusivamente para o
transporte de contêineres que podem ser alocados tanto nos porões dos navios
quanto no convés.
Os contêineres, normalmente, seguem o padrão internacional estabelecido
pela International Standards Organization (ISO). Eles possuem altura e largura
de 8 pés e os comprimentos mais utilizados são os de 20 e 40 pés. Os contêineres
de dimensão 20’ x 8’ x 8’ são chamados de unidade padrão e adotado
internacionalmente como
Twenty Feet Equivalent Unit (TEU) ou unidade
equivalente a 20 pés.
Os navios são constituídos por porões que possuem em geral, 40 pés de
comprimento sendo subdividido em duas seções de 20 pés cada. Cada seção é
denominada
BAY de porão. No convés, os contêineres são armazenados sobre as
tampas de escotilha de cada porão formando as BAYS de convés.
Pela figura 23, podemos verificar que as BAYS são formadas por STACKS
(colunas) e TIERS (camadas), sendo que a coordenada dada pela BAY, STACK e
TIER forma o chamado SLOT/CELL, ou seja, uma posição de contêiner. Cada
BAY de porão ou de convés tem diversas colunas (stack) de 8 pés de largura. A
altura das colunas é limitada pela resistência das tampas da escotilha no caso de
contêineres armazenados no convés do navio e pela resistência do fundo da
embarcação no caso de contêineres armazenados no porão do navio. As BAYS se
estendem de bombordo (metade esquerda do navio olhando para a Proa) a boreste
(metade direita do navio olhando para a Proa). Em geral, são construídas para a
colocação de contêineres de 20’ e 40’, que são embarcados longitudinalmente.
PUC-Rio - Certificação Digital Nº 0312525/CA
46
A figura 24 mostra a numeração das BAYS a partir da Proa (parte dianteira)
para a Popa (parte traseira) em números ímpares (1, 3, 5, 7, 9, ...) que corresponde
as BAYS ocupadas por contêiner de 20’. Quando a BAY for ocupada por contêiner
de 40’, ela recebe uma numeração par que equivale a numeração de 2 BAYS
ímpares. Por exemplo, se for colocado um contêiner de 40’ na BAY 22, entende-se
que as BAYS que estão sendo ocupadas são as de número 21 e 23.
Figura 23 – Composição das BAYS
Fonte: Wilson et al (2001)
PUC-Rio - Certificação Digital Nº 0312525/CA
47
Outros termos são explicados a partir da figura 25.
Figura 24 – Arranjo das bays do navio Columbus Olivos
Fonte: Hino (1999)
Figura 25 – Formação de Blocos de carga
Fonte: Wilson et al (2001)
Escotilha
PUC-Rio - Certificação Digital Nº 0312525/CA
48
Hatch – escotilha, cobertura dos porões do navio;
Hatch-lid – são as tampas das escotilhas;
Cargos spaces – espaços para alocação de carga;
Blocks – blocos de carga.
Wilson et al (2001) introduziram um sistema de computação que gera
soluções sub-ótimas para o Problema de Planejamento de Estivagem em navios
Porta- contêineres.
O Problema de Estivagem de Contêiner consiste em determinar um arranjo
viável dos mesmos, de forma a facilitar as operações de carga e descarga, a um
custo reduzido. O fator mais importante na otimização desse processo é minimizar
o número de reestivagens pois essa atividade representa um aumento das despesas
portuárias.
Esse problema é considerado combinatorial cujo tamanho depende da
capacidade do navio, do abastecimento de contêiner e da demanda de cada POD
(porto de destino). Este problema torna-se mais complexo pois precisamos
considerar a estivagem em todos os POD e as decisões tomadas em um porto
trarão conseqüências aos portos subsequentes.
Em cada POD, os contêineres com esse destino são descarregados e novos
contêineres podem ser carregados para portos subsequentes.
Os autores consideram que:
ü Em cada POD, ocorrem operações de carga e descarga porém o
carregamento não começa até o total descarregamento dos contêineres
daquele POD;
ü Em cada POD, existem 2 guindastes disponíveis para as operações
de carga e descarga.
Devido a complexidade computacional, o Processo de Planejamento é
dividido em duas etapas:
1. Processo de Planejamento estratégico:
- nesta etapa, os contêineres são designados a um determinado
blocked cargo-space.
PUC-Rio - Certificação Digital Nº 0312525/CA
49
2. Processo de Planejamento tático
- nesta etapa, os contêineres são designados aos slots referentes aos
repectivos blocked cargo-space.
1. Processo de Planejamento Estratégico:
Os contêineres, classificados por classe (comprimento e POD), são
alocados aos “Blocos de espaço de Carga” onde os slots correspondentes a cada
tampa da escotilha são mantidos juntos. Os “Blocos de espaço de Carga” são
ilustrados na figura 26.
Os objetivos dessa fase são:
ü Minimizar o número espaços de carga
ocupado por cada destino;
ü Maximizar o número de guindastes utilizadas nas operações de
carregamento em cada POD;
ü Minimizar o número de movimentos das tampas das escotilhas;
ü Minimizar o número de reestivagem;
ü Minimizar o número de
cargo blocks ocupado por contêineres.
2. Processo de Planejamento Tático:
Nessa fase, os contêineres são alocados aos slots aos respectivos “Blocos
de espaço de carga” definidos na etapa anterior.
Os objetivos dessa fase são:
ü Minimizar o número de reestivagem;
Bloco de espaço
de carga
Bloco de espaço
de carga
Figura 26 – Blocos de Espaço de Carga
Fonte: Wilson et al (2001)
Escotilha
constituída
p
or 3 tam
p
as
PUC-Rio - Certificação Digital Nº 0312525/CA
50
ü Os contêineres devem ser armazenados do mais pesado para o mais
leve;
ü Minimizar o número de colunas de contêineres com POD variado.
A figura 27 ilustra a alocação de cada contêiner ao seu respectivo slot
contendo contêineres para dois POD distintos (ROT e ILO) sendo ROT o porto
mais próximo para a próxima carga e descarga de contêiner. Além disso, podemos
observar que a escotilha é composta por duas tampas e que existem dois tipos de
contêineres sendo carregados nessa BAY: o 2210 e o
4210.
Martin Jr. et al (1988) desenvolveram uma heurística para o Planejamento
de Carregamento de Contêineres em navio.
Aparentemente, o processo de carregamento de contêiner em um navio é
muito simples. Dado um grupo de contêineres e um grupo de posições disponíveis
no navio para o carregamento destes contêineres, o problema consiste em alocar
os contêineres no navio e determinar a seqüência de carregamento de forma que as
restrições sejam respeitadas e o custo de movimentação dos contêineres seja
minimizado.
Figura 27 – Alocação de contêineres nos respectivos slots
Fonte: Wilson et al (2001)
PUC-Rio - Certificação Digital Nº 0312525/CA
51
Podemos citar como restrições para o processo de carregamento de
contêiner:
· Estabilidade do navio;
· Exigências para o carregamento de cargas perigosas;
· Altura das colunas de carregamento;
· Comprimento do contêiner, entre outros.
Geralmente, no carregamento, os contêineres são movimentados do pátio
de estocagem para o costado do navio por meio de caminhões. O contêiner é
carregado no caminhão pelo transtainer
I
. No costado do navio, o contêiner é
retirado do caminhão pelo guindaste do navio. O descarregamento é feito de
maneira inversa.
O transtainer possue largura suficiente para “varrer” sete contêineres ao
mesmo tempo porém, no terminal em estudo (Terminal do Porto de Portland), os
contêineres são armazenadas em fileiras de seis contêineres, ficando o espaço do
sétimo contêiner livre para o carregamento e passagem de caminhões. A altura de
empilhamento do terminal em estudo é de 4 contêineres.
As fileiras de contêineres, no pátio de estocagem, são separadas por
comprimento e sempre que possível, por porto de destino e peso. Várias fileiras de
contêineres juntas formam seções sendo as seções separadas por corredores.
Para desenvolvimento da heurística, os autores utilizaram como base o
Terminal do Porto de Portland (PoP) e, para simplificar o problema, foram feitas
algumas considerações:
· Não foram consideradas as cargas perigosas e cargas com
dimensões maiores que as dimensões padrão;
· Os contêineres são movimentados por uma combinação de
transtainer, caminhão e guindaste do navio;
· Contêineres vazios não foram levados em consideração;
· Só serão carregados os navios mais novos (data de
fabricação) por esses possuírem um sistema que ajusta a
estabilidade do navio;
I
Transteiners – guindastes montados sobre grandes pórticos que se movimentam sobre
trilhos ou pneus, empilhando e transportando os contêineres de um ponto a outro.
PUC-Rio - Certificação Digital Nº 0312525/CA
52
· Os contêineres para a viagem já estão no pátio de
estocagem e estão agrupados por porto, comprimento e
peso.
O primeiro passo para resolução do problema é decidir a ordem na qual as
cells das bays serão carregadas. Para isso são necessárias as seguintes
informações: a ordem na qual os portos serão atendidos, número médio de
contêineres classificados como leve, médio e pesado para cada combinação de
porto e bay e o guindaste a ser usado para cada combinação de porto e bay quando
mais de uma for utilizado.
Conforme ilustrado na figura 28, o carregamento da bay é feito
preenchendo as cells no sentido bombordo-boreste caso o navio esteja atracado a
boreste e no sentido boreste-bombordo caso o navio esteja atracado a bombordo.
As camadas (tier) são preenchidas de baixo para cima
O algoritmo inicia a procura por um contêiner que será alocado na cell.
Para o processo de carregamento nas bays, o peso dos contêineres das
stacks (colunas) não pode superar um valor limite. Valor esse que, se não
respeitado, afeta não só a estabilidade do navio como também a integridade do
mesmo.
Dois métodos diferentes são utilizados para escolha do contêiner. O
primeiro caso ou condição normal, o autor considera que o peso do contêiner não
tem importância especial, ou seja, uma variação no peso afetará a estabilidade de
uma forma bem branda. O outro caso é quando o último contêiner da coluna
(stack) do convés for carregado. Neste caso, se a stack estiver próximo do limite
Mar
Cais do
porto
Figura 28 – Sentido de prenchimento das cells de uma determinada bay
Fonte: Wilson et al (2001)
PUC-Rio - Certificação Digital Nº 0312525/CA
53
de carregamento, o último contêiner pode causar uma instabilidade considerável.
O próximo passo é determinar a classe de peso (leve, médio ou pesado) do
contêiner que irá preencher a cell além de definir o porto de destino, comprimento
do contêiner e algumas vezes, altura. A definição da classe de peso do contêiner é
feita pela determinação de uma variação do peso, como por exemplo: o contêiner
com peso entre X ± y é classificado como leve.
O algoritmo inicia a procura por um contêiner no local onde o transtainer
se encontra (fileira atual). As seguintes situações podem ocorrer:
· Se apenas um contêiner na fileira atual for aceito, ele é
alocado na cell;
· Se mais de um contêiner for aceito, o algoritmo escolhe o
contêiner que minimiza o re-manuseio. Desses, ele escolhe o que
estiver mais próximo da pista de passagem do caminhão (truck
line
).;
· Se nenhum contêiner for aceito, o algoritmo realiza a
procura em outra fileira da seção atual.
A procura não é feita em todas as fileiras da seção atual. É feita somente
nas fileiras onde a média de peso dos contêineres é a mesma requerida pela cell a
ser preenchida. Se nenhum contêiner for encontrado na seção atual, a procura é
feita na seção adjacente e depois nas não adjacentes. Se nenhum contêiner para
uma determinada
cell for encontrado nas seções, o algoritmo muda a variação de
peso que determina a classificação do contêiner em leve, médio ou pesado e volta
a procura para a posição inicial do transtainer. Com essa mudança na variação de
peso, poderão ser visitadas nessa nova busca fileiras que não foram “visitadas”
anteriormente.
Se após a mudança na variação de peso o algoritmo ainda não aceitar
nenhum contêiner para aquela determinada cell, o algoritmo muda para a próxima
cell a ser carregada e recomeça a procura.
O outro método desenvolvido pelo autor para escolha de contêiner é
quando a
cell a ser carregada é a última da coluna (stack) do convés.
Para preenchimento dessa
cell será escolhido o contêiner mais pesado que
não ultrapassar o limite de resistência da escotilha. Para aumentar a flexibilidade
na busca pelo contêiner, são considerados aptos a preencher a cell os contêineres
PUC-Rio - Certificação Digital Nº 0312525/CA
54
cujo peso estiver dentro de uma variação de peso especificada em relação ao
contêiner mais pesado.
Dentre esses contêineres, o que minimizar re-manuseio e/ou estiver mais
próximo da passagem do caminhão (truck line) é escolhido para carregamento.
A busca é feita de seção por seção. A ordem de busca pelas seções é a
mesma do outro procedimento: primeiro na current section, depois nas seções
adjacentes e por último nas seções não-adjacentes. Se nenhum contêiner for
encontrado para a cell, o algoritmo começa a procura para a próxima cell a ser
carregada.
Uma busca cuidadosa na literatura, porém não exaustiva, mostra que a
bibliografia neste assunto é relativamente escassa. No próximo capítulo será
apresentada a heurística desenvolvida para a elaboração de Plano de Estivagem de
placas de aço em navio.
PUC-Rio - Certificação Digital Nº 0312525/CA
4
MÉTODO HEURÍSTICO PARA ELABORAÇÃO DE PLANO
DE ESTIVAGEM DE PLACA DE AÇO
O método proposto para elaboração de Planos de Estivagem de placas de
aço em navios foi desenvolvido com base nos conhecimentos adquiridos por meio
de entrevistas informais com os profissionais da CST e com os profissionais da
empresa que elabora os Planos de Estivagem para a CST.
A heurística proposta para o Problema de Estivagem de Placa de Aço foi
dividida em duas etapas:
· Distribuição dos itens pelos porões;
· Determinação do layout dos itens no porão.
4.1. Definições importantes
A seguir serão dadas algumas definições importantes para o entendimento
da heurística:
· Proa – parte anterior do navio (direção em que o navio está
navegando);
· Boreste – metade direita da embarcação olhando-se para a Proa;
· Bombordo – metade esquerda da embarcação olhando-se para a
Proa;
· Popa – parte posterior do navio;
· Hatch – escotilha (abertura na parte superior do porão – tampa);
Essas definições são ilustradas na figura 29.
PROA
POPA
BORESTE
BOMBORDO
ESCOTILHAS
(HATCH)
Figura 29 - Definições
PUC-Rio - Certificação Digital Nº 0312525/CA
56
Pela figura 30 podemos visualizar as regiões da “Boca” e do “Fora de
Boca” do porão.
· “Boca” do porão – região do porão correspondente a área delimitada
pela abertura da escotilha;
· “Fora de boca” do porão – região do porão corresponde a área que
não é acessível diretamente pela abertura da escotilha.
4.2. Dados de entrada do algoritmo
Para a realização das etapas propostas são necessários os seguintes dados:
· Variedade de itens
J
no pedido (i);
· Quantidade de cada item (Q
i
);
· Peso do item (toneladas) (w
i
);
· Dimensões do item (comprimento (cp
i
), largura (lp
i
) e espessura
(hp
i
)(metro);
· Altura/espessura do rolete/calço (h
rolete
/h
calço
)(metro);
· Quantidade de porões (j);
· Capacidade de cada porão (toneladas);
· Dimensões do porão (comprimento
K
(C
j
), largura
L
(L
j
), altura (H
j
)
(metros);
· Dimensões da abertura da escotilha (comprimento
E
(CE
j
) e largura
L
(LE
j
))(metro);
J
O Item é constituído de placas que possuem as mesmas dimensões e composição química
K
Comprimento do porão/escotilha é referente à dimensão do porão/escotilha no sentido popa-
proa;
L
Largura do porão/escotilha é referente à dimensão do porão/escotilha no sentido bombordo-
boreste.
Fora de
boca
Fora de
boca
Boca
Figura 30 – Vista superior das Regiões da “Boca” e do “Fora
de Boca” do porão
PUC-Rio - Certificação Digital Nº 0312525/CA
57
· Ordem de carregamento dos porões;
· Resistência do piso do porão (t/m
2
);
· Altura máxima de empilhamento da empilhadeira (placas (n)).
4.3. Distribuição dos itens pelos porões
4.3.1. Agrupamento dos itens
Baseado nos dados de entrada, a heurística proposta agrupa os itens
conforme a ordem decrescente de comprimento. Havendo mais de um item com
mesmo comprimento, eles são agrupados em ordem decrescente de largura e
quantidade, respectivamente.
4.3.2. Distribuição dos itens pelos porões
Feito o ordenamento dos itens, aplicaremos o “Bin Packing Next Fit”. O “Next
Fit” é uma sub-divisão do “Bin Packing” no qual o primeiro objeto (placa) da lista
é alocado em um bin (porão). Os demais objetos (placas) são colocados neste
mesmo bin (porão) até a capacidade do mesmo ser alcançada. Assim que a
restrição de capacidade for atingida, um novo bin (porão) é aberto e continua-se o
empacotamento dos objetos (placas).
Vale ressaltar que para poder ser empacotado em determinado porão, as
dimensões dos itens (comprimento e largura) têm que ser menores do que as
dimensões da escotilha do porão.
4.4. Determinação do layout das placas no porão
4.4.1. Ranqueamento dos itens
Com base na proposta de George e Robinson (1980) de ranquear as caixas
a serem carregadas, os itens serão ranqueados nesta etapa conforme os seguintes
critérios:
· Ordem decrescente de largura. Havendo empate,
· Ordem decrescente de comprimento. Havendo empate,
· Ordem decrescente de quantidade.
PUC-Rio - Certificação Digital Nº 0312525/CA
58
4.4.2.Determinação das dimensões das camadas a serem carregadas
O lado do porão, conforme ilustrado na figura 31, possue uma inclinação
de 45º no sentido popa-proa do navio até uma altura do porão de 5 metros.
Devido a essa inclinação, as camadas de carregamento não terão as
mesmas dimensões. A largura das camadas permanece a mesma para todas as
camadas de carregamento, entretanto, a cada incremento na altura do
carregamento, o comprimento dessas camadas será aumentado de um valor 2x,
devido a inclinação em dois lados do porão. O cálculo de x será detalhado a
seguir.
A princípio, serão geradas as dimensões das n primeiras camadas de
carregamento, sendo n um dado de entrada da heurística. Também será
considerada a altura dos roletes de madeira (h
rolete
) nos quais as placas ficam
apoiadas.
O procedimento para geração das dimensões das camadas é o seguinte:
A cada elevação da altura, até 5 metros, há um aumento no comprimento
da camada de carregamento conforme mostrado na figura 32.
Toma-se como exemplo a seguinte situação:
Figura 31 – Inclinação de 45º no lado do porão no sentido popa-proa
Lado com
inclinação de
45º
PUC-Rio - Certificação Digital Nº 0312525/CA
59
· Dimensões do porão: 15,2m (comprimento) x 25,4 m (largura);
· h
p
(espessura do item que está sendo carregado) = 25cm;
· h
rolete
(altura dos roletes de madeira) = 10cm .
1ª camada de carregamento:
Conforme a figura 32, para o cálculo das dimensões da 1ª camada de
carregamento, só será considerado como incremento na altura de carregamento
10cm referente a altura do rolete de madeira.
x
tg
1,0
º45 =
x = 0,1
2ª camada de carregamento:
()
x
placaespessuraroletealtura
tg
__
º45
+
=
x = 0,35 metros
25,4 + 2*(0,1) = 25,6m
15,2
H
carreg. acumulada
= 0,1 (altura do rolete) + 0,25 (espessura da placa) = 0,35m
Figura 32 – Seção Transversal do porão
h
p
+ h
rolete
x
2ª camada de carregamento
1ª camada de carregamento
PUC-Rio - Certificação Digital Nº 0312525/CA
60
3ª camada de carregamento:
()
x
placaespessuraroletealtura
tg
__
º45
+
=
x = 0,35
4ª camada de carregamento:
()
x
placaespessuraroletealtura
tg
__
º45
+
=
x = 0,35
27 + 2*(0,35) = 27,7m
15,2
H
carreg. acumulada
= 1,05 (camada anterior) + 0,1 (altura rolete) + 0,25
(altura da placa) = 1,40m
26,3 + 2*(0,35) = 27,0m
15,2
H
carreg. acumulada
= 0,70 (camada anterior) + 0,1 (altura do rolete) + 0,25 (altura da
placa) = 1,05m
25,6 + 2*(0,35) = 26,3m
15,2
H
carreg. acumulada
= 0,35 (camada anterior) + 0,1 (altura do rolete) + 0,25 (altura da
placa) = 0,70m
PUC-Rio - Certificação Digital Nº 0312525/CA
61
5ª camada de carregamento: mesmo raciocínio anterior.
()
x
placaespessuraroletealtura
tg
__
º45
+
=
x = 0,35
Calculada as dimensões das n primeiras camadas de carregamento, a
heurística definirá o layout dessas camadas.
4.4.3. Lastreamento do porão
Lastrear o porão significa preencher o perímetro do mesmo. O
carregamento do lastro do porão foi dividido em duas etapas. Na primeira etapa é
feita a distribuição das placas nas extremidades do porão. Na etapa seguinte é
feito o carregamento do restante do lastro.
4.4.3.1. Distribuição dos itens nas extremidades do porão
É considerado como ponto de origem do carregamento o ponto (0, 0, 0.1).
Na primeira camada de carregamento as placas são alocadas nos cantos do
porão, no sentido anti-horário, conforme a figura 33. Para esse procedimento é
25,6m
15,2
(0, 0, 0.1)
27,7 + 2*(0,35) = 28,4m
15,2
H
carreg. acumulada
= 1,40 (camada anterior) + 0,1 (altura do rolete) + 0,25 (altura da
placa) = 1,75m
PUC-Rio - Certificação Digital Nº 0312525/CA
62
escolhido o item melhor ranqueado conforme critérios definidos na seção 4.4.1.
Se a quantidade do item melhor ranqueado não for suficiente para preencher o
lastro das camadas atuais de carregamento, então verifica-se a possibilidade de
preenchimento do lastro com outros itens alocados no porão, respeitando o
ranqueamento dos mesmos.
PUC-Rio - Certificação Digital Nº 0312525/CA
63
Esse procedimento é repetido para as outras (n-1) camadas de
carregamento cujas as dimensões foram calculadas na seção 4.4.2. O sentido de
rotação das placas nas camadas é alternado entre anti-horário (nas camadas
impares) e horário (nas camadas pares).
4.4.3.2. Carregamento do restante do lastro do porão
Distribuídas as placas pelos cantos do porão, a heurística verifica se é
possível alocar mais alguma placa lastreando o porão. Se não for possível utilizar
o item que está sendo carregado, verifica-se se outro item alocado neste porão
pode ser utilizado para completar o lastreamento, respeitando o ranqueamento dos
itens.
c
p
= comprimento da placa
l
p
= largura da placa
Bombordo Boreste
Proa
Popa
P
c
p
l
p
Figura 34 - Cálculo de P
Figura 33 – Alocação das placas nos cantos do porão no sentido anti-horário
PUC-Rio - Certificação Digital Nº 0312525/CA
64
Procedimento para o carregamento (executar o procedimento abaixo para todos os
lados do porão).
A. Calcular P (distância entre as placas alocadas nas extremidades do porão)
conforme figura 34;
B. Verificar se o comprimento (cp
n
) do item a ser alocado é menor que P;
B.1. Se for menor, então faça:
B.1.1. Calcular a quantidade (nl
M
) de placas com comprimento cp
n
que
podem ser alocadas em P;
n
cp
P
nl =
-10
B.1.2. Calcular o espaçamento entre as placas:
()()
1
*
+
-
=
n
l
cpnlP
sl
n
B.1.3. Verificar se o espaçamento calculado (sl) é maior do que a
espessura do calço (h
calço
):
§ Se for maior, vá para B.1.4;
§ Se for menor:
ü recalcular a quantidade de placas (nl’) com
comprimento cp
n
que podem ser alocadas em
P;
1' -= nlnl
ü voltar para o passo B.1.2;
B.1.4. Verificar se a quantidade de placas (nl) com comprimento cp
n
é
menor do que a quantidade de placas disponíveis para carregamento no
porão:
§ Se for menor, então aloque as placas conforme o
espaçamento calculado em B.1.2;
§ Caso contrário:
ü alocar a quantidade de placas disponíveis
conforme o espaçamento calculado em
B.1.2;
M
nl
-
retorna o próximo menor valor inteiro ao se arredondar o valor para baixo.
PUC-Rio - Certificação Digital Nº 0312525/CA
65
ü calcular P’ (distância entre a placa a última
placa alocada anteriormente e a placa
alocada na extremidade do lastro);
ü voltar para o passo B.
B.2. Se for maior, então faça:
B.2.1. Verificar, conforme o ranking dos itens se existe alguma placa
alocada neste porão com comprimento menor que P;
§ Se existir, vá para B.1.1;
§ Caso contrário, preencher o próximo lado do
porão.
A figura 35 ilustra o carregamento do lastro do porão no caso em que a
quantidade de camadas carregadas é cinco (n=5), nl=1 para os lados do porão
paralelos a Popa e a Proa do navio e nl=0 para os lados do porão paralelos a
Bombordo e a Boreste do navio.
PUC-Rio - Certificação Digital Nº 0312525/CA
66
1ª camada:
L
2ª camada:
Bombordo
cp
lp
lp
cp
sl
sl
P
Boreste
3ª camada:
L
4ª camada:
5ª camada:
Figura 35 - Carregamento do lastro
PUC-Rio - Certificação Digital Nº 0312525/CA
67
4.4.4. Carregamento da parte central do porão
Feito o lastreamento do porão, a heurística define o carregamento da parte
central do mesmo. Conforme ilustrado na figura 36, a parte central foi dividida
nas seguintes regiões: A, B, C e em alguns casos, o 2º lastro do porão.
· Região A – região do “fora de boca” do porão que vai da
extremidade direita da placa do lastro a Boreste do navio até a
projeção esquerda da escotilha;
· Região B – região central referente à “boca” do porão;
· Região C – região do “fora de boca” do porão que vai da
extremidade esquerda da placa do lastro a Bombordo do navio até a
projeção direita da escotilha.
· 2º lastro – região paralela à largura do porão. É composta pela área
que não foi carregada pelas placas alocadas nas regiões A, B e C.
O carregamento das regiões A, B e C é divido em duas etapas devido a
incerteza em relação à existência do 2º lastro. As etapas são divididas em Pré-
carregamento e Carregamento Definitivo. No Pré-Carregamento é definida a
posição da placa referente à Popa-Pria (eixo x da figura 37). No final dessa etapa,
a placa não sofrerá deslocamento em relação a Popa e a Proa. No Carregamento
Fi
g
ura 36
–
Divisão da
p
arte central do
p
orão em re
g
iões
Bombordo
Boreste
Popa
Proa
PUC-Rio - Certificação Digital Nº 0312525/CA
68
Definitivo é determinado a posição final da placa após o deslocamento da mesma
em relação à Bombordo-Boreste (eixo y da figura 37).
A figura 37 ilustra essa situação. No Pré-carregamento a placa é alocada
conforme a placa azul. O Carregamento Definitivo é representado pela placa azul
pontilhada.
4.4.4.1. Pré-carregamento das regiões A e C
O pré-carregamento nas regiões A e C é feito alocando as placas nessas
regiões formando pilhas de n placas com o comprimento das placas paralelo ao
comprimento do porão. A heurística empilha as placas alternadamente entre as
regiões A e C.
A figura 38 ilustra o carregamento de 2 pilhas de placas nas Regiões A e C
no caso de n = 5. O índice existente nas placas indica a ordem de carregamento de
cada uma. Portanto, a primeira placa é alocada em A, sendo essa placa a primeira
placa (índice 1) da primeira pilha de placas da região A. A segunda placa (índice
2) é alocada em C, sendo essa placa a primeira placa da primeira pilha de placas
na região C. Após o carregamento da 5ª placa de cada pilha de placas (índice 9 e
10), inicia-se o carregamento da 2ª pilha de placas das regiões A e C.
x
y
Popa
Bombordo Boreste
Proa
Fi
g
ura 37
–
Pré-carre
g
amento e Carre
g
amento Definitivo
PUC-Rio - Certificação Digital Nº 0312525/CA
69
A quantidade de pilhas carregadas é proporcional ao “fora de boca” do
porão. A n-ésima camada de carregamento é que determina a quantidade de pilhas
de placas a serem carregadas nas Regiões A e C, pois ela possui comprimento
maior do que as camadas já carregadas (no caso de n=5, 1ª, 2ª, 3ª e 4ª camadas) e
consequentemente, possui a maior distância entre as placas empilhadas e a
projeção da escotilha (d), conforme ilustrado na figura 39. Enquanto d > 0, as
placas são alocadas em A e C formando pilhas.
A tática escolhida para se carregar as placas nessa região, em pilhas, tem
como justificativa o fato desse carregamento ser feito por uma empilhadeira que
fica dentro do porão do navio.
4.4.4.2. Pré-carregamento da região B
O pré-carregamento na região B é feito alocando as placas em camadas
com o comprimento da placa paralelo ao comprimento do porão. A heurística
aloca primeiro todas as placas da primeira camada, depois todas as placas da
segunda camada e assim sucessivamente, até pré-carregar a n-ésima camada.
Figura 38 – Vista lateral do carregamento de duas pilhas de placas nas
Regiões A e C
12
3
5
7
9
4
6
8
10
11
13
15
17
19
12
14
16
18
20
Região A Região C
Figura 39 – Vista lateral de duas pilhas de placas carregadas na região C
d
Região C (fora de boca)
Projeção da
abertura da
escotilha
(Região B)
PUC-Rio - Certificação Digital Nº 0312525/CA
70
Nas camadas, as placas são alocadas de forma alternada entre os lados a
Bombordo e a Boreste do navio. Além disso, os pontos de partida para o
carregamento de cada camada dessa região são as últimas placas alocadas na
respectiva camada da região A e da região C.
A tática escolhida para se carregar as placas nessa região, em camadas,
tem como justificativa o fato desse carregamento ser feito direto pelo guindaste do
porto pela da abertura da escotilha, não sendo necessário o uso da empilhadeira.
4.4.4.3. Carregamento do 2º lastro
No caso da existência do 2º lastro, esse é carregado com as placas alocadas
com comprimento perpendicular ao comprimento do porão. O procedimento para
carregamento dessa região será detalhado mais adiante.
4.4.4.4.Procedimento para carregamento da parte central do porão
O procedimento para carregamento da parte central do porão é o seguinte:
1º passo: Cálculo de MI (distância entre as placas de maior largura alocadas no
lastro do porão dos lados paralelos a Popa e a Proa do navio).
· Calcular o valor de MI para cada camada conforme a figura 40;
Fi
g
ura 40
–
Cálculo de MI
MI
Bombordo
Popa
Boreste
Proa
PUC-Rio - Certificação Digital Nº 0312525/CA
71
2º passo: Pré-carregar as regiões A e C
· Com base no ranqueamento dos itens, calcular o número de placas (nc)
paralelas ao comprimento do porão que podem ser alocadas nas Regiões A
e C conforme valor calculado de MI. Pré-alocar as placas formando pilhas
de 5 placas com base no procedimento descrito no item 4.4.4.1. Essas
placas são pré-alocadas respeitando o alinhamento da placa de maior
largura do lastro no lado do porão paralelo a Popa do navio (respeitando o
valor do h
calço
referente ao existente entre placas).
3º passo: Pré-carregar a região B
A. Com base no ranqueamento dos itens, calcular o número de placas (nc)
paralelas ao comprimento do porão que podem ser alocadas na Região B
conforme o valor de MI calculado e o procedimento descrito no item
4.4.4.2. Essas placas são pré-alocadas respeitando o alinhamento da placa
de maior largura do lastro no lado do porão paralelo a Popa do navio
(respeitando o calço existente entre placas).
B. Calcular a distância DB (distância existente entre a última placa alocadas a
Bombordo e a última placa alocada Boreste do navio);
C. Verificar se DB > ((largura da próxima placa a ser carregada (lp
n
) + (2*
h
calço
existente entre as placas))
C.1. Se sim, então faça:
ü Alocar a placa a Bombordo ou a Boreste do navio (a placa é
alocada no sentido contrário a última placa carregada pois o
carregamento é feito de forma alternada entre Bombordo e
Boreste);
ü Voltar para B.
C.2. Se não, então faça:
ü Verificar, conforme o ranking dos itens, se existe outro
item cuja a largura (lp) é menor do que (DB – 2* h
calço
existente entre as placas);
§ Se existir, alocar a placa e voltar para B;
PUC-Rio - Certificação Digital Nº 0312525/CA
72
§ Caso contrário, calcular o espaçamento final (sfb)
entre as placas da região B (nb) e re-alocar as
placas conforme o espaçamento calculado.
1
)*(
+
+
=
nb
hnbDB
sfb
calço
A figura 41 ilustra o carregamento da região B do porão. As placas de cor azul
e rosa foram alocadas na região A e C, sucessivamente. O índice existente nas
placas carregadas em B indica a ordem de carregamento das placas nessa região.
4º passo:
Calcular o valor de x e o “menor espaço que sobra”
· Pré-alocadas as placas nas primeiras n camadas de carregamento (nas
regiõs A, B e C), calcular os valores de x conforme a figura abaixo:
1
3
4
2
DB
Bombordo
Boreste
Fi
g
ura 41
–
Carre
g
amento da re
g
ião B
PUC-Rio - Certificação Digital Nº 0312525/CA
73
x – espaço entre as placas do lastro do lado do porão paralela a Proa do navio e as
placas alocadas nas regiões A, B e C. X é variável, dependo do comprimento das
placas alocadas na parte central do porão.
· Para a situação crítica, ou seja, menor valor de x encontrado nas n
camadas, fazer:
ü Se (existir algum item cuja largura) < (menor valor de x encontrado
nas camadas atuais de carregamento)
Ø Fazer para esses itens:
W
-N
= Menor valor de x / largura do item
Z
-O
= Menor valor de x – [(W+1) * h
calço
] / largura do item
Espaço que sobra = x – (Z* h
calço
) – (Z* largura do item)
Onde:
W = nº de placas de um determinado item, que pode ser
alocado neste espaço;
Z = valor de W ajustado para incluir h
calço
N
W
-
retorna o próximo menor valor inteiro ao se arredondar o valor para baixo
O
Z
-
retorna o próximo menor valor inteiro ao se arredondar o valor para baixo
Figura 42 – Cálculo de x
Po
p
a
Proa
Bombordo Boreste
PUC-Rio - Certificação Digital Nº 0312525/CA
74
Exemplo:
Menor valor de x encontrado foi x = 3,45 e h
calço
= 0,1cm.
Existe algum item cuja largura é menor ou igual a 3,45?
Tabela 04: cálculo do “espaço que sobra”
largura W
-
Z
-
Espaço que sobra
Item 15 1,8 1 1 1,45
Item 18 1,72 2 1 1,33
Item 7 1,42 2 2 0,31
Item 3 1,35 2 2 0,45
Item 5 1,07 3 2 1,01
Obs: se houver empate, escolher o item com maior quantidade.
5º passo: Definir o item que será utilizado no carregamento do 2º lastro
A. Escolher o item que gera o menor “espaço que sobra” conforme
calculado no 4º passo;
B. Calcular y. Nas camadas ímpares (1, 3, 5,...) cujo o sentido de rotação
para preenchimento do lastro é o sentido anti-horário, y é a distância
paralela a Boreste do navio. Nas camadas pares (2, 4, 6,...), y é a
distância paralela a Bombordo do navio. Se Z > 1, y será calculado
tanto a Bombordo quanto a Boreste do navio nas camadas pares e
ímpares, conforme ilustrado nas figuras 43 e 44;
Observação: Se Z = 1, o 2º lastro será composto apenas pela região
paralela a Proa do navio. Se Z > 1, o 2º lastro será dividido em 2 regiões: uma
paralela a Proa e outra paralela a Popa do navio.
PUC-Rio - Certificação Digital Nº 0312525/CA
75
C. Verificar se (y > lp)
lp – largura da próxima placa a ser alocada no porão
ü Se (y > lp), calcular o valor de D1 indicado na figura 45;
ü Se (y < lp), calcular o valor de D2 indicado na figura 45.
Re
g
ião
p
aralela a Proa
Popa
Proa
Boreste
Re
g
ião
p
aralela a Po
p
a
y
y
Re
g
ião
p
aralela a Proa
Popa
Proa
Boreste
Re
g
ião
p
aralela a Po
p
a
y
y
Figura 43 – divisão do 2º lastro do porão em 2 regiões nos casos em que Z > 1 e a
camada de carregamento é ímpar
Bombordo
Bombordo
Figura 44 – divisão do 2º lastro do porão em 2 regiões nos casos em que Z > 1 e a
camada de carregamento é par
PUC-Rio - Certificação Digital Nº 0312525/CA
76
D. Calculado os valores de D1 e/ou D2 para as n camadas, verificar a
quantidade de placas que podem ser alocadas no 2º lastro. A posição
final dessas placas será definida no 6º passo;
D.1. Verificar se a quantidade de placas necessárias para o
preenchimento desse 2º lastro nas n primeiras camadas é menor
ou igual a quantidade de placas disponíveis.
D.1.1. Se for menor ou igual, então alocar as placas
conforme o procedimento descrito no 6º passo.
D.1.2. Caso contrário, procurar a placa que gera a 2ª menor
perda de espaço e voltar para “B”.
Se após esse procedimento, a heurística ainda não tiver encontrado um
item em quantidade suficiente, alocar a quantidade de placas do item
existente que gera menor “espaço que sobra” e completar o carregamento
com outro item situado na posição subseqüente do ranking dos itens conforme
definido em 4.4.1;
6º passo
: Determinar a posição final das placas do 2º lastro
No passo anterior ficou definido qual item será utilizado no 2º lastro e a
quantidade de placas que serão carregadas.
Para determinar a posição dessas placas fazer:
Figura 45 – definição das distâncias D1 e D2
y
D2
D1
PUC-Rio - Certificação Digital Nº 0312525/CA
77
A. Verificar se (y > lp)?
A.1. Se sim, empacotar a primeira placa com o mesmo
alinhamento da já existente (encostando no lado do porão);
A.2. Se não, empacotar a primeira placa respeitando o alinhamento
da placa paralela a Boreste do navio.
B. Alocar o restante das placas do 2º lastro conforme quantidade de
placas calculada no 5º passo, respeitando o alinhamento da primeira
placa alocada no 2º lastro e o h
calço
existente entre placas. No caso de Z
>1, as placas são alocadas nas regiões paralelas a Popa e paralela a
Proa de forma alternada conforme ilustrado na figura 48:
Bombordo
Bombordo
Boreste
Boreste
Popa
Popa
Figura 47 - y < lp
Proa
Proa
y
F
F
Figura 46 - y > lp
y
PUC-Rio - Certificação Digital Nº 0312525/CA
78
C. Calcular F (distância que ainda não foi preenchida entre a última placa
alocada no 2º lastro e a placa do canto paralela a bombordo/boreste);
Figura 48 – Alocação das placas no 2º lastro do porão para Z = 2
PUC-Rio - Certificação Digital Nº 0312525/CA
79
D. Calcular o espaçamento S entre as placas:
(
)
(
)
1
*
+
+
=
y
hyF
S
calço
onde:
y = (quantidade de placas alocadas na região paralela a Proa ou na
região paralela a Popa do navio -1)
E. Calcular a posição final das placas do 2º lastro conforme o
espaçamento calculado anteriormente.
7º passo: Deslocar as placas alocadas nas Regiões A, B e C
Após a definição da posição final das placas embarcadas no 2º lastro,
deslocar as placas das regiões A, B e C paralelas ao comprimento do porão,
conforme a tabela abaixo:
Tabela 05: distância de deslocamento
Valor de Z Distância a ser deslocada no sentido da Proa do navio
1 ___
2 ou 3 Largura da placa alocada na Região paralela a Popa + h
calço
4 ou 5 Largura da placa alocada na Região paralela a Popa + h
calço
+
Largura da placa alocada na Região paralela a Popa + h
calço
6 ou 7 Largura da placa alocada na Região paralela a Popa + h
calço
+
Largura da placa alocada na Região paralela a Popa + h
calço
+
Largura da placa alocada na Região paralela a Popa + h
calço
Figura 49 – Posição final das placas da região paralela a Proa
S
S
PUC-Rio - Certificação Digital Nº 0312525/CA
80
8º passo: Carregamento Definitivo das Regiões A, B e C
· Após deslocar as placas paralelas ao comprimento em direção a Proa
do navio, determinar a posição final das placas, calculando o
espaçamento entre elas:
(
)
(
)
1
*
+
+
=
nc
hncx
SC
calço
onde x é a distância entre as placas alocadas nas regiões A, B e C
e a placa paralela a Proa do navio após a deslocamento efetuado no 7º
passo.
9º passo: Definição da quantidade de camadas a serem carregadas
Com base na quantidade de placas carregadas na n-ésima camada,
procede-se ao seguinte cálculo:
Onde:
R
-P
- nº de camadas que ainda serão geradas e carregadas
Q
total_porão
- Quantidade total de placas alocadas no porão;
Q
total_momento
- Quantidade de placas carregadas até o momento
Q
última_camada
- Quantidade de placas carregadas na última camada
· Se R › n, gerar e carregar mais n camadas de carregamento
conforme o procedimento explicado anteriormente;
· Se 1≤ R≤ n gerar e carregar o próximo menor valor inteiro ao se
arredondar o valor para baixo conforme o procedimento explicado
anteriormente;
· Se 0 < R< 1 gerar mais 1 camada de carregamento e carregar o
restante das placas conforme o procedimento explicado
anteriormente.
4.5. Resumo da heurística
Os passos da heurística estão representados na figura 50:
P
R
-
retorna o próximo menor valor inteiro ao se arredondar o valor para baixo
(
)
(
)
camadaúltima
momentototalporãototal
Q
QQ
R
_
__
9,0 -*
=
PUC-Rio - Certificação Digital Nº 0312525/CA
81
Ranqueamento dos itens
Lastreamento do porão
Pré-carregamento da região A e C do porão
Pré-carregamento da região B do porão
Determinação das dimensões das
camadas a serem carregadas
N
ão
R > n?
Gerar n camadas
de carregamento
Si
m
Si
m
Não
Calcular o valor de R
Existe o 2º lastro?
Carre
g
ar o mesmo
R > 1?
Gerar R
-
camadas
de carregamento
Si
m
Gerar 1 camada
de carregamento
Carregar as regiões A, B e C
Dados de entrada dos itens e dos porões
Agrupamento dos itens
Distribuição dos itens pelos porões
Figura 50 – Resumo da heurística
PUC-Rio - Certificação Digital Nº 0312525/CA
82
4.6. Teste da heurística
A partir de dados reais fornecidos pela CST, a heurística foi testada para
quatro carregamento distintos. Foram gerados os Planos de Estivagem para os
navios Konkar Lydia, Fedral Agno, Norsul Crateus e Olympic Menot. No
apêndice A é apresentado o Plano de Estivagem no navio Konkar Lydia cujo
porto de destino é o Porto da Philadelphia e a carga embarcada é constituída de
2.761placas de aço totalizando 54.878,80t.
Além de gerar o layout de cada porão do navio, o método proposto gera
como dados de saída uma planilha contendo qual e quantas placas foram
carregadas em um determinado porão, o peso total da carga embarcada, o peso
pré-determinado para o porão (capacidade do porão que é um dado de entrada do
problema) e peso calculado para cada porão. O peso calculado de cada porão é a
quantidade máxima de carga que pode ser embarcada em cada porão levando em
consideração a resistência do piso do porão.
O método proposto, como todo método heurístico, não garante que o
resultado obtido seja ótimo, porém retorna soluções de boa qualidade em um
tempo muito inferior em relação ao atual processo de elaboração de Plano de
Estivagem utilizado pela CST.
PUC-Rio - Certificação Digital Nº 0312525/CA
5
CONCLUSÕES E RECOMENDAÇÕES
Este trabalho propôs um procedimento heurístico para auxílio na
elaboração de Plano de Estivagem de placas de aço em navio. O objetivo principal
da heurística é gerar o Plano de Estivagem de forma rápida, confiável e
transparente, respeitando as restrições existentes e evitando, sempre que possível,
a mistura dos itens (placas) embarcados em um determinado porão durante o
carregamento. A grande dificuldade encontrada no desenvolvimento desse
trabalho foi o fato de não ter sido encontrado nenhum trabalho publicado
específico sobre o assunto.
A heurística apresentada nesse trabalho foi desenvolvida a partir de
conhecimentos adquiridos nas heurísticas estudadas no Capítulo 3 dessa
Dissertação e junto aos profissionais da CST e da empresa prestadora de serviço
de elaboração de Planos de Estivagem para a CST.
O primeiro passo da heurística consiste em distribuir as placas de aço pelos
porões do navio respeitando o Plano de Carga da embarcação e a ordem de
carregamento dos porões pré-estabelecida pelo comandante do navio.
No segundo passo, o porão é dividido em cinco regiões: lastro, região A,
região B, região C e 2º lastro. A princípio, a determinação do layout é feita para as
n primeiras camadas de carregamento cujas as dimensões calculadas levam em
consideração a inclinação de 45º existente no porão até uma altura de 5 metros. O
layout das placas nos porões é determinado de forma que as regiões do “fora de
boca” do porão (lastro, 2º lastro e regiões A e C da heurística) sejam carregadas
através de empilhadeiras e a região da “boca” do porão (região B da heurística)
seja carregada diretamente pelo guindaste do porto. A distribuição das placas da
região denominada na heurística de 2º lastro é feita de forma a maximizar a
utilização do espaço do porão no sentido Popa-Proa do navio a fim de evitar
grandes espaços vazios nesta região.
As demais camadas de carregamento a serem carregadas são determinadas
conforme a relação entre a quantidade total de placas que ainda não foram
embarcadas no porão e a quantidade total de placas embarcadas na última camada
carregada.
PUC-Rio - Certificação Digital Nº 0312525/CA
84
Com base nos dados reais fornecidos pela CST, foram realizados alguns
testes da heurística. Os resultados obtidos foram bastante satisfatórios, uma vez
que, as restrições impostas foram obedecidas e os Planos de Estivagens foram
gerados de forma rápida, confiável e transparente.
Podemos considerar como ponto positivo deste trabalho a confiabilidade e
a rapidez na sua elaboração, fatores estes que são bastante relevantes, pois torna o
processo de estivagem mais rápido, reduzindo o tempo de permanência do navio
em operação, o que acarreta menores custos de estadia do próprio navio e dos
demais navios em cascata que aguardam na fila para atracação.
Para os testes realizados com carregamentos distintos, o tempo de
processamento foi inferior a 1 segundo. Essa rapidez no processamento da
heurística é de extrema importância, uma vez que, em função de qualquer
problema no porto, o Plano de Estivagem pode ser refeito sem atrasar o embarque
da carga no navio. Vale ressaltar que atualmente, a elaboração do Plano de
Estivagem demora em média quatro horas pois é feito manualmente e que um
atraso de um dia no carregamento do navio gera uma multa para a CST
(demurrage) em torno de U$40.000/dia.
Para trabalhos futuros sugere-se:
· o desenvolvimento de uma heurística para a elaboração de Plano de
Estivagem para o carregamento dos porões das extremidades do
navio (Popa e Proa) que possuem seção trapezoidal;
· a partir dos resultados obtidos neste trabalho, elaborar uma forma
de armazenar as placas no pátio de estocagem de forma a diminuir
o laytime dos navios no porto;
· estudar o caso de Estivagem de placas de aço com espessuras
diferentes. Por seu um problema mais complexo, verificar a
possibilidade de utilização de uma meta-heurística;
· estudar a formulação exata do problema de estivagem de placa de
aço abordado nessa dissertação para posterior comparação entre os
resultados obtidos por cada método;
· estudar um material alternativo para fabricação dos calços e roletes
e dimensionar essas peças em função da resistência do material.
PUC-Rio - Certificação Digital Nº 0312525/CA
6
Referências Bibliográficas
BISCHOFF, E.; DOWSLAND, W. B. An application of the micro to product
design and distribution. Operational Research Society, vol. 33, 1982, p. 271-
280.
BISCHOFF, E. E.; JANETZ, F.; RATCLIFF, M.S.W. Loading pallets with non-
identical items. European Journal of Operational Research, vol. 84, 1995, p. 681-
692.
CECILIO, F. O.; MORABITO, R. Heurística para o problema de
carregamento de carga dentro de contêineres. SIMPÓSIO BRASILEIRO DE
PESQUISA OPERACIONAL, 2003, Natal. Anais em CD-ROM: XXXV
Simpósio Brasileiro de Pesquisa Operacional, 2003.
COFFMAN JR, E. G.; GALAMBOS, G.; MARTELLO, S.; VIGO, D..
Handbook of Combinatorial Optimization. Kluwer Academic Publishers, 1998.
DYCKOFF, H. A typology of cutting and packing problems. European Journal
of Operational Research, vol. 44, 1990, p. 145-159.
GEORGE, J.A.; ROBINSON, D.F. A heuristic for packing boxes into a
container. Computers&Operations Research, vol. 07, 1980, p. 147-156.
HINO, C. M. Desenvolvimento de métodos para elaboração de modelos
heurísticos de designação e sequenciamento de planos de estivagem de navios
porta-conteineres. Dissertação de Mestrado – Departamento de Engenharia
Naval e Oceânica, USP. São Paulo, 1999. 221 p.
MARTIN JR, G. L.; RANDHAWA, S. U.;MCDOWELL, E.D. Computerized
container-ship load planning: a methodology and evaluation.
Computers&Industrial Enginnering, vol. 14, 1988, p. 429-440.
WILSON, I. D.; ROACH, P. A.; WARE, J. A.. Container stowage pre-
planning:using search to generate solutions, a case study. Knowledge-based
systems, vol. 14, 2001, p. 137-145.
<http://www.cst.com.br>. Acesso em jun. 2004.
PUC-Rio - Certificação Digital Nº 0312525/CA
86
Apêndice A – Plano de estivagem gerado pela heurística
DADOS DE ENTRADA DAS PLACAS
Item
(i)
Quantidade (Qi) Comprimento (cpi) Largura (lpi) Altura (hpi)
Peso médio
(wi)
1 214 8,99 0,95 0,25 16,7
2 250 9 1,12 0,25 19,7
3 234 9 1,25 0,25 22
4 133 9 1,29 0,25 22,7
5 146 8,99 0,95 0,25 16,7
6 250 9 1,03 0,25 18,1
7 101 9 1,15 0,25 20,2
8 122 9 1,25 0,25 22
9 143 8,99 0,97 0,25 17
10 111 9 1,25 0,25 22
11 106 9 1,29 0,25 22,7
12 138 8,99 1,03 0,25 18,13
13 248 8,99 1,12 0,25 19,67
14 89 8,99 1,25 0,25 22
15 150 9 1,15 0,25 20,2
16 116 8,99 1,04 0,25 18,2
17 108 9 1,29 0,25 22,7
18 50 9 1,29 0,25 22,7
19 52 9 1,29 0,25 22,7
DADOS DE ENTRADA DOS PORÕES
Porão
(j)
comprimento
(Cj)
largura
(Lj)
altura
(Hj)
Capacidade
(ton)
Resistência
do piso
(t/m2)
Dimensões
da abertura
da escotilha
1 19,3 18,8 18 6440 20,45 16 x 12,8
2 21,2 25,4 18 7563 16,28 18,10 x 12,8
3 22,2 25,4 18 10200 20,15 18,7 x 12,8
4 15,2 25,4 18 6095 18,42 11,9 x 12,8
5 22 25,4 18 9540 20,23 18,7 x 12,8
6 22 25,4 18 8117 16,28 18,7 x 12,8
7 20 24,8 18 7070 18,84 18,7 x 12,8
Outros dados de entrada da heurística:
h
calço
= 10cm
n = 5
Ordem de carregamento dos porões: 3, 5, 4, 2, 6, 1 e 7.
PUC-Rio - Certificação Digital Nº 0312525/CA
87
As figuras a seguir ilustram o layout gerado pela heurística para o porão 4.
PUC-Rio - Certificação Digital Nº 0312525/CA
88
PUC-Rio - Certificação Digital Nº 0312525/CA
89
PUC-Rio - Certificação Digital Nº 0312525/CA
90
PUC-Rio - Certificação Digital Nº 0312525/CA
91
A tabela a seguir apresenta o resumo do carregamento obtido pela heurística com base nos dados de entrada da situação descrita na página 86.
Peso total pré-determinado é a capacidade do porão que entramos no programa como dados de entrada do porão
Peso total calculado é o peso calculado a partir da resistência do piso do porão
Peso total embarcado(t) é o peso das placas embarcadas no porão.
Porão
1 2 3 4 5 6 7
Quant. Placas
358 396 449 299 433 409 417
Peso total pré-
determinado
6.444,00 7.563,00 10.200,00 6.095,00 9.540,00 8.117,00 7.070,00
Peso total
calculado
7.420,00 8.766,45 11.362,18 7.111,53 11.304,52 9.097,26 9.344,64
Peso total
embarcado(t)
6.429,20 7.545,20 10.192,30 6.094,00 9.526,00 8.111,10 6.981,00
item 13 - 18 placas item 2 - 236 placas item 4 -133 placas item 10 - 34 placas item 3 - 234 placas item 6 - 90 placas item 9 - 57 placas
item 16 - 116 placas item 6 - 160 placas item 17 - 108 placas item 15 - 150 placas item 8 - 122 placas item 14 - 89 placas item 1 - 214 placas
item 12 - 138 placas
item 11 - 106 placas item 7 - 101 placas item 10 - 77 placas item 13 - 230 placas item 5 - 146 placas
item 9 - 86 placas
item 19 - 52 placas item 2 - 14 placas
item 18 - 50 placas
Distribuição
das placas
Nº total de placas embarcadas: 2761
Peso total da carga (t): 54.878,80
Obs:
PUC-Rio - Certificação Digital Nº 0312525/CA
