戶外廣告資源配置優化模型及算法研究

朱 軍，陳敬良，張安淇

（1. 上海理工大學 管理學院，上海 200093；2. 復旦大學 管理學院，上海 200433）

戶外媒體是一種傳統且行之有效的媒介形式，2017年我國戶外廣告總規模超過1 300億元，較2016年度增長超過7%。據預測，隨著新技術與新模式的應用，戶外廣告市場規模將進一步提升，在2021年戶外廣告的市場規模有望達到2 200億元。戶外媒體的選擇與廣告投放既是達到廣告營銷預期目標的保障措施，同時也是支付大量廣告費用的商家最為關心的問題，并且是戶外媒體運營商在企業戰略、營銷管理中的重要基礎。

傳統戶外媒體運營者都是基于約定廣告位置，按廣告展示時間與廣告位數量的雙因素模式銷售給廣告主。從現有的戶外廣告媒體傳播理論研究來看，對戶外媒體的評估都是在空間生產理論的基礎上，通過人工有限地進行數據采集，并結合經驗進行評估，考慮了千人成本、人流量、可視機會等要素，但缺乏精準的大數據抓取，以及在此基礎上的全面數據分析[1]。這不僅導致廣告主的投放缺乏科學依據，也使媒體運營方受到廣告時間及廣告位數量限制，效益無法最大化。

戶外廣告媒體的建設由于需要占用有限的公共空間，投入大，回報周期長，不管是主管審批部門還是建設運營企業都需要對廣告媒體進行更合理的規劃，并基于精準的受眾人群推送，衍生更多的營銷形式，適應當下戶外廣告發展的需求。基于移動互聯網技術的應用及其普及，戶外媒體對受眾大數據的獲取及挖掘成為可能，進而實現對受眾偏好的精準分析，并對戶外媒體選擇與廣告效果評估方面產生根本性的影響[2]。隨著全球定位系統（GPS）、無限局域網（WIFI）、藍牙等傳感技術的日益成熟，戶外媒體已經可以精準收集其所在空間的用戶數據，包括實時人流數量、空間距離、移動速度和方向等，并通過各類地理位置信息服務 （location based service，LBS）順利地了解到用戶的消費習慣、收入水平、關注領域等核心數據，勾畫出準確的用戶畫像。此外，由于大數據基礎建設在重點行業的日益完善，以及不同行業間底層支撐技術相同，廣告行業在應用大數據時可以通過跨行業合作獲得線上及線下數據[3]。

戶外廣告媒體價值的精準測算對廣告運營公司而言具有重要的決策參考價值，廣告運營公司可以通過戶外廣告資源的優化配置，更加科學有效地制定戶外廣告媒體的出售價格策略，從而更好地為公司盈利[4]。

本文結合戶外廣告的特點，基于LBS服務和大數據技術，提出戶外廣告資源配置優化模型，在滿足廣告主要求達到的廣告營銷預期目標的基礎上，產生最大化的收益，突破傳統雙因素模式的局限性，通過數據分析方法研究戶外媒體資源的優化配置策略，建立基于用戶大數據的戶外廣告投放決策模型，為戶外媒體的生產與價值提升提供了有效方法。

1 問題描述與模型建立

1.1 問題描述及符號表示

1.2 模型建立

戶外媒體廣告公司收益最大的數學模型為

其中：方程（1）是戶外廣告屏廣告收入最大的目標函數，約束條件式（2）是指所有廣告的支出不可以超過它的預算；約束條件式（3）為廣告客戶所要求達到的最小廣告播放數；式（4）是所投放的廣告無法超過某個廣告屏的廣告容量。N為廣告客戶總數。利用大數據和定位技術獲得對應廣告屏覆蓋的受眾數據，覆蓋率的高低反映了戶外廣告和周邊客流量的相關程度。如果覆蓋率低，說明廣告和周圍客流的偏好屬性相關程度小，在這類廣告屏上就要盡量少投放廣告；如果覆蓋率高，說明廣告和廣告屏周圍客流偏好屬性相關程度大，在這類廣告屏上就要盡量多投放廣告。

2 對戶外廣告資源配置優化問題的求解

本文的優化目標是基于某種戶外廣告預算，廣告商全部收入最大化。需要解決的問題是通過算法提升運行效率，實現對于最優值的搜索與求解。

2.1 粒子群優化算法

