大規模かつ複雑な組合せ最適化問題に対する効率的かつ汎用的メタ戦略の開発と応用

点击翻译按钮获取中文摘要

近年、インターネットの整備、携帯電話の普及、計算機性能の進化など、技術革新が急速に進み、最新かつ大量のデータを高速に入手・処理できるようになった。このような技術革新に伴って、これらの技術資源やそこから得られる情報を有効に利用する必要性が高まってきた。この目的において重要な問題として、スケジューリング問題やネットワーク設計問題などのシステム工学的・情報工学的問題が挙げられるが、その多くは組合せ最適化問題として定式化できる。上述の技術革新に伴い、応用上重要な問題はますます大規模化・複雑化してきている。しかし、NP困難性に代表されるように、多くの組合せ最適化問題に対し、問題の規模が大きい場合、厳密な最適解を求めることがきわめて困難であることが認知されている。このような問題に対する現実的手法としてメタ戦略が有効であることが知られている。本研究では、現実の応用問題に幅広く対応できるような汎用ソルバをメタ戦略に基づいて開発し、企業などのシステムにおける問題解決エンジンとしての貢献を目指している。本研究の目的を達成するためには、高い汎用性を持ちつつアルゴリズムの性能向上に利用できる構造を有する問題の選択が重要となる。本年度は、主に、時間ペナルティ関数つき配送計画問題、多角形パッキング問題、多資源一般化割当問題、カッティングストック問題に対する研究を進めた。とくに、配送計画問題に対しては、移動時間に変更を許す場合や、移動時間が出発時刻に依存する場合など、より汎用性の高い定式化のに対しても現実的に高速な多項式時間アルゴリズムの開発に成功した。このように汎用性を高めたにもかかわらず、これを組み込んだソルバの性能はきわめて高く、客数1000までの大規模なベンチマーク問題例において、専用アルゴリズムに劣らない性能を示すという大きな成功をおさめた。