VRP Demo Report

Bối cảnh và dạng bài toán

Bản demo mô hình hóa lập tuyến đa xe từ một điểm xuất phát (depot) trong một horizon thời gian cố định (một ca). Đây là Vehicle Routing Problem (VRP) với vector ràng buộc thực tế: thời gian di chuyển và phục vụ tích lũy theo tuyến, khối lượng và thể tích trên từng xe, và thời điểm giao tương ứng deadline từng đơn. Khác với VRP “phải thăm hết khách”, lớp bài toán này cho phép một số đơn không được gán trong lượt hiện tại: mỗi đơn mang một chi phí opportunity nếu bị bỏ qua (disjunction với penalty), để solver cân bằng giữa tối thiểu hóa chi phí vận hành và giữ các đơn cận hạn khỏi bị hoãn khi còn khả năng vật lý.

Hai trụ cột cùng một giải pháp: Bảng KPI và bản đồ trên trang minh họa tối ưu tuyến, SLA và chi phí cung (km, thời gian, hoãn, 3PL). Khối ước tính chi phí lớp định tuyến ngay bên dưới trình bày cách kiểm soát OPEX ma trận khoảng cách/thời gian khi replan thường xuyên — thường là hạng mục ngân sách lớn hơn nhiều so với chi phí chạy solver nội bộ nếu không thiết kế cache và kiến trúc phù hợp.

Mô hình hóa và cơ chế tối ưu

Chi phí mục tiêu gắn với quãng đường (arc cost) trên từng cạnh; đồng thời một dimension thời gian tích lũy thời gian đi và thời gian phục vụ tại điểm trước khi rời điểm, nhằm kiểm soát thời điểm đến so với deadline. Hai ràng buộc capacity (trọng lượng và thể tích) được mô hình độc lập để phản ánh xe tải thực tế. Ma trận khoảng cách và thời gian đi giữa các cặp điểm lấy từ định tuyến đường thực (OpenStreetMap qua OSRM) khi khả dụng; khi không, lớp dự phòng dùng khoảng cách đại cầu (Haversine) để đảm bảo luôn có nghiệm tính được. Solver dùng Google OR-Tools (routing model) với chiến lược tìm kiếm cục bộ trong giới hạn thời gian chạy cố định, phù hợp bài toán lớn trong production: chấp nhận nghiệm gần tối ưu có kiểm soát thay vì chờ tối ưu toàn cục không thực tế.

Nhiều lượt trong ca và tầng 3PL

Luồng tối ưu trong demo có thể gồm hai lượt in-house liên tiếp: lượt một xếp toàn bộ đơn còn trong ca; sau khi xe hoàn tất và quay về kho, lượt hai chạy lại bài toán trên tập đơn chưa được phục vụ, với deadline dịch chuyển theo thời gian đã tiêu hao — phản ánh khả năng “quay vòng” nội bộ trước khi chuyển chi phí sang ngoài. Chỉ phần còn lại sau khi cạn khả năng in-house trong horizon mới được xét gán đối tác giao ngoài (3PL) như lớp overflow, nhằm tránh dùng OPEX 3PL thay thế năng lực nội bộ khi vẫn còn cửa sổ thời gian trong ca. Tầng điều phối có thể so sánh nhiều chính sách ưu tiên (ví dụ thuần chi phí đường so với cân bằng deadline và chi phí 3PL) bằng một hàm điểm tổng hợp — làm rõ trade-off giữa chi phí vận hành và SLA.

Nội dung trang và cách đọc kết quả

Phần danh sách đơn được sắp theo thứ tự thực tế trên từng chuyến xe (lượt một trước, lượt hai sau). Cột quãng đường cạnh là khoảng cách đoạn đi tới điểm dừng đó; cột tổng km chuyến (gom theo chuyến) là tổng quãng của cả tuyến đó. ETA là thời gian tích lũy từ đầu chuyến (và với lượt hai là sau offset thời gian lượt một), nên có thể cao dù cạnh cuối ngắn — điều này là bình thường về mặt mô hình. Bản đồ minh họa hình học tuyến và phân lớp theo xe; bảng KPI tổng hợp mức độ đạt SLA, chi phí cung (km, thời gian chạy) và vai trò 3PL/hoãn — cùng một luồng xử lý với phần mô tả phía trên.