粒子群優化算法（particle swarm optimization，PSO）主要依據鳥類群體的相關行為作為基礎進行研究，同時根據相關的生物模型進行進一步優化[5]。這種算法以整體為參考，從而消除了個體之間的差異。算法將測量的個體粒子化，在空間中對相關的性能指標進行測量，并按照群體的狀況作動態調整。

所有粒子現在的最好位置 P b可通過下列式子來確定：

每個粒子位置的各維值按式（8）和式（9）進行動態調整。

式中：w為慣性因子；為介于（0, 1）之間的隨機數。

2.2 引力搜索算法

引力搜索算法（gravitational search algorithm，GSA)是以萬有引力為基礎的一種基本算法。在一個空間中，粒子之間的作用受到萬有引力的影響，并且具有一定的指引作用，同時在所有的相關粒子之間會產生一種奇特的現象，即對于整體中質量最大的粒子，會產生一種相當于人類所說的“人格魅力”，不斷地去吸引其他的粒子[6-7]。與PSO相似，這種算法在多維空間中進行相關的初始化過程時，一般對于其慣性質量有固定的公式進行計算，根據下列式子得出相關數據：

在搜索空間的不同維數中，粒子的引力

依照牛頓萬有引力定律，粒子i在d維空間上的合力與別的所有粒子對它的作用力的和是完全相同的。

要想提高算法的隨機性，將粒子i受到的全部作用力進行隨機化，這時粒子的加速度

在群體的進化環節里，粒子依照以下方程進行相應的改變。

2.3 混合粒子群算法

對于本文的優化問題，粒子群優化算法具有一定的優勢，同時也有相關的劣勢存在，它主要是在前期的相關運算中表現出很強的優化能力。但隨著運算的進行，相關的優化收斂速度會有所下降，到后期就會有衰退的現象。所以，無法保證整體性的優化，容易陷入局部最優。通過結合上述引力原理進行優化融合，剛好填補了粒子群優化算法在后期容易陷入局部最優的劣勢，將兩種方式進行整合優化，能夠達到最優的效果，對于整體優化有很好的優勢，并能夠進行廣泛運用[8]。混合粒子群算法（hybrid particle swarm optimization，HPSO）步驟如下：

a. 初始化算法的相關系數；

b. 隨機初始化粒子群所處位置；

c. 求各粒子的最佳值；

d. 尋找個體歷史最優解與全局最優解；

e. 使用PSO算法更新粒子速度和所處位置；

f. 若粒子群的進化停滯步數大于設定值T，那么，轉入步驟g，否則，轉步驟h；

g. 采用GSA進行優化搜素，更新個體歷史最優解和全局最優解；

h. 若符合搜索精度或者達到最大搜索次數，那么，進入步驟i，否則，搜索次數提高一次，且進入步驟c，進行下一次的搜索工作；

i. 輸出全局最優解和最優個體值。

2.4 協同混合粒子群算法

協同進化概念最早由Ehrlich和Raven共同提出，討論的是植物與蝴蝶在進化過程中的相互影響，這種相互作用方式在大自然中特別是在相互的生存依賴方面，是一種普遍存在的關聯關系。通過雙方的共同努力、共同生存及進化，很好地體現了物競天擇、適者生存的自然生存法則。

這種相互作用和進化的方式，要求充分掌握與個體關聯的其他個體的各類信息數據，體現了個體與整體之間的相關性，而不僅僅由定義目標個體的函數來評價個體。通過對自然界的各類相互作用進行觀察和研究后，Jason也提出了相近的協同進化理論，內容不僅涵蓋了生物間的競爭關系、寄生依存關系，同時還包括了捕食者和被捕食者之間存在的相關關系，以及互利的協同進化[9]，基于并行與相互合作，協同進化算法提升了運行效率，減少了計算時間，提高了種群的精度，實現對于最優值的搜索。

由協同進化理念演變而成的算法最主要的特點是在搜索時通過多個種群并聯運行，而在后續迭代時設置各類差異性的進化，這種方法不僅對全局整體搜索起到效率提升作用，并且還能對后期所獲的最優值進行迅速收斂。在搜尋運行過程中，種群之間建立起一個不斷相互進化影響的機制，從而有效地解決了陷入局部最優的問題，能夠取得更好的辨識效果[10]。

在協同混合粒子群算法（cooperative hybrid particle swarm optimization，CHPSO）中，將粒子群平均劃分為k個子群，每個子群首先獨立，并行完成尋優過程，通過子群交流獲得種群的最優粒子，并用該最優粒子隨機替換各子群中的一個粒子（最優粒子所在子群除外）。協同混合粒子群算法流程如圖1所示，其步驟主要包括：

