見出し画像
Photo by norinity1103

今週のTech News #98 -Pythonパッケージ geospacial が便利すぎた、配送ルートの自動生成：配送計画問題...etc

KG データの分析・可視化とGBFS


Twitterで流れてきた興味深いTweetを取り上げて、解像度をあげて読者に届けていくマガジンです。
データ分析、VR/AR、航空、GISなどの情報が多めになります。
ぜひフォローよろしくお願いいたします。



■Pythonパッケージ geospacial が便利すぎた

導入の文章が面白かったので少しご紹介。（笑）
Qiitaの記事もぜひ読んでみてください。

Mac民にとってはめちゃくちゃ朗報かも
GISをやる人ならわかってくれると思うんですが、MacでPythonを使ってGIS（主にgeopandasなど）をやる時依存関係の解決にかかる時間ヤバすぎ問題っていうのがありまして…
主にGDLAとかGDALとかがかなりやばくて偉大なる先人様のお知恵を拝借して鼻血出しながらなんとかかんとか実行環境を整えていました
が！！！！！もうそんな必要はないのかもしれませんね！！！！！！


■配送ルートの自動生成：配送計画問題（Vehicle Routing Problem, VRP）

興味深いところを少し抜粋。

道路を考慮した移動時間を計算するために Open Source Routing Machine (OSRM) を使っています。

http://project-osrm.org/

OSRM は OpenStreetMap (OSM) の地図データを用いて経路計算をしてくれるルーティングエンジンです。Google Maps の経路検索をイメージしてもらうとわかりやすいと思います。

OSRM はフロントエンドまで含めたプロジェクトになっていますが、バックエンドの API だけでも利用することが可能です。クックパッドマートでは社内にデプロイした OSRM の API を使って移動時間を計算しています。また、この API は数十msと比較的高速にレスポンスを返してくれますが、ルート生成の過程では大量の移動時間の計算が発生するため、必要になる移動時間は事前に計算して DB に入れておいて、計算時には一括でメモリに載せてしまうなどのパフォーマンス上の工夫もいくつかおこなっています。

画像1

配送ルートの組み方
配送ルートを組む問題を一般に配送計画問題（Vehicle Routing Problem, VRP）と呼びます。組み合わせ最適化問題の一種で、最適解を現実的な時間（多項式時間）で求めることはできない問題です。

一方で、VRP という名前がついているくらいには有名な問題なので、近似解を求めるライブラリなどは存在しています。クックパッドマートでは OR-Tools というライブラリの Ruby wrapper を使用しています。公式の C++, Python 実装ではなく非公式の Ruby 版を使っているのは既存実装との繋ぎ込みやチームのメンバー構成などを考慮した結果です。

https://developers.google.com/optimization
https://github.com/ankane/or-tools-ruby
VRP の最も難しい部分である解の探索はライブラリがやってくれるので、我々アプリケーション開発者は自分たちのサービスが必要としているルートの条件を整理・変形して、ライブラリが解ける一般的な問題に落とし込んでいきます。

画像2


イラスト - Noriaki Kawanishi
とてもシンプルでわかりやすく絵のタッチが気に入っており使用させてもらっています。いつもありがとうございます。


サポートのお金は，少し値段の高い マシュー・J.サルガニック 著『ビット・バイ・ビット -- デジタル社会調査入門 』(￥4,320)の購入資金にあて，noteに書評を書こうと思います．ぜひサポートお願いします＼(^o^)／