(57)【特許請求の範囲】
【請求項１】
デジタルサイネージで放映されるコンテンツの放映計画を生成する放映計画生成装置において、
デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、前記コンテンツを放映可能な複数の放映可能時間枠とを記憶する記憶手段と、
前記記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成する生成手段と、
各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように前記任意の放映計画を最適化する最適化手段と、を有し、
前記効果指標は、
τΣｋ＝１ｎ｛Ｎｋｄｋ＋δ（１＋Σｉ＝１Ｎｋ−１（１−ｅ−（Ｄｋｉ−ｄｋ）／δ））｝（但し、τはデジタルサイネージの近傍を通過した単位時間辺りの平均通行人数、Ｎｋはｋ番目のコンテンツの指定放映回数、ｄｋはｋ番目のコンテンツの時間長、δはデジタルサイネージの近傍で留まった通行人の単位時間辺りの平均滞留時間、ｅは指数関数の底（ネイピア数）、Ｄｋｉはｋ番目のコンテンツがｉ回目に放映されてから次に放映開始されるまでの放映間隔）の関数であることを特徴とする放映計画生成装置。
【請求項２】
前記最適化手段は、
前記第１条件を満たさないコンテンツの数及び／又は前記第２条件を満たさない放映可能時間枠の数と前記効果指標との差を評価関数とし、前記任意の放映計画から始めて当該放映計画に近傍な放映計画を探索しながら、前記評価関数が最小となる放映計画を探索することを特徴とする請求項１に記載の放映計画生成装置。
【請求項３】
前記近傍な放映計画は、
放映計画を構成している要素の一部を変更することにより生成されることを特徴とする請求項２に記載の放映計画生成装置。
【請求項４】
デジタルサイネージで放映されるコンテンツの放映計画を生成する放映計画生成装置で行う放映計画生成方法において、
前記放映計画生成装置は記憶手段を備え、
デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、前記コンテンツを放映可能な複数の放映可能時間枠とを前記記憶手段に記憶する第１のステップと、
前記記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成する第２のステップと、
各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように前記任意の放映計画を最適化する第３のステップと、を有し、
前記効果指標は、
τΣｋ＝１ｎ｛Ｎｋｄｋ＋δ（１＋Σｉ＝１Ｎｋ−１（１−ｅ−（Ｄｋｉ−ｄｋ）／δ））｝（但し、τはデジタルサイネージの近傍を通過した単位時間辺りの平均通行人数、Ｎｋはｋ番目のコンテンツの指定放映回数、ｄｋはｋ番目のコンテンツの時間長、δはデジタルサイネージの近傍で留まった通行人の単位時間辺りの平均滞留時間、ｅは指数関数の底（ネイピア数）、Ｄｋｉはｋ番目のコンテンツがｉ回目に放映されてから次に放映開始されるまでの放映間隔）の関数であることを特徴とする放映計画生成方法。
【請求項５】
コンピュータを請求項１乃至３のいずれかに記載の放映計画生成装置として機能させるための放映計画生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルサイネージで放映されるコンテンツの放映計画を生成する技術に関する。
【背景技術】
【０００２】
デジタルサイネージは、電子看板や電子ポスター等とも称され、「屋外・店頭・公共空間・交通機関等のあらゆる場所で、通信ネットワークに接続されたディスプレイ等の電子的な表示機器を使用して情報を発信するシステム」と定義される。通信ネットワークを介して様々な場所にコンテンツを配信し、時間帯や場所に応じてコンテンツをタイムリーに切り替えて表示できるという特徴を持つ。例えば、「夜は帰宅途中のサラリーマンが多く、昼は主婦層が多い」といった場所の特性に合わせて、時間帯毎にコンテンツを切り替えることも可能である。
【０００３】
このようなデジタルサイネージは、看板・ポスター・テレビ等の従来型のメディアでは実現できない情報発信手法と言える。
【０００４】
〔従来技術１〕
非特許文献１には、標準的なデジタルサイネージシステムで使用されるコンテンツの放映計画編集方法が記載されている。
【０００５】
図１１に示すように、標準的なデジタルサイネージシステムは、コンテンツや放映計画を管理及び配信する配信サーバ２０１と、その放映計画に基づいてコンテンツを再生するプレーヤ２０２と、再生されたコンテンツを表示するディスプレイ２０３と、放映計画を生成するための各設定値やコンテンツを配信サーバ２０１に入力する操作端末２０４とで構成されている。１台の配信サーバ２０１には複数のプレーヤ２０２が接続され、１台のプレーヤには１台以上のディスプレイが接続される。
【０００６】
図１２及び図１３を参照しながら、この標準的なデジタルサイネージシステムの基本的な運用フローについて説明する。
【０００７】
最初に、操作者によるコンテンツの登録操作に基づいて、操作端末２０４により、映像・静止画のファイルやテロップ文字列等のコンテンツが配信サーバ２０１に登録される（Ｓ３０１）。
【０００８】
次いで、操作者によるプレイリストの生成操作に基づいて、操作端末２０４及び配信サーバ２０１により、コンテンツの再生順又は表示順を設定したプレイリストが生成される（Ｓ３０２）。例えば、図１３（ａ）に示すようなプレイリストＡ，Ｂが生成される。プレイリストＡには、３つのコンテンツＡ１，Ａ２，Ａ３をＡ１→Ａ２→Ａ３の順で６０秒で一巡するように再生することが定義されている。一方、プレイリストＢには、４つのコンテンツＢ１，Ｂ２，Ｂ３，Ｂ４をＢ１→Ｂ２→Ｂ１→Ｂ３→Ｂ１→Ｂ４の順で９０秒で一巡するように再生することが定義されている。なお、一般的なデジタルサイネージシステムでは、プレイリストを生成するためのグラフィカルユーザインタフェースが提供されている。
【０００９】
次いで、操作者によるスケジュールの生成登録操作に基づいて、操作端末２０４により、プレイリストの再生日時（再生日・再生開始時刻・再生終了時刻）を設定したスケジュールが生成され、配信サーバ２０１に登録される（Ｓ３０３）。例えば、図１３（ｂ）に示すようなスケジュールが生成される。このスケジュールには、６時から１２時までの間はプレイリストＡを再生し、１２時から１６時までの間はプレイリストＢを再生し、１６時から２３時までの間はプレイリストＣを再生することが定義されている。具体的には、例えば、プレイリストＡの再生開始時刻については６時が設定され、再生終了時刻については１２時が設定されている。
【００１０】
そして、プレイリストとスケジュールのセットがコンテンツの放映計画に対応しており、図１３（ｃ）に示すような、プレイリストとスケジュールから個々のコンテンツの再生開始時刻及び再生終了時刻をリスト化した放映計画が生成される。この例では、６０秒で一巡するプレイリストＡが、６時から１２時までの６時間（＝３６０分）で３６０回繰り返し再生されることになる。同様に、９０秒で一巡するプレイリストＢは、１２時から１６時までの４時間（＝２４０分）で１６０回繰り返し再生されることになる。特にコンテンツＢ１については、一巡する間に３回の再生回数が設定されているため、その４時間で４８０回（＝３回×１６０回）再生されることになる。
【００１１】
次いで、操作者によって指定された時刻に到達すると、配信サーバ２０１により、登録されているコンテンツや該コンテンツの放映計画が各プレーヤ２０２に配信され（Ｓ３０４）、各プレーヤ２０２により、配信されたコンテンツと放映計画が蓄積される。
【００１２】
最後に、コンテンツの放映計画で設定された時刻に到達すると、各プレーヤ２０２によって、その時刻に対応するコンテンツが自動再生され、ディスプレイ２０３に表示される（Ｓ３０５）。
【００１３】
このようなコンテンツの運用方法は、コンテンツの放映主（コンテンツが広告の場合には広告主）からコンテンツを放映する時刻指定が殆どなく、放映回数やコンテンツの時間長（以下、尺という）を操作者が任意に決めてよいのであれば、非常に効率的である。
【００１４】
しかしながら、放映主や広告主からは、放映効果や広告効果を高めるために、コンテンツの再生・表示場所の選択のみではなく、放映時刻・放映回数・尺を詳細に設定したいという要望がある。
【００１５】
例えば、コンテンツＡ１，Ａ２，Ａ３の放映回数を広告予算に応じて広告主がそれぞれ１０回，２０回，５０回と指定した場合には、プレイリストＡの単純な繰り返し再生では対応できず、コンテンツＡ１，Ａ２，Ａ３を１：２：５の割合で組み込んだプレイリストを新たに生成しなくてならない。また、コンテンツ毎に尺が異なる場合には、コンテンツを空き時間枠に隙間なく割り付けることが難しくなる。
【００１６】
すなわち、従来技術１によれば、放映申込条件や広告申込条件の自由度を高めるほどコンテンツの放映計画の生成作業が複雑化するため、運用コストが高くなるという問題があった。
【００１７】
〔従来技術２〕
非特許文献２には、デジタルサイネージの広告申込（オーダー）の表現方法が記載されている。具体的には、デジタルサイネージに対して広告申込を行う際に、広告主又はその代理店が、図１４に示すような広告申込項目に対して値を指定する。非特許文献２のデジタルサイネージのシステムは、広告主又はその代理店から複数の広告申込を受け付け、その申込順に、広告に対して放映時間帯を自動的に割り付ける処理を行う。
【００１８】
図１５及び図１６を参照しながら、非特許文献２で示された放映計画生成方法について説明する。図１５は、４種類の広告申込（オーダー）を示す図である。図１６は、その４種類の広告申込に基づいて割り付けられた放映時間帯を示す図である。なお、図１６の横軸は時刻を表し、縦軸は４種類のオーダーを示し、各オーダーに基づいて割り付けられた放映時間帯を点ハッチで示す。なお、点ハッチ内の数字は、オーダーの申込順（優先度）を表している。
【００１９】
４種類のオーダーのうち時間指定オーダーＴは、Ｌ５０１という３単位時間（例えば、１５秒を単位時間とすると４５秒間）の尺を持つ広告を、Ｔ１７の表示開始時刻からＴ２０の表示終了時刻まで表示することを依頼するものである。この時間指定オーダーＴは、表示開始時刻及び表示終了時刻が固定的に指定されているため、Ｔ１７〜Ｔ１９の時間帯が割り当てられることになる（図１６の符号７００参照）。
【００２０】
一方、バルクオーダーＢは、ＸＰという３単位時間の尺を持つ広告を、Ｔ１の表示開始時刻からＴ５０００の表示時刻終了まで繰り返し表示することを依頼するものである。サイクル時間長（再生許容時間間隔）が１０単位時間であるため、図１６の符号７０１〜７０３で示す時間帯に３単位時間の広告をそれぞれ１回ずつ放映することになる。
【００２１】
一方、繰り返しオーダーＲは、Ｆｅａｔという２単位時間の尺を持つ広告を、Ｔ１の表示開始時刻からＴ２３の表示終了時刻まで繰り返し表示することを依頼するものである。この繰り返しオーダーＲは、サイクル時間長が２単位時間であってサイクル間隔が８単位時間であるため、Ｔ０１とＴ０２、Ｔ１１とＴ１２、Ｔ２１とＴ２２の時間帯を割り当てるしかない。なお、前述のバルクオーダーＢに対しては、繰り返しオーダーＲが割り当てられていない時間帯であるＴ０３〜Ｔ０５、Ｔ１３〜Ｔ１５、Ｔ２３〜Ｔ２５が割り当てられることになる。
【００２２】
一方、標準スケジュールオーダーＳは、ＭｃＤという２単位時間の尺を持つ広告を、Ｔ１の表示開始時刻からＴ３０の表示終了時刻まで繰り返し表示することを依頼するものである。サイクル時間長が１０単位時間であるため、図１６の符号７０４〜７０６で示す１０単位の時間枠に２単位時間の広告をそれぞれ１回ずつ放映したい。符号７０４，７０６には、Ｔ０６とＴ０７、Ｔ２６とＴ２７の時間帯をそれぞれ割り当てることができるが、符号７０５の時間枠には２単位時間分の空き時間帯がないため、広告申込通りの放映計画を生成できない。そのような場合には、１回少ない放映時間で問題ないかを広告主又はその代理店に逆提案することになる。
【００２３】
このように、従来技術２によれば、放送時間帯を広告申込順で割り付けていくため、広告主又はその代理店にとって常に最適な放映計画を生成できないという問題があった。すなわち、広告申込が遅れるほど広告の放映時間帯を所期の時間帯に割り当てることが難しく、広告申込を受け付けられずに断らなくてはならない状況になる。また、図１６のＴ１６やＴ２０の時間帯のように、生成された放映計画に隙間（広告が割り付けられていない時間帯）ができてしまうことも問題である。
【００２４】
〔従来技術３〕
特許文献１には、再生時間帯とコンテンツを列挙し、「再生回数の多い順」や「再生回数の少ない順」といったコンテンツ再生優先モードを指定することで、再生数を平均化し、コンテンツ間の不公平を排除するコンテンツ繰り返し再生装置が開示されている。これは、コンテンツの人気度に基づいて放映計画を自動生成するものである。
【００２５】
しかしながら、デジタルサイネージで再生されるコンテンツは、コンテンツの時間長が可変であり、１５秒や３０秒等のように固定されていないため、再生回数を平均化すると、長いコンテンツを放映する放映主又は広告主の方が長い放映時間を占めるため有利になり、放映主間又は広告主間の公平性が保てないという問題があった。また、コンテンツを機械的に繰り返し再生すると同業種のコンテンツが連続して流れる可能性があるため、放映主や広告主からクレームが生じるという不都合があった。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】特開２００５−１６５８７８号公報
【非特許文献】
【００２７】
【非特許文献１】「デジタルサイネージ標準システムガイドライン」、デジタルサイネージコンソーシアム・システム部会、1.0版、2008年11月1日
【非特許文献２】John V. Harrison、外１名、「A virtual marketplace for advertising narrowcast over digital signage networks」、Electronic Commerce Research and Applications 3、2004年、p.163-175
【非特許文献３】柳沼、外１名、「組み合わせ最適化問題に対するメタ戦略について」、電子情報通信学会 D-I,J83-D-I,1、2000年、p.3-25
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上述したように、従来技術によれば、放映申込条件や広告申込条件を詳細に指定できるようにするほど、コンテンツの放映計画の生成作業が複雑化して手間がかかるという問題があった。
【００２９】
本発明は、上記を鑑みてなされたものであり、所定の申込条件を満たしながら予め設定した基準で最適化した放映計画を生成することを課題とする。
【課題を解決するための手段】
【００３０】
請求項１に記載の放映計画生成装置は、デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、前記コンテンツを放映可能な複数の放映可能時間枠とを記憶する記憶手段と、前記記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成する生成手段と、各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように前記任意の放映計画を最適化する最適化手段と、を有し、前記効果指標は、τΣｋ＝１ｎ｛Ｎｋｄｋ＋δ（１＋Σｉ＝１Ｎｋ−１（１−ｅ−（Ｄｋｉ−ｄｋ）／δ））｝（但し、τはデジタルサイネージの近傍を通過した単位時間辺りの平均通行人数、Ｎｋはｋ番目のコンテンツの指定放映回数、ｄｋはｋ番目のコンテンツの時間長、δはデジタルサイネージの近傍で留まった通行人の単位時間辺りの平均滞留時間、ｅは指数関数の底（ネイピア数）、Ｄｋｉはｋ番目のコンテンツがｉ回目に放映されてから次に放映開始されるまでの放映間隔）の関数であることを特徴とする。
【００３１】
本発明によれば、デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、コンテンツを放映可能な複数の放映可能時間枠とを記憶手段に記憶しておき、その記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成し、各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように任意の放映計画を最適化するため、所定の申込条件を満たしながら予め設定した基準で最適化した放映計画を生成することができる。
【００３２】
請求項２に記載の放映計画生成装置は、請求項１に記載の放映計画生成装置において、前記最適化手段が、前記第１条件を満たさないコンテンツの数及び／又は前記第２条件を満たさない放映可能時間枠の数と前記効果指標との差を評価関数とし、前記任意の放映計画から始めて当該放映計画に近傍な放映計画を探索しながら、前記評価関数が最小となる放映計画を探索することを特徴とする。
【００３３】
本発明によれば、第１条件を満たさないコンテンツの数及び／又は第２条件を満たさない放映可能時間枠の数と効果指標との差を評価関数とし、任意の放映計画から始めて当該放映計画に近傍な放映計画を探索しながら、その評価関数が最小となる放映計画を探索するため、全ての制約条件を満たしていない場合であっても、最適に近い放映計画を生成することができる。
【００３４】
請求項３に記載の放映計画生成装置は、請求項２に記載の放映計画生成装置において、前記近傍な放映計画が、放映計画を構成している要素の一部を変更することにより生成されることを特徴とする。
【００３８】
請求項４に記載の放映計画生成方法は、デジタルサイネージで放映されるコンテンツの放映計画を生成する放映計画生成装置で行う放映計画生成方法において、前記放映計画生成装置は記憶手段を備え、デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、前記コンテンツを放映可能な複数の放映可能時間枠とを前記記憶手段に記憶する第１のステップと、前記記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成する第２のステップと、各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように前記任意の放映計画を最適化する第３のステップと、を有することを特徴とする。
【００３９】
本発明によれば、デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、コンテンツを放映可能な複数の放映可能時間枠とを記憶手段に記憶しておき、その記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成し、各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように任意の放映計画を最適化するため、所定の申込条件を満たしながら予め設定した基準で最適化した放映計画を生成することができる。
【００４２】
請求項５に記載の放映計画生成プログラムは、コンピュータを請求項１乃至３のいずれかに記載の放映計画生成装置として機能させることを特徴とする。
【００４３】
本発明によれば、デジタルサイネージでの放映が所期される複数のコンテンツの各時間長及び各指定放映回数と、コンテンツを放映可能な複数の放映可能時間枠とを記憶手段に記憶しておき、その記憶手段から取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画を生成し、各指定放送回数分の全てのコンテンツが放映計画に割り付けられるという第１条件と、全ての放映可能時間枠内に全てのコンテンツが収まるという第２条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように任意の放映計画を最適化するため、所定の申込条件を満たしながら予め設定した基準で最適化した放映計画を生成することができる。
【発明の効果】
【００４６】
本発明によれば、所定の申込条件を満たしながら予め設定した基準で最適化した放映計画を生成することができる。
【図面の簡単な説明】
【００４７】
【図１】放映計画生成装置の機能ブロック構成を示す図である。
【図２】放映計画生成装置の入力情報及び出力情報を示す図である。
【図３】入力情報及び出力情報の具体例を示す図である。
【図４】放映計画と放映間隔との関係を示す図である。
【図５】放映間隔と評価関数値との関係を示す図である。
【図６】放映計画生成装置の全体動作フローを示す図である。
【図７】第１の初期解の生成フローを示す図である。
【図８】第２の初期解の生成フローを示す図である。
【図９】最良解の生成フローを示す図である。
【図１０】近傍解の生成手順を模式的に示す図である。
【図１１】標準的なデジタルサイネージシステムの全体的なシステム構成を示す図である。
【図１２】標準的なデジタルサイネージシステムの基本的な運用フローを示す図である。
【図１３】基本的な運用フローでコンテンツの放映計画が策定される迄の状況を説明する図である。
【図１４】広告申込項目の一例を示す図である。
【図１５】広告申込の一例を示す図である。
【図１６】広告申込に基づいて割付られた放映時間帯を示す図である。
【発明を実施するための形態】
【００４８】
以下、本発明を実施する一実施の形態について図面を用いて説明する。但し、本発明は多くの異なる様態で実施することが可能であり、本実施の形態の記載内容に限定して解釈すべきではない。
【００４９】
〔放映計画生成装置の構成について〕
最初に、本実施の形態に係る放映計画生成装置の構成について説明する。この放映計画生成装置は、デジタルサイネージで放映されるコンテンツの放映計画を生成するものである。以下、コンテンツの代表例として広告を用いて説明する。なお、広告はあくまでも一例であり、映像及び／又は音声からなるコンテンツであればその種類は問わない。
【００５０】
図１は、一実施の形態に係る放映計画生成装置の機能ブロック構成を示す図である。この放映計画生成装置は、広告申込条件格納部１０１と、枠情報格納部１０２と、広告条件入力部１０３と、近傍探索法実行部１０４と、放映計画出力部１０５とで構成されている。
【００５１】
広告申込条件格納部１０１は、デジタルサイネージでの放映が所期される広告の申込条件を格納する機能を有し、具体的には、放映が所望される様々な広告の各時間長と、広告毎に入力として与えられる各広告の各指定放映回数と、各広告の種類（以下、ジャンルという）とを広告識別子等に関連付けて格納している。
【００５２】
枠情報格納部１０２は、そのデジタルサイネージで広告を放映可能な複数の放映可能時間枠の情報を格納する機能を有し、具体的には、日付情報を含む放映可能時間帯を格納している。
【００５３】
広告条件入力部１０３は、広告申込条件格納部１０１から取得した広告申込条件と、枠情報格納部１０２から取得した枠情報とを後段の近傍探索法実行部１０４に入力する機能を有している。
【００５４】
近傍探索法実行部１０４は、図１に示すように、初期解生成部１０４ａと、効果指標計算部１０４ｂと、放映計画更新部１０４ｃと、放映計画格納部１０４ｄとで構成されている。
【００５５】
初期解生成部１０４ａは、広告条件入力部１０３によって入力された広告申込条件及び枠情報を利用して、どの放映可能時間枠にどの順番でコンテンツを割り付けて放映するかを表した任意の放映計画（初期解）を生成する機能を有している。
【００５６】
効果指標計算部１０４ｂは、予め定義された放映計画の良さを評価する効果指標を用いて、生成された放映計画（初期解又は中間解）の効果指標値を計算する機能を有している。なお、中間解とは、後段の放映計画更新部１０４ｃによって更新された最適解に至るまでの途中段階の放映計画をいう。
【００５７】
放映計画更新部１０４ｃは、広告申込条件（制約条件）を満たしながら上記効果指標が最大となるように放映計画（初期解又は中間解）を更新する機能を有している。なお、この広告申込条件（制約条件）とは、各指定放送回数分の全ての広告が放映計画に割り付けられるという第１の制約条件と、全ての放映可能時間枠内に全ての広告が収まるという第２の制約条件と、同じジャンルの広告が隣接しないという第３の制約条件とをいう。
【００５８】
すなわち、近傍探索法実行部１０４は、効果指標計算部１０４ｂによる処理と放映計画更新部１０４ｃによる処理とを効果指標が最大になるまで繰り返し実行することにより、最適化された放映計画（近似的な最適解）を生成して放映計画格納部１０４ｄに格納する機能を有している。
【００５９】
放映計画出力部１０５は、放映計画格納部１０４ｄから放映計画を取得して、表示装置や他の装置（不図示）に出力する機能を有している。
【００６０】
〔放映計画生成装置の入力情報及び出力情報について〕
次に、放映計画生成装置に入力される入力情報と、放映計画生成装置から出力される出力情報とについて説明する。
【００６１】
まず、入力情報について説明する。入力情報は、放映申込を受け付けた広告と、広告申込条件格納部１０１に一時的に格納される広告申込条件と、枠情報格納部１０２に一時的に格納される枠情報とである。なお、放映計画生成装置は広告の放映計画を生成するものであるため、放映計画を生成する際に広告自体は不要であるが、ここでは説明の都合上入力するものとして記載している。
【００６２】
広告申込条件は、放映の申込を受け付けた広告Ａｋ（ｋ＝１，２，…，ｎ）について指定され、広告Ａｋの指定放映回数Ｎｋと、広告Ａｋの尺（時間長）ｄｋと、広告Ａｋのジャンルｇｅｎｒｅ（ｋ）との項目を有している。なお、ジャンルとは広告の種類であり、例えば、飲料や衣料を挙げることができる。
【００６３】
図２（ａ）は、ｎ種類の広告Ａ１，…，Ａｎの広告申込条件を模式的に表している。例えば、広告Ａ１は、ｄ１の尺を有し、指定された放映回数Ｎ１は４回である。ここでは、申込時に放映回数を任意に指定するようにしているが、一般的に行われているように、広告予算に比例して指定放映回数Ｎｋを設定するようにしてもよい。また、尺ｄｋは、単位時間（例えば、１５秒）の倍数で指定される。
【００６４】
枠情報は、広告を放映可能な放映可能時間枠Ｚｉ（ｉ＝１，２，…，Ｎｚ）である。デジタルサイネージのディスプレイは複数の用途で共有されることが一般的であるため、広告以外のコンテンツ（例えば、施設案内やニュース等）を放映している時間帯を除いた空き時間に広告を割り当てる必要がある。放映可能時間枠Ｚｉは、放映開始時刻ｂｉ、枠の時間長ｓｉを属性として持つ時間帯であり、図２（ｂ）に示すように、異なる放映可能時間枠間で隙間があっても良いが互いに重複しないように指定される。
【００６５】
続いて、出力情報について説明する。出力情報は、近傍探索法実行部１０４によって最適化された放映計画である。この放映計画は、図２（ｃ）に示すように、放映可能時間枠Ｚｉの時間帯に放映される広告の番号リストｑｉ＝ｑｉｊ（ｑｉｊ∈［１，２，…，ｎ］，ｊ＝１，２，…，Ｎｉ）として表現される。
【００６６】
例えば、図３（ａ）に示すように、広告Ａ１，Ａ２，Ａ３と、広告申込条件として指定放映回数Ｎ１＝４，Ｎ２＝２，Ｎ３＝１とが与えられた場合、実行可能な放映計画は複数存在するものの、例えば、図３（ｂ）に示す放映計画１や、図３（ｃ）に示す放映計画２が生成される。放映計画１は、ｑ１＝（１，２，１）；ｑ２＝（１，２）；ｑ３＝（３，１）と表される。
【００６７】
なお、全ての広告Ａｋが隙間なく放映可能時間枠Ｚｉに収まる場合には、ΣＮｋｄｋ＝Σｓｉが成立する。但し、この等式を満たしても、放映可能時間枠Ｚｉに収まるような放映計画が存在するとは限らない。
【００６８】
〔放映計画の最適化について〕
放映計画の最適化とは、入力情報である広告申込条件及び枠情報を用いて生成された任意の放映計画を、広告申込条件（制約条件）を満たしながら効果指標が最大となるように最適化することである。すなわち、広告申込条件（制約条件）を満たす放映計画の組み合わせのうち、予め指定した効果指標を近似的に最大化する問題を解くことにより、最適化された放映計画を生成する。ここでは、最適化時に利用される効果指標について説明する。
【００６９】
広告Ａｋ（ｋ＝１，２，…，ｎ）と、広告Ａｋの指定放映回数Ｎｋと、広告Ａｋの尺ｄｋと、広告Ａｋのジャンルｇｅｎｒｅ（ｋ）と、時間長ｓｉの放映可能時間枠Ｚｉ（ｉ＝１，２，…，Ｎｚ）とを入力情報とし、放映計画ｑｉ（ｉ＝１，２，…，Ｎｚ）を出力情報として、式（１）に示す効果指標Ｒ（ｑｉ）の目的関数を利用する。
【００７０】
【数１】
0005417270.tif 000002
ここで、τはデジタルサイネージの近傍を通過した単位時間辺りの平均通行人数、δはデジタルサイネージの近傍で留まった通行人の単位時間辺りの平均滞留時間、ｅは指数関数の底（ネイピア数）、Ｄｋｉはｋ番目の広告がｉ回目に放映されてから次に放映開始されるまでの放映間隔である。なお、放映間隔Ｄｋｉは、図４に示すように、放映計画ｑｉと尺ｄｋとから算出される。
【００７１】
また、最適化される放映計画は、以下の制約条件を全て満たすものとする。第１の制約条件は、各指定放送回数分の全ての広告Ａｋが放映計画ｑｉに割り付けられることである。すなわち、式（２）が満たされる必要がある。
【００７２】
【数２】
0005417270.tif 000003
ここで、１（・）は、括弧内の等式が成立する時に１を返す関数である。
【００７３】
第２の制約条件は、全ての放映可能時間枠Ｚｉに全ての広告Ａｋが収まること、換言すれば、放映可能時間枠Ｚｉに割り付けられた広告の尺ｄｋの合計が放映可能時間枠Ｚｉの時間長より小さいことである。すなわち、広告の途中で放映が切れないことを保証しており、式（３）が満たされる必要がある。
【００７４】
【数３】
0005417270.tif 000004
ここで、ｄ（ｑｉｊ）は、放映可能時間枠Ｚｉのｊ番目の広告の尺を表している。
【００７５】
第３の制約条件は、同じジャンルの広告が隣り合わない、換言すれば、競合するジャンルが連続しないことである。すなわち、同業種の広告が並ぶことを禁止する条件であり、式（４）が満たされる必要がある。
【００７６】
【数４】
0005417270.tif 000005
ここで、ｇｅｎｒｅ（ｑｉｊ）は、放映可能時間枠Ｚｉのｊ番目の広告の業種や商品等のジャンルを表している。
【００７７】
本実施の形態で利用している式（１）の効果指標Ｒ（ｑｉ）は、広告視聴数と呼ばれ、広告を見た人の期待値を広告毎に計算し、全ての広告について合計したのべ人数の期待値である。同じ人が同じ広告を２回以上見ても１人としかカウントされないが、同じ人が別の広告を見た場合には見た広告の数がカウントされる。
【００７８】
広告視聴数の定性的な説明は以下のとおりである。式（１）の第１項は、広告Ａｋの総露出時間Ｎｋｄｋであり、広告Ａｋの尺ｄｋと指定放映回数Ｎｋとが大きくなればなるほど露出時間Ｎｋｄｋが長くなり、多くの人が広告Ａｋに接触することを表している。
【００７９】
一方、式（１）の第２項は、広告Ａｋの放映間隔Ｄｋｉの効果を表しており、広告Ａｋの放映間隔Ｄｋｉが短くなると、１人の人が２回以上、同じ広告に接触する確率が増えるため、広告視聴数は減少する。
【００８０】
従って、利用される効果指標は、放映間隔Ｄｋｉが大きくなるに従って効果指標値が増加する関数であれば、どのような関数を用いてもよい。
【００８１】
また、広告視聴数を最大化するには、露出時間Ｎｋｄｋを確保しつつ、放映間隔Ｄｋｉを均等に大きくするようにすれば良い。τは単位時間辺りの平均通行人数であるため、τの値が変化しても解として得られ放映計画に影響はない。一方、δは平均滞留時間であるため、滞留時間が長くなればなるほど複数の広告を目にする人が増えるので、広告視聴数が大きくなる。
【００８２】
ここでは、効果指標の第２項を指数関数として定義しているが、変数である放映間隔Ｄｋｉについて単調増加、かつ、下に凸の関数（例えば、ｔａｎｈ）を使用するようにしてもよい。そうすれば、放映間隔Ｄｋｉが均等に大きくなるような放映計画が生成される。
【００８３】
なお、第１の制約条件〜第３の制約条件の全てを満たす放映計画（解）ｑｉは、実行可能解（ｆｅａｓｉｂｌｅ  ｓｏｌｕｔｉｏｎ）と呼ばれる。第１の制約条件及び第２の制約条件によって広告Ａｋの全てが放映可能時間枠Ｚｉに割り付けられるため、第３の制約条件を満たすか否かは選択的である。
【００８４】
〔放映計画の探索法について〕
次に、放映計画更新部１０４ｃにおいて放映計画の更新時に実行される放映計画の探索法について説明する。上述したように、最適化された放映計画を生成するということは、広告申込条件（制約条件）を満たす放映計画の組み合わせの最適化問題に対する近似解を求めることであり、本実施の形態では、多スタート局所探索法（ｍｕｌｔｉ  ｍｕｌｔｉ−ｓｔａｒｔ  ｌｏｃａｌ  ｓｅａｒｃｈ；ＭＬＳ法）と呼ばれる手法を用いる。
【００８５】
局所探索法（ｌｏｃａｌ  ｓｅａｒｃｈ；ＬＳ法）は、適当な初期解（開始点）から出発し、その近傍の点を順に探索すること、つまり、目的関数を用いて近傍点を評価し、その評価値が今までの評価値よりも大きくなれば解を更新する手続きを繰り返すことによって、局所最適解を見つける方法である。
【００８６】
多スタート局所探索法（ＭＬＳ法）は、初期解をランダムに生成しながら繰り返し局所探索法を実行し、結果として得られる局所最適解のうち最良なものを記憶しておく方法である。
【００８７】
なお、多スタート局所探索法については、非特許文献３に開示されている。
【００８８】
〔放映計画生成装置の動作フローについて〕
次に、放映計画生成装置の動作フローについて説明する。なお、以下説明する動作フローでは、上述した効果指標Ｒ（ｑｉ）を最大化する代わりに、各制約条件の違反回数をペナルティとして加えた式（５）の評価関数ｆ（ｑｉ）を利用して、その評価関数を最小化するようにしている。
【００８９】
【数５】
0005417270.tif 000006
この評価関数ｆ（ｑｉ）は、第１の制約条件〜第３の制約条件に違反する違反回数と効果指標Ｒ（ｑｉ）との差からなる関数である。λは、ペナルティの重みパラメータである。違反回数とは、各制約条件を満たさなかった際にカウントされる数であり、第１の制約条件の場合には、放映計画に割り付けられなかった広告の数であり、第２の制約条件の場合には、コンテンツを収められなかった放映可能時間枠の数であり、第３の制約条件の場合には、隣り合った広告の数である。
【００９０】
評価関数ｆ（ｑｉ）は、図５に示すように、放映間隔Ｄｋｉに対して単調減少である。広告申込条件（制約条件）が厳しい場合には、全ての制約条件を満たす実行可能解が存在しない場合もあるが、ペナルティ項を加えた評価関数ｆ（ｑｉ）を採用することで、全ての制約条件を満たしていない場合であっても、最適解に近い放映計画を生成することが可能となる。
【００９１】
続いて、放映計画生成装置の動作フローについて説明する。図６は、放映計画生成装置の全体動作フローを示す図である。
【００９２】
最初に、近傍探索法実行部１０４により、現時点での最良の放映計画（以下、最良解という）ｑｍｉｎが空（φ）で初期化され、最良解の評価値ｆｍｉｎが∞で初期化される（Ｓ１０１）。
【００９３】
次いで、初期解生成部１０４ａにより、広告申込条件及び枠情報を利用して任意の放映計画（以下、初期解という）ｑｉが生成される（Ｓ１０２）。初期解ｑｉの生成法については後述する。
【００９４】
次いで、効果指標計画部１０４ｂ及び放映計画更新部１０４ｃにより、多スタート局所探索法に基づく近傍探索法を実行することによって、初期解ｑｉから始めて該初期解に近傍な中間解を探索しながら、評価関数ｆを近似的に最小化する改善解ｑｉ’と、その改善解ｑｉ’の評価値ｆ（ｑｉ’）とが求められる（Ｓ１０３）。なお、改善解ｑｉ’と該改善解ｑｉ’の評価値ｆ（ｑｉ’）とは、第１の制約条件〜第３の制約条件を満たしながら求められる。評価値ｆ（ｑｉ’）の計算には各制約条件の違反回数が必要であるが、この違反回数は、放映計画更新部１０４ｃにおいて近傍な中間解を探索する際に適宜カウントされる。近傍探索法については後述する。
【００９５】
次いで、放映計画更新部１０４ｃにより、Ｓ１０３で求めた改善解ｑｉ’の評価値ｆ（ｑｉ’）が、今までの最良解の評価値ｆｍｉｎより小さいか否かが判定される（Ｓ１０４）。
【００９６】
次いで、Ｓ１０４での判定の結果、ｆ（ｑｉ’）＜ｆｍｉｎの場合には、より最良な解が得られたため、最良解ｑｍｉｎと最良解の評価値ｆｍｉｎとがそれぞれ改善解ｑｉ’と該改善解ｑｉ’の評価値ｆ（ｑｉ’）とに置き換えられる（Ｓ１０５）。一方、Ｓ１０４での判定の結果、ｆ（ｑｉ’）＜ｆｍｉｎ以外の場合には、今までの解の方が最良であるため、Ｓ１０５は実行しないで後段のＳ１０６に進む。
【００９７】
次いで、放映計画更新部１０４ｃにより、所定の終了条件を満たしているかが判定される（Ｓ１０６）。終了条件を満たしていない場合には、Ｓ１０２に戻ってＳ１０５までの処理を繰り返し、終了条件を満たしている場合には、この動作フローを終了する。なお、終了条件としては、例えば、Ｓ１０２→Ｓ１０３→Ｓ１０４→（Ｓ１０５）→Ｓ１０２のループの繰り返し回数が、予め定められた数を超えることが一例として挙げられる。
【００９８】
〔初期解の生成法について〕
ここでは、上述した動作フローのＳ１０２における初期解の生成法について２つ説明する。
【００９９】
最初に、ビンパッキング法の基本的なヒューリスティックスであるＦＦＤ（Ｆｉｒｓｔ  Ｆｉｔ  Ｄｅｃｒｅａｓｉｎｇ）法を変形した第１の初期解生成法について説明する。この生成法は、尺が大きい広告が最後まで残ると放映可能時間枠に収まらずに第２の制約条件に違反する可能性が高いため、尺の大きい順に広告を放映可能時間枠に割り付けていく方法である。
【０１００】
図７は、第１の初期解の生成フローを示す図である。最初に、放映計画（解）ｑｉ（ｉ＝１，２，…，Ｎｚ）が空（φ）で初期化される（Ｓ１００１）。
【０１０１】
次いで、広告Ａｋが尺ｄｋの大きい順にソートされる（Ｓ１００２）。つまり、全てのｋ＝１，２，…，ｎ−１についてｄｋ≧ｄｋ＋１を成立させる。
【０１０２】
次いで、全ての広告Ａｋ（ｋ＝１，２，…，ｎ）について、以下のＳ１００４〜Ｓ１００７の処理が繰り返される（Ｓ１００３）。
【０１０３】
次いで、以下のＳ１００５〜Ｓ１００７の処理が指定放映回数Ｎｋだけ繰り返される（Ｓ１００４）。
【０１０４】
次いで、放映可能時間枠Ｚｉ（ｉ＝１，２，…，Ｎｚ）が順に走査され（Ｓ１００５）、最初に収まる放映可能時間枠Ｚｉに広告Ａｋが挿入（ｑｉ＝ｑｉ＋｛ｋ｝）される（Ｓ１００６、Ｓ１００７）。
【０１０５】
以上説明した第１の初期解生成法では、Ｚ１，Ｚ２，…，ＺＮｚの順に放映可能時間枠を走査するようにしているが、初期解にランダム性を持たせるために放映可能時間枠の走査開始位置を乱数により決定することもできる。すなわち、放映可能時間枠の走査開始位置ｉ０を１以上Ｎｚ以下の整数をとる乱数とし、ｉ＝ｉ０，ｉ０＋１，…の順に放映可能時間枠を検査し、ｉがＮまで到達したら先頭ｉ＝１に戻って走査を行う。
【０１０６】
次に、オペレーティングシステムのプロセス管理に用いられるｒｏｕｎｄ  ｒｏｂｉｎ法を変形した第２の初期解生成法について説明する。この生成法は、ｒｏｕｎｄ  ｒｏｂｉｎ法に着想を得たヒューリスティックスであり、広告の放映間隔がなるべく均等になるように未割付の広告を順に放映可能時間枠に割り付けていく方法である。
【０１０７】
図８は、第２の初期解の生成フローを示す図である。最初に、放映計画（解）ｑｉ（ｉ＝１，２，…，Ｎｚ）が空（φ）で初期化され、広告Ａｋの未割付広告数ｒｋがＮｋで初期化される（Ｓ１１０１）。
【０１０８】
次いで、ｋ＝１，２，…，ｎに対して、未割付広告数の割合ｒｋ／Ｎｋが最大になるｋが求められる（Ｓ１１０２）。
【０１０９】
次いで、放映可能時間枠Ｚｉ（ｉ＝１，２，…，Ｎｚ）が順に走査され（Ｓ１１０３）、最初に収まる放映可能時間枠Ｚｉに広告Ａｋが挿入（ｑｉ＝ｑｉ＋｛ｋ｝）される（Ｓ１１０４、Ｓ１１０５）。
【０１１０】
次いで、未割付広告数ｒｋが１だけ減らされ（Ｓ１１０６）、全ての広告の割り付けが終わっていれば、すなわちｒｋが０（零）であれば、処理を終了する（Ｓ１１０７）。
【０１１１】
以上２つは初期解生成の一例であり、これ以外の生成法を利用することも可能である。但し、全くランダムに初期解を生成すると解の収束に時間がかかるため、最適解に近い初期解から出発することが望ましい。また、第１の制約条件〜第３の制約条件を満たすような初期解を生成するようにしてもよい。
【０１１２】
〔最良解（最適解）の生成法について〕
ここでは、近傍探索法に基づく上述した動作フローのＳ１０３〜Ｓ１０６における最良解の生成法について説明する。
【０１１３】
図９は、最良解の生成フローを示す図である。最初に、初期解生成部１０４ａにより生成された放映計画（初期解）ｑｉ（ｉ＝１，２，…，Ｎｚ）が入力され、その初期解ｑｉを用いて最良解の評価値ｆｍｉｎがｆ（ｑｉ）で初期化される（Ｓ１２０１）。
【０１１４】
次いで、初期解（又は中間解）ｑｉの近傍解（上述した改善解に相当し、概念上は近傍する点である）ｑｉ’が生成される（Ｓ１２０２）。ここで、近傍解の生成手順を以下説明する。図１０は、近傍解の生成手順を模式的に示す図である。
【０１１５】
最初に、初期解（又は中間解）ｑｉを連結した広告番号リストＱ←ｑ１＋ｑ２＋…＋ｑＮｚが生成される（Ｓ１２０２ａ）。
【０１１６】
次に、初期解（又は中間解）ｑｉが第１の制約条件を満たさない実行不可能解であり、未割付広告が存在する場合には、未割付広告の広告番号がＱの末尾に追加される（Ｓ１２０２ｂ）。
【０１１７】
次に、広告番号リストＱから２つの要素Ｑｌ，Ｑｍがランダムに選択され、それらが交換されて、新たな広告番号リストＱ’が生成される（Ｓ１２０２ｃ）。
【０１１８】
次に、新たな広告番号リストＱ’の先頭から順に要素Ｑｊが取り出され、放映可能時間枠Ｚｉ（ｉ＝１，２，…，Ｎｚ）に収まるのであれば詰められ（ｑｉ’←ｑｉ’＋｛Ｑｊ｝）、Ｚｉがいっぱいになったら次の枠に詰めることを繰り返す（Ｓ１２０２ｄ）。
【０１１９】
Ｓ１２０２ａ〜Ｓ１２０２ｄの処理により近傍解ｑｉ’が生成される。探索の収束を早めるために、Ｓ１２０２ｃで第１の制約条件〜第３の制約条件を満たさない要素を優先的に選択することも有効である。
【０１２０】
次いで、評価関数ｆ（ｑｉ）を用いて、生成された近傍解ｑｉ’の評価値ｆ（ｑｉ’）が求められる（Ｓ１２０３）。
【０１２１】
次いで、求められた近傍解ｑｉ’の評価値ｆ（ｑｉ’）が、今までの最良解の評価値ｆｍｉｎより小さいか否かが判定される（Ｓ１２０４）。
【０１２２】
次いで、Ｓ１２０４での判定の結果、ｆ（ｑｉ’）＜ｆｍｉｎの場合には、より最良な解が得られたため、最良解の評価値ｆｍｉｎが評価値ｆ（ｑｉ’）で更新され、Ｓ１２０２の初期解（又は中間解）ｑｉが改善解ｑｉ’で置き換えられて（Ｓ１２０５）、Ｓ１２０２戻り、更に中間解ｑｉの近傍により良い解が無いかが探索される。
【０１２３】
一方、Ｓ１２０４での判定の結果、ｆ（ｑｉ’）＜ｆｍｉｎ以外の場合には、今までの解の方が最良であるため、Ｓ１２０５は実行せずに、初期解（又は中間解）ｑｉの近傍を全て探索したかが検査され（Ｓ１２０６）、全ての近傍探索が終了又は既定回数の近傍の点の探索が終了した場合に、処理が終了する。
【０１２４】
本実施の形態では、組み合わせ最適化の近似解法として、多スタート局所探索法を用いたが、アニーリング法や反復局所探索法等を用いることも可能である。また、計算時間がかかるという問題はあるものの、近似解法ではなく、分枝限定法等の厳密解法を用いることも可能である。
【０１２５】
本実施の形態では、広告申込条件に対応して第１の制約条件〜第３の制約条件を設定したが、様々な他の制約条件を設定することも可能である。例えば、静止画のように尺が決まっていないコンテンツを扱うように拡張することも可能である。その他、広告の尺の最小値、最大値がそれぞれｄ（ｑｉｊ）（ｄの下に「−」）、ｄ（ｑｉｊ）（ｄの上に「−」）で与えられる場合には、式（３）で表現された第２の制約条件を式（６）に変形することも可能である。
【数６】
0005417270.tif 000007
【０１２６】
また、フィラー（埋め草）コンテンツを予め用意しておき、第２の制約条件が等号で満たされない場合、すなわち隙間ができた場合に、フィラーコンテンツを挿入するように変形することも可能である。
【０１２７】
本実施の形態によれば、デジタルサイネージでの放映が所期される複数の広告の各時間長及び各指定放映回数と、広告を放映可能な複数の放映可能時間枠とをそれぞれ広告申込条件格納部１０１と枠情報格納部１０２とに記憶しておき、近傍探索法実行部１６０４が、それら格納部からそれぞれ取得したコンテンツの時間長及び指定放映回数と放映可能時間枠とを利用して、どの放映可能時間枠にどの順番で広告を割り付けて放映するかを表した任意の放映計画を生成し、各指定放送回数分の全ての広告が放映計画に割り付けられるという第１の制約条件と、全ての放映可能時間枠内に全ての広告が収まるという第２の制約条件と、同じジャンルの広告が隣り合わないという第３の制約条件とを満たしながら、予め定義された放映計画の良さを評価する効果指標が最大となるように任意の放映計画を最適化するので、広告主が広告申込条件を細かく指定でき、その申込条件（制約条件）を満たしながら、予め設定した基準で最適化した放映計画を自動的に生成することができる。
【０１２８】
本実施の形態によれば、第１の制約条件を満たさないコンテンツの数、第２の制約条件を満たさない放映可能時間枠の数、第３の制約条件を満たさない広告の数と効果指標との差を評価関数とし、任意の放映計画から始めて当該放映計画に近傍な放映計画を探索しながら、その評価関数が最小となる放映計画を探索するので、全ての制約条件を満たしていない場合であっても、最適に近い放映計画を生成することができる。
【０１２９】
最後に、本実施の形態で説明した放映計画生成装置は、コンピュータで構成される。すなわち、広告申込条件格納部１０１と、枠情報格納部１０２とは、メモリ等の記憶手段で実現される。また、広告条件入力部１０３と、近傍探索法実行部１０４と、放映計画出力部１０５とは、ＣＰＵ等の演算手段で実現され、プログラムで実行される。
【０１３０】
また、本実施の形態で説明した放映計画生成装置をプログラムとして光記憶装置や磁気記憶装置等の記録媒体に読出可能に記録し、この記録媒体をコンピュータに組み込んだり、若しくは記録媒体に記録されたプログラムを、任意の通信回線を介してコンピュータにダウンロードしたり、又は記録媒体からインストールし、該プログラムでコンピュータを動作させることにより、上述した各処理動作を放映計画生成装置として機能させることができるのは勿論である。
【符号の説明】
【０１３１】
１０１…広告申込条件格納部（記憶手段）
１０２…枠情報格納部（記憶手段）
１０３…広告条件入力部
１０４…近傍探索法実行部（生成手段・最適化手段）
１０４ａ…初期解生成部（生成手段）
１０４ｂ…効果指標計算部（最適化手段）
１０４ｃ…放映計画更新部（最適化手段）
１０４ｄ…放映計画格納部（最適化手段）
１０５…放映計画出力部
２０１…配信サーバ
２０２…プレーヤ
２０３…ディスプレイ
２０４…操作端末
Ｓ…ステップ
【図１】
0005417270.tif 000008
【図２】
0005417270.tif 000009
【図３】
0005417270.tif 000010
【図４】
0005417270.tif 000011
【図５】
0005417270.tif 000012
【図６】
0005417270.tif 000013
【図７】
0005417270.tif 000014
【図８】
0005417270.tif 000015
【図９】
0005417270.tif 000016
【図１０】
0005417270.tif 000017
【図１１】
0005417270.tif 000018
【図１２】
0005417270.tif 000019
【図１３】
0005417270.tif 000020
【図１４】
0005417270.tif 000021
【図１５】
0005417270.tif 000022
【図１６】
0005417270.tif 000023