数字标牌广告即时排期优化算法研究

王敏　寇亚龙　赵霞

摘要：数字标牌广告是一种新型多媒体广告，通过在特定场所的终端机上进行广告投放，达到营销目的。传统的半自动化排期方式难以应对广告投放业务的即时变化，存在时间碎片多、屏幕利用率低的问题。针对这一问题，设计了时间碎片优化算法，对广告按照上刊日建立队列，达到即时目的。引入最早开始时间Et和最晚开始时间Lt概念，实现碎片优化处理。实验表明，算法高效稳定，能够避免排期冲突，大大降低碎片率，提高广告位的资源利用率。

关键词：广告；广告位；排期；时间轴；时间碎片

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）26-6238-04

随着媒体行业向新媒体方向发展，越来越多的媒体商成为数字标牌的拥有者，数字标牌逐渐从专用场所扩展到户内、户外的各种场所，除了承载传统报刊等媒体信息发布的功能，也同时为户内外广告发布提供了生动、即时、灵活、交互、直接等优势，成为新媒体行业中深具发展潜力和商业价值的新兴领域，得到新媒体行业中广告商、媒体商、运营商的青睐[9]。

现有的广告投放方法可以基本归为两大类：一类是互联网广告的投放方法[1]，可分为基于网页内容[2][3]，基于用户的个性化投放，主要工作内容为分类[6]和计算相似度；一类是移动终端的广告投放，可分基于用户特征和基于地理信息的推荐性投放，通过获取和预测用户的个人信息和喜好[4][11]，利用GPS地理定位进行广告的及时推送。但是没有针对新媒体中数字标牌广告的成熟的广告投放方法。随着广告主和媒体商（屏主）需求的变化[1]，广告投放市场规模不断扩大，需要提高广告投放过程的智能决策程度，提高广告位利用率，减小时间碎片率，高效、即时、精准[5]的数字标牌广告投放方法成为亟待研究的问题。

广告屏时间资源利用率主要取决于选屏的准确率以及广告排期过程中产生的时间碎片率。广告的排期算法决定了时间碎片率，该文对广告投放的即时性要求和时间碎片过多提出优化算法。根据时间指针、排期间隔和最小时间间隔计算出广告最早开始时间Et和最晚开始时间Lt，选择时间碎片优化方案。从而实现广告屏时间资源的充分利用，降低碎片率，增强广告即时投放的灵活性和即时性。

1 问题建模

1.1广告排期问题描述

数字标牌广告排期是广告投放系统根据广告主[8]给定的广告[Ai]，所给定广告屏[Si]的地理位置[7]、分辨率大小、进行选屏，得到广告屏集合，给出满足条件的广告位[Ri]集合；根据广告[Ai]的相关属性，得到时间约束条件，在时间约束条件下，给出广告位上播放广告的时间表（简称排期表）的过程。

2.2时间碎片优化算法

2.2.1即时排期的实现

订单中广告的属性包括上刊日和下刊日，即广告的真实播放时间。上刊日和下刊日通常为持续的一些天数，当广告进入订单库，排期服务器会读取其上刊日期，根据时间的先后按照上刊日期建立从当天开始每天的广告待排期列表。排期服务器会按照时间顺序进行每天的广告排期。实现了即时的目的。

本文设计和实现了数字标牌广告即时排期优化算法，实现了广告即时排期，引入最早开始时间Et和最晚开始时间Lt，时间指针tp概念，改进了简单排期算法中广告位时间资源连续的假设的缺陷。时间碎片优化算法在完成广告的时间约束的排期基础上，实现了碎片率的降低，减少了时间碎片的个数和时间碎片总时长，提高了广告屏时间资源的利用率。