Skip to main content

2019 | OriginalPaper | Buchkapitel

Pareto-Based Hybrid Algorithms for the Bicriteria Asymmetric Travelling Salesman Problem

verfasst von : Yulia V. Kovalenko, Aleksey O. Zakharov

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

We consider the bicriteria asymmetric travelling salesman problem (bi-ATSP): Given a complete directed graph where each arc is associated to a couple of positive weights, the aim is to find the Pareto set, consisting of all non-dominated Hamiltonian circuits. We propose new hybrid algorithms for the bi-ATSP using the adjacency-based representation of solutions and the operators that use the Pareto relation. Our algorithms are based on local search and evolutionary methods. The local search combines principles of the well-known Pareto Local Search procedures and Variable Neighborhood Search approach, realizing the search in width and depth. A genetic algorithm with NSGA-II scheme is applied to improve and extend a set of Pareto local optima by means of evolutionary processes. The experimental evaluation shows applicability of the algorithms to various structures of the bi-ATSP instances generated randomly and constructed from benchmark asymmetric instances with single objective.

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!

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!

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!

Literatur
1.
5.
16.
19.
Zurück zum Zitat Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. LNEMS, vol. 535, pp. 177–199. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-642-17144-4_7CrossRef Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. LNEMS, vol. 535, pp. 177–199. Springer, Heidelberg (2004). https://​doi.​org/​10.​1007/​978-3-642-17144-4_​7CrossRef
22.
Zurück zum Zitat Podinovskiy, V.V., Noghin, V.D.: Pareto-optimal’nye resheniya mnogokriterial’nyh zadach (Pareto-optimal solutions of multicriteria problems). Fizmatlit, Moscow (2007, in Russian) Podinovskiy, V.V., Noghin, V.D.: Pareto-optimal’nye resheniya mnogokriterial’nyh zadach (Pareto-optimal solutions of multicriteria problems). Fizmatlit, Moscow (2007, in Russian)
24.
29.
Zurück zum Zitat Whitley, D., Starkweather, T., McDaniel, S., Mathias, K.: A comparison of genetic sequencing operators. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 69–76. Morgan Kaufmann, New York (1991) Whitley, D., Starkweather, T., McDaniel, S., Mathias, K.: A comparison of genetic sequencing operators. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 69–76. Morgan Kaufmann, New York (1991)
Metadaten
Titel
Pareto-Based Hybrid Algorithms for the Bicriteria Asymmetric Travelling Salesman Problem
verfasst von
Yulia V. Kovalenko
Aleksey O. Zakharov
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-22629-9_25