邵進(jìn)明 蔣 煒 李艷婷

(1.上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院，上海 200030；2.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240)

0 引言

IPTV(Internet Protocol Television)是寬帶電視的一種，它利用廣電網(wǎng)絡(luò)提供的豐富的節(jié)目資源，采用數(shù)據(jù)傳輸速率更高、覆蓋范圍更廣、運(yùn)行狀況良好的寬帶通信網(wǎng)作為基礎(chǔ)網(wǎng)絡(luò)設(shè)施。除了計(jì)算機(jī)和移動(dòng)設(shè)備終端，用戶使用網(wǎng)絡(luò)機(jī)頂盒和普通電視機(jī)即可通過(guò)互聯(lián)網(wǎng)接入享受個(gè)性化、交互式、可定制的TV視聽(tīng)業(yè)務(wù)及其他增值服務(wù)。

從2001年3月15日通過(guò)的“十五計(jì)劃綱要”第一次明確提出“三網(wǎng)融合：促進(jìn)電信、電視、互聯(lián)網(wǎng)三網(wǎng)融合”開(kāi)始，到近日國(guó)務(wù)院辦公廳印發(fā)《三網(wǎng)融合推廣方案》，明確在總結(jié)試點(diǎn)經(jīng)驗(yàn)的基礎(chǔ)上，加快在全國(guó)全面推進(jìn)三網(wǎng)融合，推動(dòng)信息網(wǎng)絡(luò)基礎(chǔ)設(shè)施互聯(lián)互通和資源共享，將廣電、電信業(yè)務(wù)雙向進(jìn)一步擴(kuò)大到全國(guó)范圍，并開(kāi)展實(shí)質(zhì)性工作。在中央推進(jìn)三網(wǎng)融合的重點(diǎn)工作中，IPTV融合了電信、廣電、互聯(lián)網(wǎng)三方面的技術(shù)和優(yōu)勢(shì)并創(chuàng)造了新的價(jià)值領(lǐng)域。廣電運(yùn)營(yíng)商擁有豐富的節(jié)目?jī)?nèi)容資源和穩(wěn)定的用戶群體，電信和互聯(lián)網(wǎng)運(yùn)營(yíng)商則擁有交互技術(shù)和網(wǎng)絡(luò)，在很大程度上，IPTV將會(huì)促進(jìn)三網(wǎng)融合的進(jìn)程，推進(jìn)電信、廣電、互聯(lián)網(wǎng)利用各自的特點(diǎn)更好地為人們提供服務(wù)。2012年，中國(guó)IPTV用戶規(guī)模占全球的1/4，根據(jù)工信部官網(wǎng)2015年2月的數(shù)據(jù)，2014年我國(guó)三家基礎(chǔ)電信企業(yè)IPTV用戶達(dá)到了3363.6萬(wàn)戶。不管是從用戶規(guī)模、政策扶持，還是從與之相關(guān)的互聯(lián)網(wǎng)行業(yè)發(fā)展?fàn)顩r來(lái)看，IPTV在實(shí)踐中的發(fā)展前景相當(dāng)可觀。

國(guó)內(nèi)外學(xué)者關(guān)于IPTV廣告投放算法的研究，并不能很好地解決我國(guó)目前IPTV行業(yè)的實(shí)際問(wèn)題。我國(guó)的IPTV業(yè)務(wù)采取的是廣電與電信合作的模式，雙方掌握的用戶數(shù)據(jù)是不共享的，IPTV廣告運(yùn)營(yíng)方無(wú)法獲取準(zhǔn)確的用戶行為數(shù)據(jù)來(lái)定制用戶標(biāo)簽，也就無(wú)法使用競(jìng)拍投放定向廣告的方式將用戶出售給廣告主，因而目前使用的依然是基于節(jié)目?jī)?nèi)容而非用戶的售賣模式，在面對(duì)眾多廣告主時(shí)，如何優(yōu)化流量分配方案、提高廣告流量利用效率顯得尤為重要。

1 問(wèn)題描述

