Je suis à la recherche d'un algorithme de planification de la publicité radio/exemple/expérience

Question

J'ai essayé de faire un peu de recherche sur ce qui suit sans aucune chance. Je pensais que je demanderais ici au cas où quelqu'un l'aurait déjà rencontré auparavant. J'aide les stations de radio exploitées par des bénévoles à répondre à leurs besoins technologiques. Une des principales choses qui ont été soulevées est qu'ils aimeraient programmer leur publicité par programme.

Il existe un grand nombre de moteurs de règles simples et complexes pour la publicité, mais tout ce dont nous avons besoin est quelque chose de très simple (avec toute expérience qui mérite d'être pensée).

Je voudrais écrire quelque chose en SQL si possible pour gérer ces entités. Idéalement, si quelqu'un a écrit quelque chose comme ça pour d'autres supports publicitaires (web, etc.), ce serait vraiment utile.

Entités:

• annonces (composé d'une catégorie, nombre de pièces par jour, la date de début, date de fin ou jeu permanent)
• Catégorie de l'annonce (Restaurant, Santé, Commerce alimentaire, etc.)

Pour simplifier à l'excès le problème, il s'agira d'une instruction SQL élégante. Comment y arriver ... :)

Je voudrais être en mesure de générer une liste de lecture par jour en utilisant les deux entités ci-dessus où:

• Pas deux annonces dans la même catégorie sont joués dans x nombre d'annonces l'un de l'autre.
• (agréable d'avoir) des annonces de haute promotion peuvent être poussés

A cette époque, il n'y a pas « espaces publicitaires » pour remplir. Il n'y a pas de considérations sur «l'heure du jour».

Nous fait la queue des annonces pour la journée et de passer par les chansons entre/spectacles, etc. Nous savons combien par heure nous devons remplir, etc.

Toutes les pensées/idées/liens/exemples? Je vais continuer à regarder et j'espère trouver quelque chose au lieu de l'apprendre sur le long chemin.

Answer 1

Question très intéressante, SMO. À l'heure actuelle, cela ressemble à un problème de programmation par contraintes parce que vous ne cherchez pas une solution optimale, mais une solution qui satisfait toutes les contraintes que vous avez spécifiées. En réponse à ceux qui voulaient clore la question, je dirais qu'ils doivent vérifier un peu la programmation des contraintes. Il est beaucoup plus proche de stackoverflow que tous les sites de recherche opérationnelle. Examinez la programmation et la planification des contraintes - je parie que vous trouverez un problème analogue trop sucré!

Tenez-nous au courant de vos progrès, s'il vous plaît.

Answer 2

Ignorer la demande T-SQL pour le moment puisque c'est peu susceptible d'être la meilleure langue pour écrire ceci dans ...

Un de mes favoris approches des problèmes difficiles « layout » comme celui-ci est Simulated Annealing. C'est une bonne approche parce que vous n'avez pas besoin de penser COMMENT résoudre le problème réel: tout ce que vous définissez est une mesure de la qualité de la disposition actuelle (un score si vous voulez) et ensuite vous permettez des changements aléatoires qui augmentent ou diminuent ce score.Au cours de nombreuses itérations, vous réduisez progressivement la probabilité de passer à un score plus mauvais. Cette approche de «recuit simulé» réduit la probabilité de rester coincé dans un minimum local. Donc, dans votre cas, la fonction de notation pour une disposition donnée peut être basée sur la distance à la prochaine annonce dans la même catégorie et la distance à une autre annonce de la même série. Si vous avez plus tard des considérations d'heure, vous pouvez facilement les ajouter à la fonction de score.

Initialement, vous allouez les annonces de manière séquentielle, uniforme ou aléatoire dans leur fenêtre de temps (peu importe vraiment). Maintenant, vous choisissez deux emplacements et considérez ce qu'il advient du score lorsque vous changez le contenu de ces deux emplacements. Si l'une des publicités sort de sa plage autorisée, vous pouvez rejeter la modification immédiatement. Si les deux sont toujours à portée, cela vous amène-t-il à un meilleur score global? Au départ, vous prenez des changements au hasard, même si cela les aggrave, mais au fil du temps, vous réduisez la probabilité que cela se produise, de sorte qu'à la fin vous vous déplacez de façon monotone vers un meilleur score.

Facile à mettre en œuvre, facile d'ajouter de nouvelles « règles » qui affectent score, peut facilement ajuster la gestion du temps pour accepter une réponse « assez bonne », ...

Une autre approche serait d'utiliser un algorithme génétique , voir cette question similaire: Best Fit Scheduling Algorithm cela est probablement plus difficile à programmer mais convergera probablement plus rapidement sur une bonne réponse.