Phạm vi demo và giới hạn khi mở rộng

Đây là một depot, dữ liệu mô phỏng: mục đích là minh họa khả năng kết nối định tuyến — tối ưu — báo cáo trong một luồng, không thay thế đánh giá trên dữ liệu vận hành thật hay đa kho. Hướng mở rộng sản phẩm điển hình gồm tích hợp hệ thống đơn và fleet, mở rộng đa depot, và ràng buộc nghiệp vụ (zone, skill, cửa sổ cứng). Rủi ro kỹ thuật cần lường trước khi scale: phụ thuộc dịch vụ định tuyến công cộng (rate limit, SLA), và cần chiến lược cache/hosting khi triển khai thật.

Thông điệp giá trị

Sản phẩm cốt lõi là quyết định tối ưu hóa có giải thích được (tuyến, thời điểm, hoãn, 3PL) dưới ràng buộc vận hành, giảm chi phí cung và tăng khả năng đạt SLA trong cùng năng lực xe — với lộ trình tách biệt lớp thuật toán và lớp tích hợp dữ liệu doanh nghiệp. Đầu tư song song vào lớp ma trận và chính sách cache giúp duy trì cùng mức SLA khi mở rộng quy mô đơn và tần suất replan mà không để OPEX định tuyến tăng tuyến tính theo số lần gọi API.

Problem context and class

This demo models a multi-vehicle routing flow from one depot within a fixed planning horizon (one shift). It is a Vehicle Routing Problem (VRP) under practical constraints: cumulative travel/service time, per-vehicle weight and volume capacity, and order-level deadline pressure. Unlike mandatory-visit VRP variants, this setting allows some orders to be left unassigned in the current run: each deferred order carries an opportunity cost (disjunction with penalty), so the solver can trade off total routing cost versus SLA protection for near-due orders.

Two pillars, one product: the KPI table and map illustrate optimized routes, SLA, and fleet cost (distance, time, deferrals, 3PL). The routing-layer cost estimate section below shows how to control distance/time matrix OPEX under frequent replanning — often a far larger budget line than the internal solver if caching and architecture are not designed intentionally.

Modeling and optimization mechanics

The objective is anchored on arc distance cost, while a dedicated time dimension accumulates travel and service to control arrival time against due-time pressure. Two independent capacity constraints (weight, volume) model real fleet limits. Distance/time matrices come from road-network routing (OSRM/OpenStreetMap) when available; fallback to Haversine keeps the pipeline feasible when live routing is unavailable. The solver uses Google OR-Tools with bounded search time, favoring controlled near-optimal solutions over impractical global-optimum waits.

Multi-wave operation and 3PL layer

The optimized flow supports two sequential in-house waves: wave 1 serves the first feasible set; after vehicles return, wave 2 replans the remaining set with shifted effective deadlines based on elapsed time. Only residual hard cases after in-house exhaustion are pushed to 3PL overflow, preventing premature externalization while in-house capacity still has viable time windows. The policy layer can compare distance-first and SLA-balanced variants via a composite score to make cost-vs-SLA trade-offs explicit.

How to read results on this page

The order list is sorted by actual stop sequence per trip (wave 1 first, then wave 2). Arc distance is the incoming segment to that stop; trip total km is the route total grouped by trip. ETA is cumulative from trip start (wave 2 ETAs include wave-offset), so a short final arc can still show high ETA. The map shows route geometry and vehicle layering; the KPI table consolidates SLA attainment, supply cost (km/time), and 3PL/defer buckets from the same processing pipeline.

Demo scope and scale limits

This is a single-depot, synthetic-data demonstration to validate algorithmic behavior and explainability, not a substitute for full production benchmarking on live multi-store operations. A production roadmap typically includes order/fleet system integration, multi-depot orchestration, and richer constraints (zones, skills, hard windows), with explicit controls for routing API rate/SLA and matrix cache/hosting strategy.

Value proposition

The core product is explainable optimization (routes, timing, deferrals, 3PL) under operational constraints, reducing fleet cost and improving SLA within the same vehicle capacity — with a clear separation between algorithm logic and enterprise data integration. Parallel investment in the matrix layer and caching policy keeps routing OPEX under control when order volume and replan frequency grow, instead of letting billed API elements grow linearly with every rebuild.

