Oh ... I misread @karussell to start with, and thought he meant something else. I now think we're talking about the same thing = ) Oh well, I'll post this anyway if it's helpful.
I wonder if you can use a custom energy consumption weighting. This solves one of your problems (minimising energy consumption), and you can tweak it further to handle the main one (requiring stops at charging stations). To get round this, I'd look at tweaking the weighting/algorithm so that it also includes a (dynamic) 'maximum consumption-distance until next charge' (MCDUNC). Assuming you start fully charged, this might be e.g. 100kwh. So you start routing, and at each step, you
- increment the consumption weight by Xkwh
- decrement the MCDUNC by Xkwh
- if MCDUNC goes below zero, stop
- if you pass a charging station:
- assume you stop at it - if you don't make this assumption you'll need to fork here and consider both possibilities (whether you charged or not) afterward which, I think, might get tricky.
- add a penalty (as it takes time to wait and charge). This should be based on the charge left in the car (which you can get from the MCDUNC) as e.g. a full car takes longer to charge than a partially charged on.
- assume you charge fully, and hence set MCDUNC to current consumption-distance + maximum car charge (e.g. 100kwh from above).
This should find you a route (or that none are available). The issue is that you're stopping at every charging station, when you might not need to. To get round this, I'd simply post-process the final route to remove 'unnecessary' charging stations. (And it's not a bad thing to have extra charging stations on your route which are unused - they're a good back up e.g. if you take a detour.) I'm not sure, but I think this should get pretty close to a good solution - it should find feasible routes, and if multiple are available, it should find the 'best' one (which depends on your definition of 'best': charge more often, drive further, etc.).
Some other things:
- you may need to keep multiple weights so you can e.g. balance consumption and time taken.
- you could allow users to configure their own starting charge - e.g. I might be nearly empty when I start, so need to go to a charging station immediately.
- it's probably a more realistic solution than e.g. requiring a charge every Xkm (as X is not constant and depends on the route).
- you could eventually add more constraints - e.g. allowing the user to fill only half-way at the last charging station if they're in a rush, etc.
- initially you could assume energy consumption only depends on distance, and hence just talk about range in km as opposed to kwh. It'd just simplify things and e.g. in flat cities, may be sufficient.