在IPTV廣告庫(kù)存的分配問(wèn)題中，涉及節(jié)目?jī)?nèi)容所有者、運(yùn)營(yíng)媒體、廣告主(需要投放產(chǎn)品廣告的商家)、廣告代理商、收視用戶等多個(gè)主體，在不影響問(wèn)題本質(zhì)的前提下，這里簡(jiǎn)化成媒體、廣告主、用戶三者之間的關(guān)系(如圖1所示)。在這三者之中，媒體擁有節(jié)目資源版權(quán)，并通過(guò)IPTV渠道將這些節(jié)目?jī)?nèi)容以直播、點(diǎn)播、回看等形式供用戶自行免費(fèi)或付費(fèi)收看；用戶根據(jù)個(gè)人興趣喜好及空閑時(shí)間，通過(guò)遙控器向媒體的服務(wù)器發(fā)出收視請(qǐng)求，然后媒體服務(wù)器根據(jù)接收到的用戶請(qǐng)求將對(duì)應(yīng)的節(jié)目投播到用戶終端；節(jié)目資源在用戶終端的每一次播放都意味著一次投放廣告的機(jī)會(huì)，或稱之為廣告流量，媒體將擁有的廣告流量出售給不同的廣告主，并在協(xié)商過(guò)程中根據(jù)廣告主提出的投放訴求制定具體的投放分配計(jì)劃。

圖1 廣告業(yè)務(wù)流程

一般而言，IPTV運(yùn)營(yíng)方采用預(yù)售方式(例如出售未來(lái)三個(gè)月的廣告流量)：廣告主可以對(duì)節(jié)目?jī)?nèi)容、播出時(shí)間、曝光次數(shù)提出要求，形成意向訂單，媒體結(jié)合自身廣告流量的預(yù)期庫(kù)存水平與廣告主協(xié)商后決定是否簽訂正式售賣合同。

廣告主的需求可以用播放時(shí)段(播放廣告的時(shí)間段)、節(jié)目路徑(播放廣告的節(jié)目載體)和投放數(shù)量(廣告曝光次數(shù))三個(gè)維度來(lái)描述。例如：廣告主希望于2013年4月1日至4月3日及4月11日至4月17日這10天的19:00—21:00在《中國(guó)達(dá)人秀》及《港臺(tái)電影》將廣告素材播放50萬(wàn)次。廣告素材由廣告主提供，可以是圖片、文字或短視頻等。有別于傳統(tǒng)電視直播或重播均由電視臺(tái)控制的特點(diǎn)，IPTV用戶收看節(jié)目有點(diǎn)播、回看、時(shí)移、直播等多種形式且可自由選擇，因而在廣告主的廣告投放訂單描述中，對(duì)投放時(shí)間及投放節(jié)目的描述也有相應(yīng)的特殊之處。

圖2 IPTV廣告投放要求圖示

如圖2所示，假設(shè)某訂單一共需要投放100萬(wàn)廣告流量。投放協(xié)議約定，廣告必須在指定的6個(gè)時(shí)段內(nèi)播出，且這6個(gè)時(shí)段被拆分成3個(gè)時(shí)段分組，各組投放流量分別為20萬(wàn)、30萬(wàn)、50萬(wàn)，合計(jì)100萬(wàn)；同時(shí)，廣告必須在指定的5個(gè)節(jié)目中播出，且這5個(gè)節(jié)目被拆分成2個(gè)節(jié)目分組，各組投放流量分別為40萬(wàn)、60萬(wàn)，合計(jì)100萬(wàn)。訂單在時(shí)段和節(jié)目?jī)蓚€(gè)維度對(duì)流量的需求是獨(dú)立的，不要求某個(gè)節(jié)目與某個(gè)時(shí)段一一對(duì)應(yīng)，但由于廣告主并不會(huì)為超額投放的廣告流量買單，卻會(huì)對(duì)未完成投放的流量索取違約金(懲罰成本)，因而媒體只能在對(duì)節(jié)目流量預(yù)測(cè)的基礎(chǔ)上，完成訂單的同時(shí)充分利用節(jié)目流量，盡可能讓廣告主需求的時(shí)段和節(jié)目匹配投放。

在實(shí)踐中，對(duì)于IPTV媒體運(yùn)營(yíng)者而言，由于采用預(yù)售方式，需要對(duì)未來(lái)一段時(shí)間的廣告流量進(jìn)行預(yù)測(cè)，終端用戶作為廣告流量的創(chuàng)造者，其收視行為的偶然性造成流量預(yù)測(cè)必然存在不確定性；與此同時(shí)，廣告主的訂單到達(dá)時(shí)間及訂單需求的數(shù)量也是不確定的。在這樣一個(gè)廣告流量供給和需求均存在不確定性的售賣模式中，如何制定廣告投放計(jì)劃成為亟待解決的問(wèn)題。