Từ SLA khung giờ đến OPEX định tuyến: vì sao ma trận là trọng tâm đầu tư

Cam kết giao đúng khung giờ đòi hỏi ma trận thời gian và khoảng cách trên đường thật đủ tin cậy cho từng cặp điểm. Khi vận hành replan định kỳ (ví dụ mỗi 5 phút) để bắt kịp đơn mới và giữ on-time, số phần tử ma trận phải tính phí nhân với số lần build — OPEX lớp Distance Matrix / Matrix API có thể vượt xa chi phí chạy solver (OR-Tools) nội bộ nếu không có chiến lược riêng cho lớp này.

Giải pháp không chỉ là “chọn Google hay HERE”: đó là kiến trúc sản phẩm — cache theo cặp tọa độ, cập nhật ma trận gia tăng khi đơn đổi, gộp batch hợp lý, và tùy quy mô OSRM tự host để chuyển một phần lớn chi phí từ biến đổi theo request sang hạ tầng cố định có kiểm soát.

Thách thức: SLA khung giờ + tần suất replan cao → nhu cầu ma trận lớn và lặp lại.
Đầu tư đúng chỗ: tách dịch vụ ma trận, đo cache hit rate và billable elements — nền tảng cho ngân sách định tuyến bền vững.
Minh chứng dưới đây: bảng so sánh nhà cung cấp; kịch bản ~47,7 triệu phần tử/tháng (1 store, 100 đơn/khung, không cache); và bảng cache 50–85% khi cron 5 phút — thể hiện thứ tự độ lớn giữa các lựa chọn.

Các số liệu là khung tham chiếu để lập kế hoạch; số tiền thực tế lấy theo bảng giá và hợp đồng hiện hành của từng nhà cung cấp.

VRP cần ma trận khoảng cách và thời gian giữa depot và các điểm đơn (và có thể giữa các đơn). Chi phí vận hành thực tế phụ thuộc số lần build ma trận, cách gộp request, vùng địa lý, hợp đồng doanh nghiệp và bậc giá. Bảng dưới đây là khung so sánh và một kịch bản số minh họa — mang tính tham chiếu, không thay thế báo giá chính thức từ nhà cung cấp.

Nguồn tham chiếu giá & billing (chính thức):

Google Maps Platform — Bảng giá · Chi tiết SKU · Distance Matrix — Usage & billing
HERE — Pricing · Routing (nền tảng)
OSRM (mã nguồn mở — không có giá API; chi phí là triển khai & vận hành)

Tiêu chí	OSRM (mã nguồn mở)	Google Maps Platform	HERE
Mô hình kinh doanh	Tự triển khai trên hạ tầng riêng; hoặc dùng endpoint công cộng (thường có giới hạn, không bảo đảm SLA production).	Dịch vụ đám mây theo SKU (Distance Matrix, Routes, v.v.), trả theo mức sử dụng và bậc khối lượng.	Dịch vụ đám mây theo gói; trả theo giao dịch (transaction) hoặc cam kết doanh nghiệp tùy hợp đồng.
Đơn vị tính tiền điển hình	Chi phí máy chủ, lưu trữ bản đồ OSM, vận hành (và tùy chọn CDN); không tính “per request” nội bộ.	Distance Matrix: thường tính theo phần tử (cặp gốc–đích trong ma trận); Routes API tính theo request/tuyến.	Matrix / Routing: tính theo giao dịch; một request ma trận có thể quy ra nhiều giao dịch tùy kích thước và loại API.
Điểm mạnh cho VRP	Kiểm soát chi phí biến đổi theo lưu lượng; không phụ thuộc đơn giá từng API call nội bộ. Phù hợp khối lượng lớn nếu tự host ổn định.	Dữ liệu đường phố và ETA phổ biến toàn cầu; tích hợp hệ sinh thái Google.	Nền tảng định vị doanh nghiệp; thường dùng trong fleet/logistics với hợp đồng và hỗ trợ.
Rủi ro / hạn chế	Chi phí DevOps; cập nhật dữ liệu OSM; endpoint công cộng dễ bị rate-limit hoặc ngắt khi tải cao.	Chi phí tăng nhanh khi số phần tử ma trận lớn hoặc replan thường xuyên; cần cache và thiết kế batch.	Cần làm rõ quy tắc tính transaction cho Matrix; giá hiển thị công khai có thể khác Enterprise.
Tham chiếu giá công khai (minh họa)	VPS/tự host vùng đơn: thường khoảng vài chục–vài trăm USD/tháng tùy CPU/RAM và số vùng; API công cộng ~0 USD nhưng không dùng cho production nặng.	Distance Matrix (Essentials): bậc phổ thông thường quanh ~4–6 USD / 1.000 phần tử (giảm dần theo bậc khối lượng); có hạn mức miễn phí theo chính sách Google (thay đổi theo thời điểm).	Nhiều gói công khai nằm khoảng ~1–2 USD / 1.000 giao dịch sau hạn mức miễn phí (số liệu mang tính tham chiếu; Matrix có thể đếm khác Routing).

