Consider Battery Status for Vehicle Rental Routing

[UserX20]

Is your feature request related to a problem? Please describe.

If a vehicle, for example an E-scooter, was to be rented it was possible for this vehicle to have had not enough remaining power to complete the entire trip.
In this case you would probably want to use a different scooter, which has enough remaining energy.

Describe the solution you'd like

Use the currentRangeMeters field of the GBFS-Feed Vehicles to check if the vehicle can complete the distance, if no currentRangeMeters are available the battery status is not considered and the usual routing is done

Additional context

GBFS-Standard: https://github.com/MobilityData/gbfs/blob/v2.3/gbfs.md#free_bike_statusjson
The field is: current_range_meters

[t2gran]

The solution suggested does not work - the distance is not known before the search is done, and the reminding distance change for every scooter. The solution is to let scooters with a longer reach dominate during the search. We can compute an estimate for the total distance and use it during the search, but there is no point in making the algorithm more precise than the "weakest" link.

Note, the the range is also probably not exact, so having a very accurate implementation would be slow - but in practise not improve the search much. The reach vary depending on the elevation, so an estimation of the reminding distance using "line-of-sight" is also inaccurate. In some cases it will be better to use two scooters to get to the destination in stead of one - if the combined walk distance is much shorter. So, I would normalize the reach(x) down to e.g. f(x)=[too-low, 1 .. N, sufficient]. The N should be a smal number like 3-5. This will make sure that not every scooter along the way fork the search space. The function f(x) should depend on the line-of-sight and possible an estimate for the elevation.

[UserX20]

The solution suggested does not work - the distance is not known before the search is done, and the reminding distance change for every scooter. The solution is to let scooters with a longer reach dominate during the search. We can compute an estimate for the total distance and use it during the search, but there is no point in making the algorithm more precise than the "weakest" link.

Note, the the range is also probably not exact, so having a very accurate implementation would be slow - but in practise not improve the search much. The reach vary depending on the elevation, so an estimation of the reminding distance using "line-of-sight" is also inaccurate. In some cases it will be better to use two scooters to get to the destination in stead of one - if the combined walk distance is much shorter. So, I would normalize the reach(x) down to e.g. f(x)=[too-low, 1 .. N, sufficient]. The N should be a smal number like 3-5. This will make sure that not every scooter along the way fork the search space. The function f(x) should depend on the line-of-sight and possible an estimate for the elevation.

Arguably my suggested solution is also a bit lackluster in terms of actual suggestions. Sorry about that.
I will try to explain it in more depth here, as our idea is what was implemented in the current PR. Please correct me if any of this should be in a comment in the PR instead of the issue.

The idea was to use the currentRangeMeters field of the GBFS-Feed Vehicles to check if the vehicle can complete the distance and if no currentRangeMeters are available the battery status is not considered and the usual routing is done. As mentioned the distance is not known before the search is done - to circumvent this issue the battery is checked while iterating through the AStar-Algorithm, after every iterated edge. Every edge has a length and with that it's possible to calculate if the vehicles battery is enough to traverse this edge, if not that branch is stopped.
In our PR we implemented this by adding traversedBatteryMeters and the currentRangeMeters (Note: currentRangeMeters are of a constant value during Routing, as they should only change if a vehicle is actually driven) to a State and using a SkipEdgeStrategy to check if the traversedBatteryMeters were more than the currentRangeMetersand if yes, stop that branch going back to the backState.

The note the range might not be exact is a good Point and one we have not really considered. And how precise this value is could also vary strongly between providers. Based on that it might make sense to make sure this can be deactivated.
Of course our current implementation would fall under the accurate, but slower part. It also does not offer the ability to use two scooters in the same routing, which I agree would make sense in some cases.

[t2gran]

Thank you for the answer, I added this to the agenda of tomorrows meeting - there are things here witch is not clear to me, but maybe there are someone in the meeting that knows OTP well witch can answer. I would like to know?

• Supporting only one scooter is probably ok.
• Degrading performence/mem-usage for none scooter search?
• Turn on/off feature?
• Normalizing the range
• Branch explosion, when traveling closer to the goal by foot it is likely that new scooters will have a longer range, but higher generalized-cost and time.
• Alternative might be good enough: Only consider the range when the scooter is picked up. The reminding distance can be estimated.

[t2gran]

Please correct me if any of this should be in a comment in the PR instead of the issue.

This is the right place - we should agree on an algorithm - analysis and design independent of the implementation.

Every edge has a length and with that it's possible to calculate if the vehicles battery is enough to traverse this edge, if not that branch is stopped.

Do you back-track or drop the path? Note! Dropping the path is algorithmically incorrect - not acceptable.

As fare as I can see from the implementation the currentRangeMeters is not used to compare states - only to abort the search (skip edge strategy). Is this correct? If you pick up two scooters early on and they both reach the same place the "fastest/lowest cost" wins. But, the other path might be the only one with enough battery to reach the destination.

[UserX20]

Do you back-track or drop the path? Note! Dropping the path is algorithmically incorrect - not acceptable.