本文主要基于媒體的視角，研究如何在廣告流量庫(kù)存有限的情形下快速有效且合理地對(duì)其進(jìn)行分配以滿足不同廣告主的投放需求，簡(jiǎn)而言之就是庫(kù)存與需求的匹配問(wèn)題。為了簡(jiǎn)化考慮，本文假設(shè)廣告流量和廣告主訂單都是已知的，廣告流量單價(jià)在售賣合同簽訂時(shí)約定，在此基礎(chǔ)上設(shè)計(jì)以月為周期的廣告流量分配算法。

2 建立模型

經(jīng)過(guò)對(duì)問(wèn)題的分析，本文選用線性規(guī)劃模型給出數(shù)學(xué)表述形式。首先對(duì)模型中涉及的變量進(jìn)行定義：

i,j,k：訂單編號(hào)，投放時(shí)段(以小時(shí)為單位)，節(jié)目編號(hào)；

I,J,K：所有訂單集合，所有時(shí)段集合，所有節(jié)目集合；

m,n,Mi,Ni：時(shí)段分組編號(hào)，節(jié)目分組編號(hào)，訂單i指定的時(shí)段分組集合，訂單i指定的節(jié)目分組集合；

pi：訂單的合同約定單價(jià)(常用每千次展示成本CPM，這里處理成單次播放售價(jià))；

zjk：節(jié)目k在時(shí)段j的實(shí)際流量，則預(yù)期流量Zjk=E(zjk)，銷售取期望值；

Xijk：節(jié)目k在時(shí)段j實(shí)際分配給訂單i的廣告流量；

顯然，滿足訂單要求的所有時(shí)段可以表示為集合：

(1)

滿足訂單要求的所有節(jié)目可以表示為集合：

(2)

對(duì)于訂單，從時(shí)段和節(jié)目?jī)蓚€(gè)維度獨(dú)立定義的廣告流量總需求量應(yīng)當(dāng)一致，從而有

(3)

對(duì)于訂單i，若時(shí)段或節(jié)目不在指定的集合內(nèi)，則默認(rèn)分配的廣告流量為零：

Xijk≡0 ?i∈I，j?Tiork?Pi

(4)

此外，預(yù)期廣告流量Zjk使用預(yù)測(cè)值，視為已知量，Xijk為決策變量，最終目標(biāo)是使得收益R最大化。具體模型如下：

(5)

s.t.

(6)

(7)

(8)

Xijk≥0 ?j∈I，j∈Ti，k∈Pi

(9)

在上述模型中，式(5)作為目標(biāo)函數(shù)，優(yōu)化目標(biāo)是使得總收益R最大化，式(6)、(7)表示實(shí)際分配的流量在節(jié)目和時(shí)間兩個(gè)維度都應(yīng)當(dāng)與訂單需求量相等，式(8)表示實(shí)際分配流量不應(yīng)當(dāng)超過(guò)流量的預(yù)期庫(kù)存水平，式(9)是非負(fù)約束。若式(6)、(7)不成立則直接導(dǎo)致客戶訂單未滿足或因過(guò)分配造成流量浪費(fèi)，若式(8)不成立則表示存在超賣現(xiàn)象(按超過(guò)預(yù)期的庫(kù)存水平出售)，這兩者都會(huì)帶來(lái)違約風(fēng)險(xiǎn)和懲罰成本，嚴(yán)重者甚至?xí)饾u失去客戶的信任，引發(fā)企業(yè)信譽(yù)危機(jī)。

故而，企業(yè)在實(shí)際決策時(shí)需要考慮以下條件和目標(biāo)：

②應(yīng)盡可能滿足已形成正式售賣合同的所有客戶訂單，但不要超過(guò)需求量；

③應(yīng)盡可能充分售出廣告流量，但不要過(guò)度超賣。

這樣，流量分配決策轉(zhuǎn)化成多目標(biāo)決策問(wèn)題，從而可以將以上線性規(guī)劃轉(zhuǎn)化為目標(biāo)規(guī)劃問(wèn)題?，F(xiàn)假定以上三個(gè)目標(biāo)對(duì)應(yīng)的優(yōu)先因子分別為P1、P2、P3并規(guī)定P1?P2?P3，表示首先保證第一個(gè)目標(biāo)的實(shí)現(xiàn)，這時(shí)可以不考慮第二個(gè)目標(biāo)，P2級(jí)目標(biāo)是在實(shí)現(xiàn)P1級(jí)目標(biāo)的基礎(chǔ)上考慮的，以此類推。此外，對(duì)于同一個(gè)優(yōu)先因子的兩個(gè)目標(biāo)差別，可以賦予不同的權(quán)重系數(shù)w。優(yōu)先因子P和權(quán)重系數(shù)w都由決策者按照具體情況確定。