Kịch bản số minh họa (cùng một giả định lưu lượng)

Giả định: cần 200.000 phần tử ma trận tính phí trong tháng (tương đương nhiều lần build ma trận cho bài toán cỡ trung, sau khi gộp request hợp lý). Áp mức tham chiếu ở bảng trên (bậc giá phổ thông, chưa gồm thuế, chưa chiết khấu doanh nghiệp):

Nguồn	Ước tính OPEX biến đổi (minh họa)	Ghi chú
OSRM (tự host 1 cụm nhỏ)	~80–250 USD/tháng hạ tầng + vài giờ vận hành	Biến đổi theo quy mô; không tỷ lệ thuận trực tiếp với 200k “phần tử” như SaaS.
Google (Distance Matrix, ~5 USD/1k phần tử)	~1.000 USD/tháng (200 × 5)	Thực tế có bậc giảm giá theo khối lượng; có thể thấp hơn khi đạt tier cao.
HERE (giả định ~1,5 USD/1k giao dịch tương đương quy mô)	~300 USD/tháng (200 × 1,5)	Chỉ minh họa nếu quy đổi 1:1 với đơn vị; Matrix HERE có thể tính nhiều transaction mỗi request — nên đối chiếu với bảng giá và tài liệu billing của HERE.

Kịch bản khả thi vận hành: cron 5 phút, cache bắt buộc

Với giao hàng theo khung giờ, nếu chỉ lập tuyến 1 lần/giờ thì rủi ro miss on-time cao khi có đơn mới. Kịch bản thực tế hơn là cron replan mỗi 5 phút trong ca 8h–21h (780 phút) ⇒ 156 lần replan/ngày. Vì vậy cache ma trận là yêu cầu bắt buộc.

Kịch bản: 1 store, ca 8h–21h, cron 5 phút, mốc 100 đơn/khung

Giả định mô hình: 13 khung giao trong ngày (8–9, …, 20–21), trung bình 100 đơn/khung cần giao trong đúng khung đó. Mỗi lần lập tuyến (VRP) trên depot + 100 điểm tạo ma trận đầy đủ 101 × 101 = 10.201 phần tử (cặp gốc–đích). Với cron 5 phút trong ca 8h–21h: 156 lần/ngày → mỗi ngày 156 × 10.201 = 1.591.356 phần tử; tháng 30 ngày: 47.740.680 phần tử/tháng (không cache).

Nguồn định tuyến	Ước tính OPEX biến đổi / tháng (minh họa)	Cách tính gần đúng
Google Distance Matrix (không cache)	~191.000–238.700 USD/tháng	47.740.680 phần tử × (4–5 USD/1.000 phần tử) ở bậc phổ thông; bậc khối lượng cao hơn có thể xuống ~3 USD/1k → ~143.200 USD/tháng.
HERE (mô hình giao dịch)	~71.600 USD/tháng	Nếu quy đổi thô ~1,5 USD/1k giao dịch tương đương quy mô phần tử: 47.741 × 1,5; HERE đếm Matrix theo quy tắc riêng — nên đối chiếu tài liệu billing của HERE.
OSRM tự host	~250–700 USD/tháng hạ tầng + vận hành	Không tính theo phần tử; chi phí chủ yếu máy chủ đủ phục vụ ~156 lần replan/ngày + cập nhật OSM định kỳ.

