Routing with Fueling Stops

[dburnsii]

Looked around but didn't see an implemented application of this, but it would be useful to implement fueling stops for long routes (i.e. cross-country). I've thought of a couple ways to do this efficiently, and I'm sure there are some great algorithms out there, but I just wanted to see if this has been implemented already.

[danpat]

@dburnsii OSRM is specifically built to solve the Shortest Path Problem.

Fuel consumption isn't a consideration in the current algorithm. Calculating a path with optimum refueling falls more into the Vehicle Routing Problem class of combinatorial constraint problems.

The OR-Tools example library has a sample of how to set up a refueling scenario here: https://github.com/google/or-tools/blob/stable/examples/cpp/cvrptw_with_refueling.cc

What you'd need is a travel time matrix (which OSRM can generate) between all your locations (including possible refueling stations) - the VRP solver will then find the shortest way to get from your source to the destination, avoiding running out of fuel, and minimizing detours.

[dburnsii]

Fair enough, thank you for that resource, that could definitely solve my problem. But would a feature like this really be out of the scope of OSRM? With the number of applications for this out there, I feel like it could really add value to the project. Since there's already a decently well defined algorithm for solving this problem, it doesn't seem like a huge project to implement.

[danpat]

@dburnsii Just because it's decently defined doesn't mean it's fast :-)

The combinatorial nature of VRP means that finding exact answers is virtually impossible, and finding good answers takes time. It's a very different family of algorithms to the SPP that OSRM optimizes for. Just compare the size of the or-tools codebase and you'll get an idea of the depth in that problem space.

OSRM has a very simple VRP solver (not capable of solving the refueling problem) built in, but any more complex capability there would be a fairly significant time investment.

The usual workflow for a problem like this is to:

1. Use OSRM's /table plugin to generate a travel time matrix between all points in your problem (there are 160,000-ish gas stations in the US, so this is a large problem to solve).
2. Setup the VRP solver model, and get a solution out of it.
3. Use OSRM's /viaroute to return the final route geometry based on the ordered waypoints the VRP solver gives you

[dburnsii]

Sounds like a solid solution, I'll definitely be looking into it. Thanks for pointing me in the right direction!

[wangyoucao577]

@dburnsii OSRM is specifically built to solve the Shortest Path Problem.

Fuel consumption isn't a consideration in the current algorithm. Calculating a path with optimum refueling falls more into the Vehicle Routing Problem class of combinatorial constraint problems.

The OR-Tools example library has a sample of how to set up a refueling scenario here: https://github.com/google/or-tools/blob/stable/examples/cpp/cvrptw_with_refueling.cc

What you'd need is a travel time matrix (which OSRM can generate) between all your locations (including possible refueling stations) - the VRP solver will then find the shortest way to get from your source to the destination, avoiding running out of fuel, and minimizing detours.

Hi @danpat, After read the resources, I feel like the VRP solver solves the problem which expect to visit all nodes. But routing with fueling stops will expect to pick up the best one or several fueling stops along the route(origin-destination) due to current fueling is insufficient to reach the destination, and ignore other huge possible fueling stops. They seems have very different targets. Maybe I doesn't understand it well...

[danpat]

The OR-Tools example isn't a perfect match to your problem, but it does allow "skipping" of nodes if the cost of visiting them is too high, see line 154. If you change that code so the cost for skipping refueling nodes is 0, and infinity (or very large) for delivery nodes, then the solver would drop all refueling stops except those needed to complete the drive (as refueling nodes are the only ones which can restore a vehicle's fuel capacity).

[dburnsii]

As an update, I have a working solution, but it is more computationally intensive that the shortest path by a significant margin. The steps are as follows:

1. Generate a table for distances between all fueling stops (This only has to be done once and can be cached. Only has to update when stops are added or removed).
2. Generate a table from the origin to every stop.
3. Generate a table from every stop to the destination.
4. Insert the generated values (for origin and destination) into the original table.
5. Filter the table for acceptable values considering the range of the vehicle in question.
6. Run Dijkstra's on that table.
7. Route from Origin, to each of the waypoints, to the destination to get the final route with fueling stops.

I was also able to create a secondary table that used the duration rather than the distance, but still filtered based on the distance, so that the fastest route could still be calculated but only using paths that are short enough for the vehicle to traverse. More work to be done to account for things like elevation changes, traffic, weather, etc. but that's all beyond the scope of this issue.

[danpat]

Hmm, you're right, I was probably over-complicating the situations. Here's a simplified version of your approach.

1. Generate a full table including your origin, destination, and all stops (OSRM should be able to do this quickly).
2. Use the table as a dense graph (everything is connected to everything), run Dijkstra on it directly.

You'd want to modify Dijkstra to track not just the elapsed time (for shortest time routing), but the remaining fuel capacity at each node, resetting it to the maximum each time you visit a refueling station, and not following edges to nodes that are beyond the capacity of the vehicle. This would also allow for extra waypoints to be injected that don't refuel the vehicle.