原問(wèn)題轉(zhuǎn)化為目標(biāo)規(guī)劃數(shù)學(xué)模型如下：

(10)

(11)

r=1,2,…,QQ=j·k

(12)

Xijk,d-,d+≥0

?i∈I?j∈J?k∈K

(13)

在對(duì)以上模型求解時(shí)可以按照線性規(guī)劃的常見(jiàn)算法進(jìn)行，例如單純形法、內(nèi)點(diǎn)法、外點(diǎn)法等。當(dāng)然，在具體的實(shí)踐案例中，要根據(jù)案例自身的特殊性及數(shù)據(jù)的特征靈活處理。

3 實(shí)證分析

本文的研究案例來(lái)自一家新媒體IPTV公司，所使用的數(shù)據(jù)在不影響業(yè)務(wù)描述和學(xué)術(shù)研究實(shí)證分析的前提下進(jìn)行了抽樣、縮放等處理，僅作為學(xué)習(xí)研究使用，不對(duì)外公開(kāi)。需要解決的問(wèn)題正如前文中的問(wèn)題描述所示：基于媒體的視角，研究如何在廣告流量庫(kù)存有限的情形下快速有效且合理地對(duì)其進(jìn)行分配，以滿足不同廣告主的投放需求。

本文選擇了一個(gè)月的節(jié)目播放歷史數(shù)據(jù)及對(duì)應(yīng)時(shí)段的廣告投放訂單，共計(jì)包含215個(gè)節(jié)目、264個(gè)需求訂單，其中需求細(xì)分包括371個(gè)時(shí)段分組及446個(gè)節(jié)目分組。媒體服務(wù)器在播出節(jié)目時(shí)系統(tǒng)會(huì)自動(dòng)記錄收看用戶的操作信息，包括用戶ID、節(jié)目路徑ID和點(diǎn)播時(shí)間。由于廣告主訂單一般對(duì)時(shí)間的要求都是精確到小時(shí)為單位，故而首先需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將原先精確到秒級(jí)別的播放記錄統(tǒng)計(jì)成小時(shí)級(jí)別的流量。此外，假定所有的流量售賣單價(jià)均為1，懲罰成本設(shè)定為零。

若直接按照模型中的訂單編號(hào)、投放時(shí)段、節(jié)目編號(hào)三個(gè)維度來(lái)定義，將會(huì)產(chǎn)生超過(guò)4000萬(wàn)個(gè)(264×(30×24)×215)決策變量及15.6萬(wàn)條(371+446+30×24×215)約束條件。在硬件及軟件處理能力的雙重限制下，如此龐大的線性規(guī)劃模型無(wú)法快速有效求解。但是經(jīng)過(guò)觀察，對(duì)于同一個(gè)訂單，在時(shí)段維度上的持續(xù)時(shí)間一般為3至7天中的部分時(shí)段，而非完整的1個(gè)月，并且在節(jié)目維度上也不會(huì)同時(shí)覆蓋全部215個(gè)節(jié)目。剔除每個(gè)訂單中不涉及的節(jié)目及對(duì)應(yīng)播放時(shí)段后，留下決策變量約70萬(wàn)個(gè)，不足原先個(gè)數(shù)的2%。同時(shí)，由于廣告主對(duì)節(jié)目?jī)?nèi)容及播放時(shí)段有自主選擇性，使得部分節(jié)目的部分點(diǎn)擊量超出所有廣告主的需求范圍，從而在考慮庫(kù)存約束條件時(shí)可以剔除這一部分。于是，約束條件剩下約9.5萬(wàn)條，僅為原來(lái)個(gè)數(shù)的60%. 經(jīng)此簡(jiǎn)化，線性規(guī)劃模型中的系數(shù)矩陣A縮減為約10萬(wàn)行70萬(wàn)列。同時(shí)，觀察到該矩陣中存在大量的零元素，故而選擇使用稀疏矩陣形式對(duì)其進(jìn)行存儲(chǔ)和相關(guān)運(yùn)算。

對(duì)于本案例的實(shí)際運(yùn)算，硬件設(shè)施是普通的臺(tái)式機(jī)(RAM-12G，CPU-i7-4770)，軟件為MATLAB及CPLEX，最終在10秒之內(nèi)輸出最優(yōu)解。