Lưu ý: Chi phí không gồm solver (OR-Tools chạy nội bộ), lưu trữ đơn, hay 3PL. Nếu replan thêm giữa khung (ví dụ mỗi 15 phút) hoặc tách batch, nhân số phần tử tương ứng; ngược lại cache ma trận theo cặp tọa độ có thể cắt giảm đáng kể OPEX API.

Ước tính chi phí khi bật cache (cron 5 phút)

Công thức: billable_elements = raw_elements × (1 - cache_hit_rate). Giả định giá: Google ~4–5 USD/1.000 phần tử; HERE ~1,5 USD/1.000 giao dịch quy đổi thô.

Quy mô	Raw phần tử/tháng	Cache hit	Google (USD/tháng)	HERE (USD/tháng, quy đổi thô)
100 đơn/khung 101×101/lần, 156 lần/ngày	47.740.680	50%	~95.481–119.352	~35.806
		70%	~57.289–71.611	~21.484
		85%	~28.644–35.806	~10.742

Nhận định tham chiếu: với khối lượng ma trận lớn và replan thường xuyên, OSRM tự host thường có tổng chi phí biến đổi hấp dẫn hơn sau khi amortize hạ tầng; với triển khai nhanh và khối lượng vừa, Google/HERE có thể hợp lý nếu tối ưu số request và dùng cache. Trước khi chốt ngân sách, nên đối chiếu bảng giá hiện hành (các liên kết phía trên) và điều khoản hợp đồng với nhà cung cấp.

Giải pháp giảm chi phí khi bill Google/HERE quá cao

Khi chi phí ma trận vượt ngưỡng ngân sách (ví dụ mức >10.000 USD/tháng), chúng ta không chỉ đổi nhà cung cấp mà tối ưu trực tiếp số phần tử phải tính và số lần gọi API đắt trong pipeline định tuyến.

Không luôn cần ma trận đầy đủ N×N: nhiều luồng chỉ cần depot → tất cả điểm và một đồ thị thưa giữa các điểm gần nhau (lọc bằng Haversine/grid), rồi mới bổ sung cạnh khi solver cần mở rộng.
Cập nhật gia tăng (incremental): khi có đơn mới, chỉ thêm các hàng/cột liên quan thay vì build lại toàn bộ ma trận ở mỗi lần replan.
Gom điểm / snap theo cụm: các đơn rất gần nhau có thể snap về cùng node để giảm kích thước ma trận (đánh đổi độ chính xác theo cấu hình).
Tiền lọc bằng nguồn rẻ: dùng Haversine hoặc OSRM nội bộ cho bước lọc ứng viên, chỉ gọi API trả phí cho tập cạnh nhỏ sau clustering/greedy.
Giảm tần suất full rebuild: nếu nghiệp vụ cho phép, replan theo sự kiện (đơn mới, SLA sắp trượt) thay vì fixed interval mọi chu kỳ.

Mục tiêu triển khai: giảm billable elements và API calls/tháng trước khi phải tăng ngân sách; sau đó mới quyết định kết hợp thêm phương án self-host phù hợp quy mô.

Ước tính chi phí sau khi áp dụng levers (tham chiếu)

Giả định mức cắt giảm số phần tử cần billable = f_matrix và giảm số lần full-build còn lại = f_frequency so với baseline cron 5 phút/cache hit 85% (Google ~28.6k–35.8k USD/tháng; HERE ~10.7k USD/tháng). Các tỷ lệ dưới đây mô tả 3 mức triển khai thường gặp để chốt ngân sách theo thứ tự độ lớn.

Kịch bản	Giả định cắt giảm	Google OPEX	HERE OPEX	Ghi chú
Conservative	f_matrix≈40%, f_frequency≈70% (≈28% baseline)	~8.0–10.0k USD/tháng	~3.0k USD/tháng	Triển khai từng bước, giảm rủi ro vận hành.
Base case	f_matrix≈25%, f_frequency≈50% (≈12.5% baseline)	~3.6–4.5k USD/tháng	~1.3k USD/tháng	Cân bằng SLA và kiểm soát chi phí.
Aggressive	f_matrix≈15%, f_frequency≈35% (≈5.25% baseline)	~1.5–1.9k USD/tháng	~0.6k USD/tháng	Kiến trúc tốt + sparse edges + event-driven replan.

