Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003 Subsymbolische Verfahren zur Ressourcenallokation Riezlern 23.1.2003 Oliver Wendt

Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003

Subsymbolische Verfahrenzur Ressourcenallokation

Riezlern 23.1.2003

Oliver Wendt


Gliederung

• Anwendungsbeispiele automatisierter Informationsdienstleistungen– e-finance– e-logistics

• Übertragbarkeit der Methoden desYield Management „klassischer“ Dienstleistungen ?

• Ansätze zur heuristischen Bewältigung der Komplexitätsprobleme desNetwork Yield Management– KNN + GA– KNN + Reinforcement Learning


Anwendungsfall 1e-finance


Bayerische Landesbank


1822 und 1822direct


Berliner Volksbank


BBBank


Deutsche Bank


Deutsche Bank


Comdirect


Comdirect


AnwendungspartnerIS Innovative Software AG

• seit 2000 fusioniert mit Teledata GmbH

• europäischer Marktführer für internetbasierte Finanzinformationsdienstleistungen

• ASP (Application Service Provider) für über 100 Banken, Broker, Medienhäuser und Internet-Portale

• ca. 1.600 eFinance-Sites im Internet und Intranet


AnwendungspartnerIS Innovative Software AG

• Augenblicklicher „Serverpark“– ca. 1.200 Linux-Server im Rechenzentrum der

Deutschen Börse– über 200 Mbit Peak-Netzlast (upstream)– 55 Mio. Visits pro Monat

allein für Hauptkunden Comdirect

• Europaweit größter Kunde von C.O.L.T.


Mittelfristziel: individuelles Portfoliomanagement

• Charts der historischen individuellen Portfolioentwicklung

• Risikoanalyse (z.B. Value-at-Risk-Metrikengemäß Kapitaladäquanz nach „Basel 2“)

• Portfoliooptimierung unter Berücksichtigung– vorgegebener Risikostrukturziele– individueller Transaktionskosten– „operativer“ Geschäftsrisiken


Langfristziel:individualisierte wissensintensive

Dienstleistungen durch/für Web Services


Anwendungsfall 2e-logistics


e-logistics

• Ziel: dynamische Tourenplanung und Umplanung mit Kunden-Zeitfenstern

• Prognose der Fahrzeiten von x nach y– tageszeitabhängig– verkehrssituationsabhängig

• typische Antwortzeiten der Time-Distance Web-Services ca. 300ms

Problem für heuristische Suchverfahren


e-logistics


Übertragbarkeit der Methoden des

Yield Management ?


Information als Repetierfaktor ?

• vernachlässigbaren Reproduktionskosten(sog. quasibeliebige Kopierbarkeit)

• „Verbrauch“ von Informationsgütern unkritisch• einfache Vernichtung / Entsorgung

keine Knappheit existierender Information

Einordnung als Repetierfaktor wenig sinnvoll


Information als Potentialfaktor ?

• Konkurrenz der Produktionsprozesse um diese Ressource fehlt bei Informationsprodukten

auch jede Software („logische Maschine“) kann beliebig repliziert werden

Kernproblem liegt nicht in der Konkurrenz um die Ressource Information selbst, sondern in der mittelbaren Konkurrenz um die knappen physischen Träger der Informationsverarbeitung !

–Menschen (Arbeitszeit)–Rechner (CPU / Memory)–Infrastruktur (Netzressourcen / Bandbreite)


Menge aller Verfahren, welche durch eine integrierte Preis- und Kapazitätssteuerung, die richtigen Einheiten eines zukünftig bereitzustellenden Kapazitätstyps dem richtigen Kundentyp so zuordnen, dass der Deckungsbeitrag der Betriebseinheit maximiert wird

[vgl. Belobaba (1989), Vogel (1989)].

Yield Management /Perishable Asset Revenue

Mgmt


Charakteristika YM-geeigneter

Produktionsprozesse[Kimes (1989)]

• hohe Kapazitätsbereitstellungskosten : Kapazität kurzfristig nur zu prohibitiv hohen, sprungfixen Kosten ausweitbar

•variable Grenzkosten einer zusätzlichen Leistungseinheit innerhalb der gegebenen Kapazitäten gering

• Möglichkeit zur Marktsegmentierung•Nichtlagerbarkeit und Verderblichkeit• Produktverkauf vor Produktionsbeginn• hohe Volatilität der Nachfrage


Yield Management /Perishable Asset Revenue

Mgmt

• Airline Industries (Passage & Cargo)

• Hotel- & Tourismus-Gewerbe

• Autovermietungen

• (Bekleidungs- / Modeartikel)

