Agosto 2016 vol. 2 num. 1 - XVIII Simpósio de Pesquisa Operacional & Logística da Marinha

Artigo Completo - Open Access.

Idioma principal

APROXIMAÇÃO EXTERNA/DECOMPOSIÇÃO DE BENDERS PARA PROJETO DE REDES SOB CONGESTIONAMENTO VIA -ÓTIMO

Santos, Karolliny Danielle ; Miranda Júnior, Gilberto de ; Camargo, Ricardo Saraiva de ;

Artigo Completo:

Neste trabalho apresenta-se a técnica de seleção de cortes de Benders conhecida como -ótimo ao problema de projeto de redes sob congestionamento, via Aproximação Externa/ Decomposicão de Benders. O problema de projeto de redes tem uma ampla aplicação em atividades de planejamento, estratégias de empresas que operam sistemas de distribuição, produção, transporte de energia, matéria, etc; visa atender as demandas dos clientes, assegurar o lucro e a eficiência da operação e respeitar os níveis de serviço pré-estabelecidos. Deste esforço de modelagem derivou um programa não-linear, NP-difícil e de grande porte. Experimentos computacionais e comparações com versões mais simples demonstram o sucesso do esquema adotado.

Artigo Completo:

Download (PDF)

Palavras-chave: Projeto de Redes com Custos Convexos; Método de Decomposição de Benders; Aproximação Externa; Esquema -ótimo,

Palavras-chave: ,

DOI: 10.5151/marine-spolm2015-140578

Referências bibliográficas
  • [1] Altiparmak, F., Dengiz, B., and Smith, A. E. (2003). Optimal design of reliable computer networks: A comparison of metaheuristics. Journal of Heuristics, 9(6):471–487.
  • [2] Benchakroun, A., Ferland, J., and Cleroux, R. (1992). Distribution system planning through a generalized benders decomposition approach. European journal of operational research, 62(2):149– 16
  • [3] Contreras, I., Fernández, E., and Marín, A. (2009). Tight bounds from a path based formulation for the tree of hub location problem. Computers & Operations Research, 36(12):3117–3127.
  • [4] Contreras, I., Fernández, E., and Marín, A. (2010). The tree of hubs location problem. European Journal of Operational Research, 202(2):390–400.
  • [5] Cordeau, J.-F., Pasin, F., and Solomon, M. M. (2006). An integrated model for logistics network design. Annals of operations Research, 144(1):59–82.
  • [6] Costa, A. M. (2005). A survey on benders decomposition applied to fixed-charge network design problems. Computers & operations research, 32(6):1429–1450.
  • [7] Dantzig, G. (1962). Linear Programming and Extensions. Princeton University Press.
  • [8] De Camargo, R. S., De Miranda, G., and Ferreira, R. P. (2011). A hybrid outerapproximation/ benders decomposition algorithm for the single allocation hub location problem under congestion. Operations Research Letters, 39(5):329–337.
  • [9] de Sá, E. M., de Camargo, R. S., et al. (2013). An improved benders decomposition algorithm for the tree of hubs location problem. European Journal of Operational Research.
  • [10] Dias, P. G. F., de Miranda Jr, G., Saldanha, R. R., and de Camargo, R. S. (2011). Projeto de rede com custos convexos e balanceamento de fluxos. Revista Controle & Automação/Vol. X no. X/Fev, page 1.
  • [11] Duran, M. and Grossmann, I. E. (1986). An outer-approximation algorithm for a class of mixed integer nonlinear programms. Mathematical Programming, 36:307–339.
  • [12] Fletcher, R. and Leyffer, S. (1994). Solving mixed integer nonlinear programs by outer approximation. Mathematical programming, 66(1-3):327–349.
  • [13] Geoffrion, A. (1972). Generalized Benders decomposition. Journal of optimization Theory and Applications, 10(4):237–260.
  • [14] Grossmann, I. E. and Kravanja, Z. (1995). Mixed-integer nonlinear programming techniques for process systems engineering. Computers & chemical engineering, 19:189–204.
  • [15] Hahn, P., Anjos, M., Burkard, R., Karisch, S., and Rendl, F. (2006). Qaplib-a quadratic assignment problem library. Avialable at http://www. seas. upenn. edu/qaplib.
  • [16] Huang, S., Batta, R., and Nagi, R. (2005). Distribution network design: Selection and sizing of congested connections. Naval Research Logistics (NRL), 52(8):701–712.
  • [17] Hwang, F. K. and Richards, D. S. (1992). Steiner tree problems. Networks, 22(1):55–89.
  • [18] Karuppiah, R., Furman, K. C., and Grossmann, I. E. (2008). Global optimization for scheduling refinery crude oil operations. Computers & Chemical Engineering, 32(11):2745–2766.
  • [19] Klincewicz, J. G. (1998). Hub location in backbone/tributary network design: a review. Location Science, 6:307–335.
  • [20] Maculan, N. (1987). The Steiner problem in graphs. Annals of Discrete Mathematics, 31:185–212.
  • [21] Magnanti, T. L., Mirchandani, P., and Wong, R. T. (1986). Tailoring Benders decomposition for uncapacitated network design. Mathematical Programming Study, 26:112–154.
  • [22] Magnanti, T. L. and Wong, R. T. (1981). Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3):464–483.
  • [23] Miranda, G., Luna, H., De Camargo, R., and Pinto, L. (2011). Tree network design avoiding congestion. Applied Mathematical Modelling, 35(9):4175–4188.
  • [24] Papadakos, N. (2008). Practical enhancements to the magnanti–wong method. Operations Research Letters, 36:444–449.
  • [25] Ramírez-Rosado, I. J. and Domínguez-Navarro, J. A. (2006). New multiobjective tabu search algorithm for fuzzy optimal planning of power distribution systems. Power Systems, IEEE Transactions on, 21(1):224–233.
  • [26] Randazzo, C. and Luna, H. (2001). A comparison of optimal methods for local access uncapacitated network design. Annals of Operations Research, 106:263–286.
  • [27] Yuan, X., Zhang, S., Pibouleau, L., and Domenech, S. (1988). Une méthode d’optimisation non linéaire en variables mixtes pour la conception de procédés. RAIRO-Operations Research- Recherche Opérationnelle, 22(4):331–346.
Como citar:

Santos, Karolliny Danielle; Miranda Júnior, Gilberto de ; Camargo, Ricardo Saraiva de; "APROXIMAÇÃO EXTERNA/DECOMPOSIÇÃO DE BENDERS PARA PROJETO DE REDES SOB CONGESTIONAMENTO VIA -ÓTIMO", p. 544-555 . In: Anais do XVIII Simpósio de Pesquisa Operacinal & Logística da Marinha. São Paulo: Blucher, 2016.
ISSN 2175-6295, ISBN: 2358-5498
DOI 10.5151/marine-spolm2015-140578

últimos 30 dias | último ano | desde a publicação


downloads


visualizações


indexações