トピックス
組合せ最適化ってどんな研究をするんだろう??? と思っている人のために
分かりやすくてちょっとおもしろい話題を集めてみました.
研究成果の紹介ビデオ
私たちの研究グループ(最適化アルゴリズムグループ)の研究成果を分かりやすく紹介したビデオです.
(ファイルサイズが大きいですがご容赦願います.)
- 長方形パッキング問題
複数の長方形を目的に応じて効率よく配置する問題です.
鉄鋼や繊維産業などに幅広い応用を持ちます.
MPEGファイル(約37MB)(出演: 茨木先生)
- 時間枠つき配送計画問題
複数の客に複数の車両で荷物を配達するとき,
客の時間枠を考慮しつつ配送ルートの効率化を目指す問題です.
宅配やコンビニエンスストアへの商品配達など,
身近でしかも重要な応用がたくさんあります.
MPEGファイル(約43MB)(出演: 柳浦)
最長しりとり
- 国語辞典の単語を用いてもっとも長いしりとりを作ると何語続けることができるかという問題です.
- テレビ番組「トリビアの泉」のトリビアの種のコーナーで取り上げられました(2004年
3月上旬放映済).
関連記事
- トリビアというだけあって, どうでもいいといえばどうでもいいことなのですが,
何だか気になる問題です. 簡単そうに見えますが, いい加減な方法では解けません.
これを数理計画の手法を駆使してまじめに解いた人たちがいます.
- 解き方の詳細等については以下の記事をご参照下さい.
- 乾伸雄, 品野勇治, 鴻池祐輔, 小谷善行,
最長しりとり問題の解法,
情報処理学会論文誌「数理モデル化と応用」,
Vol.46, No.SIG2, 2005年1月, pp.105-117.
- 品野勇治,乾伸雄,
最長しりとり問題とその解法,
オペレーションズ・リサーチ,Vol.50, No.3, 2005年3月,pp.175-180.
最長片道切符
- JRの片道切符一枚でできるだけ長い距離を旅行するにはどのようなルートの片道切符を買えばよいのでしょうか?
- 鉄道ファンにとっては夢の旅なのだそうです. こちらも簡単そうに見えて難しい問題です.
この問題を数理計画の手法を駆使して解き, しかもそのルートに沿って旅行した人がいます.
- 最長片道切符の経路と求める方法
- 詳細は以下の論文を参照下さい.
- 宮代隆平, 葛西隆也, 最長片道切符,
オペレーションズ・リサーチ, Vol. 49, No. 1, pp. 15-20, 2004.
- 関連する話題として,
NHKの番組
「列島縦断鉄道12000キロの旅〜最長片道切符でゆく42日〜」
がありました.
最長しりとりと最長片道切符の二つの話題は以下の解説でも紹介しています.
- 柳浦, ``簡単そうで難しい組合せ最適化 --- 身近な話題から,''
数理工学のすすめ(改訂版),現代数学社, 2005年1月, pp. 9-13.
なお, この解説では組合せ最適化に関するそのほかの話題もいろいろ取り上げて
いますので, 興味のある方は是非ご覧下さい.
柳浦のホームページ