ROUTING A VEHICLE WITH THE LIMITATION OF FUEL
Tetsuo Ichimori, Hiroaki Ishii, Toshio Nishida · Journal of the Operations Research Society of Japan · 1981
The paper considers the problem of routing a vehicle with the limitation of fuel. The optimal route is a shortest path along which a vehicle can pass through a network, visiting some refueling vertices on the way for fear of running out of fuel. An efficient algorithm for it is presented whose computational complexity is 0 (pn^2) where n is the number of vertices in a network and p is that of refueling vertices.