多少リアルな搬送経路最適化を量子アニーリングで

　前回の記事では、TSP（巡回セールスマン問題）は量子アニーリングのための良い例題であることを述べた。今回は、これをもう一歩進めた、多少現実味のある搬送経路最適化問題を量子アニーリングで解いてみた。Fixstars Amplifyの無料オンラインセミナーの資料を参考にさせていただいた。

■課題：公園56ヶ所への花壇配送計画    
　これは筆者が勝手に設定した架空の問題である。区役所「緑と水の課」では区内の公園56ヶ所に、新たにミニ花壇を１セットづつ配送することにした。配送トラック（最大４台）は、「楓川久安橋公園」から出発し、配送後ここへ戻る。それらの総走行距離が最小になるようにしたい。また、できるだけ短時間に配送を完了することを念頭に、各トラックの訪問先の公園数は均等にする。 

　この問題、なんだか多少リアルっぽい（あり得る）ように思いませんか！

　図１には、全56ヶ所の公園の位置と、トラック１台を使った場合の最適配送経路の算出結果を示した。１台の場合は、明らかに、前回のTSPと同一の問題となる。出発地の「楓川久安橋公園」を除いて、残りの55の公園に配送することになる。

■トラック複数台を使った搬送経路の最適化
　複数台のトラックを使用する場合には、通常のTSPの解き方を若干変更した。まず、複数台のトラックが出発点からスタートしてここへ戻るため、経路の順番毎、および、公園毎のone-hot制約を外す必要がある。すなわち、トラックの台数分に応じて、該当するQUBO変数を1または0に定数化する。さらに、トラック毎の走行距離を得るために、制約条件の対象範囲を調整する必要がある。しかしながら、これらは微々たる変更なので特段の問題はないだろう。 

　実際、図２に示す量子アニーリング結果は、トラック2台と４台を使った場合の最適経路（に近いもの）になっているはずだ。図1、図２の上部にあるenergyの値は、総走行距離に相当する。（ただし、経度と緯度をスケーリングしているため、実際の距離ではないが。）トラック台数が増えるに従って、総走行距離は増えるが、台数分に応じた配送時間の短縮が得られるのである。

　これ以外にも興味深い近似解が得られたので以下に示す。（トラック３台、４台の場合）

■感想
　現実味のあるこのような配送計画（搬送経路最適化）が、量子アニーリングにより、かなり容易に解ける（最適解に近いものが得られる）ことを体験できた。量子アニーリングでは、一般に、短時間で大量の近似解が得られる。Google Maps上に結果を描画することも難しくないので、それを眺めれば、それらの中から真に実用的な解を見出せるだろう。

　一方、実際の配送計画問題では、以下のような制約も含まれるので、それらにも挑戦したい。コストとして、次の公園までの距離に加算できる制約であれば取り扱いは容易だ。

• 通行止め区間がある。
• 通過できる経路が定められている
• トラックの積載量に制限がある
• 配達先ごとに到着時間の制限がある
• 各配達先で作業時間が異なる
• 工場内のAGVでは、交差点制御、衝突回避なども考慮

　一例として、「通行止め区間がある場合」の検討結果はこちら。

-------------------