【ゆかしゅんぶろぐ】streamlitで配送計画問題を解くwebアプリを作ってみたので実際に使ってみる

はじめに

こんにちは！しゅんです！

今回はstreamlitで配送計画問題を解くwebアプリを作ってみたのでそれを実際に使ってみようと思います。

これまでは組合せ最適化の色んな問題をpythonで解く方法などを紹介していましたが、コードを書かなくても皆さんが解けるようなwebアプリを作ろうかな～と思い、streamlitを使ってwebアプリを作ってみました。

今回作ったものはこちらからアクセスできます。良ければ使ってみてください。
Streamlit (vehicle-routing-problem.streamlit.app)

webアプリ開発に関してはまだまだ初心者で解説できるレベルではないので、今回作ったアプリのコード解説とかはしません。githubにソースコードを公開しているので気になる人はそれを見てみてください。

ソースコードはここをクリックGitHub

それではやっていきましょう！

普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！

もっとみる

このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。

このブログについて

このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！

ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。

そもそも経営工学とは何なのでしょうか。Wikipediaによると

経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。

引用元 : 経営工学 – Wikipedia

長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。

配送計画問題ってなに？

問題設定：
ある運送会社は1個のデポと\(m\)台の車両を持っている。いまこの運送会社は\(n\)個の地点に配送しようとしている。各車両はデポから出発して各地点を回ってまたデポに戻ってくるルートを通って配送する。各車両には走行距離の上限があり、それを超えて配送することはできない。またどの地点も必ずちょうど一回訪れなければならない。

目的：
走行距離制約を満たす配送ルートの中で移動距離が最小となるようなルートを求める。

上図は2台のトラックで5つの地点に配送する問題における配送ルートの例です。オレンジ色の矢印が配送ルートを表していて、どっちのルートもデポから出発してデポを通っていますね。

配送計画問題は車両に容量制限がある場合や時間に関する制約がある場合など、色々なバリエーションがあります。入力するパラメータをなるべく少なくしたかったので、今回は超シンプルな配送計画問題が解けるwebアプリを作ってみました。

webアプリの概観

アプリを開くと上記のような画面が出てきます。一応このサイトの使い方ページも用意しました。左側のページ選択の所から「このサイトの使い方」ボタンを押せば以下のようなページに飛ばされます。

それでは実際にパラメータを入力して配送計画問題を解いてみたいと思います。

実際に配送計画問題を解いてみる

STEP 1 : データを入力する

まず最初に各パラメータの数値を入力しましょう。今回は頂点数、車両数、車両の走行距離の上限を入力します。頂点は最大で10個まで、車両は最大で4台まで扱えます。

STEP 2 : 「グラフを表示して最適ルートを計算」ボタンを押す

数値を入力し終えたら、左下にある「グラフを表示して最適ルートを計算」ボタンを押します。ボタンを押したら右側に2つの図が出てきました。

上にある図はデポと地点を描画したグラフになります。各地点は\([0,10] \times [0,10]\)の2次元ユークリッド平面上にランダムに配置されます。

下にある図は最適な配送ルートを描画したグラフになります。先ほどのグラフに加えて、オレンジ色の矢印が追加されています。これは各車両の配送ルートを表しています。

各地点の座標はランダムに配置されるので、ボタンを押すたびに異なる問題を解くことになります。