In den letzten Jahren erlebte die Fernsehwerbung in Deutschland durch die Einführung des Privatfernsehens einen regelrechten Boom. Waren zu Zeiten des alleinigen öffentlich-rechtlichen Fernsehens Sendeplätze für Werbespots noch Mangelware - die Werbekunden kauften jeden Spot, den sie bekommen konnten - eröffnete der neue Markt der privaten Anbieter den Kunden erstmals die Möglichkeit der Auswahl und damit der Optimierung.
Abbildung: Zuordnung von Werbespots zu Werbeblöcken
Werbeagenturen kaufen jeweils für ein Jahr im voraus Sendeplätze für die von ihnen vertretenen Produktanbieter ein. Diesen Sendeplätzen werden dann jeweils einen Monat im voraus konkrete Werbespots für einzelne Marken zugewiesen. Das Ziel ist es jetzt, die Summe der für die einzelnen Marken (,,brands``) erreichten relevanten Zuschauer durch eine optimale Zuteilung der Werbespots auf die Werbeplätze (,,slots``) zu maximieren. Hierbei müssen zahlreiche Nebenbedingungen eingehalten werden, wie z.B. Budgetbeschränkungen der einzelnen Marken oder das Trennen der Werbung für Produkte der gleichen Kategorie.
Das oben beschriebene Problem wurde von uns gemeinsam mit einem der größten deutschen Werbekunden und dessen Mediaagentur spezifiziert und in ein formales Modell umgesetzt. Hierbei konnten wir beweisen, daß bereits das Finden einer zulässigen Lösung aufgrund der Nebenbedingungen schwierig (NP-vollständig) ist. Dies gilt selbst dann, wenn man auf eine Reihe von Nebenbedingungen, wie z.B. Mindestzuschauerzahlen für bestimmte Marken, verzichtet. Zur Lösung mußten daher geeignete Näherungsverfahren eingesetzt werden.
Es zeigte sich, daß insbesondere mit Hilfe des
Simulated-Annealing-Verfahrens gute Lösungen gefunden werden konnten. Durch
eine spezielle Modellierung der Zielfunktion gelang es uns dabei,
Unzulässigkeiten so zu ,,bestrafen``,
daß das Verfahren schnell in Richtung
einer zulässigen Lösung gelenkt wurde. Insbesondere war darauf zu
achten, daß Marken mit einem kleinen Werbebudget oder schwer zu
erreichenden Zielgruppen nicht vernachlässigt wurden.
Uns lagen verschiedene Originaldatensätze vor, auf die wir die Verfahren
angewendet haben. Dabei waren die Lösungen stets 10 % besser als die
tatsächlich zum Einsatz gekommenen Mediapläne. Insbesondere konnten
im Gegensatz zu den Originalplanungen in fast allen Fällen
Lösungen erzielt werden, die sämtliche Nebenbedingungen einhielten.