imprint:
Association for the Advancement of Artificial Intelligence (AAAI), 2016
Published in:Proceedings of the International Conference on Automated Planning and Scheduling
Language:
Not determined
DOI:
10.1609/icaps.v26i1.13748
ISSN:
2334-0843;
2334-0835
Origination:
Footnote:
Description:
<jats:p>
We consider the problem of covering a street network with loading stations for electric vehicles (EVs) such that EVs can travel along shortest paths and only require small detours (e.g., at most 3 km) to recharge along the route. We show that this problem can be formulated as a Hitting Set problem. Unfortunately, it turns out that even the explicit problem 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 high-quality EV-routes in a network with loading stations placed by our approach. We empirically show the usability of the routes by evaluating the number of reloading stops and the actually induced detour.
</jats:p>