Efficient multi-destinations route planning with deadlines and cost constraints

Yu Huang, Bo Hau Lin, S. Tseng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In recent years, multi-destinations route planning has been the topic of much research, which is an emerging branch of the route planning problem. The existing works have been focusing on how to find routes that minimize a single kind of trip cost, such as trip time or distance, amongst others. In fact, users may have multiple requirements in real-life multi-destinations route planning applications, including for personal or business purposes (e.g., express delivery). We observed the fact that (i) there may exist a respective deadline in reaching each of the destinations, (ii) users may consider to reduce further kinds of trip costs, such as fuel, in addition to the deadline constraint. In this paper, we address a novel route planning problem named Multi-Destinations Route Planning with Deadlines and Cost Constraints and propose two approaches, namely BMDC (Basic Multi-Destinations Route Computation) and AMDC (Advanced Multi-Destinations Route Computation) to efficiently plan a route that satisfies deadline requirements and optimizes another criterion such as trip cost. To the best of our knowledge, this is the first work on route planning that considers multiple deadlines for multi-destinations as well as optimizing trip cost, simultaneously. Experimental results demonstrate that our proposed algorithms deliver excellent performance in terms of efficiency and effectiveness.

Original languageEnglish
Title of host publicationProceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages228-233
Number of pages6
ISBN (Electronic)9781538639320
DOIs
StatePublished - 29 Jun 2017
Event18th IEEE International Conference on Mobile Data Management, MDM 2017 - Daejeon, Korea, Republic of
Duration: 29 May 20171 Jun 2017

Publication series

NameProceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017

Conference

Conference18th IEEE International Conference on Mobile Data Management, MDM 2017
CountryKorea, Republic of
CityDaejeon
Period29/05/171/06/17

Keywords

  • Deadline Constraint
  • Multi-Destinations
  • Route Planning
  • Trip Cost Constraint

Fingerprint Dive into the research topics of 'Efficient multi-destinations route planning with deadlines and cost constraints'. Together they form a unique fingerprint.

  • Cite this

    Huang, Y., Lin, B. H., & Tseng, S. (2017). Efficient multi-destinations route planning with deadlines and cost constraints. In Proceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017 (pp. 228-233). [7962456] (Proceedings - 18th IEEE International Conference on Mobile Data Management, MDM 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/MDM.2017.38