數(shù)字標(biāo)牌廣告即時(shí)排期優(yōu)化算法研究

王敏　寇亞龍　趙霞

摘要：數(shù)字標(biāo)牌廣告是一種新型多媒體廣告，通過(guò)在特定場(chǎng)所的終端機(jī)上進(jìn)行廣告投放，達(dá)到營(yíng)銷目的。傳統(tǒng)的半自動(dòng)化排期方式難以應(yīng)對(duì)廣告投放業(yè)務(wù)的即時(shí)變化，存在時(shí)間碎片多、屏幕利用率低的問(wèn)題。針對(duì)這一問(wèn)題，設(shè)計(jì)了時(shí)間碎片優(yōu)化算法，對(duì)廣告按照上刊日建立隊(duì)列，達(dá)到即時(shí)目的。引入最早開(kāi)始時(shí)間Et和最晚開(kāi)始時(shí)間Lt概念，實(shí)現(xiàn)碎片優(yōu)化處理。實(shí)驗(yàn)表明，算法高效穩(wěn)定，能夠避免排期沖突，大大降低碎片率，提高廣告位的資源利用率。

關(guān)鍵詞：廣告；廣告位；排期；時(shí)間軸；時(shí)間碎片

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）26-6238-04

隨著媒體行業(yè)向新媒體方向發(fā)展，越來(lái)越多的媒體商成為數(shù)字標(biāo)牌的擁有者，數(shù)字標(biāo)牌逐漸從專用場(chǎng)所擴(kuò)展到戶內(nèi)、戶外的各種場(chǎng)所，除了承載傳統(tǒng)報(bào)刊等媒體信息發(fā)布的功能，也同時(shí)為戶內(nèi)外廣告發(fā)布提供了生動(dòng)、即時(shí)、靈活、交互、直接等優(yōu)勢(shì)，成為新媒體行業(yè)中深具發(fā)展?jié)摿蜕虡I(yè)價(jià)值的新興領(lǐng)域，得到新媒體行業(yè)中廣告商、媒體商、運(yùn)營(yíng)商的青睞[9]。

現(xiàn)有的廣告投放方法可以基本歸為兩大類：一類是互聯(lián)網(wǎng)廣告的投放方法[1]，可分為基于網(wǎng)頁(yè)內(nèi)容[2][3]，基于用戶的個(gè)性化投放，主要工作內(nèi)容為分類[6]和計(jì)算相似度；一類是移動(dòng)終端的廣告投放，可分基于用戶特征和基于地理信息的推薦性投放，通過(guò)獲取和預(yù)測(cè)用戶的個(gè)人信息和喜好[4][11]，利用GPS地理定位進(jìn)行廣告的及時(shí)推送。但是沒(méi)有針對(duì)新媒體中數(shù)字標(biāo)牌廣告的成熟的廣告投放方法。隨著廣告主和媒體商（屏主）需求的變化[1]，廣告投放市場(chǎng)規(guī)模不斷擴(kuò)大，需要提高廣告投放過(guò)程的智能決策程度，提高廣告位利用率，減小時(shí)間碎片率，高效、即時(shí)、精準(zhǔn)[5]的數(shù)字標(biāo)牌廣告投放方法成為亟待研究的問(wèn)題。

廣告屏?xí)r間資源利用率主要取決于選屏的準(zhǔn)確率以及廣告排期過(guò)程中產(chǎn)生的時(shí)間碎片率。廣告的排期算法決定了時(shí)間碎片率，該文對(duì)廣告投放的即時(shí)性要求和時(shí)間碎片過(guò)多提出優(yōu)化算法。根據(jù)時(shí)間指針、排期間隔和最小時(shí)間間隔計(jì)算出廣告最早開(kāi)始時(shí)間Et和最晚開(kāi)始時(shí)間Lt，選擇時(shí)間碎片優(yōu)化方案。從而實(shí)現(xiàn)廣告屏?xí)r間資源的充分利用，降低碎片率，增強(qiáng)廣告即時(shí)投放的靈活性和即時(shí)性。

1 問(wèn)題建模

1.1廣告排期問(wèn)題描述

數(shù)字標(biāo)牌廣告排期是廣告投放系統(tǒng)根據(jù)廣告主[8]給定的廣告[Ai]，所給定廣告屏[Si]的地理位置[7]、分辨率大小、進(jìn)行選屏，得到廣告屏集合，給出滿足條件的廣告位[Ri]集合；根據(jù)廣告[Ai]的相關(guān)屬性，得到時(shí)間約束條件，在時(shí)間約束條件下，給出廣告位上播放廣告的時(shí)間表（簡(jiǎn)稱排期表）的過(guò)程。

2.2時(shí)間碎片優(yōu)化算法

2.2.1即時(shí)排期的實(shí)現(xiàn)

訂單中廣告的屬性包括上刊日和下刊日，即廣告的真實(shí)播放時(shí)間。上刊日和下刊日通常為持續(xù)的一些天數(shù)，當(dāng)廣告進(jìn)入訂單庫(kù)，排期服務(wù)器會(huì)讀取其上刊日期，根據(jù)時(shí)間的先后按照上刊日期建立從當(dāng)天開(kāi)始每天的廣告待排期列表。排期服務(wù)器會(huì)按照時(shí)間順序進(jìn)行每天的廣告排期。實(shí)現(xiàn)了即時(shí)的目的。

本文設(shè)計(jì)和實(shí)現(xiàn)了數(shù)字標(biāo)牌廣告即時(shí)排期優(yōu)化算法，實(shí)現(xiàn)了廣告即時(shí)排期，引入最早開(kāi)始時(shí)間Et和最晚開(kāi)始時(shí)間Lt，時(shí)間指針tp概念，改進(jìn)了簡(jiǎn)單排期算法中廣告位時(shí)間資源連續(xù)的假設(shè)的缺陷。時(shí)間碎片優(yōu)化算法在完成廣告的時(shí)間約束的排期基礎(chǔ)上，實(shí)現(xiàn)了碎片率的降低，減少了時(shí)間碎片的個(gè)數(shù)和時(shí)間碎片總時(shí)長(zhǎng)，提高了廣告屏?xí)r間資源的利用率。