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.
local pruningissue in original paperProblem
local pruningshould work fine, but its implementation inAlgorithm 1: RAPTORseems bad so it doesn't work properly.Indeed, line
18, the check is only done by comparing the arrival time withτ*and nott_k(which is expected) ; butτ*isn't updated when checking for foot-paths,τ_kis 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 pruningimprovment.Illustrating
Branch no-local-pruning shows a version of RAPTOR without any
local pruningupgrade, theoretically working.Branches test-bibm and test-bibm-no-local-pruning implement tests based on BIBM data, demonstrating the issue.