权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

针对大规模复杂组合优化问题的高效通用元策略的开发和应用

基本信息

批准号：
14750333
负责人：
柳浦睦憲
金额：
$ 2.18万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

项目摘要

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

In recent years, the development of mobile phones, the popularity of mobile phones, the evolution of computer performance, the rapid progress of technological innovation, the latest development of a large number of high-speed start processing The need for technological innovation and the availability of technical resources is high. The purpose of this is to solve important problems, design problems, information engineering problems, and optimization problems. The technological innovation mentioned above is accompanied by important problems in application, such as large-scale and complex transformation. NP-difficulty represents optimization problem, problem size, optimal solution, cognitive difficulty, etc. The problem is solved by means of a simple solution. This study aims to provide guidance on how to solve the problem of enterprise development and how to contribute to the development of enterprise development strategies. The purpose of this study is to achieve high versatility, maintain high performance, and improve the utilization of structural problems. This year, we will make progress in the research on the main problem, the problem of time distribution, the problem of polygon distribution, the problem of multi-resource generalization, and the problem of time distribution. In this case, the distribution plan problem is related to the movement time, the movement time is dependent on the departure time, and the high speed polynomial time is successfully developed. This is a high availability, high customer count, 1000 large scale problem with high availability, low performance, and high success.