Este relatório apresenta os resultados do desenvolvimento de técnicas eficientes para resolução de problemas combinatórios. Para avaliar as técnicas desenvolvidas foram considerados os seguintes problemas:

1) Alocação Dinâmica de Espaços (ADE);

2) Diversidade Máxima (DM);

3) Planejamento Operacional de Lavra (POLAD);

4) Programação Integrada de Veículos e Tripulações no Sistema de Transporte Público (PPVT);

5) Seqüenciamento em Uma Máquina com penalidades por Antecipação e Atraso da produção (PSUMAA);

6) Roteamento de veículos com coleta e entrega simultânea (PRVCES);

7) Recobrimento de Rotas com Coleta de Prêmios (PRRCP)

8) Árvore Geradora Mínima Capacitada em Níveis (MLCMST)

9) Fluxo de Produção em Mineração (FPM)

O trabalho está organizado como segue. Na seção 2 é listada a produção científica gerada. Na seção 3 são enumerados os sistemas computacionais desenvolvidos. Na última seção são anexados todos os trabalhos produzidos.

2 Produção científica

Com relação à produção científica, todos os objetivos traçados foram alcançados, tendo-se, inclusive, superado a produção originalmente proposta.

2.1 Artigos em eventos nacionais

Propostos: 04 Apresentados e publicados: 11

1) ADE-SBPO2009.pdf: Silva, G. C.; Boaventura, P. O; Bahiense, L.; Ochi, L. S. O problema de alocação dinâmica de espaços: aplicação das metaheuristicas GRASP e Busca Tabu. Anais do XLI Simposio Brasileiro de Pesquisa Operacional (XLI SBPO) (CD-ROM) - Porto Seguro/BA - 2009.

2) DM-SBPO2008.pdf: Duarte, I. L.; Silva, G. C.; Costa, T. A. Algoritmos Heurísticos para o Problema da Diversidade Máxima. In: XL Simpósio de Pesquisa Operacional, 2008, João Pessoa. Anais do XL SBPO, 2008.

3) POLAD-SBPO2009.pdf: Ribas, S.; Coelho, I. M.; Souza, M. J. F.; Menotti, D. Parallel Iterated Local Search aplicado ao planejamento operacional de lavra In: XLI Simpósio Brasileiro de Pesquisa Operacional, 2009, Porto Seguro. Anais do XLI SBPO. Rio de Janeiro: SOBRAPO, 2009. v.1. p. 2037-2047.

4) POLAD-CBRN2009.pdf: Ribas, S.; Coelho, I. M., Souza, M. J. F., Coelho, V. N. Um algoritmo híbrido, baseado em GRASP, VND e Iterated Local Search para o planejamento operacional de lavra In: IX Congresso Nacional de Redes Neurais e Inteligência Computacional, 2009, Ouro Preto. Anais do IX CBRN. SBRN, 2009. v.1. 5 p.

5) POLAD-IBRAM2008.pdf: Araújo, F. C. R.; Souza, M. J. F. Planejamento operacional de lavra com alocação dinâmica de caminhões: abordagens exata e heurística In: V Congresso Brasileiro de Mina a Céu Aberto, 2008, Belo Horizonte. Anais do V CBMCA. Belo Horizonte: IBRAM, 2008. v.1. 14 p.

6) POLAD-SIMPEP2008.pdf: Coelho, I. M.; Ribas, S.; Souza, M. J. F. Um algoritmo baseado em GRASP, VND e Iterated Local Search para a resolução do Problema de Planejamento Operacional de Lavra In: XV Simpósio de Engenharia de Produção, 2008, Bauru. Anais do XV SIMPEP. Bauru (SP): UNESP, 2008. v.1. 12 p.

7) PPVT-SBPO2008.pdf: Souza, M. J. F., Ribas, S.; Coelho, I. M. Um algoritmo heurístico híbrido para resolução do problema de programação integrada de veículos e tripulações In: XL Simpósio Brasileiro de Pesquisa Operacional, 2008, João Pessoa (PB). Anais do XL SBPO. Rio de Janeiro: Instituto de Lógica, Filosofia e Teoria da Ciência, 2008. v.1. p.1871 – 1882.

Além da produção anterior, também foram geradas duas dissertações de mestrado tratando do tema Roteirização, com co-orientação do coordenador do presente projeto. Desses dois trabalhos foram gerados dois artigos, um dos quais ganhou o prêmio de produção acadêmica 2009, concedido pela Confederação Nacional do Transporte (CNT) e Associação Nacional de Pesquisa e Ensino em Transportes (ANPET):