Để “chốt ngân sách”, nên đo cache hit-rate, % cạnh cần tính thêm và tỷ lệ full-build còn lại trong 1–2 tuần vận hành đầu.

From delivery windows to routing OPEX: why the matrix is the investment focus

Honoring customer-chosen time windows requires a reliable drive-time and distance matrix on the road network for every pair of points you optimize. With scheduled replanning (e.g. every 5 minutes) to absorb new orders and protect on-time performance, billable matrix elements multiply by how often you rebuild — Distance Matrix / Matrix API OPEX can far exceed the cost of running an internal solver (e.g. OR-Tools) unless you treat the matrix as a first-class product layer.

The answer is not only “pick Google vs HERE”: it is architecture — coordinate-pair caching, incremental matrix updates when orders change, sensible batching, and at scale self-hosted OSRM to shift cost from variable per-request charges to predictable infrastructure.

Challenge: slot-based SLA + high replan frequency → large, repeated matrix demand.
Where to invest: a dedicated matrix service, cache hit-rate metrics, and billable-element accounting — the foundation of sustainable routing OPEX.
Evidence below: provider comparison; a ~47.7M elements/month scenario (one store, ~100 orders/slot, no cache); and a 50–85% cache-hit table for a 5-minute cron — showing order-of-magnitude differences.

Figures are directional for planning; actual spend follows each provider's current price list and contract.

VRP needs distance and time between the depot and orders (and often between orders). Real OPEX depends on how often you build the matrix, request batching, region, enterprise tiers, and pricing. The tables below are a comparison framework and illustrative scenarios — directional only, not a substitute for official vendor quotes.

Official pricing & billing references:

Google Maps Platform — Pricing · SKU details · Distance Matrix — Usage & billing
HERE — Pricing · Routing platform
OSRM (open source — no API list price; cost is deployment & operations)

Criteria	OSRM (open source)	Google Maps Platform	HERE
Business model	Self-host on your infrastructure; or public demo endpoints (rate-limited, not production-SLA).	Cloud SKUs (Distance Matrix, Routes, etc.), usage-based tiers.	Cloud plans; per transaction or enterprise commitment depending on contract.
Typical billable unit	Server, OSM data storage, ops (no per-internal-request list price).	Distance Matrix: often per element (origin–destination pair in the matrix).	Matrix / Routing: per transaction; one matrix request may count as multiple transactions.
Strengths for VRP	Controls variable cost at high volume; no per-call list price internally. Strong fit when self-hosted well.	Street network and global ETA footprint; Google ecosystem.	Enterprise location stack; common in fleet/logistics with support contracts.
Risks / limits	DevOps overhead; OSM updates; public endpoints rate-limited.	Cost scales quickly with large matrices or frequent replans; needs cache and batch design.	Clarify Matrix transaction counting; public list price may differ from Enterprise.
Illustrative public pricing	Single-region VPS/self-host: often tens–hundreds USD/month depending on CPU/RAM; public demo ~$0 but not for heavy production.	Distance Matrix (Essentials): commonly around ~$4–6 / 1,000 elements at typical tiers (volume discounts apply); free credits per Google policy (changes over time).	Many public tiers around ~$1–2 / 1,000 transactions after free tier (illustrative; Matrix may differ from Routing).

Illustrative scenario (same traffic assumption)

Assumption: 200,000 billable matrix elements per month (many matrix builds at medium problem size, after reasonable batching). Applying the reference rates above (typical tier, excluding tax and enterprise discounts):

Source	Illustrative variable OPEX	Notes
OSRM (small self-hosted cluster)	~$80–250/month infra + light ops	Scales with footprint; not linear in “200k elements” like SaaS.
Google (Distance Matrix, ~$5/1k elements)	~$1,000/month (200 × 5)	Volume tiers can reduce effective $/1k at high usage.
HERE (illustrative ~$1.5/1k transactions)	~$300/month (200 × 1.5)	Illustrative 1:1 mapping; HERE Matrix billing rules may differ — check billing docs.

