Dynamic Graph Mining for Multi-weight Multi-destination Route Planning with Deadlines Constraints

Yu Huang, Josh Jia Ching Ying, Philip S. Yu, Vincent S. Tseng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Route planning satisfied multiple requests is an emerging branch in the route planning field and has attracted significant attention from the research community in recent years. The prevailing studies focus only on seeking a route by minimizing a single kind of Travel Cost, such as trip timeor distance, among others. In reality, most users would like to choose an appropriate route, neither fastest nor shortest route. Usually, a user may have multiple requirements, and an appropriate route would satisfy all requirements requested by the user. In fact, planning an appropriate route could be formulated as a problem of Multi-weight Multi-destination Route Planning with Deadlines Constraints (MWMDRP-DC). In this article, we propose a framework, namely, MWMD-Router, which addresses the MWMDRP-DC problem comprehensively. To consider the travel costs with time-variation, we proposenot only four novel dynamic graph miner to extract travel costs that reveal users' requirements butalso two new algorithms, namely, Basic MWMD Route Planning and Advanced MWMD Route Planning, to plan a route that satisfies deadline requirements and optimizes another criterion like travel cost with time-variation efficiently. To the best of our knowledge, this is the first work on route planning that considers handling multiple deadlines for multi-destination planning as well as optimizing multiple travel costs with time-variation simultaneously. Experimental results demonstrate that our proposed algorithms deliver excellent performance with respect to efficiency and effectiveness.

Original languageEnglish
Article number3
JournalACM Transactions on Knowledge Discovery from Data
Volume15
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • deadline constraint
  • multi-destination
  • Route planning
  • trajectory data mining

Fingerprint Dive into the research topics of 'Dynamic Graph Mining for Multi-weight Multi-destination Route Planning with Deadlines Constraints'. Together they form a unique fingerprint.

Cite this