Queries of K-discriminative paths on road networks

Chien Wei Chang, Chu Di Chen, Kun Ta Chuang

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1751-1780
Number of pages30
JournalKnowledge and Information Systems
Issue number5
Publication statusPublished - 2020 May 1

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Queries of K-discriminative paths on road networks'. Together they form a unique fingerprint.

Cite this