2022年5月28日土曜日

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

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

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

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

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

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

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

 これ以外にも興味深い近似解が得られたので以下に示す。(トラック3台、4台の場合)
感想
 現実味のあるこのような配送計画(搬送経路最適化)が、量子アニーリングにより、かなり容易に解ける(最適解に近いものが得られる)ことを体験できた。量子アニーリングでは、一般に、短時間で大量の近似解が得られる。Google Maps上に結果を描画することも難しくないので、それを眺めれば、それらの中から真に実用的な解を見出せるだろう。
 一方、実際の配送計画問題では、以下のような制約も含まれるので、それらにも挑戦したい。コストとして、次の公園までの距離に加算できる制約であれば取り扱いは容易だ。
  • 通行止め区間がある。
  • 通過できる経路が定められている
  • トラックの積載量に制限がある
  • 配達先ごとに到着時間の制限がある
  • 各配達先で作業時間が異なる
  • 工場内のAGVでは、交差点制御、衝突回避なども考慮
-------------------

0 件のコメント:

コメントを投稿