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.
ArtmeierA.HaselmayrJ.LeuckerM., and SachenbacherM., The optimal routing problem in the context of battery-powered electric vehicles, Advances in Artificial Intelligence, Springer, Berlin, 2010, 309–316.
Van KeulenT.de JagerB.SerrarensA. and SteinbachM., Optimal energy management in hybrid electric trucks using route information, Oil & Gas Science and Technology, 2010, 65, 103–113.
7.
KarsargyriG.-E., Optimally controlling hybrid electric vehicles using path forecasting, in: Proceedings of the American Control Conference, St. Louis, 2009, 4613–4617.
8.
KobayashiY.KiyamaN.AoshimaH. and KashiyamaM., A route search method for electric vehicles in consideration of range and locations of charging stations, in: Proceedings of the Intelligent Vehicles Symposium (IV) IEEE Workshop, Baden-Baden, 2011, 920–925.
9.
KämpkeT. and WangJ., The fastest itinerary in time-dependent decentralized travel information systems, Journal of Combinatorial Optimization, 2006, 12, 167–185.
RenY.XingT.SongH. and ChenX., Urban delivery distribution routing optimization key technology based on Web GIS, Journal of Software, 2011, 6, 1103–1109.
12.
TakaokaT., Subcubic cost algorithms for the all pairs shortest path problem, Algorithmica, 1998, 20, 309–318.
13.
TarapataZ., Selected multicriteria shortest path problems, International Journal of Applied Mathematics and Comput. Science, 2007, 17, 269–287.
14.
Touati-MounglaN., Jost, V. and Combinatorial optimization for electric vehicles management, Renewable Energy & Power Quality Journal, 2011, paper no. 504, www.icrepq.com/rev-papers.htm.
15.
ZhanF.B. and NoonC.E., Shortest path algorithms: An evaluation using real road networks, Trnasportation Science, 1998, 32, 65–73.
