Routing Algorithms with Range Restriction in Sparse Supply Networks. Issue 2 (June 2013) - Kämpke, Thomas
Shortest paths are computed for vehicles with comparatively small maximum range so that they must refuel, recharge or change batteries along a single trip in a road network. Heuristic solutions are given as well as exact algorithms. For sparse networks of service stations, shortest paths within these subnetworks serve as core paths. Extensions from the origin and towards the destination then yield overall shortest paths. Preprocessing shortest paths in sparse subnetworks allows computational speed-up. Parametric problem versions are dealt with by simultaneously minimizing overall path length and minimizing the length of the longest arc in use.