Illustrating local pruning issue in original paper

[Catatomik]

local pruning issue in original paper

Problem

local pruning should work fine, but its implementation in Algorithm 1: RAPTOR seems bad so it doesn't work properly.
Indeed, line 18, the check is only done by comparing the arrival time with τ* and not t_k (which is expected) ; but τ* isn't updated when checking for foot-paths, τ_k is the only one assigned.
So back to the comparison line 18, paths found thanks to foot-paths aren't taken into account.
This eventually leads to cyclic paths, and produces wrong shortest paths.

Source : RAPTOR.

Solution

Remove local pruning improvment.

Illustrating

Branch no-local-pruning shows a version of RAPTOR without any local pruning upgrade, theoretically working.
Branches test-bibm and test-bibm-no-local-pruning implement tests based on BIBM data, demonstrating the issue.