WU_Wien - Mi 13.04.05 22:11
Titel: Raumoptimierungssoftware - Optimierungsalgorithmen

---

Hallo!

Da wir gerade für die Wirtschaftsuniversität Wien - Abteilung Entrepreneurship und Innovation ein Projekt über das Suchfeld "Raumoptimierung" bzw. "Optimierungssoftware" durchführen, wollte ich hier mal kurz nachfragen ob Ihr Leute kennt, die in diesen Bereichen zu tun haben. Vorallem würden mich Personen (vielleicht du selbst) interessieren, die in diesem Bereich Erfahrungen hat - zb. in der Erstellung von Algorithmen für die Raumoptimierung bei der Bepackung von Containern (optimale Raumausnutzung).

Ich hoffe auf Eure Hilfe!
Danke schon im Voraus! :)

lg
Christian

Keldorn - Do 14.04.05 22:31

---

Hallo,

ich bin auf Arbeit u.a. für die Erstellung von Stauplänen für LKW/Container zuständig. Wir nutzen auch ein Programm (mein eigenes :mrgreen: ), das uns dabei hilft. Das verstaut aber nicht allein, hilft nur dabei (generelle Prüfung der Abmessungen, staplen, welche Verpackungsarten sind stapelbar, nebeneinder setzen, freien Platz und Gewichte ausrechnen usw... ), da einfach zu viele Sachen zu berücksichtigen sind, das kann man nicht programmieren.

Eine Algo kann ich nicht liefern, nur Gründe, warums in der Praxis kaum funktionieren wird ;).

Wo ich damals das Program entwickelt habe, bin ich im Internet auch über solche Abhandlungen von Optimierungsalgos gestoßen. Allerdings war das so theoretisch, das ich mich frage, ob sowas überhaupt in der Wirtschaft angewendet wird oder anwendbar ist. Habt ihr da eine spezielle Firma als Ziel/Vorbild oder wie macht ihr das? Wer ist die Zielgruppe im allgemeinen für solche Optimierungssoftware?

Mfg Frank

delfiphan - Do 14.04.05 22:51

---

Bio-inspirierte/evolutionäre (/randomisierte) Algorithmen sind hier recht geeignet. Man versucht dort nicht das globale Optimum zu finden, sondern eine "gute" Lösung innert einer vernünftigen Zeit.

Asgar - Mi 04.05.05 13:34

---

Und wie sieht so ein evulotionärer Algorythmus aus? gibts dazu irgendwo beispiele oder kann jemand hier ein Beispiel posten?

delfiphan - Mi 04.05.05 13:49

---

Hier findest du Tausende von Seiten über evolutionäre Algorithmen [http://www.google.de/search?hl=de&q=evolution%C3%A4re+Algorithmen&meta=].

Asgar - Mi 04.05.05 13:53

---

Danke, aber Google kannte ich schon, da steht überall nur was ein Evulotionärer Algorythmus ist und was er macht, aber da sind keine Beispiele, und ich weis auch nicht wie man so was programmieren soll. Deshalb fragte ich ja nach Beispielen oder noch besser, einem Quellcode.

delfiphan - Mi 04.05.05 14:08

---

Das ganze funktioniert nicht wie 1+1. So ein Algorithmus sieht auch von Fall zu Fall anders aus, da gibt es keine allgemeingültige Prozedur. Man sollte sich zuerst mit der Theorie befassen, sonst kommt am Schluss nichts Schlaues raus oder du wirst nur Toy-Problems lösen können. Zwei klassische Probleme sind das TSP und das Knapsack Problem. Such mal im Google danach.

Im Grunde geht das ganze aber so:
Du hast am Anfang eine Menge von (nicht-optimalen) Lösungen. Aus diesen wählst du dann einige raus und kreust die miteinander. Jetzt gibt es natürlich verschiedene Arten, wie man Eltern aussucht. Es muss quasi ein Konkurrenzkampf entstehen - schlussendlich dürfen nur die besten Lösungen Eltern werden. Man muss die "Fitness" der Lösungen irgendwie angeben. Diese sind wiederum problemabhängig und beeinflussen die Lösung sehr stark. Diese ausgesuchten Eltern werden dann miteinander gekreuzt und es gibt daraus Kinder. Diese Kinder sind Mischlösungen der Eltern. Man sollte auch Mutationen zulassen, damit es eine gewisse Gen-"Diversität" gibt. Schlussendlich wählt man dann geeignete Kinder und Eltern aus - die bilden dann die nächste Generation. Dann fängt das ganze wieder von vorne an.

alzaimar - So 08.05.05 09:30

---

Ich stell mir das kniffelig vor, hier einen evolutionären Algorithmus zu nehmen.
Besser sind genetische Algorithmen.

1. Ich finde *irgendeine* Lösung (=die 'DNS').
2. Ich ändere "einige" Elemente (=die Gene)der Lösung und schaue, ob die neue Lösung besser ist (Auslese, na gut, Evolution).
3. Goto 2

Vorteil: Es klappt, der Algorithmus findet immer eine bessere Lösung.
Nachteil: Man weiss nicht, wann.

Vorteil: Man kann dieses Verfahren auf 1000000 Rechner gleichzeitig über einen bestimmten Zeitraum laufen lassen. Nach dieser Zeit werden die jeweils besten Lösungen die ein Rechner gefunden hat, miteinander verglichen. Die beste Lösung wird wieder an alle Rechner als Ausgangslösung verschickt und das Spiel beginnt von Neuem.

Hier kommen dann evolutionäre Überlegungen ins Spiel: Es gibt ja evolutionäre Sackgassen, die wir vermeiden wollen. Wir merken uns also die letzten paar 'Gewinner' und 'Platzierten' und können im Falle einer Sackgasse andere Kandidaten nehmen und weitersuchen.

Es gibt bei http://www.torry.net (glaube ich) ein Beispielprojekt, das das Verfahren am "Travelling Salesman" eindrucksvoll demonstriert.

ademus - So 15.05.05 13:34

---

Am IEMAR der TU Wien (http://www.iemar.tuwien.ac.at/) hat Herr Dipl.-Ing. Dr.techn. Tomor Elezkurtaj ein Programm entwickelt, dass dieses Problem für Grundrisse löst.
Siehe z.B.: http://www.iemar.tuwien.ac.at/publications/Umbau1.pdf
"tomor elezkurtaj" in Google liefert weitere Dokumentationen.

Das Programm funktioniert ausgezeichnet. Solltest Dich mal mit Ihm in Verbindung setzen. Gruß ademus