• (Lebensmittel)


Strukturanalogientypischer Dienstleistungen

Hotel

(physische DL)

Computer

(informationelle DL)

externe Potentialfaktoren

zu beherbergende Gäste zu veredelnde Kundendaten

interne Potentialfaktoren

Hotelzimmer Personal

Memory Systembus Zentralprozessor

Repetierfaktoren Nahrung, Energie, Toilettenartikel Energie

Allokationsproblem Gewinnmaximale Zuweisung von Zeitscheiben der Ressourcen

an die optimale Teilmenge der nachfragenden Gäste

Gewinnmaximale Zuweisung von Zeitscheiben der Ressourcen

an die optimale Teilmenge der angefragten Verarbeitungsaufträge

Prozessstruktur-alternativen

diskret, endlich diskret, abzählbar unendlich (durch Schleifen und Rekursion)

Prozessauswahl-zeitpunkt

ex ante (bei Buchung) „real-time“ im Ausführungsprozess


Verfahren des Yield Management

• Pragmatische / heuristischeLösungsverfahren

– Geschachtelte Kontingentierung– Expected Marginal Seat Revenue

[Belobaba 89]

• Optimale Lösungsverfahren– Stochastische Dynamische Programmierung

auf Basis Markoff’scher Entscheidungsprozesse


StochastischeDynamische

Programmierung

• Sitzplatzkapazität von sechs Sitzplätzen

( Z := { 0, 1, 2, 3, 4, 5, 6 } )

• Sitzplätze können einzeln oder in Gruppen verkauft werden

• keine Unsicherheit über die Anzahl der noch eingehenden Anfragen


StochastischeDynamische

Programmierung

• drei Anfragetypen:

• rückwärts zählender Index k für Anfragen

Wahrschein- lichkeit

angefragte Kapazität

Erlös

F1 0.5 1 „Sitz“ 1 Geldeinheit F2 0.3 2 „Sitze“ 4 Geldeinheiten F3 0.2 3 „Sitze“ 9 Geldeinheiten


Stage 1

i a*(i) V*1(i) Berechnung

0 000 0.00 0.2*0 + 0.3*0 + 0.5*0 1 001 0.50 0.2*0 + 0.3*0 + 0.5*1 2 011 1.70 0.2*0 + 0.3*4 + 0.5*1 3 111 3.50 0.2*9 + 0.3*4 + 0.5*1 4 111 3.50 0.2*9 + 0.3*4 + 0.5*1 5 111 3.50 0.2*9 + 0.3*4 + 0.5*1 6 111 3.50 0.2*9 + 0.3*4 + 0.5*1


Stage 2 (z.B. i=4)

V2(4,000) = (0.2*0+0.3*0+0.5*0) +0.2 V1(4) +0.3 V1(4) +0.5 V1(4) = 3.50

V2(4,001) = (0.2*0+0.3*0+0.5*1) +0.2 V1(4) +0.3 V1(4) +0.5 V1(3) = 4.00

V2(4,010) = (0.2*0+0.3*4+0.5*0) +0.2 V1(4) +0.3 V1(2) +0.5 V1(4) = 4.16

V2(4,011) = (0.2*0+0.3*4+0.5*1) +0.2 V1(4) +0.3 V1(2) +0.5 V1(3) = 4.66

V2(4,100) = (0.2*9+0.3*0+0.5*0) +0.2 V1(1) +0.3 V1(4) +0.5 V1(4) = 4.70

V2(4,101) = (0.2*9+0.3*0+0.5*1) +0.2 V1(1) +0.3 V1(4) +0.5 V1(3) = 5.20

V2(4,110) = (0.2*9+0.3*4+0.5*0) +0.2 V1(1) +0.3 V1(2) +0.5 V1(4) = 5.36

V2(4,111) = (0.2*9+0.3*4+0.5*1) +0.2 V1(1) +0.3 V1(2) +0.5 V1(3) = 5.86


Stage 2 (z.B. i=3)

V2(3,110) = (0.2*9+0.3*4+0.5*0) + 0.2 V1(0) +0.3 V1(1) +0.5 V1(3) = 4.90 aber V2(3,111) = (0.2*9+0.3*4+0.5*1) + 0.2 V1(0) +0.3 V1(1) +0.5 V1(2) = 4.50


Stochastische Dynamische Programmierung

Restwert V*(i) bei optimaler Annahmestrategie

0

2

4

6

8

10

12

14

16

18

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

verbleibende Zahl N von Anfragen

Re

stw

ert

V*(

i) e

ine

r K

ap

azi

tät

i

i = 6