Operational pattern: 5-minute cron, cache is mandatory

For slot-based delivery, planning only once per hour risks missing on-time windows when orders arrive mid-hour. A realistic pattern is replan every 5 minutes during an 8:00–21:00 shift (780 minutes) ⇒ 156 replans/day. Hence matrix caching is not optional at scale.

Scenario: one store, 8:00–21:00, 5-minute cron, ~100 orders per slot

Model: 13 one-hour delivery slots (8–9, …, 20–21), average 100 orders per slot to be served inside that slot. One VRP per slot on depot + 100 stops ⇒ a full matrix has 101 × 101 = 10,201 elements per build. With a 5-minute cron during 8:00-21:00: 156 runs/day, so daily volume is 156 × 10,201 = 1,591,356 elements; over 30 days: 47,740,680 elements/month (no cache).

Routing source	Illustrative variable OPEX / month	Rough calculation
Google Distance Matrix (no cache)	~$191,000–238,700/month	47,740,680 elements × ($4–5/1,000) at typical tier; higher tiers may reach ~$3/1k ⇒ ~$143,200/month.
HERE (transaction model)	~$71,600/month	Rough ~$1.5/1k transactions mapped to element scale: 47,741 × 1.5; HERE counts Matrix per its own rules — verify billing docs.
OSRM self-hosted	~$250–700/month infra + ops	Not per element; mostly servers for ~156 replans/day + periodic OSM updates.

Note: Excludes internal solver (OR-Tools), order storage, and 3PL. More intra-slot replans scale elements accordingly; coordinate-pair matrix cache can cut API OPEX dramatically.

Cache scenario (5-minute cron)

Formula: billable_elements = raw_elements × (1 - cache_hit_rate). Assumed rates: Google ~$4–5/1,000 elements; HERE ~$1.5/1,000 transactions (rough mapping).

Scale	Raw elements/month	Cache hit	Google (USD/month)	HERE (USD/month, rough)
100 orders/slot 101×101/run, 156 runs/day	47,740,680	50%	~95,481–119,352	~35,806
		70%	~57,289–71,611	~21,484
		85%	~28,644–35,806	~10,742

Directional takeaway: at large matrix volume and frequent replans, self-hosted OSRM often wins on total variable cost after infrastructure amortization; for fast launch and moderate volume, Google/HERE can make sense if requests and cache are optimized. Before locking budget, reconcile with current official pricing (links above) and vendor contract terms.

Cost-reduction levers when Google/HERE spend is too high

When matrix spend exceeds budget thresholds (for example >$10,000/month), the most effective response is to optimize how many billable elements you compute and how often you call premium APIs in the routing pipeline.

You do not always need a full N×N matrix: many pipelines only need depot → all stops plus a sparse graph for nearby stop pairs (filtered by Haversine/grid), then expand edges only when the solver needs them.
Incremental updates: when new orders arrive, add only the required rows/columns instead of rebuilding the full matrix every replan cycle.
Cluster and snap close points: orders in the same micro-area can be snapped to a shared node to reduce matrix size (with a configurable accuracy trade-off).
Use lower-cost prefiltering: Haversine or internal OSRM for candidate pruning, then call paid APIs only for a smaller edge set after clustering/greedy screening.
Reduce full rebuild frequency: where operations allow, trigger replans by events (new order, SLA-at-risk) instead of fixed full rebuilds on every interval.

Practical objective: cut billable elements and paid API calls/month first, then decide the right self-host and vendor mix for the next scale step.

Estimated matrix cost after applying levers (directional)

Assumptions: reduction in billable elements = f_matrix and remaining full-build frequency = f_frequency versus the baseline 5-minute cron/cache hit 85% (Google ~$28.6k–35.8k/month; HERE ~$10.7k/month). The percentages below represent three typical deployment levels for budgeting by order of magnitude.

