Relaxação Lagrangeana Aplicada ao Problema de Cobertura por Hubs

Autores

  • Clayton Henrique Samora Faculdade de Engenharia Elétrica e de Computação - UNICAMP
  • Fábio Luiz Usberti IC/Unicamp
  • Christiano Lyra Faculdade de Engenharia Elétrica e de Computação - UNICAMP

DOI:

https://doi.org/10.5540/tema.2018.019.03.547

Palavras-chave:

Problema de localização de hubs, Relaxação Lagrangeana, Heurística Construtiva

Resumo

Este trabalho tem por objetivo investigar e propôr novas formulações para o problema de cobertura por hubs capacitado de alocação única com custo fixo. Este problema envolve a localização de nós hubs e a atribuição de nós de demandas aos hubs de modo que o tempo de percurso entre qualquer par de nós origem-destino não exceda a janela máxima de tempo e a capacidade de processamento dos hubs. Uma relaxação Lagrangeana é proposta e através do método do subgradiente são obtidos limitantes primais e duais. Para acelerar o método subgradiente, uma heurística construtiva primal fornece boas soluções de partida, além disso, foi realizada uma etapa de pré-processamento das instâncias para a eliminação de variáveis dos modelos. Experimentos computacionais foram realizados com um conjunto de instâncias reais da "Australian Post". Os resultados indicam que a relaxação lagrangeana proposta, quando comparada com a solução do modelo da literatura, foi capaz de aprimorar os limitantes primais e duais sob limites de tempo de execução e de consumo de memória.

Referências

S. Alumur, Kara, B. Y., Network hub location problem: the state of the art.

{em European Journal of Operational Research },

{bf v.190 }, n. 1 (2008), p. 1-21.

D. L. Bryan, M. E. O'Kelly (1999), Hub-and-spoke network in air

transportation: an analytical review. {em Journal of Regional Science },

{bf v. 39 }, n. 2, p. 275-295.

J. F. Campbell , Integer programming formulation of discrete hub location problems.

{em European Journal of Operational Research }, {bf v.72 }

(1994b), p.387-405.

J. F. Campbell, Morton E. O'Kelly, Twenty-five years of hub location research.

{em Transportation Science }, {bf v. 46 } (2012), p. 153-169.

I. Contreras, J. A. Díaz, E. Fernández. A Lagrangean relaxation approach for the

capacitated single allocation hub location problem. ``Meeting of the thematic network:

Analysis and applications decisions on locations of services and related problems'',

Baeza, Spain, Mars 2007.

A. T. Ernst, M. Krishnamoorthy, Efficient algorithms for the uncapacitated

single allocation p-hub median problem. {em Location Science }, {bf v. 4 }

(1996b), n. 3, p. 139-154.

A. M. Geoffrion, The Lagrangian relaxation method for solving integer programming problems.

{em Management Science }, {bf v.27 }, n. 1 (1974), p. 1-18.

J. L. Goffin, On convergence rate of subgradient optimization methods.

{em Mathematical Programming }, {bf v. 13 } (1977), p. 329-347.

B. Y. Kara, B. C. Tansel, The single-assignment hub covering problem: models and linearizations.

{em Journal of the Operational Research Society }, {bf v. 54 } (2003), p. 59-64.

J. G. Klincewicz, Hub location in backbone tributary network design: a review.

{em Location Science }, {bf v.6 } (1998), p. 307-335.

S. Martello, D. Pisinger, P. Toth., Dynamic programming and strong bounds

for the 0-1 knapsack problem. {em Management Science }, {bf 45 } (3) (1999) INFORMS.

M. E. O'Kelly, The location of interacting hub facilities.

{em Transportation Science }, {bf v. 20 } (1986), p. 92-106.

M. E. O'Kelly, A quadratic integer programming for location of interacting hub facilities.

{em European Journal of Operational Research }, {bf v. 32 } (1987), p. 393-404.

D. Skorin-Kapov, J. Skorin-Kapov, M. E. O'Kelly, Tight linear programming relaxations

of uncapacitated p-hub median problems. {em European Journal of Operation Research },

{bf v. 94 } (1996a), p. 582-593.

A. Turgut, Lagrangian relaxation based approaches to capacitated hub-and-spoke

network design problem. {em European Journal of Operational Research }, {bf v. 79 }

(1994), p. 501-5023.

A. Turgut, Networking policies for hub-and-spoke systems with applications

to the air transportation system. {em Transportation Science }, {bf v. 3 } (1995), p. 201-221.

B. Wagner, Model formulation for hub covering problems. {em Journal of the

Operational Research Society }, {bf v. 59 } (2008), n. 7, p. 932-938.

Downloads

Publicado

2018-12-17

Como Citar

Samora, C. H., Usberti, F. L., & Lyra, C. (2018). Relaxação Lagrangeana Aplicada ao Problema de Cobertura por Hubs. Trends in Computational and Applied Mathematics, 19(3), 547. https://doi.org/10.5540/tema.2018.019.03.547

Edição

Seção

Artigo Original