Warenkorboptimierung in EGIS – was geschieht da eigentlich genau?


23. November 2012, von in Neuigkeiten

Ein nicht unerheblicher Teil der theoretischen Informatik beschäftigt sich mit sogenannten NP-vollständigen Problemen. NP steht dabei für nichtdeterministisch polynomiell. Eine Eigenschaft solcher Probleme ist, dass heutige Rechner die beste Lösung sehr wahrscheinlich nicht in zumutbarer Zeit finden können. Unsere Warenkorboptimierung kann mathematisch als ein Rucksackproblem formuliert werden (http://de.wikipedia.org/wiki/Rucksackproblem) und ist damit NP-vollständig.

Ich hatte dazu bereits vor einiger Zeit geblockt und mit dieser Begründung die Nicht-Umsetzung der Warenkorboptimierung in EGIS begründet. Wir haben jedoch in dieser Woche diese Optimierung für alle unsere angeschlossenen Partnerbetriebe freigeschaltet.

Hierzu folgendes:
Beim Suchen nach einem optimalen Warenkorb hängt die Zahl potentieller Lösungen von der Anzahl der Artikel im Warenkorb ab, aber auch von der Zahl potentieller Lieferanten, lieferbaren Mengen, individuellen Frachtkonditionen, etc. Weil die Anzahl der zu berücksichtigenden Kombinationen multiplikativ steigt, spricht man an dieser Stelle von dem Phänomen der kombinatorischen Explosion. Bei kleinen Warenkörben kann unser EGIS-Server die optimale Lösung in der Tat in adäquater Zeit ermitteln, aber bedenken wir: Schon bei Warenkörben mit 3 Artikeln und jeweils 10 dazu gehörigen Lieferantenartikeln hätten wir 10 hoch 3 = 1000 Kombinationsmöglichkeiten. Das liegt daran, dass wir zu jedem Artikel jeden Lieferantenartikel ermitteln müssen und dann in jeder daraus konstruierbaren x-beliebigen Kombination aus Zuordnungen zu Distributoren die Zusatzkosten wie Transportversicherung, Mindermengenzuschlag, Frachtfreigrenze, Frachtkosten, minimaler Bestellwert, etc. Das hört sich nicht nur komplex an, es ist komplex!

Aus diesem Grund haben wir uns entscheiden, eine Approximierung der optimalen Lösung zu finden. Unser Algorithmus läuft endlich und in zumutbar viel Zeit und ermittelt eine Annäherung an den günstigsten Gesamtpreis. Wichtig ist aber auch, dass er NIE einen schlechteren Preis liefert, als den des vom Kunden selbst zusammengestellten Warenkorbs.

Ich bin sehr gespannt darauf, ob sich durch Anwendung dieser Optimierung eine Preisverbesserung bei unseren angeschlossenen Partnerbetrieben realisieren läßt.

Schreiben Sie einen Kommentar

Ihre E-Mail Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert