Genetische Algorithmen - Evolutionsstrategien (PDF)

...
Aufgrund der Komplexität des VRP bzw. VRPTW steigt ab einer bestimmten Größe des Fuhrparks und einer bestimmten Anzahl an Kunden die Problemgröße und stößt oft an die Grenzen des mit heutigen Technologien Berechenbaren. Für die Lösung dieser Probleme ste-hen im Allgemeinen zwei Ansätze zur Verfügung: exakte und heuristische Methoden (vgl. ZÄPFEL und BÖGEL 2007, S. 15ff.). Analog zu STRÄTER (2007, S. 23) haben die exakten An-sätze den Vorteil, dass eine optimale Lösung berechnet wird, bei größeren Problemen oder bei zusätzlichen Restriktionen sind sie jedoch aufgrund der langen Berechnungsdauer ungeeignet. Bei einer heuristischen Vorgehensweise wird auf die Optimalität der Lösung verzichtet, um in einer akzeptablen Zeit sehr gute Lösungen zu erhalten (vgl. STRÄTER 2007, S. 24).
Das nachfolgende Kapitel befasst sich mit den Evolutionären Algorithmen (EA), mit welchen bereits sehr gute Lösungen für das VRP bzw. das VRPTW generiert wurden (vgl. BRÄYSY und GENDREAU 2005, S. 120). Die EA, welche die grundlegenden evolutionstheoretischen Prinzipien nach Darwin (Replikation, Variation und Selektion) imitieren, können in die Gene-tischen Algorithmen (GA), die 'genetische Mechanismen' betonen, die Evolutionsstrategien (ES), welche die Evolution 'auf der phänotypischen Ebene' abbilden und die Evolutionäre Programmierung (EP), welche 'konkurrierende Strukturen auf der Ebene evolvierender Popu-lationen bzw. Spezies' betrachtet, unterteilt werden (vgl. NISSEN 1994, S. 181). Nach einer ausführlichen Erläuterung der einzelnen Verfahren folgt eine Untersuchung, inwieweit die GA, die ES und die EP die evolutionären Prozesse der Evolutionstheorie nach DARWIN (1860) tatsächlich abbilden sowie ein Vergleich der Varianten GA und ES. Auf das Tourenplanungsproblem aus betriebswirtschaftlicher und kombinatorischer Sicht wird im dritten Kapitel eingegangen. Im vierten Kapitel werden die beiden von HOMBERGER und GEHRING (1999) generierten Evolutionsstrategien ES1 und ES2 für das VRPTW dargestellt und evaluiert. Die mit den Verfahren erzielten Ergebnisse werden anhand der Probleminstanzen nach SOLOMON (1987, S. 254ff.), RUSSEL (1995) und GEHRING und HOMBERGER (1999) bewertet. Die Seminararbeit endet anschließend mit einer kritischen, zusammenfassenden Schlussbetrachtung.
...