论文标题
使用Kinetica-graph的数千个涉及数千个EV充电站的旅行的最佳路由算法
Optimal routing algorithm for trips involving thousands of ev-charging stations using Kinetica-Graph
论文作者
论文摘要
本文讨论了基于图的路线解决算法，以找到电动汽车在数千个中选择最佳充电位置的最佳路径，以最大程度地减少行程末端之间的总累积驾驶距离。为此，我们设计了一种组合优化算法和美国大陆的图形路网络的固定存储图形拓扑结构。我们还重新使用了现有的Dijkstra求解器，以降低许多最短路径的计算成本解决算法。还设计了一种自适应和轻量级的空间搜索结构，用于使用均匀的垃圾箱和双链路关联在每个充电位置找到一组潜在的站点。整个算法被实现为Kinetica-Graph Analytics套件中的另一个多线程图形求解器，该算法被视为一个静止的API端点，在SQL中可操作。解决了几个示例旅行，并在上下文中证明了结果。
This paper discusses a graph based route solving algorithm to find the optimal path for an electric vehicle picking the best charging locations among thousands to minimize the total cumulative driving distance between the end points of the trip. To this end, we have devised a combinatorial optimization algorithm and a fixed storage graph topology construction for the graph road network of the continental USA. We have also re-purposed our existing Dijkstra solver to reduce the computational cost of many shortest path solves involved in the algorithm. An adaptive and light weight spatial search structure is also devised for finding a set of prospective stations at each charging location using uniform bins and double link associations. The entire algorithm is implemented as yet another multi-threaded at-scale graph solver within the suite of Kinetica-Graph analytics, exposed as a restful API endpoint and operable within SQL. Several example trips are solved and the results are demonstrated within the context.
