Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.42k stars 3.4k forks source link

POC of one-to-many bidirectional routing in map-matching #7009

Open SiarheiFedartsou opened 3 months ago

SiarheiFedartsou commented 3 months ago

Issue

What issue is this PR targeting? If there is no issue that addresses the problem, please open a corresponding issue and link it here.

Please read our documentation on release and version management. If your PR is still work in progress please attach the relevant label.

Tasklist

Requirements / Relations

Link any requirements here. Other pull requests this PR is based on?

Benchmark Results

| Benchmark | Base | PR | |-----------|------|----| | osrm_contract | Time: 184.58s Peak RAM: 191.12MB | Time: 184.61s Peak RAM: 191.06MB | | osrm_customize | Time: 2.52s Peak RAM: 111.68MB | Time: 2.52s Peak RAM: 111.68MB | | osrm_extract | Time: 24.10s Peak RAM: 399.42MB | Time: 24.17s Peak RAM: 400.31MB | | osrm_partition | Time: 5.89s Peak RAM: 121.34MB | Time: 5.89s Peak RAM: 121.17MB | | random_match_mld | 500 matches, default radius
ops: 204.88 ± 0.60 ops/s. best: 205.40ops/s.
total: 278.21 ± 0.83ms. best: 277.51ms.
avg: 4.88 ± 0.01ms
min: 0.21 ± 0.00ms
max: 27.10 ± 0.05ms
p99: 27.10 ± 0.05ms

500 matches, radius=10
ops: 72.86 ± 0.06 ops/s. best: 72.95ops/s.
total: 878.44 ± 0.66ms. best: 877.35ms.
avg: 13.73 ± 0.01ms
min: 0.24 ± 0.00ms
max: 162.66 ± 0.15ms
p99: 162.66 ± 0.15ms

500 matches, radius=20
ops: 15.34 ± 0.01 ops/s. best: 15.36ops/s.
total: 4236.04 ± 2.29ms. best: 4232.57ms.
avg: 65.17 ± 0.04ms
min: 0.29 ± 0.00ms
max: 846.10 ± 0.95ms
p99: 846.10 ± 0.95ms

Peak RAM: 51.500MB | 500 matches, default radius
ops: 210.04 ± 0.63 ops/s. best: 210.53ops/s.
total: 271.38 ± 0.82ms. best: 270.75ms.
avg: 4.76 ± 0.01ms
min: 0.24 ± 0.01ms
max: 27.61 ± 0.02ms
p99: 27.61 ± 0.02ms

500 matches, radius=10
ops: 72.06 ± 0.64 ops/s. best: 73.75ops/s.
total: 888.21 ± 7.76ms. best: 867.75ms.
avg: 13.88 ± 0.12ms
min: 0.34 ± 0.01ms
max: 179.37 ± 0.23ms
p99: 179.37 ± 0.23ms

500 matches, radius=20
ops: 14.34 ± 0.09 ops/s. best: 14.57ops/s.
total: 4532.92 ± 27.07ms. best: 4461.05ms.
avg: 69.74 ± 0.42ms
min: 0.44 ± 0.01ms
max: 1016.15 ± 1.07ms
p99: 1016.15 ± 1.07ms

Peak RAM: 63.500MB |