search

e-VRO / frvcpy

A solver for the fixed route vehicle charging problem
Apache License 2.0
18 stars 5 forks source link

Improvement of the algorithm to find the optimal route. #4

Closed lhoupert closed 3 years ago

lhoupert commented 3 years ago

Is there a way to adapt the solver so it find by itself the optimal route minimizing the total travel time, instead of giving as input argument a fixed route ?

Or do you think it would need to be another package?

nkullman commented 3 years ago

The short answer to your question is that this would be better as a separate package.

What you're describing is quite a challenging EV routing problem (E-VRP). There has been some research into solving these problems, but the solutions generally aren't "packageable." For an example, see this paper. You'd basically want to implement Section 4.3 (just ignoring the part about uncertainty at the charging stations). The general idea is that you iterate over customer sequences (the "master problem"), and for each one, you use frvcpy to determine how long it would take to do energy feasibly (the "subproblem"). Obviously, iterating over all customer sequences is impossible to do via brute force, which is why we use some tricks in that paper (e.g., Benders Decomposition) to speed up the process.

That said, if you produced a package that solved E-VRPs, I think the community would be quite excited.

Since we're not planning to pursue this extension to frvcpy, I'm going to go ahead and close this issue.

lhoupert commented 3 years ago

Thank you for sharing your article, I will look in details the method you used.