Direkt zum Inhalt
AIT Logo

Hybride Lösungsansätze für kombinatorische Optimierungsprobleme

In unserem täglichen Leben sind wir oft mit Situationen konfrontiert, in denen harte Entscheidungen getroffen werden müssen. In vielen Fällen kann dieser Entscheidungsprozess formalisiert und als kombinatorisches Optimierungsproblem abgebildet werden. Beispiele für solche Entscheidungsprobleme sind die Routenplanung und die Aktivitätsplanung. Auch in der Unternehmenswelt können wir zahlreiche kombinatorische Optimierungsprobleme identifizieren, z.B. in der Produktions- und Transportplanung, im Logistikbereich oder in der Personaleinsatzplanung. Generell ist ein kombinatorisches Optimierungsproblem dadurch gekennzeichnet, dass es eine begrenzte Anzahl möglicher Optionen aufweist, die möglicherweise durch mehrere Nebenbedingungen eingeschränkt sind, so dass ein Sollwert maximiert oder minimiert wird. Unser Ziel am AIT ist es, mathematische Modelle, neuartige Methoden und effiziente Lösungsalgorithmen zu entwickeln, um die optimale oder nahezu optimale Entscheidung zu treffen.

Transportoptimierung

Im Bereich der Transportoptimierung und Logistik können nahezu alle relevanten Probleme als kombinatorisches Optimierungsproblem abgebildet werden. Daher unternimmt das AIT-Team für Transportoptimierung und Logistik die folgenden vier Schritte, um ein (reales) Problem zu lösen:

  • Zunächst wird die Problemstellung mathematisch modelliert, um eine formale Problembeschreibung zu erhalten.
  • Anschließend wird das Problem über ganzzahlige lineare Programmierung oder Constraint-Programmierverfahren modelliert, um eine genaue Lösungsmethode zu erhalten.
  • Wie in den meisten Situationen erfordern die Fälle des zugrunde liegenden realen Problems hochskalierbare Lösungsmethoden, es werden (meta-)heuristische oder hybride Lösungsansätze entwickelt.
  • Schließlich werden die vorgeschlagenen Lösungsmethoden in Bezug auf (Standard-)KPIs wie Leistung und Lösungsqualität bewertet.

Der Ansatz des AIT konzentriert sich auf reale Probleme aus der Verkehrswissenschaft. Daher hat das AIT das algorithmische Framework DynaTOP entwickelt, das in der Lage ist, Standardprobleme im Transportwesen so zu lösen, dass die von den Anwendern (die typischerweise Projektpartner sind) angegebenen realen Randbedingungen einfach integriert werden können. Da dieser Rahmen auf metaheuristischen Ansätzen basiert (da typische Fälle der angegangenen realen Probleme für rein exakte Ansätze zu groß sind), kann ein Wechsel zwischen verschiedenen metaheuristischen Ansätzen angewendet werden. Daher können wir verschiedene metaheuristische Ansätze so bewerten, dass der für die jeweilige Problemstellung am besten geeignete Ansatz für die weitere Entwicklung ausgewählt werden kann.

 

Publikationen

G. Hiermann, M. Prandtstetter, A. Rendl, J. Puchinger, G. Raidl: 
"Metaheuristics for Solving a Multimodal Home-Healthcare Scheduling Problem"; 
Central European Journal of Operations Research, 23 (2015), 1; S. 89 - 113.