Scenario	Assumed cut	Google OPEX	HERE OPEX	Notes
Conservative	f_matrix≈40%, f_frequency≈70% (≈28% baseline)	~$8.0–10.0k/month	~$3.0k/month	Phased rollout; reduced operational risk.
Base case	f_matrix≈25%, f_frequency≈50% (≈12.5% baseline)	~$3.6–4.5k/month	~$1.3k/month	Balanced SLA protection and cost control.
Aggressive	f_matrix≈15%, f_frequency≈35% (≈5.25% baseline)	~$1.5–1.9k/month	~$0.6k/month	Good architecture + sparse edges + event-driven replan.

To finalize budgeting, measure cache hit-rate, the % of additional edges required, and the remaining full-build share in the first 1–2 weeks.

Order ID	Time left (min)	Weight (kg)	Volume (dm3)	Trạng thái	Xe nội bộ	Quãng đường cạnh (km)	Tổng km chuyến	ETA (min)
6109	60	18	20	In-house wave 1	Xe 1 (lượt 1)	3.48	15.85	4 min
6131	60	3	22	In-house wave 1	Xe 1 (lượt 1)	5.80		15 min
6120	60	12	26	In-house wave 1	Xe 1 (lượt 1)	0.00		18 min
6117	55	12	13	In-house wave 1	Xe 1 (lượt 1)	0.00		25 min
6119	50	14	37	In-house wave 1	Xe 1 (lượt 1)	0.00		31 min
6105	20	15	30	In-house wave 1	Xe 2 (lượt 1)	3.54	7.06	4 min
6107	25	11	24	In-house wave 1	Xe 2 (lượt 1)	0.00		12 min
6121	60	21	15	In-house wave 1	Xe 2 (lượt 1)	0.00		16 min
6130	60	7	23	In-house wave 1	Xe 2 (lượt 1)	0.00		24 min
6092	60	17	9	In-house wave 1	Xe 2 (lượt 1)	0.00		27 min
6093	57	6	17	In-house wave 1	Xe 2 (lượt 1)	0.00		33 min
6132	25	8	10	In-house wave 1	Xe 3 (lượt 1)	3.45	7.13	5 min
6091	35	7	36	In-house wave 1	Xe 3 (lượt 1)	0.16		13 min
6104	60	22	16	In-house wave 1	Xe 3 (lượt 1)	0.06		20 min
6094	49	19	12	In-house wave 1	Xe 3 (lượt 1)	0.00		28 min
6123	60	11	46	In-house wave 1	Xe 3 (lượt 1)	0.00		34 min
6126	60	7	13	In-house wave 1	Xe 4 (lượt 1)	0.42	7.31	1 min
6108	60	21	30	In-house wave 1	Xe 4 (lượt 1)	3.36		9 min
6114	50	9	42	In-house wave 1	Xe 4 (lượt 1)	0.00		16 min
6113	60	18	21	In-house wave 1	Xe 4 (lượt 1)	0.00		19 min
6124	50	16	14	In-house wave 1	Xe 4 (lượt 1)	0.06		23 min
6128	60	16	39	In-house wave 1	Xe 5 (lượt 1)	0.42	0.85	1 min
6127	60	7	44	In-house wave 1	Xe 5 (lượt 1)	0.00		6 min
6125	60	21	26	In-house wave 1	Xe 5 (lượt 1)	0.00		10 min
6115	60	13	52	In-house wave 2	Xe 1 (lượt 2)	3.54	7.06	46 min
6112	60	22	51	In-house wave 2	Xe 1 (lượt 2)	0.00	7.06	49 min
6122	45	18	32	In-house wave 2	Xe 2 (lượt 2)	3.21	6.39	45 min
6110	60	4	40	In-house wave 2	Xe 2 (lượt 2)	0.00	6.39	53 min
6106	55	21	53	In-house wave 2	Xe 3 (lượt 2)	0.47	0.97	42 min
6111	60	10	52	In-house wave 2	Xe 4 (lượt 2)	3.07	15.47	39 min
6118	55	8	35	In-house wave 2	Xe 4 (lượt 2)	5.82	15.47	54 min
6129	35	5	54	In-house wave 2	Xe 5 (lượt 2)	3.54	15.97	19 min
6116	35	10	46	In-house wave 2	Xe 5 (lượt 2)	5.86	15.97	35 min
6090	15	8	31	3PL	-	-	-	8 min
6095	57	20	40	Deferred	-	-	-	-