關于IPTV業務中廣告庫存分配算法的研究

邵進明 蔣 煒 李艷婷

(1.上海交通大學 安泰經濟與管理學院，上海 200030；2.上海交通大學 機械與動力工程學院，上海 200240)

0 引言

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

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

國內外學者關于IPTV廣告投放算法的研究，并不能很好地解決我國目前IPTV行業的實際問題。我國的IPTV業務采取的是廣電與電信合作的模式，雙方掌握的用戶數據是不共享的，IPTV廣告運營方無法獲取準確的用戶行為數據來定制用戶標簽，也就無法使用競拍投放定向廣告的方式將用戶出售給廣告主，因而目前使用的依然是基于節目內容而非用戶的售賣模式，在面對眾多廣告主時，如何優化流量分配方案、提高廣告流量利用效率顯得尤為重要。

1 問題描述

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

圖1 廣告業務流程

一般而言，IPTV運營方采用預售方式(例如出售未來三個月的廣告流量)：廣告主可以對節目內容、播出時間、曝光次數提出要求，形成意向訂單，媒體結合自身廣告流量的預期庫存水平與廣告主協商后決定是否簽訂正式售賣合同。

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

圖2 IPTV廣告投放要求圖示

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

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

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

2 建立模型

經過對問題的分析，本文選用線性規劃模型給出數學表述形式。首先對模型中涉及的變量進行定義：

i,j,k：訂單編號，投放時段(以小時為單位)，節目編號；

I,J,K：所有訂單集合，所有時段集合，所有節目集合；

m,n,Mi,Ni：時段分組編號，節目分組編號，訂單i指定的時段分組集合，訂單i指定的節目分組集合；

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

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

Xijk：節目k在時段j實際分配給訂單i的廣告流量；

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

(1)

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

(2)

對于訂單，從時段和節目兩個維度獨立定義的廣告流量總需求量應當一致，從而有

(3)

對于訂單i，若時段或節目不在指定的集合內，則默認分配的廣告流量為零：

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

(4)

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

(5)

s.t.

(6)

(7)

(8)

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

(9)

在上述模型中，式(5)作為目標函數，優化目標是使得總收益R最大化，式(6)、(7)表示實際分配的流量在節目和時間兩個維度都應當與訂單需求量相等，式(8)表示實際分配流量不應當超過流量的預期庫存水平，式(9)是非負約束。若式(6)、(7)不成立則直接導致客戶訂單未滿足或因過分配造成流量浪費，若式(8)不成立則表示存在超賣現象(按超過預期的庫存水平出售)，這兩者都會帶來違約風險和懲罰成本，嚴重者甚至會逐漸失去客戶的信任，引發企業信譽危機。

故而，企業在實際決策時需要考慮以下條件和目標：

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

③應盡可能充分售出廣告流量，但不要過度超賣。

這樣，流量分配決策轉化成多目標決策問題，從而可以將以上線性規劃轉化為目標規劃問題。現假定以上三個目標對應的優先因子分別為P1、P2、P3并規定P1?P2?P3，表示首先保證第一個目標的實現，這時可以不考慮第二個目標，P2級目標是在實現P1級目標的基礎上考慮的，以此類推。此外，對于同一個優先因子的兩個目標差別，可以賦予不同的權重系數w。優先因子P和權重系數w都由決策者按照具體情況確定。

原問題轉化為目標規劃數學模型如下：

(10)

(11)

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

(12)

Xijk,d-,d+≥0

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

(13)

在對以上模型求解時可以按照線性規劃的常見算法進行，例如單純形法、內點法、外點法等。當然，在具體的實踐案例中，要根據案例自身的特殊性及數據的特征靈活處理。

3 實證分析

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

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

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

對于本案例的實際運算，硬件設施是普通的臺式機(RAM-12G，CPU-i7-4770)，軟件為MATLAB及CPLEX，最終在10秒之內輸出最優解。

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

圖3 訂單滿足率分布圖

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

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

4 結論建議

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

后續研究主要有三方面：首先，提高前期流量預測的準確性，這是售賣的基礎；其次，將廣告流量的具體售價及訂單懲罰成本具體化并納入實證求解過程，嘗試研究廣告定價策略及違約成本的確定；最后，考慮分配模型對流量預測不確定性的適應性，以及實際投放過程與計劃方案出現偏離時如何快速及時地進行動態調整的問題。希望這一系列的后續研究能與實踐的聯系更加密切，并進一步提高模型的實用性。