| Autor: |
Feng Anran, Xuren Wang, Xu Yina, Famei He |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
Proceedings of the 2019 2nd International Conference on Machine Learning and Machine Intelligence. |
| DOI: |
10.1145/3366750.3366752 |
| Popis: |
In order to solve the path planning problem of time-dependent road network(TDRN), an dynamic A* landmarks triangle algorithm(ALT) is proposed based on landmark-oriented technique and short-path tree(SPT). There are three main contributions: (1) constructing the shortest path tree in the preprocessing stage and calculating the distance between the landmark and other nodes; (2) using the dynamic shortest path tree to optimize the query in the point-to-point heuristic path planning process; (3) When the edge weight of the network changes, the shortest path tree is dynamically updated, and the structural characteristics of the tree are used to reduce the redundancy calculation. Experimental results indicate that the DALT algorithm not only outperforms the ALT implementation in point-to-point shortest path problem as the average query time is reduced by up to 51.71%, but also computes economically for updating shortest path tree compared with previous dynamic update algorithm as the average update times for increments are reduced by up to 9.90% with less modifications. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
