有時間窗限制的線上廣告排程

Abstract

隨著網際網路使用者數量的快速累積，網際網路其媒體力量隨之變得具體而引人注目。網頁版面上的橫幅廣告為其最重要的商業應用之一，同時也是許多入口網站最主要的收入來源。然而，對於如何有效率的排程這些網路廣告以增加獲利的研究卻顯得稀少，因此，我們在這篇論文中，提出了一個更加貼近今日網際網路商業情形的模式。在此模式中，我們為每筆廣告訂單設定一段有效的刊登期間，然後站在廣告排程者的立場，努力滿足每筆訂單中對不同廣告欄位的次數需求，完全滿足者方可依各廣告欄位的訂價賺取收入。此模式不同於以往的研究，以廣告欄位的種類計價，而不以所占用的分割廣告空間大小為計價方式。而排程的目標，則是選取訂單並滿足其訂單內容，以獲得最大的營收。在這篇論文裡，我們先提出一個正式的數學式描述這個題目，考量此題目的計算複雜度，我們試著在合理的運算時間下尋求近似解。我們設計了一個三段式解題的啟發式演算法來解題，也設計一個推算可得利潤上限的方法，最後實作了此啟發式演算法，實驗結果顯示此法可有效的填滿百分之九十七的總廣告欄位。

As the population of the Internet users increases explosively, the media power of the Internet becomes concrete and remarkable. One of the leading commercial applications on the Internet is banner advertisements publishing, which also is the major source of income of many portal websites. However, there are few researches on how to schedule banners efficiently and profitably in the past decades. We thereby propose a new model for banner advertisements scheduling that further resembles the Internet business world. In the proposed model, we apply a feasible time window to each candidate order, and we schedule advertisements into various predefined banner spaces on the webpage. This approach allows various pricing strategies according to banner types, contrary to previous research models which schedule and price by banner space sharing. Each order will demand its frequency of each type of banner. The goal is to select orders and schedule their demands to achieve a maximum total profit. We first give a mathematical formulation to formally describe the problem. Due to the computational complexity of the studied problem, we seek to produce approximate solutions in a reasonable time. A three-phase heuristic is developed to cope with this problem. An upper bound on the profits is developed. Computational experiments are designed to examine the performance of the heuristic. Statistics from the experiments reveal that the heuristic can successfully fill up to 97 % of the ad spaces.