Modelo matemático e meta-heurística Simulated Annealing para o problema de alocação de berços com múltiplas cargas

Autores

  • Rafael Silva Banos UFES-Universidade Federal do Espírito Santo
  • Rodrigo Alvarenga Rosa UFES-Universidade Federal do Espírito Santo
  • Geraldo Regis Mauri Universidade Federal do Espírito Santo
  • Glaydston Mattos Ribeiro Universidade Federal do Espírito Santo

DOI:

https://doi.org/10.14295/transportes.v24i1.980

Palavras-chave:

Problema de Alocação de Berços com Múltiplas Cargas, Simulated Annealing, Operação Portuária.

Resumo

Ocorre no Brasil um forte crescimento do comércio exterior na área de granéis, como minério de ferro e agrícolas que são exportados pelos portos. Assim, metodologias que auxiliem o planejamento da operação dos portos são importantes. Este artigo propõe um modelo matemático aplicado a um porto de granel que difere dos demais por três itens: 1) berços operam mais de um tipo de carga e com taxas de operação diferentes para cada um, 2) certas cargas não são operadas em todos os berços, 3) o tempo de operação é dependente do berço e da carga. O modelo proposto elabora a sequência de atendimento dos navios em cada berço e foi implementado no CPLEX 12.6. Como soluções ótimas são difíceis de serem alcançadas, é proposta também uma meta-heurística Simulated Annealing (SA). Para avaliação do modelo e do SA, foram realizados testes com dados reais do Complexo Portuário de Tubarão.

Downloads

Não há dados estatísticos.

Biografia do Autor

Rafael Silva Banos, UFES-Universidade Federal do Espírito Santo

Engenheiro de Produção UFES

Rodrigo Alvarenga Rosa, UFES-Universidade Federal do Espírito Santo

Pesquisador de Pós Doutorado no Programa de Engenharia de Transportes (PET) na COPPE/UFRJ. Bolsista de Produtividade da Fundação de Amparo à Pesquisa do Espírito Santo (FAPES) recebendo a bolsa Pesquisador Capixaba (2013-2016). Doutor em Engenharia Elétrica pela Universidade Federal do Espírito Santo (UFES), Planejamento Portuário utilizando Inteligência Artificial Distribuída (2006). Mestre em Informática pela UFES, Roteirização de Veículos (1996). Graduado em Engenharia Civil pela UFES (1989). Professor adjunto no Depart. Eng. Produção da UFES; Professor permanente do Mestrado de Engenharia Civil (UFES) - Área de Transportes . Professor permanente do Mestrado Profissional de Gestão Pública (UFES) Pesquisador de modelos matemáticos aplicados às áreas: planejamento da operação portuária, planejamento da operação ferroviária, planejamento logístico e roteirização de veículos. 

Geraldo Regis Mauri, Universidade Federal do Espírito Santo

Bacharel em Ciência da Computação pela Universidade Federal de Ouro Preto (2003), possui Mestrado (2005) e Doutorado (2008) em Computação Aplicada pelo Instituto Nacional de Pesquisas Espaciais - INPE. Atualmente é Professor Adjunto do Departamento de Computação do Centro de Ciências Agrárias da Universidade Federal do Espírito Santo - UFES. Tem experiência na área de otimização combinatória, com ênfase em programação linear, atuando principalmente nas áreas de meta-heurísticas, geração de colunas, algoritmos evolutivos e relaxações.

Glaydston Mattos Ribeiro, Universidade Federal do Espírito Santo

Possui Graduação em Engenharia Civil pela Universidade Federal do Espírito Santo (1999), Mestrado em Engenharia de Transportes pelo Instituto Militar de Engenharia (2002), Doutorado em Computação Aplicada pelo Instituto Nacional de Pesquisas Espaciais (2007) e Pós-Doutorado pela HEC-Montréal/Universidade de Montréal (2011). É professor do Programa de Pós-Graduação em Engenharia de Transportes da COPPE/UFRJ e também atua no Programa de Pós-Graduação em Energia do CEUNES/UFES. Tem experiência na área de Logística e Pesquisa Operacional (ênfase em Otimização Combinatória)

Referências

ANTAQ. (2013) Boletim anual de movimentação de cargas. 2013. Disponível em: <http://www.antaq.gov.br/Portal/Anuarios/Anuario2013/Tabelas/AnaliseMovimentacaoPortuaria.pdf>. Acesso em: junho de 2016.

Barros, V. H.; Costa, T. S.; Oliveira, A. C. M.; Lorena, L. A. N. (2011) Model and heuristic for berth allocation in tidal bulk ports with stock level constraints. Computers and Industrial Engineering, v. 60, n. 4, p. 606-613. DOI: 10.1016/j.cie.2010.12.018

