Differences between 1:1 and m:n in CostMatrix

I recently noticed that results for a given connection pair in CostMatrix can differ based on the overall request constellation. Using a sample data set including 38 gas stations in Cologne (~1400 location pairs), I found that the results were different for about ~3% of location pairs between 1) computing a 1:1 matrix for a location pair and 2) just sending all locations with one request.

When setting the A* cost factor to 0 (i.e. making it behave like Dijkstra), I get none of those differences, which leads me to believe something is wrong with the A* logic.

After lots of head scratching, I've determined two underlying issues so far:

1. the way we determine the A* heuristic: the current logic uses the A* heuristic of the unfound target that's closest to the source we're expanding from. The issue I see is that we seem to mark a target as found once a path to it is first found. We still allow finding better connections to that target, but it's unlikely we will if the A* heuristic for that target is ignored and no longer informs the expansion.

2. the hierarchy limits: currently, we allow downward transitions based on the amount of downward transitions we've done already, so we might exhaust all our available transitions while expanding towards the first few targets, but eventually run out of transitions.

Fixing both of these issues means more expansion, but we should prioritize correctness over performance, and while differences between route and matrix are difficult to avoid, we should try to get rid of these diffs.