Novos
algoritmos para sistemas de produção, localização e transportes
Sigla:
NASPLOT
Resumo:
Este projeto visa contribuir com o desenvolvimento de novos algoritmos eficientes para problemas de Otimização Combinatória. Serão enfocados especialmente os problemas que aparecem nos sistemas de produção, localização e transportes. Serão desenvolvidos algoritmos usando os conceitos de relaxação Lagrangeana/surrogate combinada com o processo de geração de colunas. Também serão exploradas aplicações do Algoritmo Genético Construtivo. Espera-se produzir trabalhos de qualidade que poderão ser divulgados internacionalmente.
1. Introdução
O presente
projeto, denominado NASPLOT – Novos Algoritmos para Sistemas de Produção,
Localização e Transportes, tem como objetivo complementar as pesquisas
do projeto ALESPLOT – Algoritmos Eficientes para Sistemas de Produção,
Localização e Transportes, iniciado em março de 2001 (CNPq, área de
Engenharia de Produção/Pesquisa Operacional, processo # 300837/89-5).
O
objetivo principal do NASPLOT será o de continuar a pesquisa e desenvolvimento de
algoritmos eficientes para problemas de Otimização Combinatória que ocorrem em
Sistemas de Produção e em Alocação/Localização de facilidades e Roteamento de
veículos. Outros objetivos estão na continuação da formação de recursos humanos
e de pesquisa e desenvolvimento, e na colaboração com outros colegas
pesquisadores em projetos temáticos de equipe.
Problemas
de Otimização Combinatória aparecem quando temos que selecionar de um conjunto
discreto e finito de dados o melhor subconjunto que satisfaz a determinados
critérios. Um fato que tem motivado os estudos na área é a dificuldade de
solução da maioria dos problemas de Otimização Combinatória. Até o momento não
se conhecem abordagens eficientes, em tempo de processamento e/ou memória, de
solução geral para esses problemas.
Nos sistemas de produção e em ambientes urbanos
ocorrem diversos problemas de natureza combinatória, que devem ser resolvidos
de maneira otimizada. Entre estes se destacam os problemas de formação de
grupos ou agrupamentos e os de permutação ou escalonamento. Os problemas de agrupamento
aparecem geralmente na classificação de dados para determinados propósitos,
tais como sua armazenagem e recuperação de modo eficiente. Qualquer algoritmo
de agrupamento tenta determinar grupos que ocorrem nos dados por alguma
característica determinante. São usadas medidas de distancias e/ou
similaridades. Os problemas de permutação ocorrem quando se procura a
melhor ordem numa seqüência de tarefas para aumentar a eficiência de processos.
Recursos podem ser requeridos para a execução das tarefas, bem como prioridades
e disponibilidades na execução (entre outras condições).
São vários os problemas importantes que podem ser classificados como de agrupamento
e permutação e que surgem em sistemas de produção e transportes. Entre
eles, os seguintes têm sido estudados e novos algoritmos foram e estão sendo
propostos:
·
Formação de células de manufatura, coloração de grafos, bin-packing,
problemas de cortes e empacotamento, carregamento de palletes, layout de
facilidades, p-medianas, p-medianas capacitado, localização capacitado e
não-capacitado, máxima cobertura, cobertura de conjuntos, rotulação de mapas,
problema generalizado de atribuição, roteamento de veículos com janelas de
tempo, problema de sequenciamento de padrões de corte, problema de minimização
de trilhas no layout de VLSI, problema do caixeiro viajante, problema de
programação de horários para empregados, e outros.
Na seção dois serão descritos os novos algoritmos que
estão sendo desenvolvidos. Na seção três serão descritos alguns dos problemas
que serão abordados. Um cronograma de atividades será apresentado ao final e a
expectativa com respeito a publicações, tese e participações em eventos.
2. Novos
algoritmos
Os novos algoritmos continuarão a ser desenvolvidos
em duas frentes:
-
Uso
combinado das relaxações Lagrangeana e surrogate (relaxação
Lagrangeana/surrogate) com geração de colunas, e
-
Em
meta-heurísticas (meta-heurísticas não-evolutivas e Algoritmo Genético
Construtivo).
·
Relaxação Lagrangeana/surrogate
Esta pesquisa produziu várias publicações
internacionais, com a participação de alunos como co-autores, bem como outros
pesquisadores de instituições brasileiras e do exterior. Seus resultados demonstram
a eficiência do uso combinado das relaxações Lagrangeana e surrogate na solução
de problemas de otimização combinatória.
A continuação das pesquisas deve enfocar o relacionamento entre a
relaxação Lagrangeana/surrogate e o processo tradicional de geração de
colunas em Programação Linear para problemas de grande porte.
É bem conhecida a equivalência entre os
processos de decomposição de Dantzig-Wolfe (DW), geração de colunas e a
relaxação Lagrangeana. Resolver o dual Lagrangeano pelo método de Kelley é
equivalente a aplicar o processo de decomposição de DW ao primal. Entretanto, a
aplicação direta de método de Kelley (ou DW) geralmente enfrenta problemas de
estabilidade, onde muitos cortes (colunas) improdutivos são acrescentados em
fases intermediárias do método de Kelley (DW). A relaxação
Lagrangeana/surrogate fornece colunas de qualidade para o programa mestre do DW
(ou cortes para Kelley), acelerando a solução do problema linear por geração de
colunas.
Um trabalho preliminar foi desenvolvido aplicando
estes conceitos ao problema de p-medianas. Os resultados foram muito bons,
mostrando que geração de colunas pode ser uma alternativa mais rápida que
métodos subgradientes. O uso da relaxação Lagrangeana/surrogate permitiu gerar
um número menor de colunas e obter os mesmos resultados que métodos
tradicionais. Seus tempos computacionais foram também reduzidos em até 50%.
Pode ser mostrado ainda que a relaxação
Lagrangeana/surrogate produz um limite inferior de qualidade para ser usado em
etapas intermediarias do processo de geração de colunas (minimização). Isto
pode ser útil como critério de parada do processo de geração de colunas, e é
especialmente importante quando o subproblema a ser resolvido é um problema
difícil.
Dois alunos de doutorado estão iniciando
pesquisa no assunto, e a colaboração de co-autores continuará a ser enfatizada.
·
Genético Construtivo
As meta-heuristicas, ou heurísticas
modernas, têm se destacado nos últimos anos como métodos eficientes para
solução de problemas de otimização combinatória. Dentre elas, podemos citar a
busca tabu e variações e algoritmos evolutivos.
O Algoritmo Genético Construtivo (AGC)
foi proposto para tratar eficientemente o problema da avaliação de esquemas em
Algoritmos Genéticos, e têm sido desenvolvido e pesquisado no INPE por alunos e
colaboradores de outras instituições. Pretende-se como continuação da pesquisa
estudar o uso do AGC com codificação real, com o processo de geração de colunas e dedicar maior tempo na
análise de parâmetros do método.
Um aluno de doutorado está iniciando
pesquisa no AGC com representação real. Outro aluno de doutorado está finalizando
tese aplicando o AGC a problemas de localização e uma aluna de doutorado está
explorando aplicações do AGC ao problema de rotulação de mapas.
Problemas de roteamento de veículos
e escalas para empregados
São problemas importantes do ponto de
vista econômico, envolvendo a logística de empresas de transportes, incluindo
caminhões, trens e aviões. Do ponto de vista acadêmico, os algoritmos mais
eficientes usam a formulação de particionamento (cobertura) de conjuntos como
problema mestre (gerado em grande parte das aplicações pela aplicação da decomposição de
Dantzig-Wolfe), onde os sub-problemas geradores de colunas são problemas de
fluxo não-triviais (com capacidades e/ou janelas de tempo).
Estaremos
iniciando a aplicação combinada da relaxação Lagrangeana/surrogate com o
processo de geração de colunas, como tese de doutorado do aluno Marcos. A.
Pereira, no curso de Computação Aplicada do INPE.
Problemas de Localização
Os problemas de localização vêm sendo
abordados com a relaxação Lagrangeana/surrogate, com a combinação da relaxação
Lagrangeana/surrogate e o processo de geração de colunas, e ainda com o
Algoritmo Genético Construtivo.
O problema de localização das p-medianas consiste em
localizar p facilidades (medianas) em uma rede de modo a minimizar a soma total
das distâncias de cada nó de demanda à sua mediana mais próxima. No caso
capacitado (p-medianas capacitado) cada nó possui uma demanda e as medianas
possuem capacidades de atendimento.
O problema de localização de máxima cobertura consiste em
localizar p centros que cubram a maior parte da demanda que esteja situada a
uma determinada distância fixada a priori.
Alguns trabalhos estão sendo preparados,
outros já foram submetidos para congressos e/ou revistas. Um aluno de doutorado
está finalizando tese com a aplicação do Genético Construtivo aos problemas de
máxima cobertura e de p-medianas capacitado. Um outro trabalho que combina
Lagrangeana/surrogate e geração de colunas foi terminado recentemente e vai ser
apresentado no congresso EURO’2001.
Problemas de produção
São várias as possibilidades, mas a ênfase
será dada aos problemas de cortes e empacotamento e correlatos. Nesta classe de
problemas a modelagem por geração de colunas é freqüente. Muito pode-se
contribuir com novos algoritmos. Estaremos estudando os problemas de palletes e
o problema de sequenciamento de padrões de corte, através de problema
relacionado ao projeto de circuitos VLSI.
Atividades básicas para períodos de um
ano:
(válidas
para os anos 1 e 2, com as devidas adaptações)
·
Pesquisa e
implementação de algoritmos eficientes para Problemas de Otimização
Combinatória;
·
Pesquisa
sobre novas aplicações dos métodos propostos;
·
Apresentação
dos resultados obtidos em Congressos Internacionais e Nacionais, bem como a
publicação em periódicos de circulação Internacional e Nacional;
·
Orientações
de dissertações e teses.
Participantes:
Dr. Luiz Antonio Nogueira Lorena
Pesquisador Titular
INPE – Instituto Nacional de Pesquisas
Espaciais
Pesquisador nível 1B – CNPq
5 alunos de doutorado do curso de
Computação Aplicada – INPE
Participantes colaboradores da UNESP –
Guaratinguetá, CNPTIA – EMBRAPA – Campinas, UMC – Mogi das Cruzes, UFSCAR – São
Carlos e Imperial College – UK.
Observação:
Detalhes a respeito das informações fornecidas neste projeto, podem ser
encontrados no endereço: http://www.lac.inpe.br/~lorena
Bibliografia relevante ao projeto
1.
Barnhart, C.; Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P. and Vance,
P.H. Branch-and-Price: Column Generation for Solving Huge Integer Programs,
Operations Research 46 (1998) 316-329.
2. Beasley,
J.E. Lagrangean Heuristics for Location Problems. Europen Journal of
Operational Research, 65: 383-399, 1993.
3.
Bodin, L.;
Golden, B.; Assad, A.; Ball, M. Routing and scheduling of vehicles and crews:
the state of the art. Computers and Operations Research, 10(2): 65-211,
1983.
4.
Braca, J.; Bramel, J.; Posner, B.; Simchi-LeviI, D. A computerized
approach to the New York City school bus routing problem. 1995.
5.
Burrough,
P.A. Principles of Geographical Information Systems for Land Resources
Assessment, Clarendon Press, Oxford, 1986.
6.
Christofides,
N.; Mingozzi, A and Toth P. The vehicle routing problem. In Combinatorial
Optimization, Christofides, N. ; Mingizzi, A ; Toth P. and Sandi C. (eds.).
John Wiley, 1979.
7.
Dantzig, G.B. and Wolfe, P. Decomposition principle for linear programs.
Operations Research, 8: 101-111, 1960.
8.
Daskin, M. Network
and Discrete Location: Models, Algorithms, and Applications, Wiley
Interscience, NY, 1995.
9.
Desrochers, M. and Soumis, F. A
Column Generation Approach to the Urban Transit Crew Scheduling Problem,
Transportation Science 23 (1989) 1-13.
10.
Desrosiers,
J. ; Dumas Y.; Solomon, M. M. and Soumis, F. Time constrained routing and
scheduling. In Handbooks in Operations Research and Management Science, Vol8,
Network routing, Ball, M. O , T. L. Magnanti and G. L. Nemhauser (eds.)
North-Holland, 1995.
11.
Drezner, Z.
(ed.) Facility Location: A Survey of Applications and Methods,
Springer-Verlag, NY, 1995.
12.
du Merle, O.; Villeneuve, D.; Desrosiers, J. and
Hansen, P. Stabilized column
generation. Discrete Mathematics, 194:
229-237, 1999.
13. Fischbeck
P. GIS: More than a Map. OR/MS Today 42-45, Aug. 1994.
14. Fisher,
M.L. Vehicle Routing. In: Handbooks in Operations Research and
Management Science, Networks and Distribution, 1992.
15.
Francis,
R.L.; McGinnis, L.F.; White, J.A. Facility Layout and Location: An
Analytical Approach, Prentice Hall, NJ, 1992.
16.
Furtado,
J.C. and Lorena, L.A.N. Algoritmo Genético Construtivo na otimização de
problemas combinatoriais de agrupamentos. III Oficina de cortes e
empacotamento. Curitiba-Nov. 1998
17.
Gengreau, M.
; Laporte G. and Potvin J-Y. Vehicle routing: modern heuristics. In Local
Search in Combinatorial Optimization. Edited by E. Aarts and J. K. Lenstra - p.
311-336. John Wiley, 1997.
18. Gilmore, P.C. and
Gomory, R.E. A linear programming approach to the cutting stock problem.
Operations Research, 9: 849-859, 1961.
19.
Ghosh, A.;
Rushton, G. (eds.) Spatial Analysis and Location-Allocation Models, VNR,
NY 1987.
20.
Glover, F.;
Klingman, D.; Phillips, N. Network Models in Optimization and Their
Applications in Practice, Wiley Interscience, NY, 1992.
21.
Hillsman, E.L. The p-median structure as a unified
linear model for location-allocation analysis. Environment and Planning A,
16, p. 305-318, 1984.
22.
Kelly J. P.
and Xu, J. A set-partitioning based heuristic for the vehicle routing
problem , 1998.
23. Kelley, J.E. The Cutting Plane Method for Solving Convex Programs, Journal of the SIAM 8 (1960)
703-712.
24.
Kohl, N. and Madsen O. B. G. An optimization
algorithm for the vehicle routing problem with time windows based on Lagrangian
relaxation. Operations Research 45: 395-406, 1997.
25.
Laporte, G.
The vehicle routing problem: an overview of exact and approximate algorithms. European
Jounal of Operational Research, 59: 345-358, 1992.
26.
Larson,
R.C.; Odoni, A.R. Urban Operations Research, Prentice Hall, NJ, 1981.
27.
Li, L.Y.O.;
Eglese, W. An interactive algorithm for vehicle routeing for winter-gritting. Jounal
of the Operational Research Society, 47(2): 217-228, 1996.
28.
Lorena, L. A
N. and Narciso, M. G. Using local surrogate information in Lagrangean
relaxation: an application to symmetric traveling salesman problems. Versão
resumida apresentada na 1ª Oficina do projeto temático FAPESP - Planejamento e
Controle da Produção em Sistemas de manufatura. UNICAMP - Abril, 1999.
29.
Lorena, L. A
N. and Narciso, M. G. Using logical surrogate information in Lagrangean
relaxation: an application to symmetric traveling salesman problems.
Apresentado no IFORS´99 - China - Agosto - 1999. Aceito para publicação no EJOR.
30.
Lorena,
L.A.N.; Furtado, J.C. Constructive genetic algorithm for clustering problems.
Apresentado no Optimization 98- Coimbra, Portugal, Jul. 1998. Aceito para
publicação na revista internacional Evolutionary Computation.
31.
Lorena,
L.A.N.; Lopes, F.B. A Dynamic List Heuristic for 2D-Cutting. In: System
Modeling and Optimization, ed. J. Dolezal and J. Fidler, Chapman & Hall,
London, p. 481-488, 1996.
32. Lorena,
L.A.N.; Lopes, F.B. A surrogate heuristic for set covering problems.
European Journal of Operational Research, 79: 138-150, 1994.
33.
Lorena,
L.A.N.; Lopes, L.S. Computational Experiments with Genetic Algorithms Applied
to Set Covering Problems. Pesquisa Operacional, 16(1): 41-53, Jun. 1996.
34.
Lorena,
L.A.N.; Lopes, L.S. Genetic Algorithms Applied to Computationally Difficult Set
Covering Problems. Journal of the Operational Research Society, 48:
440-445, 1997.
35.
Lorena,
L.A.N.; Marengoni, H.F.; Senne, E.L.F. Solving p-Median Problems in Microcomputer.
In: TIMS XXX/SOBRAPO XXIII Joint International Meeting, Rio de Janeiro, RJ,
Jul. 1991. Abstracts, p. 61-62.
36.
Lorena,
L.A.N.; Marengoni, H.F.; Senne, E.L.F. Uso de Microcomputador na Resolução de
Grandes Problemas de p-Medianas. Pesquisa Operacional, 11(1):10-22, Jun.
1991.
37.
Lorena,
L.A.N.; Narciso, M.G. Relaxation Heuristics for Generalized Assignment Problem.
European Journal of Operational Research, 91: 600-610, 1996.
38.
Lorena,
L.A.N. ; Narciso, M. G. and Beasley J. E.
A constructive genetic algorithm for the generalized assignment problem.
Submetido para publicação na revista internacional Evolutionary Optimization
– nov. 1999
39.
Lorena, L. A. N. and Pereira M. A. A Lagrangean/surrogate heuristic for the maximal covering location
problem using Hillsman's edition. Submetido para publicação
- International Journal of Industrial Engineering - Special Issue on Facility
Location and Layout - 2001.
40.
Lorena,
L.A.N.; Senne, E.L.F. A Lagrangean/Surrogate Heuristic for Uncapacitated
Facility Location Problems. VIII CLAIO - Latin-Iberian-American Congress on
Operations Research and System Engineering e XXVIII SBPO - Simpósio Brasileiro
de Pesquisa Operacional, Rio de Janeiro, Ago. 1996.
41.
Lorena,
L.A.N.; Senne, E.L.F. Improving traditional subgradient scheme for Lagrangean
relaxation: an application to location problems, International Journal of
Mathematical Algorithms, Vol. 1, pp. 133-151, 1999.
42.
Lorena,
L. A. N. and Senne, E. L. F. Local search heuristics for capacitated p-median problems
Submetido para publicação – Networks and Spatial Economics – 2001.
43.
Lorena,
L. A. N. ; Senne, E. L. F. ; Paiva, J. A. C. e Pereira M. A. Integração de modelos de localização a sistemas de
informações geográficas. Submetido para publicação - Gestão e
Produção - 2001.
44.
Love, R.F.;
Morris, J.G.; Wesolowsky, G.O. Facilities Location: Models and Methods,
North Holland, NY, 1988.
45.
Marengoni,
H.F.; Lorena, L.A.N.; Senne, E.L.F. A Implementação de um Algoritmo para o
Problema das p-Medianas. In: Seminário de Engenharias e suas Aplicações,
10. FEG, Guaratinguetá, SP, Nov. 1989b. Anais p. 440-447.
46.
Marengoni,
H.F.; Senne, E.L.F.; Lorena, L.A.N. Um Algoritmo Exato para o Problema das
p-Medianas. In: Simpósio Brasileiro de Pesquisa Operacional, 22. Fortaleza,
CE, Out. 1989a. Anais p. 374-380. (Relatório Técnico INPE-4914-PRE/1415, Ago.
1989).
47.
Narciso,
M.G.; Lorena, L.A.N. Lagrangean/surrogate Relaxation for Generalized Assignment
Problems. European Journal of Operational Research , 114(1), 165-177,
1999.
48.
Olivo, A.A.;
Lorena, L.A.N.; Vijaykumar, N.L. Aplicação do problema de grupamento
capacitado no planejamento de uma rede de postos médicos de atendimento
primário. Apresentado no IV Simpósio Latino-Americano de Sensoriamento
Remoto, Bariloche, Argentina, Nov. 1989. Anais, p. 82.
49.
Oliveira
A. C. M. and Lorena, L. A. N. A Constructive Genetic Algorithm for the Linear Gate
Assignment Problem. Submetido para publicação - IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems - 2001
50.
Papadimitriou,
C. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity.
Prentice-Hall, Inc. , Englewood Cliffs, 1982.
51.
Ribeiro
Filho, G.; Lorena, L.A.N. A constructive algorithm for cellular
manufacturing desing. EURO XVI -
16th European Conference on Operational Research, 12 a 15/07/98, Bruxelas,
Bélgica.
52.
Ribeiro
Filho, G.; Lorena, L.A.N. Algoritmo genético construtivo aplicado ao ao
projeto de células de manufatura. III Oficina de cortes e empacotamento/XXX
SBPO, 25 a 27/11/98, Curitiba, PR, anais da III Oficina de Cortes e
Empacotamento, pp. 131-142.
53.
Ribeiro
Filho, G.; Lorena, L.A.N. Improvements on Contructive Genetic Approaches to
Graph Coloring. Versão resumida apresentada na 1ª Oficina do
projeto temático FAPESP - Planejamento e Controle da Produção em Sistemas de
manufatura. UNICAMP - Abril, 1999.
54.
Ribeiro
Filho, G.; Lorena, L.A.N. Improvements on Contructive Genetic Approaches to
Graph Coloring. Apresentado no IFORS´99 - China - Agosto - 1999.
55.
Ribeiro
Filho, G. and Lorena, L. A. N. A Constructive Evolutionary Approach to School Timetabling.
In Applications of Evolutionary Computing , Boers, E.J.W., Gottlieb, J., Lanzi,
P.L., Smith, R.E., Cagnoni, S., Hart, E., Raidl, G.R., Tijink, H., (Eds.) - Springer Lecture Notes in Computer Science vol. 2037, pp. 130-139 - 2001
56.
Ribeiro
Filho, G. and Lorena, L. A. N. A Constructive Evolutionary Approach to the Machine-Part
Cell Formation Problem
In Buildings Competencies for International Manufacturing - Perpectives
for developing countries, A. Fleury, H. Yoshizaki, L. B. M. Guimaraes and J. L.
D. Ribeiro (eds.) UFRGS/FEENG, Porto Alegre, pp. 340-348, 2000
57.
Senne,
E.L.F.; Lorena, L.A.N. Lagrangean/Surrogate Heuristics for p-Median Problems.
In Computing Tools for Modeling, Optimization and Simulation: Interfaces in
Computer Science and Operations Research, M. Laguna and J. L. Gonzalez-Velarde
(eds.) Kluwer Academic Publishers, pp. 115-130, 2000.
58.
Senne,
E.L.F.; Lorena, L.A.N. Lagrangean/Surrogate Heuristics for Facility Location
Problems. In: EURO XV - INFORMS XXXIV Joint International Meeting.
Barcelona, Espanha, Jul. 1997. Abstracts, p. 128.
59.
Senne,
E.L.F.; Lorena, L.A.N.; Narciso, M.G. Lagrangean/Surrogate Relaxation for
Generalized Assignment Problems. In: EURO XV - INFORMS XXXIV Joint
International Meeting. Barcelona, Espanha, Jul. 1997. Abstracts, p. 44.
60.
Senne.
E.L.F. and Lorena, L.A.N. Stabilizing column generation using Lagrangean/surrogate relaxation: an
application to p-median location problems. Submetido para
publicação - European Journal of Operational Research - 2001
61.
Teitz, M.B.
and Bard, P., “Heuristic methods for estimating the vertex median of a weighted
graph” Operations Research 16 (1968) 955-961.
62. Valério de Carvalho, J.M. Exact Solution of
Bin-Packing Problems Using Column Generation and Branch-and-Bound, Universidade
do Minho, Departamento Produção e Sistemas Working Paper, 1996.
63.
Weigel, D.
and Cao, B. Applying GIS and OR techniques to solve Sears
technician-dispatching and home-delivery problems, Interfaces 29: 112-130,
1999.
64.
Yamamoto, M.
, Lorena, L. A N. and Câmara. G. Tabu Search Application for Point Features
Cartographic Label Placement Problem. Aceito para apresentação no MIC´99 -
III Metaheuristics International Conference - Angra dos Reis, July 19-22, 1999.
65.
Yamamoto, M.
; Camara, G. and Lorena, L. A. N. Tabu
search heuristic for point-feature cartographic label placement. Aceito para
publicação na revista internacional Geoinformatica – 1999
66.
Yamamoto, M.
; Camara, G. and Lorena, L. A. N. Uma
aplicação da busca tabu ao problema da rotulação cartográfica de pontos.
Apresentado no GISBRASIL99 - Salvador - Julho 1999