解けないパズルとは？
社会課題の解決、売上・利益の向上、
人事最適化やDX推進を検討するうえで、
今までは、解くのに非常に時間のかかるパズルがありました。
それは 組合せ最適化問題 かもしれません。
組合せ最適化問題とは
いきなりですが問題です。
「1から10までの数字の中から3つを選んで足したとき、
合計が15になる組合せをすべて選んでください」
紙と鉛筆があれば手計算でも解けるかもしれません。
しかし、もっと選択する数字や条件が複雑になった場合は、
計算量が爆発的に増えて、手計算では解けなくなります。
このような問題を「組合せ最適化問題」と言います。
組合せ最適化問題とは、
ある条件下で複数の選択肢から最適な組み合わせを選び出す問題です。
従来のコンピューターを利用して計算することもできますが、
組合せ数が増えるにつれて、計算処理時間が爆発的に増大し、
たちまち、手に負えなくなります。
このような組合せ最適化問題を解くため専用に開発されたのが
「量子アニーリング」という計算手法です。
従来のコンピューターだと、何年も計算時間が必要であった問題でも、
量子アニーリングだと数秒で計算できる場合があります。
以下では、さまざまな組合せ最適化問題を紹介します。
遠足のおやつ問題
簡単な例として、遠足のおやつを組合せ最適化問題として考えることができます。あなたは遠足にどのお菓子を買っていくかを迷っています。予算300円の範囲内で、満足度が最大になるお菓子の組合せを考えます。
お菓子の種類、価格及び満足度は下記のとおりです。
この場合、チョコレート、キャンディ、ポテチを選ぶとき、満足度21点、総額300円となり、最適な選択肢となります。
このような「組合せ最適化問題」は身近にありそうですね。
バイトシフト問題
バイトのシフト表を作成することを考えてみましょう。
2、3名なら簡単に作成できますが、従業員やアルバイトが10名以上になると、従業員のスキルや、アルバイトの希望を勘案して、時間帯に漏れがないかなど、管理が複雑となります。
ままた、急な休暇の対応のたびにシフトの変更も必要となり、担当者の負担の大きい業務と言えます。この問題もまた組合せ最適化問題です。
長方形詰め込み問題
大きさの違う複数の長方形を重ならないように、長方形容器の中に配置する問題は、組合せ最適化問題と言えます。手計算ですとかなりの時間が必要なことは想像できると思います。
大きな鉄板から長方形の材料を効率よく切り出すのに利用にできそうです。
また、長方形でなく革製品など任意の図形を切り出すことにも応用できます。
条件を変更すれば、出し入れしやすく、できる限り多くの自動車を駐車することができる駐車場のレイアウト設計にも応用できそうです。
生産計画
工場で生産される製品の種類や数量を最適に決定する問題にも組合せ最適化問題が使われます。例えば、製品の種類、生産ラインの能力、部品の在庫量、製品の需要などを考慮し、生産数を最大にするなど、最適な生産計画を立てることができます。
生産計画は主に三つの要素があり、品質（Quality）、原価（Cost）、納期（Delivery）から成り立っています。このQCDを最適化することが生産管理です。
防災
四季があり、世界が羨む美しい自然を持つ日本の国土は、一方で地形・地質・気象等の特性により災害に対し脆弱で、極めて厳しい自然条件にある。
大規模災害のとき、複数の要救助者が発生することが予想されます。患者さんの容体、救急車、ランデブーポイント、ドクターヘリをうまく運用して、できる限りフライトドクターが患者さんに接触する時間を短縮することが求められます。これは組合せ最適化問題として扱うことでます