Optimization

Moderne Heuristiken lösen komplexe Optimierungsprobleme

In Zeiten zunehmender Globalisierung, gestiegener Variantenvielfalt und erhöhtem Wettbewerbsdruck reichen die Methoden der Advanced Analytics bisweilen nicht aus. Um Daten in kluge Entscheidungen verwandeln zu können, sind bei komplexeren Aufgabenstellungen auch komplexere Methoden und Algorithmen erforderlich. Moderne Heuristiken sind in der Lage, in unterschiedlichsten Branchen auch hochkomplexe, kombinatorische Optimierungsprobleme zu lösen:

Telekommunikation

Netzplanung und Optimierung der Netzwerkausbaustrategie entsprechend zukünftiger Bedarfsentwicklung sowie Optimierung von Produkt- und Preisportfolio

Produktion

Optimierung der Ablaufplanung der Produktion, Verschnittoptimierung, Optimierung der logistischen Beschaffungsprozesse (Supply Chain Management) sowie der Distribution der Endprodukte

Transport und Logistik

Optimierung von Routen-, Touren- und Einsatzplanungen für Auslieferungen und Abholungen unter Berücksichtigung von Terminen, Fuhrpark, Ladekapazitäten, Arbeitszeiten, etc. sowie Optimierung von Beladungsplänen

Dienstleistungen

Optimierung von Terminplanungen, Einsatz- Belegungs- und Verfügbarkeitsplänen (z.B. in Call Centern) sowie Angebotsoptimierung (optimale Preis- und Produktkombinationen)

Luftfahrt

Optimierung des Revenue Managements (Ermittlung optimaler Ticketpreise zur Maximierung von Auslastung und Umsatz);

Einsatzplanungen für Crews;

Optimierung der Flugpläne

Nah- und Fernverkehr

Optimierung von Fahrplänen zur Maximierung der verfügbaren Verbindungen und Minimierung von Verspätungen unter Berücksichtigung technischer und personeller Rahmenbedingungen

Tourismus

Aktives Revenue Management zur Ermittlung der optimalen Kombination von Umsatz und Auslastung in Hotels, Gaststätten und Freizeiteinrichtungen

Energie

Ermittlung einer gewinnoptimalen Steuerung   von Energiesystemen unter stochastischen Umwelteinflüssen (Entwicklung von Preis und Bedarf, etc.), optimales Risikomanagement sowie Ermittlung optimaler Handlungsstrategien

Optimierung – Die Algorithmen

Wir haben in verschiedenen Branchen eine Reihe moderner Heuristiken erfolgreich zur Lösung realer kombinatorischer Optimierungsprobleme eingesetzt

Tabu Suche (TS)

TS ist ein iterativer Algorithmus, basierend auf einer intelligenten Nachbarschaftssuche. Er speichert gefundene Lösungen und Suchgebiete im Lösungsraum und verhindert das erneute Suchen in diesen Teilgebieten für eine definierte Anzahl von Iterationen (Tabu Liste). Bei der Suche sind auch vorübergehend Verschlechterungen zugelassen, was ein Verharren in einem lokalen Optimum verhindert.

Simulated Annealing (SA)

Simulated Annealing (simuliertes Ausglühen) basiert auf der Nachbildung des Abkühlungsprozesses aus der Physik. Nach Erhitzen von Metall oder Glas sorgt die langsame Abkühlung dafür, dass die Moleküle einen möglichst stabilen, energieminimalen Zustand erreichen. SA bildet diesen Prozess in einem Algorithmus nach und wendet ihn zur Lösung komplexer Optimierungsprobleme an.

Genetische Algorithmen (GA)

GA basieren auf der Idee der biologischen Evolution. Aus einer zufällig bestimmten Menge von Lösungen (Population) werden die besten ausgewählt (Auslese), variiert und miteinander kombiniert (Rekombination). Auf die entstehende neue Population werden wiederum Auslese und Rekombination angewandt.

GA verwenden dieses Grundprinzip der Evolution in einem Optimierungsalgorithmus.

Ant Colony Optimization (ACO)

ACO ist eine Gruppe von Algorithmen, die auf Schwarmintelligenz von Ameisenkolonien bei der Futtersuche basiert: Ameisen markieren die erfolgreichsten Wege mit Pheromonen und folgen tendenziell Pfaden mit hoher Pheromon-Konzentration.

ACO–Algorithmen simulieren dieses Verhalten, um eine Lösung zu finden, die möglichst nahe am Optimum liegt.

Künstliche Neuronale Netze (KNN)

KNN übertragen Teile der Funktionsweise eines biologischen neuronalen Netzes (Gehirns) in ein Rechenmodell bzw. einen Algorithmus.

KNN sind parallel verbundene, hierarchisch organisierte Netzwerke, die in einer überwachten Lernphase so lange trainiert werden, bis das Netz auch für nicht erlernte Eingabemuster den gewünschten Output generiert.

Selbst organisierende Karten (SOM)

Selbst organisierende Karten oder Kohonen-Netze sind ein Spezialfall eines KNN.

SOM bilden die Elemente des Neuronalen Netzes in einem topologischem Raum ab und lernen ohne Überwachung. Durch wiederholt herangeführte Eingangsreize wird die Topologie des Netzes solange verändert, bis eine Lösung erreicht wird, die nahe am Optimum liegt.

Optimierung mit Microsoft Excel

Es gibt eine Vielzahl kommerzieller Software-Applikationen für kombinatorische Optimierung. Allerdings gehen wir einen alternativen Weg und implementieren moderne Optimierungsverfahren direkt in Microsoft Excel. Dies hat eine Reihe von Vorteilen:

  • Implementierung des Algorithmus in einer im Unternehmen bereits vorhandenen Standard-Anwendung:
  • keine zusätzlichen Lizenzkosten für neue Applikationen
  • geringe oder keine Einarbeitungszeit
  • kein Prüfungs-, Installations- und Wartungsaufwand bei IT-Operations
  • „All-in-One“ Ansatz: Inputdaten, Code, Berechnungsergebnisse und Visualisierung der Ergebnisse (Dashboard) in einer Excel-Arbeitsmappe, d.h. keine externen Dateien oder Datenbanken, keine zusätzlichen Programmbibliotheken, etc. Das Modell mit integriertem Optimierungsalgorithmus ist auf jedem Computer mit einer Excel-Installation lauffähig und kann daher von allen Mitarbeitern im Unternehmen genutzt werden
  • Möglichkeit der Erweiterung des Funktionsumfangs bestehender Excel-Modelle durch Einbindung eines Optimierungsalgorithmus‘
  • Verfügbarkeit der Standard-Funktionalitäten von Microsoft Excel
  • Datenimport und -export
  • Analysefunktionen wie Tabellen (List Objects), Pivot-Tabellen, etc. zur Weiterbearbeitung der Ergebnisse des Algorithmus‘
  • Visualisierung der Optimierungsergebnisse in Diagrammen und auf Dashboards
  • Einfache Möglichkeit zur direkten Vergleichbarkeit verschiedener Parameterkonstellationen eines Algorithmus‘ oder der Ergebnisse und Laufzeiten mehrere Algorithmen innerhalb von Excel. Excel als Tabellenkalkulation bietet naturgemäß einfache und flexible Möglichkeiten, Datenreihen (Modellergebnisse) zu vergleichen