In

Paper abstract bibtex

Paper abstract bibtex

We consider the problem of covering a street network with loading stations for electric vehicles (EVs). With the resulting placement an EV must be able to travel along shortest paths between any pair of nodes in the network and only require small detours (e.g., at most three kilometers) to recharge along the route. We show that this problem can be formulated as a Hitting Set problem. Unfortunately, even the instance construction requires too much time and space to be practical. Therefore, we develop several approximation algorithms and heuristics to solve the problem. Our experiments show that even though small, the allowed detours lead to a considerable reduction in the number of required loading stations. Moreover, we devise an algorithm for planning reasonable EV-routes in loading station covered networks. We empirically prove the usability of the routes by evaluating the number of reloading stops and the actually induced detour.

@inproceedings {icaps16-109, track = {Main Track}, title = {Placement of Loading Stations for Electric Vehicles: Allowing Small Detours}, url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13086}, author = {Stefan Funke and Andre Nusser and Sabine Storandt}, abstract = {We consider the problem of covering a street network with loading stations for electric vehicles (EVs). With the resulting placement an EV must be able to travel along shortest paths between any pair of nodes in the network and only require small detours (e.g., at most three kilometers) to recharge along the route. We show that this problem can be formulated as a Hitting Set problem. Unfortunately, even the instance construction requires too much time and space to be practical. Therefore, we develop several approximation algorithms and heuristics to solve the problem. Our experiments show that even though small, the allowed detours lead to a considerable reduction in the number of required loading stations. Moreover, we devise an algorithm for planning reasonable EV-routes in loading station covered networks. We empirically prove the usability of the routes by evaluating the number of reloading stops and the actually induced detour.}, keywords = {Applications and case studies,Multi-objective planning and scheduling,Planning activities; motions and paths} }

Downloads: 0