Queries of K-discriminative paths on road networks

Chien Wei Chang, Chu Di Chen, Kun Ta Chuang

研究成果: Article同行評審

摘要

In this paper, we study the problem of searching k-discriminative paths on road networks. Given a source node src and a destination node dest on a road network, we aim to search k paths between src and dest, where these k paths satisfy the multi-objective goal including the minimization of the path overlapping and the minimization of the path length. Specifically, the requirement of minimizing the overlapping among paths, which is a NP-hard issue, is highly demanded in applications of disaster rescue management such as the evacuation plan. In this paper, we consider the deployment of k-discriminative paths for various applications, including queries for emergency-purpose applications, queries of multi-objective Pareto front for pre-schedule transportation plan, and queries with multiple sources and destinations for the regional evacuation. Due to its NP-hard nature, the heuristic strategy based on the ant colony optimization is devised in this work. As validated by our experimental studies on real road networks, the proposed algorithm can achieve the discovery of k-discriminative paths efficiently and effectively, showing its prominent advantages to be a practicable service for evacuation-related applications.

原文English
頁(從 - 到)1751-1780
頁數30
期刊Knowledge and Information Systems
62
發行號5
DOIs
出版狀態Published - 2020 五月 1

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence

指紋 深入研究「Queries of K-discriminative paths on road networks」主題。共同形成了獨特的指紋。

引用此