i = 5

i = 4

i = 3

i = 2

i = 1

Annahme wenn: Erlösk + V*k-1(i - Zimmerk) V*k-1( i ).


Eigenschaften der Restwertfunktion V*

• inventory monotonicity– V* steigt monoton mit der Restkapazität i

• time monotonicity– V* steigt monoton mit der der Anzahl verbleibender

Anfragen k

• ABER: Monotonie der PREISE nur, wenn keine Zunahme der Zahlungsbereitschaft über die Zeit !


Beispiel:nichtmonotone Nachfrage

• k > 2

• k <= 2

probability requested capacity

revenue

F1 0.6 1 „seat“ 1 monetary unit F2 0.4 2 „seat“ 4 monetary units F3 0 3 „seat“ 9 monetary units

probability requested capacity

revenue

F1 0.33 1 „seat“ 1 monetary unit F2 0.33 2 „seat“ 4 monetary units F3 0.34 3 „seat“ 9 monetary units


Stochastic Dynamic Programming

expected revenue V*(i) from applying an optimal strategy

0

2

4

6

8

10

12

14

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

remaining number N of requests

va

lue

V*(

i) o

f a

re

ma

inin

g c

ap

ac

ity

i

i = 6

i = 5

i = 4

i = 3

i = 2

i = 1


Network Yield ManagementDemo


Network Yield Management

Relevanz

• Hohe Relevanz derartiger Verbundeffekte im Informations-Kontext:

– einerseits müssen hier die Ergebnisse der Sub-Services zur Verarbeitung des übergeordneten Service weitergeleitet werden, die ggf. auf anderen Hardware-Komponenten untergebracht sind (Airline-Analogie)

– andererseits beanspruchen viele Service-Aufträge mehrere konsekutive Zeitscheiben einer Ressource(Multi-Day-Analogie zum Hotel-Fall)


„kleiner Trost”:

Viele IV-Prozesse sind glücklicherweise “preemptiv”

“Umzug” der Zwischenergebnisse des IV-Prozesses in ein anderes “Hotel” (anderer Prozessor) möglich

Ausnahmen insbes. bei „humaner“ Weiterverarbeitung:

Audio-Übertragung

Video-Übertragung


Relevanz


Bewältigung der Komplexitätsprobleme des Network

Yield Management

Genetische Algorithmen (+KNN)Reinforcement Learning (+KNN)


Bestimmung der Restwertfunktion bei

Ressourcenkomplementarität

• optimale Lösung:Zustandsraum als Menge aller möglichen Bündel von Verfügbarkeiten aller zu bewertenden Ressourcen! Kombinatorische Explosion

• lineares „Bid-Pricing“ deutlich suboptimal[Weatherford 92], [Talluri / Ryzin 96]

• Repräsentation der multidimensionalen Restwertfunktion mittelsKünstlicher Neuronaler Netze ?



Kombinationsgewinn

• Fall A: Kombinationsgewinn

Typ Wahrschein-lichkeit

AngefragteRess.

Erlös

F1 0.4 11 700 GEF2 0.3 01 300 GEF3 0.3 10 300 GE



Kombinationsgewinn


0

200

400

600

800

1000

1200

1400

0 1 2 3 4 5 6 7 8 9 10


Re

stw

ert

V*(

i) e

ine

r K

ap

azi

tät

i

s10=s01

s20=s02

s11

s21=s12

s22

s00



Kombinationsverlust

• Fall B: Kombinationsverlust

Typ Wahrschein-lichkeit

AngefragteRess.

Erlös

F1 0.4 11 550 GEF2 0.3 01 300 GEF3 0.3 10 300 GE



Kombinationsverlust


0

200

400

600

800

1000

1200

1400

0 1 2 3 4 5 6 7 8 9 10


Re

stw

ert

V*(

i) e

ine

r K

ap

azi

tät

i

s10=s01

s20=s02

s11

s21=s12

s22

s00


weight matrix 1

weight matrix 2

x1 x5x2 x3 x4 x10x7x6 x9x8

hidden layer

output layer

Vt(x)= 3200

input layer

Network Yield ManagementKNN als Lösung ?


weight matrix 1

weight matrix 2

x1 x5x2 x3 x4 x10x7x6 x9x8

hidden layer

output layer

input layer

Vt(x)= 2300

Network Yield ManagementKNN als Lösung ?


Aufbau eines Neurons

Transferfunktion

Localmemory

“activate”X1 X2 Xn

y Output signal

Copies of output signal

Input signals


Backpropagation (20000 steps)

MLP-3-5-1

0

0.01

0.02

0.03

0.04

