Landmark approximation calculation

Open Source Routing Engine
1

Hello,

in the calculation of the landmark approximation,

int fromWeightInt = activeFromIntWeights[activeLMIdx] - (lms.getFromWeight(landmarkIndex, node) + virtEdgeWeightInt);
int toWeightInt = lms.getToWeight(landmarkIndex, node) - activeToIntWeights[activeLMIdx];
if (reverse) {
                fromWeightInt = -fromWeightInt;
                // we need virtEntryWeight for the minuend
                toWeightInt = -toWeightInt - virtEdgeWeightInt;
 } else {
                toWeightInt -= virtEdgeWeightInt;

the virtualedgeweight ist always subtracted from the toWeightInt, but once you flip the sign with reverse, it is added (positively) to the fromWeightInt. As these two should be lower bounds of the distance, in my opinion the virtualEdgeWeight should not contribute with a positive sign as it might lead to an overestimate.
What is the reason for this behavior?

Cheers,
Hendrik

2

Will have to think this through again and it might be a bug but it’ll probably occur seldom or even never especially as the virtual edge weight is much smaller than the total weight.

There are likely improvements possible and it would be really great to get this faster, so thanks for taking care of it :slight_smile: !

Probably the code in the following is more clear and is this what you meant?

if (reverse) {
    fromWeightInt = lms.getFromWeight(landmarkIndex, node) - activeFromIntWeights[activeLMIdx] + virtEdgeWeightInt;
    // your suggestion?
    // fromWeightInt = lms.getFromWeight(landmarkIndex, node) - activeFromIntWeights[activeLMIdx] - virtEdgeWeightInt;
    toWeightInt = activeToIntWeights[activeLMIdx] - lms.getToWeight(landmarkIndex, node) - virtEdgeWeightInt;
} else {
    fromWeightInt = activeFromIntWeights[activeLMIdx] - lms.getFromWeight(landmarkIndex, node) - virtEdgeWeightInt;
    toWeightInt = lms.getToWeight(landmarkIndex, node) - activeToIntWeights[activeLMIdx] - virtEdgeWeightInt;
}

BTW: would be interested to get your feedback about this new branch: Flexible Vehicle Profiles