お客様の研究とOR部による解決
1日以内に通信データの割り当てスケジュールを立てたい → 数秒で解を算出するシステムを構築
衛星通信ネットワークにおいて、広範囲に何万局も存在する通信局が持つ大量のデータを、 限られた周波数帯域、限られた時間で効率良く通信できるようにスケジューリングするのは非常に困難な問題です。数万局から送信される膨大でかつ情報量の異なるデータを24時間の範囲で 複数周波数帯に割り当てる組み合わせは天文学的な数になります。 そのため、その中から最適な組み合わせを求めることは現実的には不可能です。
私達は、厳密な最適解を得るアルゴリズムの代わりに、現実的な時間で実行可能で 極力最適解に近い近似解を得ることのできるヒューリスティックな解法を独自に開発しました。 これにより、いままで利用されていた最適化アルゴリズムでは成し得なかった、算出までにわずか数秒～数十秒と 遙かに高いパフォーマンスを示すアルゴリズムを開発することができました。
使用周波数帯域をなるべく抑えたい → 現行システムよりも利用周波数帯域を削減
衛星通信を用いて、数万の局からそれぞれ情報速度、周期、情報量の違うデータが日々送信されます。 これを横軸が時間、縦軸が周波数という枠の中に形の異なる通信データを隙間なく詰め込むことで 周波数資源を最小化することができます。通信以外の世界でもこういった詰め込み問題は オペレーションズ・リサーチで解決できる典型的な問題の一つですが、 限られた周波数帯域の中で、いかに使用周波数帯域を抑えることが出来るかも課題でした。 私たちは、効率的な割り当て方法を検討し、精度の高い最適化アルゴリズムを独自に開発したことで、 利用されていた最適化アルゴリズムよりも使用周波数帯域を削減することに成功しました。
解決までの手順
新ロジックの検討とシステムの構築
スケジューリングエンジンを開発するにあたり、最大の課題は計算速度の問題でした。 それは、1日当たりテラバイトにも上る大量の通信データを短時間でスケジューリングする 必要があったためです。様々な手法を検討した結果、多スタートグリーディー法を採用し、使用する周波数帯域を 出来るだけ少なく抑えるロジックを取り込むことで、僅かな時間で最適な割り当てスケジュールが行えるようになりました。
シミュレーションによる評価検証
開発したシステムが行っている通信データ割り当て結果の有効性を検証するため、 シミュレーションによる評価検証を行いました。衛星通信ネットワークのシミュレーションモデルを作成し、様々な通信発生パターンを生成後、 開発したシステムで得られた通信スケジュールで滞りなく有効に通信が行えることを検証しました。
通信のオペレーションズ・リサーチに関するお問い合わせ
本事例の利用周波数スケジューリングに関するお問い合わせは、下記フォームにご入力ください。