Queries of K-discriminative paths on road networks

Chien Wei Chang, Chu Di Chen, Kun-Ta Chuang

Research output: Contribution to journalArticle

Abstract

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
JournalKnowledge and Information Systems
DOIs
Publication statusAccepted/In press - 2019 Jan 1

Fingerprint

Ant colony optimization
Disasters

All Science Journal Classification (ASJC) codes

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

Cite this

@article{60c2e3ed6a97413e98b9a160e0bb014c,
title = "Queries of K-discriminative paths on road networks",
abstract = "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.",
author = "Chang, {Chien Wei} and Chen, {Chu Di} and Kun-Ta Chuang",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/s10115-019-01397-4",
language = "English",
journal = "Knowledge and Information Systems",
issn = "0219-1377",
publisher = "Springer London",

}

Queries of K-discriminative paths on road networks. / Chang, Chien Wei; Chen, Chu Di; Chuang, Kun-Ta.

In: Knowledge and Information Systems, 01.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Queries of K-discriminative paths on road networks

AU - Chang, Chien Wei

AU - Chen, Chu Di

AU - Chuang, Kun-Ta

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85071834458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071834458&partnerID=8YFLogxK

U2 - 10.1007/s10115-019-01397-4

DO - 10.1007/s10115-019-01397-4

M3 - Article

AN - SCOPUS:85071834458

JO - Knowledge and Information Systems

JF - Knowledge and Information Systems

SN - 0219-1377

ER -