生産システムや交通・輸送システムはもちろんのこと，電車やパス，航空機の運行スケジュール，宅配便や郵便物の配送スケジュールなど，何気ない社会のいろいろな場面で，最適化(Optimization)の技術は実に広く用いられています．最適化と一言でいってもその分野は非常に広く，対象とする問題の性質や規模，複雑性などによって様々な研究がなされています．

自律系工学研究室では，従来から解法の統一的評価のために用いられる共通の問題（ベンチマーク問題）を用いて新しい解法の提案を行ったり，実際に社会で解決すべき問題に応用したりする研究を行なっています．

　
メタヒューリスティクスを用いた巡回セールマン問題の解法

複数のノード集合（都市とも呼ばれる）とノード間のコスト（距離）が与えられているとき，あるノードから出発して，すべてのノードを経由してスタートノードに戻ってくる経路の中で，コストの合計が最小になる経路を求めなさい，という問題は，すべての顧客を廻るセールマンに例えて，巡回セールスマン問題(TSP)と呼ばれています．一見，単純な問題のようですが，候補となる経路の総数は10ノードの場合でも18万通りを超えるだけ存在します．

ノードの総数が増えるにつれて，この候補となる経路の総数は爆発的（指数関数的）に増えていきます．このような問題は，いくらスーパーコンピュータなどの高速な計算機を用いてもその問題を解くための効率的な方法を用いないと現実的な時間で解くことは困難となります．下の動画は，TSPのベンチマーク問題の一つであるtsp225という225ノードの問題を私達が提案した粒子群最適化法(PSO)とベースとした手法で解いているときの様子を示しています．

総コストが最小となる最短経路が求まると，「TSP」という文字が浮き出るような設定になっているものです．完全な「TSP」ではないにも関わらず，ほぼ「TSP」と読める経路が求まっていることがわかります．

また，以下の動画は，5943ノードとうい非常に多くのノードからなる問題に局所クラスタリング組織化法(LCO)と呼ばれる手法の改良版を適用した結果です．

メタヒューリスティクスを用いたジョブショップスケジューリング問題(JSP)の解法

最適化の対象となる問題は，TSPだけではありません．まだまだ多数いろいろな問題が存在します．ここでは，ジョブショップスケジューリング問題(JSP)と呼ばれる問題を紹介しましょう．ある製品などをつくる製造工程において，ある製品は，複数のジョブをその順番で処理しなければならないとします．また，それぞれのジョブは，決められたマシン（機械）で処理する必要があります．複数種類の製品を製造する場合，マシンは同時に使用できないため，あるマシンが占有されている場合は，そのマシンで処理するジョブが待ちの状態となります．

このような状況の際に，すべての製品の製造終了時間を最小化するジョブを各マシンでどの順番で処理するかを決める問題をジョブショップスケジューリング問題(JSP)と呼びます．以下の動画は，JSPを解いている過程でスケジュールが変わっていく様子を示したものです．

動画の中のカラフルな帯１行があるマシンを表しており，色の同じものがある製品をつくるために必要なジョブを表しています．各マシンで処理するジョブの順番を入れ替えることによって，総作業時間（各帯の横の長さの最大値）を最小化しようとしています．自律系工学研究室では，このJSPに対して高速で有効な解法の提案を行なっています．

　
大規模倉庫におけるピッキング作業最適化

自律系工学研究室では，TSPやJSPの他にも様々な問題に取り組んでいます．それらは基本的なベンチマーク問題であることもありますが，実際の社会に現れる状況の最適化へ応用することも行なっています．具体的には，大手の販売業者の大規模倉庫における商品のピッキング作業の最適化を行なってきました．顧客からの発注伝票に応じて，作業者が倉庫から製品を集めて荷詰めし，発送の準備を行います．こういうった作業において，（１）倉庫内の製品配置，（２）類似した発注伝票をまとめる，（３）製品を集める（ピッキングする）順番，などを作業者の総作業時間が最小となるように決める問題を扱います．大規模であればあるほど，最適化によって大幅なコストダウンが期待でき，企業の収益につながるため非常に重要な研究です．