search

blegat / ContractionHierarchies.jl

Contraction Hierarchies shortest path for OpenStreetMap
2 stars 0 forks source link

Increase in routing perfomance over a standard OpenStreetMapX.jl implementation is only 10% #3

Open pszufe opened 8 months ago

pszufe commented 8 months ago

I have had my student to run a benchmark of this code. While the papers claim that CH provides several orders of magnitude larger performance (like 1000x), here the improvement seems to be only 10%. Do you have any idea why this could be happening?

using BenchmarkTools, OpenStreetMapX
# I downloaded just the repo
include("ContractionHierarchies.jl/src/ContractionHierarchies.jl")

hmap = ContractionHierarchies.HierarchicalMap()
ContractionHierarchies.add_map(hmap,"europe","lithuania")

vanila_alg = get_map_data(raw"ContractionHierarchies.jl\data\europe\lithuania\local.osm.pbf");

local_src = ContractionHierarchies.local_node(hmap, LLA(56.029,21.182))
local_dst = ContractionHierarchies.local_node(hmap, LLA(54.085, 24.631))

The benchmarks look like this:

julia> @btime ContractionHierarchies.shortest_time(hmap, local_src => local_dst)
  363.060 ms (1095 allocations: 196.05 MiB)
14508.10548045409

julia> @btime OpenStreetMapX.fastest_route(vanila_alg,local_src.node, local_dst.node)
  392.500 ms (130 allocations: 97.96 MiB)
([1042563717, 1808547120, 2359284321, 1042563670, 1042563587, 1042563728, 8239734199, 281071174, 11432462077, 11432462073  …  4255203033, 3633328331, 36165820, 36165981, 36166239, 2301230201, 2301230192, 3633327823, 2301230167, 3633327818], 368404.4079332626, 14508.105480454087)

This definitely not expected (this is a long route from one edge to another of Lithuania). Do you have any idea why this is happening?