Bierwirth, C.; Meisel, F. (2010) A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, v. 202, n. 3, p. 615-627. DOI: 10.1016/j.ejor.2009.05.031

Buhrkal, K.; Zuglian, S.; Ropke, S.; Larsen, J.; Lusby, R. (2011) Models for the discrete berth allocation problem: A computational comparison. Transportation Research Part E, v. 47, p. 461-473. DOI: 10.1016/j.tre.2010.11.016

Cordeau, J. F.; Laporte, G.; Legato, P.; Moccia, L. (2005) Models and tabu search heuristics for the berth-allocation problem. Transportation Science, v.39, n.4, p. 526-538. DOI: 10.1287/trsc.1050.0120

Golias, M. M. (2007) The discrete and continuous berth allocation problem: Models and algorithms. Dissertação (Doctor of Philosophy Graduate Program in Civil and Environmental Engineering). The State University of New Jersey, New Brunswick.

Guan, Y.; Xiao, W. Q.; Cheung, R. K.; Li, C. L. (2002) A multiprocessor task scheduling model for berth allocation: heuristic and worst case analysis. Operations Research Letters, v. 30, n. 5, p. 343-350. DOI: 10.1016/S0167-6377(02)00147-5

Hansen, P., Oguz, C. (2003) A note on formulations of static and dynamic berth allocation problems. Les Cahiers du GERAD 30, 1–17.

Hansen, P.; Oguz, C.; Mladenovic, N. (2008) Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, v. 191, n. 3, p. 636-649. DOI: 10.1016/j.ejor.2006.12.057

Imai, A.; Nagaiwa, K.; Tat, C. W. (1997) Efficient planning of berth allocation for container terminals in Asia. Journal of Advanced Transportation, v. 31, n. 1, p. 75-94, 1997. DOI: 10.1002/atr.5670310107

Imai, A., Nishimura, E., Papadimitriou, S. (2003) Berth allocation with service priority. Transportation Research Part B, v. 37, n. 5, p. 437–457. DOI: 10.1016/S0191-2615(02)00023-1

Imai, A.; Sun, X.; Nishimura, E.; Papadimitriou, S. (2005) Berth allocation in a container port: using a continuous location space approach. Transportation Research Part B, v. 39, n. 3, p. 199–221. DOI: 10.1016/j.trb.2004.04.004

Imai, A., Nishimura, E., Papadimitriou, S. (2008) Berthing ships at a multi-user container terminal with a limited quay capacity. Transportation Research Part E, v. 44, n. 1, p. 136–151. DOI: 10.1016/j.tre.2006.05.002

Imai, A.; Chen, H. C.; Nishimura, E.; Papadimitriou, S. (2008) The simultaneous berth and quay crane allocation problem. Transportation Research Part E, v. 44, n. 5, p. 900-920. DOI: 10.1016/j.tre.2007.03.003

Imai, A.; Nishimura, E.; Papadimitriou, S. (2001) The dynamic berth allocation problem for a container port. Transportation Research Part B, v. 35, n. 4, p. 401–417. DOI: 10.1016/S0191-2615(99)00057-0

Júnior, A. D. C. G., Souza, M. J. F., Martins, A. X. (2005). Simulated annealing aplicado à resolução do problema de roteamento de veículos com janela de tempo. TRANSPORTES, v. 13, n. 2, p. 5-20. DOI: 10.14295/transportes.v13i2.98

Kim, K. H.; Moon, K.c. (2003) Berth scheduling by simulated annealing. Transportation Research Part B, v. 37, n. 6, p. 541-560. DOI: 10.1016/S0191-2615(02)00027-9

Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983) Optimization by Simulated Annealing. Science, v. 220, n. 4598, p. 671-680. DOI: 10.1126/science.220.4598.671

Lai, K. K.; Shih, K. (1992) A study of container berth allocation. Journal of Advanced Transportation, v. 26, n. 1, p. 45-60. DOI: 10.1002/atr.5670260105

Li, C-L.; Cai, X.; Lee, C-Y. (1998) Scheduling with multiple-job-on-one-processor pattern. IIE Transactions, v. 30, n. 5, p. 433-445. DOI: 10.1023/A:1026487022192

Lim, A. (1998) The berth planning problem. Operations Research Letters, v. 22, n. 2-3, p. 105-110. DOI: 10.1016/S0167-6377(98)00010-8

Mauri, G. R.; Oliveira, A. C. M.; Lorena, L. A. N. (2008a) Heurística baseada no Simulated Annealing aplicada ao problema de alocação de berços. GEPROS - Gestão da Produção, Operações e Sistemas, Ano 3, v. 1, n. 1, p. 113-127.

