1
$\begingroup$

I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers.

  • A graph with Vertices representing charges and Edges representing distances among them is provided
  • Assume that car drives at constant speed (ex. 80 mph) and has a fixed maximum mile Range when its fully charged (ex. 300 miles)
  • Each charger has a rate associated with it given in miles/minute (how many miles are added for a minute of charging)
  • Goal is to go from charger A to charger B in minimum amount of time. Assume car is fully charged when you start.
  • You can stop at multiple chargers on the way and charge the car. You don't have to fully-charge the car at all chargers. You can decide how much time to spend at these chargers
  • At any point of time remaining range of the car must stay above 0

Output

  • Find minimum time path between A and B
  • List of chargers you will visit starting from A and ending at B.
  • Time spent charging at each of these chargers
  • Total travel time in minutes

I tried a solution using Dijsktra's shortest path algorithm, but does not fully solve the problem. I don't need help with coding. I don't need help with coding. I want some insights on how to design the algorithm.

Improve this question
$\endgroup$
8
  • $\begingroup$ We had questions about similar problems twice (helicopter and tourist) and no one proved that it is solvable in poly-time. $\endgroup$
    – rus9384
    Commented Sep 22, 2017 at 18:53
  • $\begingroup$ Any feasible method of computing this which is non-polynomial? If number of nodes are not too large, we might be able to get away with an exponential solution. $\endgroup$
    – Punit Soni
    Commented Sep 22, 2017 at 20:10
  • $\begingroup$ Well, the question asked dynamic programming, so, it is almost surely exponenetial. $\endgroup$
    – rus9384
    Commented Sep 22, 2017 at 20:47
  • $\begingroup$ Cross-post: stackoverflow.com/questions/46371070/… $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Sep 22, 2017 at 22:25
  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Commented Sep 22, 2017 at 22:50

1 Answer 1

Reset to default
1
$\begingroup$

This can be done in polynomial time.

I'm assuming:

  • All our your nodes are charging stations. If not, you can create a new graph that consists of only charging-stations (including start/finish) by finding the all-pairs shortest paths (or just running Dijkstra's multiple times)
  • The time spent charging is proportional to the distance driven. If there are eg. paths that are shorter but require larger charges, the problem becomes much more difficult.

The optimal method will be to drive as far as you can on one charge, then fill up your battery only barely enough to make it to the next charging station. You can do this by adding weight to each edge $\overline{AB}$ equal to the time needed to wait at $A$ while charging, taking into account the battery's initial charge.

We'll do this by altering Djikstra's algorithm. We need to make two changes to the algorithm

  1. In addition to giving each node a TentativeDistance, also assign it a CurrentBatteryLevel. This will be the battery level when reaching the node, before doing any charging. Set it to full for the initial node.
  2. When expanding the current node and calculating the tentative distance to a neighbor-node, add to the edge-weight the amount of time that will need to be spent charging. If there is enough charge to make it there, this will be 0, and the potential CurrentBatteryLevel for the neighbor-node will be >= 0. If there is not, it will be the time required to charge the battery enough so that, when you make it there, CurrentBatteryLevel will be 0.

This works because we're still guaranteed to have found the shortest path to a node when expanding it. This is true because there are no longer paths with shorter charging times, and we're only altering outgoing edges when expanding nodes (never incoming edges), so the assumptions of Dijkstra's algorithm still hold.

Also, since we only increase edge-weights, never decrease, if you have a heuristic you can still use A*. It must consistent, since our algorithm breaks if we need to expand nodes multiple times.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.