[アイディア]
配送最適化を問題に落とし込む
- お題：実際の運送会社において配送ルートの最適化とはどういうものをやりたいのか
- 加えて、整数計画法の中にある運搬経路問題がそれに適用できるのか考えてみる
課題
- (1) 複数台のトラックにて単一の地点から複数の地点にもっとも効率よく荷物を配送するルートを求めたい
- 難しいところ：ある出発地～到着地へのルートは直線距離ではなく実際のルート情報（道のり）でないと正確な距離と時間が求められない
- 効率がよいとは？
- できるだけ少ない台数のトラックで全配送地を回る（ただし、稼働時間・重量・積載量などは制限を超えてはならない）
- (2) 実際的な荷物の運送には時間指定が伴う
- 実現できると何がうれしいか
- 配送ルートを決める労力が少なくなる
- 少ないトラックで配送できれば人件費その他が節約できる
既存の研究
上記のようなことはすでに賢い先人が研究している（整数計画法）
- 運搬経路問題 (VRP)とは が素人でもよくわかるようにまとまっている
- (1)の課題はCVRPが近い
- (2)はVRPTW
- なんとGoogle APIの中にこれを解いてくれるソルバーがある
参考1
- VRPをGoogleのAPIで解決するサンプルがあった
- Managing Simple VRP with Google Maps Platform
- これのキモは、サイトで紹介されている(2)と(3)である。
- (2)で全ルート×全ルートの距離コストをAPIで出力している、(3)でVRPのソルバーを使って最適解を出している
- 疑問
- (2)の距離コストの行列を出すとき、配送先が多くなると重くなるんじゃないかな？
- (3)で使用できる条件にどの程度制限となる変数を使用できるのだろうか
- Managing Simple VRP with Google Maps Platform
ビジネス1
- 仮にこれらを使用していい感じの配送計画シミュレーターが作れたとして
- GoogleAPIのコスト < 売り上げ, にならないと厳しい
- 個人でやるなら、距離のコスト算出だけDistance Matrix APIを使って、ソルバーは自作するといいかもしれない
参考2
- OptaPlanner
- それを使ったWEBアプリ kiegroup/optaweb-vehicle-routing
参考3
- 行き先がめちゃくちゃ多くても大丈夫。jspritで効率よく目的地を回っちゃおう
- jspritというライブラリの使用例、jspritは現実的な速度でVRPの問題を解けるらしい。時間指定VRPTWもできるらしい。
ビジネス
最適なアーキテクチャー（実現および採算度外視）
- ViewにOSM(OpenStreetMap）を使用する
- 全ルート×全ルートの距離コスト算出をOSMのものを使いコストダウン（参考：Distance matrix API）
- 返ってきたコストの行列をVRP, VRPTWの問題として解くソルバーをjspritで作る
- これで「サーバ維持費 < アフィリエイト収入」にならねえかな？