8) PRRCP-CBRN2009.pdf: SILVA, M. S. A.; Mine, M. T.; Ochi, L. S.; Souza, M. J. F. Um algoritmo evolutivo híbrido para o problema de recobrimento de rotas com coleta de prêmios In: IX Congresso Nacional de Redes Neurais e Inteligência Computacional, 2009, Ouro Preto. Anais do IX CBRN. SBRN, 2009. v.1. 5 p.

9) PRVCES-ANPET2009.pdf: Mine, M. T.; Silva, M. S. A.; Ochi, L. S.; Souza, M. J. F. O Problema de Roteamento de Veículos com Coleta e Entrega Simultânea: Uma Abordagem Via Iterated Local Search e GENIUS. Capítulo de livro a ser publicado na série Transporte em transformação IX: trabalhos vencedores do prêmio CNT de Produção Acadêmica 2009.

Vinculado às dissertações de mestrado orientadas ao tema Seqüenciamento em uma máquina foram publicados vários trabalhos completos, dos quais xx são listados a seguir.

10) PSUMAA-SBPO2009.pdf: Rosa, B. F.; Souza, M. J. F.; Souza, S. R. Uma nova formulação de programação matemática indexada no tempo para uma classe de problemas de seqüenciamento em uma máquina. In XLI Simpósio Brasileiro de Pesquisa Operacional, 2009, Porto Seguro. Anais do XLI SBPO, SOBRAPO, p. 2898-2909.

11) PSUMAA-CNMAC2009.pdf: Rosa, B. F.; Souza, S. R.; Souza, M. J. F. Formulações de Programação Matemática para o Problema de Sequenciamento em uma Máquina com Janelas de Entrega Distintas e Tempo de Preparação Dependente da Sequência de Produção. In XXXII Congresso Nacional de Matemática Aplicada e Computacional, 2009, Cuiabá. Anais do XXXII CNMAC, SBMAC, 7p.

2.2 Artigos em eventos internacionais

Propostos: 00 Apresentados e publicados: 03

1) POLAD-CILAMCE2009.pdf: Coelho, I. M.; Ribas, S.; Souza, M. J. F., Coelho, V. N., Ochi, L. S. A hybrid heuristic algorithm based on GRASP, VND and Path Relinking for the open-pit-mining problem In: XXX Iberian Latin America Congress on Computational Methods in Engineering, 2009, Búzios (RJ). Proceedings of the XXX CILAMCE. Rio de Janeiro: UFRJ, 2009. v.1. 14p.

2) PPVT-EngOpt2008.pdf: Souza, M. J. F.; Silva, G. P.; Ribas, S.; Coelho, I. M. An algorithm based on Iterated Local Search, Variable Neighborhood Descent and Tabu Search for the Integrated Vehicle and Crew Scheduling Problem In: International Conference on Engineering Optimization, 2008, Rio de Janeiro. Proceedings of the EngOpt 2008. Rio de Janeiro: UFRJ, 2008. v.1. 9 p..

3) ADE-EngOpt2008.pdf: Silva, G. C.; Ferreira, T. G.; Costa, T. A.; Boaventura, P. O., and O, L. S. A Tabu Search Heuristic for the Dynamic Space Allocation Problem. Proc. of the International Conference on Engineering Optimization (EngOpt2008). Sponsoring Societies: Mathematical Programming Society (MPS), ISSMO, EUROPT, ABCM.

2.3 Artigos submetidos a periódicos internacionais

Proposto: 02 Realizado: 02

1) POLAD-EJOR-S-09-00886: Souza, M. J. F.; Coelho, I. M.; Ribas, S. A hybrid heuristic algorithm for the open-pit-mining operational planning problem. Submetido a European Journal of Operational Research, 2009. Em processo de revisão.

2) MLCMST-JournalOfHeuristics2009.pdf: Martins, A. X.; de Souza, M. C.; Souza, M. J. F.; Toffolo, T. A. M. GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem. Journal of Heuristics, v. 15, p. 133-151, DOI: 10.1007/s10732-008-9079-x.

Encontra-se em fase final de revisão o artigo A hybrid metaheuristic algorithm for the Integrated Vehicle and Crew Scheduling Problem para submissão a periódico de circulação internacional (arquivo PPVT-COR-2010.pdf)

2.4 Dissertações de mestrado

Proposta: 01 Realizada: 05

