nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Improving Traditional Dual Ascent Algorithm for the Uncapacitated Multiple Allocation Hub Location Problem: A RAMP Approach

verfasst von : Telmo Matos, Fábio Maia, Dorabela Gamboa

Erschienen in: Machine Learning, Optimization, and Data Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Hub Location Problems are complex combinatorial optimization problems that raised a lot of interest in the literature and have a huge number of practical applications, going from the telecommunications, airline transportation among others. In this paper we propose a primal-dual algorithm to solve the Uncapacitated Multiple Allocation Hub Location Problem (UMAHLP). RAMP algorithm combines information of traditional Dual Ascent procedure on the dual side with an improvement method on the primal side, together with adaptive memory structures. The overall performance of the proposed algorithm was tested on standard Australian Post (AP) and Civil Aeronautics Boarding (CAB) instances, comprising 192 test instances. The effectiveness of our approach has been proven by comparing with other state-of-the-art algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Average Performance Analysis of the Stochastic Gradient Method for Online PCA

Nächstes Kapitel Supervised Learning Approach for Surface-Mount Device Production

Alumur, S., Kara, B.Y.: Network hub location problems: the state of the art. Eur. J. Oper. Res. 190(1), 1–21 (2008)MathSciNetMATHCrossRef

Beasley, J.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 65, 1069–1072 (1990)CrossRef

Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238–252 (1962)MathSciNetMATHCrossRef

Boland, N., et al.: Preprocessing and cutting for multiple allocation hub location problems. Eur. J. Oper. Res. 155(3), 638–653 (2004)MathSciNetMATHCrossRef

de Camargo, R.S., et al.: Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput. Oper. Res. 35(4), 1047–1064 (2008)MATHCrossRef

Campbell, J.F.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72(2), 387–405 (1994)MATHCrossRef

Cánovas, L., et al.: Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique. Eur. J. Oper. Res. 179(3), 990–1007 (2007)MathSciNetMATHCrossRef

Contreras, I., et al.: Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6), 1477–1490 (2011)MathSciNetMATHCrossRef

Erlenkotter, D.: A dual-based procedure for uncapacitated facility location. Oper. Res. 26(6), 992–1009 (1978)MathSciNetMATHCrossRef

10.

Ernst, A.T., Krishnamoorthy, M.: Solution algorithms for the capacitated single allocation hub location problem. Ann. Oper. Res. 86, 141–159 (1999)MathSciNetMATHCrossRef

11.

Farahani, R.Z., et al.: Hub location problems: a review of models, classification, solution techniques, and applications. Comput. Ind. Eng. 64(4), 1096–1109 (2013)MathSciNetCrossRef

12.

Fernandez, E.: Locating hubs: an overview of models and potential applications (2013)

13.

Gamboa, D.: Adaptive memory algorithms for the solution of large scale combinatorial optimization problems. Ph.D. thesis (in Portuguese), Instituto Superior Técnico, Universidade Técnica de Lisboa (2008)

14.

Glover, F.: Tabu search—part I. ORSA J. Comput. 1(3), 190–206 (1989)MATHCrossRef

15.

Glover, F.: Tabu search—part II. ORSA J. Comput. 2(1), 4–32 (1990)MATHCrossRef

16.

Klincewicz, J.G.: A dual algorithm for the uncapacitated hub location problem. Locat. Sci. 4(3), 173–184 (1996)MATHCrossRef

17.

Kratica, J., et al.: Genetic algorithm for solving uncapacitated multiple allocation hub location problem. Comput. Inform. 24(4), 415–426 (2005)MATH

18.

Matos, T., Gamboa, D.: Dual-RAMP for the capacitated single allocation hub location problem. In: Gervasi, O., et al. (eds.) ICCSA 2017. LNCS, vol. 10405, pp. 696–708. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62395-5_48CrossRef

19.

Mayer, G., Wagner, B.: HubLocator: an exact solution method for the multiple allocation hub location problem. Comput. Oper. Res. 29(6), 715–739 (2002)MATHCrossRef

20.

Mokhtar, H., et al.: A new Benders decomposition acceleration procedure for large scale multiple allocation hub location problems. In: International Congress on Modelling and Simulation, pp. 340–346 (2017)

21.

O’Kelly, M.E.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32(3), 393–404 (1987)MathSciNetMATHCrossRef

22.

Rego, C.: RAMP: a new metaheuristic framework for combinatorial optimization. In: Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search, pp. 441–460. Kluwer Academic Publishers, Boston (2005)MATHCrossRef

23.

Rego, C., et al.: RAMP for the capacitated minimum spanning tree problem. Ann. Oper. Res. 181(1), 661–681 (2010)MathSciNetMATHCrossRef

24.

Riley, C., et al.: A simple dual-RAMP algorithm for resource constraint project scheduling. In: Proceedings of the 48th Annual Southeast Regional Conference on - ACM SE 2010, p. 1 ACM Press, New York (2010)

Titel: Improving Traditional Dual Ascent Algorithm for the Uncapacitated Multiple Allocation Hub Location Problem: A RAMP Approach
verfasst von: Telmo Matos
Fábio Maia
Dorabela Gamboa
Verlag: Springer International Publishing
Buch: Machine Learning, Optimization, and Data Science
Print ISBN: 978-3-030-13708-3

Electronic ISBN: 978-3-030-13709-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-13709-0_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"