考量不同廣告版面的線上廣告排程

Abstract

隨著網際網路使用者的數量不斷增加，橫幅廣告的利潤成為網站擁有者主要的收益來源。由於橫幅廣告版面篇幅的限制，能獲取較多點擊數和瀏覽注目的區塊，將可向廣告主收取較高的刊登費用；某些廣告主則期望只在特定時段刊登廣告以吸引目標訪客，因此對於網站擁有者來說，如何在各方限制下取得一個最佳化刊登橫幅廣告的放置方法，將能有效的提升其廣告收益。故本論文提出一系列最佳化演算法，設計兩種不同的經驗法則計算方式，以快速的找到初始解。採用結果較佳的經驗法則計算結果，進而配合禁忌搜尋改善搜尋結果，協助廣告經營者在眾多廣告主之不同類型與需求的訂單中，選出最適當之廣告訂單子集合，使網站廣告利潤最大化。論文中提出整數規劃的模型以正規化的描述此問題，並設計動態規劃演算法以證明其為NP-Hard問題。實驗結果顯示，本論文之排程方法產生之廣告收益可以與最佳化軟體Gurobi抗衡。

With the population on the Internet increases continuously, banner advertisements constitute the main source of revenue to most website owners. Because of the limit of banner space, the website advertisement space should be price-differentiated to reflect the gazes from website visitors. Additionally, some advertisements have their time-effective factors for the reason that the visitors may browse on the Internet in particular dates to find some particular goods and service. Obtaining the optimal placement of advertisements is a major issue to the website owners. In this paper, we design and implement an algorithm that combines heuristics and tabu search algorithm for solving portal advertisement with distinct banner categories problem. Two heuristics are designed to obtain an initial solution in a timely manner. Furthermore, we adapt tabu search to improve the objective value to maximize the revenue of website owners by selecting the best subset among all orders with distinct requirements. Formally describing the problem, an integer programming model is proposed in Chapter 2. The studied problem is NP-hard for it can be reduced from the classical multiple knapsack problem. We design a dynamic programming algorithm for producing optimal solutions. The objective values given by Gurobi are used as the benchmarks to examine the performances of our proposed algorithms. The experiment results suggest that the objective values obtained from the proposed algorithms outperforms Gurobi in terms of solution quality and elapsed execution time.