Resource Constrained Routing with Refueling

Question

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling refueling gives me some headaches.

The reason why I'm asking is because with the growing success of electric vehicles in presence of a still underdeveloped infrastructure for recharging stations, that kind of route calculation is important for either deciding, whether it is possible to come from $A$ to $B$ and if so, which route to take in order to optimize a secondary criterion such as length or time.

So far I found the The Aircraft Routing Problem with Refueling, that addresses the subject, but apart from that, not much seems to be available.

What I am looking for are articles with either formulations as a network-flow problem or as a breadth-first search in a Dijkstra fashion and a focus on practical applicability.

Answer 1

Here are three sources. The 2nd paper is recent (2012) and its literature review may be helpful. The 3rd is a 2013 PhD dissertation that incorporates traffic congestion.

(1) Lin, Shieu-Hong. "Finding optimal refueling policies in transportation networks." In Algorithmic aspects in information and management, pp. 280-291. Springer Berlin Heidelberg, 2008. (PDF download.)

"we can then (i) determine all-pairs optimal ($k$-stop-bounded) refueling policies given various initial fuel levels at the vertices and ending with a fuel level at least at the lower limit $L$ in $O(n^3)$ time, and (ii) determine an optimal refueling policy given a pair of vertices, an initial fuel level, and a required minimal final fuel level in $O(n^2)$ time."

---

(2) Sweda, Timothy M., and Diego Klabjan. "Finding minimum-cost paths for electric vehicles." In Electric Vehicle Conference (IEVC), 2012 IEEE International, pp. 1-4. IEEE, 2012. (PDF download.)

"In this paper, the problem of finding a minimum-cost path for an EV [Electric Vehicle] when the vehicle must recharge along the way is modeled as a dynamic program. It is proven that the optimal control and state space are discrete under mild assumptions, and two different solution methods are presented."

---

(3) Fontana, Matthew William. "Optimal routes for electric vehicles facing uncertainty, congestion, and energy constraints." PhD diss., Massachusetts Institute of Technology, 2013. (MIT link.)

"We develop an energy model, an optimization-based formulation using robust optimization, and algorithms to quickly find good routes for battery electric vehicles. The combination of using robust optimization, the A-Star algorithm to find shortest paths, and Lagrangian relaxation allows us to solve the problem in seconds or less."