I'm not entirely sure what the differences between back-tracking and just dropping the path are to be honest. I assume back-tracking means once we notice the explored path is not desirable and we return to a previous branching point / backstate our explored path is saved? While dropping means the explored path from the last branching point / backstate is not saved and will no longer be considered in the routing no matter what? Is that correct?
We use the SkipEdgeStrategy Interface, once it's determined the battery is not enough to complete the currently explored path, we return to the backstate and the search continues from the last vertex, if possible. I'm not entirely sure if that rejected path is then saved or not.
In the AStar the SkipEdgeStrategy is implemented here and if I read it correctly skips over it's iteration of the traversal results.
Does this constitute back-tracking?

[UserX20]

As fare as I can see from the implementation the currentRangeMeters is not used to compare states - only to abort the search (skip edge strategy). Is this correct?

Yes in the current implementation no two different states (except of course the current state and the back state) are compared with each other. We only use the states to save two variables and compare those two variables with each other in the skip edge strategy.

If you pick up two scooters early on and they both reach the same place the "fastest/lowest cost" wins. But, the other path might be the only one with enough battery to reach the destination.

If a scooter ends up not having enough battery to reach the destination, it should iterate through the backstates until it's back at the point of pickup of the scooter and then go looking for a different one. If no scooters with enough battery to complete the trip are available it will still pick up a scooter and use it until the battery runs out and then walks the rest of the way.

I just now realized that this behavior might lead to an issue where e.g. at the beginning of a route (let's say a 3km route) a scooter is available (after maybe 250m) which barely does not have enough remaining battery (it can traverse 2,5km still). Then the current implementation should still go looking for different scooters and if it finds one (there is one 1,5km away) which has enough battery it might use this one instead (now the user has to walk 1,5km instead of just the 500m).
I have not tested for this yet, which would be a bit difficult to do too. But this would not be a desirable behavior. Could this be an issue that might happen?

[t2gran]

Sorry, for not being 100% clear - I don´t know the implementation too well. I will address this issue in tomorrows developer meeting again.

 For limiting purposes it is preferable to {@link SearchTerminationStrategy} as it only terminates
 the current path, but continues searching along other paths until they also are terminated.
(JavaDoc SkipEdgeStrategy)

If I understand the JavaDoc right, then you can not use the SkipEdgeStrategy to terminate the path in this case. You can only use it on criteria that is part of the search dominance function. Hopefully there are someone who can anser this on tomorrows meeting. @abyrd said he should look into it, but he will probably not be present before Tuesday next week. (Setting a max-limit has side-effects, but that is not relevant here - the JavaDoc should be updated).

Could this be an issue that might happen?

Yes, that is part of what I am trying to understand. You can forget about the back-tracking, after giving it a though I do not think there are any way to implement it witch does not consumes a lot of memory, you would need to store all traversed paths in memory and that is not feasible. You would also need to reevaluate paths dropped when compared with the terminated path. The "correct way" to do this is to fork the state for each scooter you pick up and include the remindingRange in the dominance function making it a pareto criteria. But, that is likely to slow down the search exponentially (in some cases the search get 10 times slower) - that is not acceptable.

[UserX20]

@abyrd said he should look into it, but he will probably not be present before Tuesday next week

FYI, I will also not be able to attend the next two weeks, as I'm on vacation.

[t2gran]

I talked to Andrew today, to make the search valid, you need to add the remindingBatteryRange to the dominance function. If you do, you will be able to measure the performance impact. If you want we can also discuss other alternatives. We can continue the discussion when you are back.

[UserX20]

If I understand the JavaDoc right, then you can not use the SkipEdgeStrategy to terminate the path in this case. You can only use it on criteria that is part of the search dominance function

Why can the SkipEdgeStrategy only be used on criteria used in the dominance function? And does that mean we would need to add a specific dominance function like the leastWalk class? Or would it just needed to be added to one of the dominance functions? Sorry, I didn't fully understand the DominanceFunctions when looking at them.

[t2gran]

If you terminate a path because of a criteria not part of the dominance-function, then that path might have dominated other paths on its way - witch in this case had more battery and could have reached the destination. Adding this to the dominance function is likely to not scale - my guess is that it can slow down the search by 5-10 times.

Feel free to call in to the developer meeting to ask for a strategy on implementing this. By the way this is the same problem as the maxWalkDistance discussed many times in the old mailing lists: For example here: https://groups.google.com/g/opentripplanner-dev/c/cncCkcVY8Dc/m/fnxX5jtUCgAJ
https://groups.google.com/g/opentripplanner-dev/c/jp9hNVgQYRw/m/Wm_wMp6i5SQJ

[UserX20]

So if we were to use SkipEdgeStrategy, the remaining battery would have to be added to the dominance function, ideally as a Pareto-criteria, but it would likely be much slower anyways. But if it were to implemented that way, the performance impact could be measured. If that result is the expected one (i.e.5-10 slower) we could confidently say that this solution doesn't work and look for another one. If the performance impact turned out to be smaller than expected however the solution could be deemed viable? Just to make sure I properly understood.

Given all that is correct, how would the Pareto dominance function be called? Currently none of the methods setting dominance functions select the Pareto one, in the getPaths-method in the GraphPathFinder for example the dominance function is set to weight. Would a simple if (mode includes renting) {set dominance function to Pareto} else {leave as is} do in that situation?

Sorry for leaving this unattended so long btw

[t2gran]

You should not use the SkipEdgeStrategy. I would consider other solutions, like checking for enough battery when boarding the scooter. I can not provide any guidance on the implementation, ask in the dev-meeting or in the gitter channel.