a. 初始化參數，初始化種群；

b. 將種群平均劃分為k個子群；

c. 各個子群利用HPSO算法尋優，HPSO流程如圖2所示；

d. 子群交流，種群最優粒子與最優適應值更新；

e. 利用種群最優粒子隨機替換各子群中的任一粒子（最優粒子所在的子群除外）；

f. 當滿足搜索精度或達到最大搜索次數，則優化過程結束，否則轉步驟c。

M為慣性質量，a為加速度，G為引力參數，b為最好適應值，w為最差適應值。

圖1 協同混合粒子群算法流程圖Fig.1 Flow chart of the cooperative hybrid particle swarm optimization

3 仿真實驗及分析

實驗是在Matlab 2015R軟件下運行，對本文所提出的優化問題進行分析。假設目前有20個有意向的客戶需要進行廣告的播放，只有10個合適的廣告屏幕，并且對于每組的相關數據按500次的數量來進行計算。由于戶外廣告客流量偏好屬性以及定位的統計數據涉及行業保密性，不便公開，在此借鑒文獻[11-16]，在實驗環境下使用上述方法來生成不同廣告在不同廣告屏上的播放，并且和文獻[16]維持同樣狀態。這里參數調整如下：的 大小取值控制在0～200之間，是20～800之間均勻分布的任意數字，gij為第i個客戶在第j塊廣告屏時的引力參數，0.4pij，Mi取70～400之間均勻分布的任意數字，Ci取500 000～2 000 000之間均勻分布的任意數字，Sj取2 000～4 500之間均勻分布的任意數字。

CHPSO算法的相關系數調整為：協同子群個數為5，最大迭代次數為20 000，種群大小N=100，學習因子c1=c2=2，慣性權重w=0.7，PSO算法的進化停滯步數T0設定值為50，當停滯步數大于T0時，引入 GSA算法尋優。GSA中 G0=100，α=20。對仿真實例分別進行10次獨立實驗，通過一系列的計算，得知最優解為4.233 9×106，也就是所有廣告在屏幕上的呈現次數，如表1所示，該最優解體現了算法的科學性與合理化，如圖3所示。Fi為適應度函數值，g為迭代次數。

圖2 HPSO子流程圖Fig. 2 Sub flow chart of the hybrid particle swarm optimization

圖3 算法性能Fig.3 Algorithm performance

表1 算法最優解Tab.1 Optimal solution by the algorithm

4 研究結論與展望

本文模型是一個帶約束的整數優化解決方案，通過罰函數將其轉換為無約束問題，并以融合優化的方式進行最優求解，相關的仿真實驗結果表明了協同混合粒子群算法的有效性。

提出了一種基于大數據與定位技術精準營銷相結合來進行綜合定價的模型。將這種模型運用于戶外廣告領域，能夠較好地解決廣告主和相關廣告運營企業的共同利益互存，使雙方的利益最大化，具有實用性，其主要體現在3個方面：

a. 移動互聯網技術及大數據技術的發展，使戶外媒體受眾的各類行為數據得以像互聯網媒體一樣被收集與挖掘，使戶外媒體的精準營銷成為必然趨勢，此模型在廣告主及媒體運營商兩方效益共同提升的可能性方面進行了探索。

b. 戶外媒體的受眾主體行為目前僅依靠單位時間內的觀測法、調研法及攝像監控進行統計，缺乏科學的數據統計方法，在此基礎上進行數據挖掘，導致戶外媒體的選擇與廣告效果的評估均存在較大漏洞。本文提出的戶外廣告資源配置優化模型為戶外廣告效果提供了新的判斷方法。

c. 線上數據與線下場景如何進行導流互通，這是戶外廣告資源優化配置中較為關鍵的問題，現在的問題是導流過程中缺乏數據。目前戶外的數據只有車流、人流，缺少一個能夠貫通其他平臺的數據解決方案。未來，戶外能否采用和移動互聯同一基礎的數據來評估，或者提供戶外的受眾數據、人數以及畫像，從而形成真正有效導流的方法還有待進一步研究。

本研究提出的戶外廣告資源優化模型能較有效地解決廣告客戶和媒體運營商的利益平衡問題，更適合實際應用情況。模型是一個帶約束的整數優化問題，通過罰函數將其轉換為無約束問題，并通過協同混合粒子群算法進行求解，仿真實驗結果表明了算法的有效性。