Python学習チャンネル by PyQ

Pythonのオンライン学習プラットフォームPyQのオフィシャルブログです

Google OR-Toolsを学べる「経路問題」パートリリースのお知らせ

f:id:kenken0326:20200212154702p:plain

f:id:kenken0326:20191021153602p:plain
tsutomu こんにちは。PyQ開発チームのtsutomuです。

PyQの数理的アプローチによる問題解決ランクに経路問題パートを追加しました。

経路問題

経路問題では、巡回セールスマン問題配送最適化問題の解き方を学びます。

巡回セールスマン問題はよく研究されていて、書籍も何冊か出版されています。

これらの問題は、実務でよく解かれていますが、非常に難しい問題です。
Google OR-ToolsRoutingは、無料でこれらの問題を解くことができます。また、pipで簡単にインストールできます。
無料ですが、性能も良いです。実際、実務で利用されることも多いでしょう。
しかし、残念なことに、使い方が難しく日本語の資料もほとんどありません。

今回、追加したクエストでは、Google OR-ToolsのRoutingの簡単な使い方を学ぶことができます

巡回セールスマン問題

指定された都市すべてを経由して1周する経路を求める問題です。

効率的な解法は存在しないと考えられている難しい問題です。都市の数が増えると、組み合わせ爆発することが知られています。
Google OR-Toolsは、近似解法ですが、それなりに精度良い解を高速に計算できます。

配送最適化問題

複数のオーダー(注文)を複数の車両を使って配送する問題です。

f:id:kenken0326:20200205171619p:plain

たとえば、コンビニの商品補充計画の作成などで使われます。実務では様々なバリエーションが存在します。
Google OR-Toolsでは、制約を追加したりなど柔軟なモデルを作成できます。

まとめ

今回は問題解決のクエストを追加しました。
難易度高めの問題ですが、興味のある人は是非トライしてみてください。

Copyright ©2017-2020 BeProud Inc. All rights reserved.