前回の記事では、TSP(巡回セールスマン問題)は量子アニーリングのための良い例題であることを述べた。今回は、これをもう一歩進めた、多少現実味のある搬送経路最適化問題を量子アニーリングで解いてみた。Fixstars Amplifyの無料オンラインセミナーの資料を参考にさせていただいた。
■課題:公園56ヶ所への花壇配送計画
これは筆者が勝手に設定した架空の問題である。区役所「緑と水の課」では区内の公園56ヶ所に、新たにミニ花壇を1セットづつ配送することにした。配送トラック(最大4台)は、「楓川久安橋公園」から出発し、配送後ここへ戻る。それらの総走行距離が最小になるようにしたい。また、できるだけ短時間に配送を完了することを念頭に、各トラックの訪問先の公園数は均等にする。
この問題、なんだか多少リアルっぽい(あり得る)ように思いませんか!
図1には、全56ヶ所の公園の位置と、トラック1台を使った場合の最適配送経路の算出結果を示した。1台の場合は、明らかに、前回のTSPと同一の問題となる。出発地の「楓川久安橋公園」を除いて、残りの55の公園に配送することになる。■トラック複数台を使った搬送経路の最適化
複数台のトラックを使用する場合には、通常のTSPの解き方を若干変更した。まず、複数台のトラックが出発点からスタートしてここへ戻るため、経路の順番毎、および、公園毎のone-hot制約を外す必要がある。すなわち、トラックの台数分に応じて、該当するQUBO変数を1または0に定数化する。さらに、トラック毎の走行距離を得るために、制約条件の対象範囲を調整する必要がある。しかしながら、これらは微々たる変更なので特段の問題はないだろう。
現実味のあるこのような配送計画(搬送経路最適化)が、量子アニーリングにより、かなり容易に解ける(最適解に近いものが得られる)ことを体験できた。量子アニーリングでは、一般に、短時間で大量の近似解が得られる。Google Maps上に結果を描画することも難しくないので、それを眺めれば、それらの中から真に実用的な解を見出せるだろう。
- 通行止め区間がある。
- 通過できる経路が定められている
- トラックの積載量に制限がある
- 配達先ごとに到着時間の制限がある
- 各配達先で作業時間が異なる
- 工場内のAGVでは、交差点制御、衝突回避なども考慮
0 件のコメント:
コメントを投稿