.png){kind=icon}
返回
Multi-Source Shortest Path Query With Assembly Points on Large Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2024.3424947.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Computing Multi-source Shortest Path query with Assembly points ($\mathsf {MSPA}$MSPA) is a fundamental graph problem. The $\mathsf {MSPA}$MSPA problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the $\mathsf {MSPA}$MSPA problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.
Keyword:
Assembly
Heuristic algorithms
Costs
Batteries
Dynamic programming
Waste management
Power grids
Multi-source shortest path
assembly point
dynamic programming
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
引用论文
Illusory Sensation of Movement Induced by Repetitive Transcranial Magnetic Stimulation.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAI分享收藏
A robust green location-allocation-inventory problem to design an urban waste management system under uncertaintyWASTE MANAGEMENT
WASTE MANAGEMENTIF7.1
PREAI
分享收藏Multi-stage network-based two-type cost minimization for the reverse logistics management of inert construction wasteWASTE MANAGEMENT
WASTE MANAGEMENTIF7.1
PREAI
分享收藏
查看更多内容