🌎

安価に運用できるVRPソルバーをAWSで構築する

oddgai

2026/08/27に公開

こんにちは、GENDAでデータサイエンティストをしている小貝です。最近ひょんなことから2歳の娘が戦隊ヒーローにハマっており、図鑑を買ってあげたらいつもベッドに持ち込んで寝ています。朝起きたら「デカレンジャーをトントンして寝かせてあげてたの」と報告してくれます。
さて、業務で配送計画問題（Vehicle Routing Problem, VRP）を調べる機会がありました。VRPを扱うには有償のAPIを使うのが手軽なのですが、安価にできないか気になったのでAWSで試してみました。なお、具体的なコードを書くと長くなるためシステム構成を中心に書きます。

 TL;DRVRPをOSSだけで解く環境を作り、AWS上に載せた
AWSはALB → Fargate（ソルバー） → EC2（OSRM）のシンプルな構成
Fargate：OR-Tools（ソルバー）
EC2：OSRM（経路探索エンジン）

コストは関東だけなら約$245/月〜
東京リージョン、冗長化なし、常時起動
使用量しだいでは有償APIより安くなる


 VRP（配送計画問題）とはVRPは、車両が複数の地点を訪問するとき、移動時間や距離の総和が最小になるような訪問ルートを求める問題です。VRPは、Googleの Route Optimization API や HEREの Tour Planning API といった有償のサービスで解くのが速くて精度も高くて手軽です。ただ、これらは基本的に従量課金なのでコストを気にしながら運用することになります。この記事ではOSSを組み合わせて安価に運用できるやり方を紹介します。
https://developers.google.com/maps/documentation/route-optimization?hl=ja

https://docs.here.com/tour-planning/ja/v1.0/docs/introduction-tour-planning

 OR-ToolsとOSRMVRPを解くには、最適化ソルバーと地点間の移動時間やルートを計算する経路探索エンジンの2つが必要です。今回はソルバーにOR-Tools、経路探索エンジンにOSRMを使います。なお、訪問する地点集合が既知であればあらかじめ地点間の移動時間やルートを計算・保存しておいて、実際に解く際はOR-Toolsのみを使う方法もあります。ただ長期的に運用するなら、道路の新設や廃止などに対応できるOSRMなどを使うのがよいと思います。

 OR-ToolsOR-Toolsは、Googleが開発しているOSSの数理最適化ソルバー（を集めたもの）です。制約最適化、線形最適化、混合整数計画問題、VRP、スケジューリングなどさまざまな最適化問題をサポートしています。
https://developers.google.com/optimization?hl=ja
詳細は公式ドキュメントにありますが、たとえばVRPであれば以下のようにさまざまな要素を考慮することができます。
容量制約（アイテムに重量や体積などがあり、車両に載せる量が限られている）
訪問順（地点Aで集荷してから地点Bに配達する）
タイムウィンドウ（地点Aにはある時間内に訪問する必要がある）
...
注意としては、制約最適化、線形最適化、混合整数計画問題についてはコードを見るかぎり最適性の保証がある（ OPTIMAL: 最適解が得られた / FEASIBLE: 最適解か不明だが実行可能解は得られた / INFEASIBLE: 実行不可能 を区別している）ようですが、VRPに関しては得られた解が最適解であることを保証しません。

 OSRMOSRM（Open Source Routing Machine）は、OpenStreetMapの地図データ上で最短経路や移動時間、距離を計算してくれる経路探索エンジンです。地図データは毎日更新され、道路の更新があっても追従できます。デモサーバーも公開されており、以下のように移動時間やルートを取得できます。
# 新宿駅 -> ポケパーク カントー
curl 'http://router.project-osrm.org/route/v1/driving/139.6997,35.6897;139.5204,35.6262?skip_waypoints=true'

# {
#   "code": "Ok",
#   "routes": [
#     {
#       "legs": [
#         {
#           "steps": [],
#           "weight": 1868.5,
#           "summary": "",
#           # 1865秒 = 約31分（Google Mapsでは25〜45分だったので妥当そう）
#           "duration": 1865,
#           "distance": 23672.7
#         }
#       ],
#       ...
#     }
#   ]
# }
ただしデモサーバーは可用性の保証がなくいつ使えなくなるかわからないため、本格的に使うには自前でサーバーを立てましょう。
Api usage policy より
We don't give any quality guarantees. The Demo Sever is supplied on best effort basis.
品質保証は一切いたしません。デモサーバーは、最大限の努力をもって提供されます。
https://github.com/Project-OSRM/osrm-backend/wiki/Api-usage-policy

 OSRMサーバーの構築OSRMはDockerイメージが用意されているので、地図データを落としてコマンドを順に実行すればよいです。
build-osrm.sh
# 関東の地図データをダウンロード（469MB）
wget https://download.geofabrik.de/asia/japan/kanto-latest.osm.pbf

# グラフを構築。ここでメモリを大きめに使う
# 最終的に合計約3GBのファイル群ができる
OSRM="docker run --rm -v $PWD:/data ghcr.io/project-osrm/osrm-backend"
$OSRM osrm-extract -p /opt/car.lua /data/kanto-latest.osm.pbf
$OSRM osrm-partition /data/kanto-latest.osrm
$OSRM osrm-customize /data/kanto-latest.osrm

