請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/18676
標題: | 以最佳化技術為基礎之廣告時槽分配演算法以極大化電視廣播業者之收益並滿足廣告客戶之滿意度及公平性需求 An Optimization Based Ads Allocation Algorithm to Maximize Revenues with Client Satisfaction and Fairness Constraints for TV Broadcasting Operators |
作者: | Chih-Yun Chiu 邱芷芸 |
指導教授: | 林永松(Yeong-Sung Lin) |
關鍵字: | 廣播電視,廣告配置,Jain公平性指標,拉格朗日鬆弛法,FCFS演算法, broadcast television,ad scheduling,Jain’s fairness index,Lagrangian relaxation-based,FCFS scheduling algorithm, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 儘管近年來新媒體的崛起改變了人們互動的方式,電視廣告仍被視為一個與觀眾溝通的重要媒介,原因在於電視容易取得且具有極高的影響力。電視台主要靠出售廣告空間作為其收入來源,然而,電視台在對廣告進行配置時往往需要考量到多個客戶需求,因此對於電視台而言,要想出一個最佳的廣告配置來讓收入最大化同時又要滿足客戶的需求是一件相當具有挑戰且耗時的事。為了解決廣告配置的問題,我們先將問題轉換成目標為最大化電視台收入的數學規劃問題,再開發一個能在考量多種因素下找到最佳可行解的廣告配置演算法,因素包含公平性、黃金時間、可用的時槽、時槽的位置、客戶滿意度、客戶的預算、產品之間的衝突以及連播限制。為了得知每位客戶是否都被分配到相等的系統資源,我們使用Jain公平性指標來衡量公平性。除此之外,本研究也提出以拉格朗日鬆弛法為基礎的方法來解決數學規劃問題,並透過實驗來對於FCFS演算法與貪婪演算法進行比較,實驗結果顯示提出的演算法比FCFS演算法和貪婪演算法更接近預期的目標,因此擁有較佳的表現。另外,當問題規模很大時,所提出的方法與貪婪演算法在執行時間上只有不到18.3%的差距。 Even though new media has changed the way people interact with each other in recent years, advertisement (ad) on broadcast television (TV) still plays a key role in communicating with the audience due to the great impact and accessibility of TV. TV stations earn a profit primarily from selling ad spaces during commercial break, however, there are a number of client requirements they should considered when allocating the ads. Therefore, it is challenging and time-consuming for TV stations to come up with an optimal ad schedule that meets client requirements and maximizes the profit at the same time. To deal with the ad scheduling problem, we first formulate it into a mathematical programming problem that aims to maximize the revenue of TV station. Then, we develop an Langrangian relaxation-based heuristic that is able to obtain optimal feasible solution to the optimization problem that considerers a combination of several factors including fairness measured by Jain’s fairness index, prime time, available time slot, position of the time slot, client satisfaction, client budget, product conflict and multiple airing regularity. In addition, we carry out several computational experiments to evaluate the performance of the proposed heuristic, FCFS scheduling algorithm and greedy algorithm. There are also cases under different situation to simulate the performance of all the solution approaches introduced. The experimental results show that the proposed algorithm outperforms the FCFS scheduling algorithm and the greedy algorithm with a near-optimal solution. Also, the difference between the execution time of the proposed algorithm and the greedy algorithm is less than 18.3% even when the problem size is large. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/18676 |
DOI: | 10.6342/NTU202002937 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1108202013515600.pdf 目前未授權公開取用 | 1.81 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。