Relaxação Lagrangeana Aplicada ao Problema de Cobertura por Hubs
DOI:
https://doi.org/10.5540/tema.2018.019.03.547Keywords:
Problema de localização de hubs, Relaxação Lagrangeana, Heurística ConstrutivaAbstract
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.References
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
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.