1) POLAD--Dissertacao-Araujo-2009.pdf: Araújo, F. C. Planejamento operacional de lavra com alocação dinâmica de caminhões: abordagens exata e heurística. Dissertação de mestrado, Programa de Pós-Graduação em Engenharia Mineral, Universidade Federal de Ouro Preto, 2008. Orientador: Marcone Jamilson Freitas Souza.

2) PPVT--Dissertacao-Simoes-2009.pdf: Simões, E. M. L. Algoritmo para programação integrada de veículos e tripulações no sistema de transporte público por ônibus. Dissertação de mestrado, Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Minas Gerais, 2009. Orientador: Geraldo Robson Mateus, Co-orientador: Marcone Jamilson Freitas Souza.

3) FluxoProdutos--Dissertacao-Toffolo-2009.pdf: Toffolo, T. A. M. Otimização do fluxo de produtos em uma empresa mineradora. Dissertação de mestrado, Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Minas Gerais, 2009. Orientador: Geraldo Robson Mateus, Co-orientador: Marcone Jamilson Freitas Souza.

4) PSUMAA-Dissertacao-Penna-2009.pdf: Penna, P. H. V. Um algoritmo heurístico híbrido para minimizar os custos com a antecipação e o atraso da produção em ambientes com janela de entrega e tempos de preparação dependentes da sequência de produção. Programa de Pós-Graduação em Engenharia Mineral, Universidade Federal de Ouro Preto, 2009. Orientador: Marcone Jamilson Freitas Souza.

5) PSUMAA--Dissertacao-Rosa-2009.pdf: Rosa, B. F. Heurísticas para o problema de seqüenciamento em uma máquina com penalidades por antecipação e atraso da produção. Programa de Pós-Graduação em Modelagem Matemática e Computacional, Centro Federal de Educação Tecnológica – CEFET-MG, 2009. Orientador: Marcone Jamilson Freitas Souza.

2.5 Relatórios técnicos

Foram disponibilizados os seguintes relatórios técnico-científicos na página do coordenador (endereço http://www.iceb.ufop.br/decom/prof/marcone/Publicacoes/Publicacoes.htm):

PPVT-RelatorioTecnico-2009.pdf: Souza, M. J. F. Programação integrada de veículos e tripulações de ônibus urbano. Relatório técnico-científico CNPq, processo 474831/2007-8, 2009.

POLAD-RelatorioTecnico-2009.pdf: Souza, M. J. F. Planejamento operacional de lavra. Relatório técnico-científico CNPq, processo 474831/2007-8, 2009.

3 Sistemas desenvolvidos

Foram desenvolvidos os seguintes produtos computacionais, relativos aos problemas tratados:

1) Algoritmo GVILS, combinando as técnicas GRASP, Variable Neighborhood Descent e Iterated Local Search para resolver o Problema de Planejamento Operacional de Lavra (POLAD);

2) Algoritmo H-GVILS, combinando módulo de programação matemático (acionando otimizador GLPK) com as técnicas GRASP, Variable Neighborhood Descent e Iterated Local Search para resolver o Problema de Planejamento Operacional de Lavra (POLAD);

3) Algoritmo ILS-VND-BTRA, combinando as técnicas heurísticas Iterated Local Search, Variable Neighborhood Descent e Busca Tabu com Relaxação Adaptativa, para resolver o Problema de Programação Integrada de Veículos e Tripulações (PPVT);

4) Framework OptFrame, de código aberto, sob licença de uso GNU LGPLv3, para desenvolvimento de algoritmos de otimização (disponível em http://sourceforge.net/projects/optframe);

5) Algoritmos GRASP e TABU para resolução do problema de Alocação Dinâmica de Espaços (ADE);

6) Algoritmos ILS1, ILS2 e ILS3, baseados em Iterated Local Search, para resolução do problema da Diversidade Máxima;

7) Algoritmo heurístico GRASP integrado com otimizador baseado em programação matemática para resolver o problema da árvore geradora mínima capacitada em níveis (MLCMST)

8) Algoritmo BT-VND-PR, combinando as técnicas Busca Tabu, Variable Neighborhood Descent e Path Relinking para resolver o problema de seqüenciamento em uma máquina com penalidades por antecipação e atraso da produção.

9) Algoritmo GPV, combinando as técnicas GRASP, Princípio da Otimalidade Próxima e Variable Neighborhood Descent para resolver o problema de seqüenciamento em uma máquina com penalidades por antecipação e atraso da produção.

4 Anexos

Seguem os relatórios técnico-científicos, artigos e dissertações produzidas durante a execução do projeto.