Mauri, G. R.; Oliveira, A. C. M.; Lorena, L. A. N. (2008b) A hybrid column generation approach for the berth allocation problem. In: VAN EMERT, J.; COTTA, C. (Eds.), EvoCOP 2008, Lecture Notes in Computer Science, v. 4972, p. 110-122, Springer. DOI: 10.1007/978-3-540-78604-7_10

Mauri, G.r., Oliveira, A.c.m., Lorena, L.a.n. (2010) Resolução do Problema de Alocação de Berços Através de Uma Técnica de Geração de Colunas. Pesquisa Operacional, v. 30, n. 3, p. 547–562. DOI: 10.1590/S0101-74382010000300003

Monaco, M. F.; Sammarra, M. (2007) The berth allocation problem: A Strong formulation solved by a lagrangean approach. Transportation Science, v. 41, n. 2, p. 265-280. DOI: 10.1287/trsc.1060.0171

Nishimura, E.; Imai, A.; Papadimitriou, S. (2001) Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research, v. 131, n. 2, p. 282-292. DOI: 10.1016/S0377-2217(00)00128-4

Oliveira, R. M.; Mauri, G. R.; Lorena, L. A. N. (2012) Clustering search heuristics for solving a continuous berth allocation problem. Lecture Notes in Computer Science, v. 7245, p. 49-62. DOI: 10.1007/978-3-642-29124-1_5

Park, K. T.; Kim, K. H. (2002) Berth scheduling for container terminals by using a sub-gradient optimization technique. Journal of the Operational Research Society, v. 53, p. 1054-1062. DOI: 10.1057/palgrave.jors.2601412

Rodrigues, M. H. P.; Machado, C. M. S.; Lima, M. L. P. (2013) Simulated annealing aplicado ao problema de alocação de berços. Journal of Transport Literature, v. 7, n. 3, p. 117-136. DOI: 10.1590/S2238-10312013000300006

Rodrigues, P. H.; Rosa, R. A.; Arpini, B. P.; Bissoli, A. L.; Ribeiro, G. M. (2015) Planejamento de atracação de navios por meio de um modelo matemático para o problema de alocação de berços contínuos com descontinuidade do cais. TRANSPORTES, v. 23, n. 1, p. 37-46. DOI: 10.4237/transportes.v23i1.681

Rosa, R. A.; Resendo, L. C.; Lopes, F. T. (2013) Proposta de um Modelo Matemático para o Problema de Alocação de Berços para Múltiplas Cargas (PAB-MC) com Restrições Temporais e Espaciais. In: CNT Confederação Nacional do Transporte. (Org.). Transporte em Transformação XVII. 1ed. Brasília: Positiva, v. 1, p. 133-150.

Sindamares. (2013) Administração do Complexo Portuário de Tubarão e Praia Mole (TPM). Disponível em: <http://www.sindamares.com.br/tubarao.html>. Acesso em: Julho de 2013.

Teixeira, R. B.; Cunha, C. B. (2012) Modelo integrado para seleção de cargas e reposicionamento de contêineres vazios no transporte marítimo. TRANSPORTES, v. 20, n. 1, p. 59-70. DOI: 10.4237/transportes.v20i1.442

Theofanis, S., Boile, M., Golias, M. (2007) An optimization based genetic algorithm heuristic for the berth allocation problem. IEEE Congress on Evolutionary Computation 2007 (CEC 2007). IEEE Computer Society, Washington DC, pp. 4439–4445. DOI: 10.1109/CEC.2007.4425052

Ting, C. J.; Lin, S. W.; Wu, K. C. (2013) The Continuous Berth Allocation Problem by Simulated Annealing, In: APIEMS Conference 2013 Proceedings, Cebu, Philippines.

Tong, C. J.; Lau, H. C.; Lim, A. (1999) Ant colony optimization for the ship berthing problem. In: THIAGARAJAN, P.S.; Yap, R. (Eds.), Fifth Asian Computing Science Conference (ASIAN’99), Lecture Notes in Computer Science, v.1742, p. 359-370, Springer. DOI: 10.1007/3-540-46674-6_30

Vervloet, H. L., Rosa, R. A. (2016) Modelo matemático para planejamento da atracação de navios sob o contrato de charter party. TRANSPORTES, no prelo.

Downloads

Publicado

21-04-2016

Como Citar

Banos, R. S., Rosa, R. A., Mauri, G. R., & Ribeiro, G. M. (2016). Modelo matemático e meta-heurística Simulated Annealing para o problema de alocação de berços com múltiplas cargas. TRANSPORTES, 24(1), 51–62. https://doi.org/10.14295/transportes.v24i1.980

Edição

v. 24 n. 1 (2016)

Seção

Artigos

Licença

Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:

  1. Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
  2. Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
  3. Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
  4. Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
  5. Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
  6. Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.