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

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

今週の Tech News｜KG データの分析・可視化とGBFS ｜note

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

記事を投稿しました！ Pythonで地理空間情報（GIS）やるために必要なパッケージ全部入りの「geospatial」が便利すぎた on #Qiita https://t.co/aEtCXf1XVa

— のこのこ@3D寄りのWebGISエンジニア (@nokonoko_1203) June 3, 2022

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

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

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

これはいい記事！こういう仕事もあるんだなあ。
クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ https://t.co/NOWitPZ4n2

— Masaki Ito (@niyalist) April 21, 2022

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

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

http://project-osrm.org/

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

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

Project OSRM

配送ルートの組み方
配送ルートを組む問題を一般に配送計画問題（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 の最も難しい部分である解の探索はライブラリがやってくれるので、我々アプリケーション開発者は自分たちのサービスが必要としているルートの条件を整理・変形して、ライブラリが解ける一般的な問題に落とし込んでいきます。

OR-Tools  |  Google Developers

GitHub - ankane/or-tools-ruby: Operations research tools for Ruby

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

Noriaki Kawanishi｜note