Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

09.01.2017 | Ausgabe 2/2018

Natural Computing 2/2018

Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems

Zeitschrift:
Natural Computing > Ausgabe 2/2018
Autoren:
Ronghua Shang, Bingqi Du, Kaiyun Dai, Licheng Jiao, Yu Xue

Abstract

The capacitated arc routing problem (CARP) is a classical NP-Hard combinatorial optimization problem. In this paper, we present a memetic algorithm based on Extension step and Statistical filtering for Large-Scale CARP (ESMAENS) which has improvements in both the global search strategy and the local search strategy. Firstly, ESMAENS adopts the Route Distance Grouping decomposition scheme (RDG) to decompose the large-scale CARP into some independent sub-problems. Then, the initial population would evolve into a new group by using the Evolutionary Algorithm. Furthermore, ESMAENS introduces the extension step search strategy to search the potential solutions around the current solution. As a result, with the increase of the iteration number, it avoids getting to the premature convergence. Meanwhile, the diversity of the population can be increased. Finally, in the local search strategy, the statistical filter is used to filter out some solutions and make the algorithm get the lower bound at a faster convergence rate with a high stability. Compared with RDG-MAENS, experimental results on BeullenC, D, E, F, egl and EGL-G test set show that ESMAENS has a better convergence rate, and the stability of solutions obtained is improved. Furthermore, ESMAENS achieves a global search for the solutions. Especially for the large-scale EGL-G test set, ESMAENS can converge to a lower bound at a faster convergence rate, and it is suitable for solving large-scale CARP.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2018

Natural Computing 2/2018 Zur Ausgabe

OriginalPaper

Preface

Premium Partner

    Bildnachweise