# サーバーを起動する
# --max-table-sizeは/tableで一度に扱える地点数の上限。デフォルトは100
docker run --rm -p 5000:5000 -v "$PWD:/data" ghcr.io/project-osrm/osrm-backend \
  osrm-routed --algorithm mld --max-table-size 1000 /data/kanto-latest.osrm
各工程のピークRAMと所要時間は以下のとおりです。構築時のほうがメモリを使うので、同じインスタンスで両方やるならメモリは構築側に合わせて選びましょう。


工程
やっていること
ピークRAM
所要時間


osrm-extract
経路グラフを構築
6.48 GB
91秒

osrm-partition
セルの階層を構築
2.27 GB
50秒

osrm-customize
セルごとの重みを構築
4.18 GB
37秒

osrm-routed
サーバー起動
4.66 GB
-

OSRMの地図データは毎日更新されます。サーバーにあるデータを更新するにはpbfを再ダウンロードして構築の3コマンドを回し、サーバーを再起動します。関東なら3分ほどで終わるため、cronなどで定期実行しておくとよいでしょう。
update-osrm.sh
# 更新があるときだけpbfを取得する
wget -N https://download.geofabrik.de/asia/japan/kanto-latest.osm.pbf

$OSRM osrm-extract -p /opt/car.lua /data/kanto-latest.osm.pbf
$OSRM osrm-partition /data/kanto-latest.osrm
$OSRM osrm-customize /data/kanto-latest.osrm
なお、OpenStreetMapのデータはODbL（Open Database License）で提供されています。これを使ったサービスを公開する場合は「© OpenStreetMap contributors」のようなクレジットと、データがODbLである旨の明示が必要です。

 AWSでの構成AWSでの構成例はこちらです。ソルバーをFargate、OSRMをEC2に置くシンプルな構成です。


外部からALB経由でソルバーを叩き、ソルバーはOSRMから移動時間を取得する
置き場所はそれぞれの性質に合わせて選びました。

ソルバーはFargate
コンテナなので必要なときだけ立てる
使わないときはサービスのタスク数を0にしておけば課金されない

Lambdaでも動く。呼ばれたときだけ課金されるのでさらに安い
ただしortoolsはpandasとnumpyを引いて展開後191MBになり、zipの展開後サイズ上限250MBに余裕が少ない



OSRMはEC2 + Docker
地図データ（.osrm）がそれなりに大きいので、消えないEBSに置いてEC2からDockerでserveする
関東のみならインスタンスはGraviton（ARM）のm8g.xlarge（4vCPU / 16GiB）でよさそう

実際に使ってみたところ、100地点・5車両くらいの規模であれば5秒くらいで結果を返してくれました。解の精度（厳密な最適解からどのくらいギャップがあるのか）は要検証ですが、パッと見では悪くない雰囲気だったのと、うまくチューニングすればより実用的になると思います。

 コスト気になるコストですが、東京リージョンで冗長化なしで常時起動した場合の目安は以下のとおりです。数字だけ見ると安くはないですが、使用量しだいでは有償APIより安くなるはずです。


項目
スペック
月額（概算）


OSRM用EC2
m8g.xlarge (4vCPU / 16GiB)
$169

EBS
30GB (gp3)
$3

ソルバー用Fargate
ARM 1vCPU / 8GB
$55

ALB

$18

合計

$245

Reserved Instance（RI）などを使えばここからさらに下がりますが、止めているあいだも課金されるので、前述の「使わないときは落とす」運用とは両立しません。常時動かすならRI、そうでなければオンデマンドのまま落とす、という使い分けがよいでしょう。いずれにせよ、この構成のコストは稼働時間だけで決まり、解いた回数では増えません。リクエスト量が増えても定額なのは精神衛生的に嬉しいですね。

 まとめOR-ToolsとOSRMでVRPを解くシステムをAWS上に安価に構築できる構成を紹介しました。手軽さと精度では有償APIに一歩及びませんが、コストを気にせず使えるのは価値があります。ぜひ試してみてください！

工程	やっていること	ピークRAM	所要時間
osrm-extract	経路グラフを構築	6.48 GB	91秒
osrm-partition	セルの階層を構築	2.27 GB	50秒
osrm-customize	セルごとの重みを構築	4.18 GB	37秒
osrm-routed	サーバー起動	4.66 GB	-

項目	スペック	月額（概算）
OSRM用EC2	m8g.xlarge (4vCPU / 16GiB)	$169
EBS	30GB (gp3)	$3
ソルバー用Fargate	ARM 1vCPU / 8GB	$55
ALB		$18
合計		$245

GitHubで編集を提案

GENDAPublication

『世界中の人々の人生をより楽しく』をAspiration（大志）に掲げたエンターテイメント企業『GENDA』（ジェンダ）

TL;DR

VRP（配送計画問題）とは

OR-ToolsとOSRM

OR-Tools

OSRM

OSRMサーバーの構築

AWSでの構成

コスト

まとめ

Discussion