情報処理学会 第74回全国大会講演要旨

道路上に広告・宣伝などの看板を配置する際，少ないコストでより
多くの通行人や車両の目に留まるように，効果的な配置場所を求め
ることが問題になる．本研究では交差点をノード，交差点間の道路
をリンクとしたネットワークを対象に看板配置問題を考える．そし
て，任意の交差点（出発地）から他の交差点（目的地）へ最短パス
で行く際の看板閲覧確率を目的関数とし，目的関数を最適化するこ
とで，複数の最適な看板配置場所を求める．配置する看板数が1つ
の場合，ネットワーク分析手法である媒介中心性と等価であるが，
複数看板の最適配置問題は多大な計算コストがかかり，効率的な解
法が求められる．本研究では，ネットワーク上での看板配置問題の
効率的解法を提案する．