圖3所示為最終對(duì)每個(gè)訂單計(jì)算實(shí)際投放的流量達(dá)到需求數(shù)量的比例累積頻率分布圖。從圖3中可知，約有五分之一的訂單滿足率不足10%，約有40%的訂單被完全滿足。從實(shí)踐來(lái)看，當(dāng)切實(shí)考慮未完成投放的懲罰成本時(shí)，這部分滿足率特別低的意向訂單很可能被拒絕接受，即不會(huì)形成正式合同。換言之，本文的投放分配模型可以給企業(yè)銷售部門(mén)在考慮是否接受某意向訂單時(shí)提供決策支持。

圖3 訂單滿足率分布圖

圖4則是從投放結(jié)果中隨機(jī)抽取的8個(gè)訂單獲得的節(jié)目投放分布圖，可以看出這8個(gè)訂單一共涉及24個(gè)節(jié)目，其中編號(hào)為5122的訂單只投放了兩個(gè)節(jié)目，而編號(hào)為5120的訂單投放了8個(gè)節(jié)目?？傮w而言，全部264個(gè)訂單的需求總量約8200萬(wàn)，總庫(kù)存約1億，最終實(shí)際投放數(shù)量約5800萬(wàn)，訂單滿足率約為71%。在總庫(kù)存超過(guò)總需求的情形下卻沒(méi)有完全滿足所有訂單的原因主要有三點(diǎn)：第一，部分節(jié)目收視的點(diǎn)擊量在時(shí)間上較為分散，超出廣告主選擇的投放時(shí)段，造成廣告流量閑置；第二，部分節(jié)目點(diǎn)擊量很高，但其收視觀眾不被廣告主青睞，廣告流量難以全部售出變現(xiàn)；第三，部分節(jié)目的觀眾群體受到較多廣告主的爭(zhēng)奪，但點(diǎn)擊量有限造成廣告流量嚴(yán)重短缺，導(dǎo)致一些對(duì)節(jié)目定位范圍較窄、出價(jià)又缺乏競(jìng)爭(zhēng)力的廣告主未如愿分配到合適流量，最終以低滿足率甚至零滿足率收?qǐng)觥膶?shí)踐來(lái)看，可考慮結(jié)合節(jié)目本身內(nèi)容及實(shí)際投放情況，對(duì)銷售不太理想的節(jié)目和時(shí)段進(jìn)行打包，設(shè)計(jì)成新的產(chǎn)品，并通過(guò)適當(dāng)?shù)臓I(yíng)銷手段與定價(jià)方式，主動(dòng)尋找并出售給合適的廣告主。

圖4 訂單實(shí)際投放節(jié)目分布(取樣)

4 結(jié)論建議

本文主要從IPTV業(yè)務(wù)中廣告庫(kù)存售賣的實(shí)踐問(wèn)題出發(fā)，建立了廣告流量分配算法模型，并通過(guò)實(shí)踐案例對(duì)模型的可行性加以檢驗(yàn)。在求解過(guò)程中，針對(duì)問(wèn)題具體特性進(jìn)行的簡(jiǎn)化手段，以及后續(xù)為了提高運(yùn)算效率采取稀疏矩陣的處理防水，都在很大程度上提高了模型的實(shí)用性。本文的研究結(jié)果對(duì)于當(dāng)前更多依賴人工經(jīng)驗(yàn)進(jìn)行廣告流量分配的IPTV行業(yè)實(shí)踐具有一定的借鑒意義。對(duì)于未來(lái)三個(gè)月預(yù)售模式，在流量預(yù)測(cè)的基礎(chǔ)上通過(guò)本文提供的模型完成分配方案；在分配完畢之后，對(duì)于各個(gè)節(jié)目剩余未能售出的部分流量，考慮其分散化、碎片化的特性，可以考慮重新打包設(shè)計(jì)成新的產(chǎn)品，繼續(xù)尋找合適的新廣告主，從而充分提高流量變現(xiàn)效率。

后續(xù)研究主要有三方面：首先，提高前期流量預(yù)測(cè)的準(zhǔn)確性，這是售賣的基礎(chǔ)；其次，將廣告流量的具體售價(jià)及訂單懲罰成本具體化并納入實(shí)證求解過(guò)程，嘗試研究廣告定價(jià)策略及違約成本的確定；最后，考慮分配模型對(duì)流量預(yù)測(cè)不確定性的適應(yīng)性，以及實(shí)際投放過(guò)程與計(jì)劃方案出現(xiàn)偏離時(shí)如何快速及時(shí)地進(jìn)行動(dòng)態(tài)調(diào)整的問(wèn)題。希望這一系列的后續(xù)研究能與實(shí)踐的聯(lián)系更加密切，并進(jìn)一步提高模型的實(shí)用性。