Skip to main content
Top

2018 | OriginalPaper | Chapter

Reduction of the Pareto Set in Bicriteria Asymmetric Traveling Salesman Problem

Authors : Aleksey O. Zakharov, Yulia V. Kovalenko

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the bicriteria asymmetric traveling salesman problem (bi-ATSP). Optimal solution to a multicriteria problem is usually supposed to be the Pareto set, which is rather wide in real-world problems. We apply to the bi-ATSP the axiomatic approach of the Pareto set reduction proposed by V. Noghin. We identify series of “quanta of information” that guarantee the reduction of the Pareto set for particular cases of the bi-ATSP. An approximation of the Pareto set to the bi-ATSP is constructed by a new multi-objective genetic algorithm. The experimental evaluation carried out in this paper shows the degree of reduction of the Pareto set approximation for various “quanta of information” and various structures of the bi-ATSP instances generated randomly.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Literature
3.
go back to reference Buzdalov, M., Yakupov, I., Stankevich, A.: Fast implementation of the steady-state NSGA-II algorithm for two dimensions based on incremental non-dominated sorting. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO 2015), pp. 647–654 (2015). https://doi.org/10.1145/2739480.2754728 Buzdalov, M., Yakupov, I., Stankevich, A.: Fast implementation of the steady-state NSGA-II algorithm for two dimensions based on incremental non-dominated sorting. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO 2015), pp. 647–654 (2015). https://​doi.​org/​10.​1145/​2739480.​2754728
21.
go back to reference 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.
go back to reference Reeves, C.R.: Genetic algorithms for the operations researcher. INFORMS J. Comput. 9(3), 231–250 (1997)CrossRef Reeves, C.R.: Genetic algorithms for the operations researcher. INFORMS J. Comput. 9(3), 231–250 (1997)CrossRef
26.
go back to reference Vinogradskaya, T.M., Gaft, M.G.: Tochnaya verhn’ya otzenka chisla nepodchinennyh reshenii v mnogokriterial’nyh zadachah (The least upper estimate for the number of nondominated solutions in multi-criteria problems). Avtom. Telemekh. 9, 111–118 (1974). in Russian Vinogradskaya, T.M., Gaft, M.G.: Tochnaya verhn’ya otzenka chisla nepodchinennyh reshenii v mnogokriterial’nyh zadachah (The least upper estimate for the number of nondominated solutions in multi-criteria problems). Avtom. Telemekh. 9, 111–118 (1974). in Russian
27.
go back to reference 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)
28.
30.
go back to reference Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 862–876. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70928-2_64CrossRef Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 862–876. Springer, Heidelberg (2007). https://​doi.​org/​10.​1007/​978-3-540-70928-2_​64CrossRef
31.
go back to reference Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength pareto evolutionary algorithm. In: Proceedings of Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems, pp. 95–100 (2001) Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength pareto evolutionary algorithm. In: Proceedings of Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems, pp. 95–100 (2001)
Metadata
Title
Reduction of the Pareto Set in Bicriteria Asymmetric Traveling Salesman Problem
Authors
Aleksey O. Zakharov
Yulia V. Kovalenko
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-93800-4_8

Premium Partner