0.05

0.06

1 2 3 4 5 6 7 8 9 10

verbleibende Anfragen

Res

twer

t V

*(i)



MLP-3-5-1

-0.01

0

0.01

0.02

0.03

0.04

0.05

0.06

0.07

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.06

-0.04

-0.02

0

0.02

0.04

0.06

0.08

0.1

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.06

-0.04

-0.02

0

0.02

0.04

0.06

0.08

0.1

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.04

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.04

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.04

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)



MLP-3-5-1

-0.02

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

1 2 3 4 5 6 7 8 9 10


Res

twer

t V

*(i)


Training des KNN

• übliche Lernregeln für KNN leider ungeeignet, da Bewertungsfehler nur SIMULATIV abschätzbar

• Finden optimaler Gewichte w* ist somit selbst hochdimensionales stochastisches Parameteroptimierungsproblem

• prädestiniert für Einsatz naturanaloger Verfahren ??? (Evolutionsstrategien / Genetische Algorithmen)

( )* arg max w

ww V ( *) *wV V


Ablauf Genetischer Algorithmen


Crossover-Operatorenfür KNN

Eltern

Kind


KNN+GA-Ergebnisse

500.000 Evaluationen


Reinforcement Learning

agent

environment

action a r reward rstate s

rt+1

st+1

Ziel des RL-Agenten: Maximierung der Summe von Reinforcement-Signalen (long run!!)


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

)]V(s)γV(s[r α)V(s)(sV t1t1tttπ

Temporal-Difference-Learning

Beispiel

r4 = 71.2

Episode 1

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 71.2

1.6

Episode 1

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 71.2

1.6

0.4

Episode 1

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 71.2

1.6

0.4

Episode 1

= 0.2 0


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 72.48

2.96

0.72 0

Episode 2

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 73.78

4.11

0.98 0

Episode 3

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 714.9

9.77

1.97 0

Episode 20

= 0.2


r8 = 5r 1 =

6

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ



Beispiel

r4 = 715.1

9.22

1.97 0

Episode 21

= 0.2

1.0 0


TD(0) Reinforcement Learning


TD(0) Reinforcement Learning

(3-Ebenen-MLP)

50.000 Evaluationen 500.000 Evaluationen


Zusammenfassung und Ausblick


Zusammenfassung

• große strukturelle Ähnlichkeiten der Bepreisung von IV-Leistungen und des Yield-Management klassischer Dienstleistungen

• Problem des Network Yield Management muss „gelöst“ werden

• Adaption trotzdem vielversprechender als Anpassung der klassischen betriebswirtschaftlichen Preistheorie


Ausblick

• Einsatz in DISPOWEB-Verhandlungsprotokollen für Softwareagenten

• alternative Zustandsraumkompression(z.B. Growing Neural Gas-Topologie)

• Integration kombinatorischer Auktionen und Bepreisung von Real Options

• Integration nachfrageseitiger interpersoneller Netzeffekte


Kombination YM und Auktionstheorie

• dynamische Bestimmung gewinnmaximierender Preise umfaßt aber ZWEI interdependente Probleme:

– Welcher Anreizmechanismus bringt die Nachfrager dazu, ihre Zahlungsbereitschaft wahrheitsgemäß zu offenbaren?(Auktionstheorie für Leistungsbündel)

– Welcher Nachfrager wird wann mit welchem Ressourcenbündel zu welchem Preis bedient? (YM)


YM / Perishable Asset Revenue Management

t0 t

production / service

request

com

mit

request

denia

l

price

request

com

mit


Auktionen

t0 t


request

request

price

request


Generalisierung: Auktionen & YM

t0 t


price


Literatur

• Hu, J. / Wellman, M.P.: Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Madison 1998

• Kephart, J.O. / Tesauro, G.J.: Pseudo-convergent Q-Learning by Competitive Pricebots, Hawthorne 1999

• Kephart, J.O. / Tesauro, G.J.: Pricing in agent economies using multi-agent Q-Learning, Hawthorne 1999

• McGill, J.I.; van Ryzin G.J.: Revenue Management: Research Overview and Prospects; Transportation Science 33 (1999) S. 233-256.

• Sutton, R.S. : Reinforcement-Learning: An Introduction, Cambridge 1998

• Schwind, M.; Wendt, O.: Dynamic Pricing of Information Products based on Reinforcement Learning: A Yield Management Approach; Proceedings of the 25th Conference on Artificial Intelligence (KI2002); Aachen.

Documents

Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003 Subsymbolische Verfahren zur Ressourcenallokation Riezlern 23.1.2003 Oliver Wendt