论文标题
基于本地搜索的广告计划启发式方法
Local-Search Based Heuristics for Advertisement Scheduling
论文作者
论文摘要
在MaxSpace问题中，给定一组ADS A，一个人想将一个a'a a'a in a in k k插槽b_1，...，大小为l的b_k。如果任何插槽中的AD的总大小最多为L，并且A'中的每个AD A_I都出现在w_i插槽中，则计划是可行的。目的是找到一个可行的时间表，以最大化所有插槽中占用的空间。我们介绍了MaxSpace-RDWV，这是一个具有发布日期，截止日期，可变频率和广义利润的Maxspace概括。在MaxSpace-RDWV中，每个AD A_I都有一个发布日期R_i> = 1，截止日期D_I> = R_I，利润V_I可能与S_I无关，以及频率的w^min_i和w^max_i。在此问题中，AD可能仅出现在带有R_i <= J <= D_I的插槽B_J中，目标是找到可行的时间表，以最大程度地提高计划广告的值。本文介绍了一些基于元哈素化掌握，VN，本地搜索和tabu搜索MaxSpace和MaxSpace-RDWV的算法。我们将我们提出的算法与Kumar等人提出的杂种GA进行了比较。 （2006）。我们还为MaxSpace-RDWV创建了一个Hybrid-GA版本，并将其与我们的元数据进行比较。对于这两个问题，一些元映射（例如VNS和GRASP+VNS）的结果比混合GA更好。在我们的启发式方法中，我们应用了一种技术，该技术在最大化和最大程度地降低了插槽的饱满度之间以获得更好的解决方案。我们还将一个名为BIT的数据结构应用于MaxSpace-RDWV的邻域计算，并表明这使我们的算法能够运行更多迭代。
In the MAXSPACE problem, given a set of ads A, one wants to place a subset A' of A into K slots B_1, ..., B_K of size L. Each ad A_i in A has size s_i and frequency w_i. A schedule is feasible if the total size of ads in any slot is at most L, and each ad A_i in A' appears in exactly w_i slots. The goal is to find a feasible schedule that maximizes the space occupied in all slots. We introduce MAXSPACE-RDWV, a MAXSPACE generalization with release dates, deadlines, variable frequency, and generalized profit. In MAXSPACE-RDWV each ad A_i has a release date r_i >= 1, a deadline d_i >= r_i, a profit v_i that may not be related with s_i and lower and upper bounds w^min_i and w^max_i for frequency. In this problem, an ad may only appear in a slot B_j with r_i <= j <= d_i, and the goal is to find a feasible schedule that maximizes the sum of values of scheduled ads. This paper presents some algorithms based on meta-heuristics GRASP, VNS, Local Search, and Tabu Search for MAXSPACE and MAXSPACE-RDWV. We compare our proposed algorithms with Hybrid-GA proposed by Kumar et al. (2006). We also create a version of Hybrid-GA for MAXSPACE-RDWV and compare it with our meta-heuristics. Some meta-heuristics, such as VNS and GRASP+VNS, have better results than Hybrid-GA for both problems. In our heuristics, we apply a technique that alternates between maximizing and minimizing the fullness of slots to obtain better solutions. We also applied a data structure called BIT to the neighborhood computation in MAXSPACE-RDWV and showed that this enabled ours algorithms to run more iterations.
