Algorithme de recherche tabou pour la planification optimale d'une campagne marketing sur les moteurs de recherche

Avec l'essor de l'Internet et des moteurs de recherche, le Web marketing est devenu un métier à part entière qui s'est développé de manière totalement disruptive par rapport au marketing classique. Plusieurs paramètres forment la clé de voûte de la réussite d'une campagne de Web marketing dont : le choix des mots clés, le budget à allouer pour chaque mot clé, une bonne appréciation des attributs des cibles (langue, localisation, …) etc. Ce paramétrage est une tâche complexe à cause des quantités gigantesques de données à traiter d'où le recours grandissant à des firmes spécialisées dans la gestion des campagnes publicitaires sur Internet. Pour faire face à la très forte concurrence dans ce secteur de pointe, la société Aquisio, un leader mondial dans ce domaine, a lancé ce projet en collaboration avec l'École Polytechnique de Montréal. L'objectif étant de développer un module d'optimisation robuste permettant la gestion des campagnes publicitaires dans les moteurs de recherches d'Internet. Le présent projet de maîtrise porte sur le développement et l'implantation d'un module d'optimisation, à base de la recherche Tabou, dont le but est de maximiser le rendement de toute une campagne publicitaire sur Internet. L'efficacité de notre approche de résolution a été prouvée par des tests réalisés sur des échantillons de six bases de données fournies par notre partenaire industriel. En effet, l'utilisation du Tabou nous a permis de nous affranchir des limitations des méthodes d'optimisation généralement implantées dans les outils commerciaux. De plus la solution finale générée par notre module atteint aisément les 95% de la solution optimale et ceci est vrai pour les trois solutions initiales testées. Outre la bonne qualité des solutions, nous nous sommes également intéressés au temps d'exécution. Ainsi, en réduisant la taille du voisinage, nous avons réussi à générer des solutions de bonne qualité en un temps de calcul raisonnable, de l'ordre de quelques minutes. Mots clés : Web marketing, Optimisation, Recherche Tabou.

Abstract

With the rise of the Internet and search engines, Web marketing has become a profession in its own that has disrupted the evolution of traditional marketing. Several parameters are key to a successful Web marketing campaign including the selection of keywords, the budget allocated for each keyword, a good understanding of the attributes of the target (language, location, etc.). This configuration is an increasingly complex task due to the gigantic quantity of data to be processed. Thus, the use of specialized firms' services for managing advertising campaigns on the Internet is continuously growing. To cope with the strong competition in this leading sector, the company Aquisio, a world leader in this field, launched this project in collaboration with the Polytechnic School of Montreal. The objective is to develop a robust optimization module for managing advertising campaigns in Internet search engines. This Master project focuses on the development and implementation of an optimization module, based on the Tabu Search, whose goal is to maximize the performance of any advertising campaign on the Internet. The effectiveness of our approach resolution was proved by tests conducted on samples of six databases provided by our industrial partner. Indeed, the use of Tabu has allowed us to overcome the limitations of optimization methods generally provided in commercial tools. In addition, the final solution generated by our module reaches easily 95% of the optimal solution and this is true for the initial three solutions tested. Besides the high quality of solutions, we are also interested to execution time. Thus, by reducing the size of the neighborhood, we were able to generate good solution quality in a reasonable computation time, on the order of a few minutes. Key words: Web marketing, Optimization, Tabu Search