Proceedings of the AAAI Conference on Artificial Intelligence · 2011 · 137 citations · 4 references
ComputingTransportation PlanningAlgorithmsTransportTransportationCombinatorial OptimizationGraph AlgorithmsRoute PlanningRoutingRouting AlgorithmsShortest Path AlgorithmsPower-efficient RoutingRoad Network AnalysisRouting ProblemsShortest Path On Road NetworksShortest Path PlanningShortest Path ProblemsVehicle RoutingVehicle Routing Problems
We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.
4
Efficient Algorithms for Shortest Paths in Sparse Networks
D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text
An Appraisal of Some Shortest-Path Algorithms
Stuart E. Dreyfus · Operations Research · 1969 · 997 citations
A Note on Dijkstra's Shortest Path Algorithm
D. Barton Johnson · Journal of the ACM · 1973 · 317 citations · Full text