Efficient Multi-Destinations Route Planning with Deadlines and Cost Constraints

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.