Consideration of the future availability of GBFS feeds, e.g. in car sharing routing

[tobsesHub]

Issue

Is your feature request related to a problem? Please describe.
The GBFS specification supports the representation of the availability of a vehicles.

In the GBFS standard, there are two options for representation:

• The vehicles[].available_until field in the vehicle_status.json, which provides the information, how long the current available vehicle is.
• the new extension, which offers an new file(vehicle_availability.json) , that contains from and until dates, representing a time window also for currently unavailable vehicles.

Unless I have missed something, OTP does not take such availability information into account when planning routes.

Goal / high level use-case
This is particularly interesting for the routing of car rentals. These often work in such a way that you can rent a car for a time slot in the future, e.g. on 25.04.12 from 10 am to 4 pm.
It would be very convenient for the user if the routing took this availability information into account.
In an optimal world, OTP would only select the vehicles in the routing that are available in the time window in which the user wants to drive a route.

I am not sure if this use case is really possible and would like to discuss it with you.

Describe the solution you'd like
Since I have done almost no implementation in the OTP source code, my solution could be completely wrong. So please give me feedback.

If this use case is possible, I would implement the vehicles[].available_until field first, as this is probably the less complex use case. Therefore I just considered this use case in the solution.

Getting the availability information:
We would probably need to add an availableUntil filed to the VehicleRentalVehicle class.

Routing:
I don't think there is any solution that can exclude vehicles that are not available with 100% certainty. Because while processing the edges and vertexes and deciding which rental vehicle to choose, we don't know how long the leg to the target will take.
Correct me, if I am wrong.

I was thinking of estimating the time at which the destination will be reached.
We could calculate Euclidean distance and the max speed to estimate the timestamp, when the driver will arrive and then compare whether the rental vehicle is available by that time.
This would only be a rough approximation and only a lower bound.
We could also add a buffer. However, this could lead to a false-positive exclusion of a rental vehicles. It would probably be difficult to find a good value for such a buffer.

I am not sure, where in the code must be extended for this solution.

• I was thinking of extending the conditions in the VehicleRentalEdge.traverse method and returning an empty state list if we assume the vehicle is not available.
• I was also thinking of creating a new SkipEdgeStrategy that skips an edge if it is a vehicle rental edge that is unlikely to be available.

Describe alternatives you've considered
Preference for vehicles that are available for a longer time window
This would not be an exclusion, but could increase the chance to take a vehicle, of taking a vehicle that is available.
In the code I was thinking about:
- Changing DominanceFunction. I guess, we would need to extend the Pareto implementation. I also suspect this would reduce the performance (considering another factor)
- Higher weight for vehicles, that are only available for a short time. I suspect, this would lead to balancing problems. I'm really uncomfortable with changing weights.

Additional context
I have not found a similar problem. I hope I haven't overlooked anything.

Conclusion
As you can see, I don't have a 100% solution. So I am not sure, is this is a good way, to extend the OTP.
I look forward to feedback and other thoughts.
Of course we can discuss about this topic in the OTP Developer Meeting or in the Gitter Chat if you prefer.

[t2gran]

We would probably need to add an availableUntil filed to the VehicleRentalVehicle class.

This is ok. But, you might need to duplicate the information for routing, because accessing this
information and processing it is probably not optimal. But, this depend on the solution.

However, this could lead to a false-positive exclusion of a rental vehicles. It would probably be
difficult to find a good value for such a buffer.

This is true. But, it might be the only solution that scales. This is similar to the fuel consumtion
problem.

I am not sure, where in the code must be extended for this solution.

First we need to agree on the startegy for this implementation. This is my thoughts on it:

1. Some of the main contributers to OTP must be willing to spend time on this(at least design/review
   time) - this is going to take time. If you @tobsesHub is going to implement this - witch I do
   support - then you need to find someone that is willing to guide you through the design and
   review process. Joining the Developer meetings or even product owner meeting is the best way
   to do this.
2. Filtering vehicles based on heuristics is a 90% solution and is fairly easy to implement.
   This is a natural first step - you will learn about the problem and the system, and provide short turn
   value for your project.
3. Support for "available-time" during street routing (A*) is a BIG task. This can not be done without
   involvement from the main contributters.
4. A cost based approach is not possible - this lead to fare bigger problems then appraoch 1. I vote
   agains this.
5. Implementing this using a separate criteria(dominance function/state) in A* must be done in phases.
   1. A POK should confirm that this scales and that the performance is "good enough".
   2. Evaluate the POK, and decide how to proceed.

[t2gran]

This is something that I think will be implemented in OTP - as @tobsesHub say, this is a key feature to support car-rental. This is also related to opening-hours for areas like parks and open public indoor spaces(closed at night).

[tobsesHub]

@t2gran thank you for your feedback.

I can attend the Developer meeting this week and show the use case.
Maybe than we can talk about how to continue with this issue, or at least I can make the issue better known.

[t2gran]

We discussed this is in detail in a developer meeting:

Use Case
We are unsure how this is going to be used in real life use-cases in travel planning, so it is better to make something simple - and get feedback, than doing something we are unsure of.

1. The most advanced implementation of this would involve adding "available reminding time" to the pareto criteria for the AStar search.
2. A simpler variant is just to make sure the vehicles is available in a time-window, when boarding it. The time-window can be set in the request or using some kind of heuristics/calculation.

Implementation steps

• Import availability information and attach it to the vehicle.
• Make a availability information available through the APIs.
• Support availability in direct routing by only boarding vehicles witch are available in a fixed time-window(earliest-depature-time to +6h ?).
• Add time-window(as Duration) for availability to the routing API. The window should be relative to the earliest-departure-time/latest-arrival-time.
• Analyze to se what we should do next.

Notes
We also discussed if we should add a "constrained" parameter to the pareto-criteria to avoid constrained paths dominate unconstrained paths - this could potentially also be used for opening-hours for OSM street elements.