PyQの数理的アプローチによる問題解決ランクに経路問題パートを追加しました。
経路問題
経路問題では、巡回セールスマン問題と配送最適化問題の解き方を学びます。
巡回セールスマン問題はよく研究されていて、書籍も何冊か出版されています。
これらの問題は、実務でよく解かれていますが、非常に難しい問題です。
Google OR-ToolsのRoutingは、無料でこれらの問題を解くことができます。また、pip
で簡単にインストールできます。
無料ですが、性能も良いです。実際、実務で利用されることも多いでしょう。
しかし、残念なことに、使い方が難しく日本語の資料もほとんどありません。
今回、追加したクエストでは、Google OR-ToolsのRoutingの簡単な使い方を学ぶことができます。
巡回セールスマン問題
指定された都市すべてを経由して1周する経路を求める問題です。
効率的な解法は存在しないと考えられている難しい問題です。都市の数が増えると、組み合わせ爆発することが知られています。
Google OR-Toolsは、近似解法ですが、それなりに精度良い解を高速に計算できます。
配送最適化問題
複数のオーダー(注文)を複数の車両を使って配送する問題です。
たとえば、コンビニの商品補充計画の作成などで使われます。実務では様々なバリエーションが存在します。
Google OR-Toolsでは、制約を追加したりなど柔軟なモデルを作成できます。
まとめ
今回は問題解決のクエストを追加しました。
難易度高めの問題ですが、興味のある人は是非トライしてみてください。