One-Way Search Algorithm for Route Planning with Multiple Requests

Eric Hsueh Chan Lu, Sin Sian Syu

Research output: Contribution to journalArticlepeer-review


Multirequest route planning (MRRP) based on user demand is an active location-based service in point-of-interest (POI) networks. The goal of MRRP is to plan the shortest route that meets the requests specified by the user. However, because MRRP is an NP-hard problem, most existing methods involve the use of greedy search in the planning of approximate routes, leaving much room for improvement in route quality. Therefore, in this study, an anytime algorithm called one-way search (OWS) was proposed to efficiently solve MRRP queries. OWS integrates branch-and-bound and greedy search. It not only helped rapidly detect an accepted route but also allowed for more optimal routes to be iteratively generated until the most optimal route was identified. OWS has three pruning mechanisms named Filter, Potential, and Petrifaction and three operations named Wilting, Selection, and Reverse Update to avoid unnecessary searches and improve search efficiency. To the best of the authors' knowledge, this is the first study of MRRP queries that investigates both optimal route planning and searching efficiency. The experimental results obtained on real-world POI datasets indicated that OWS outperformed state-of-the-art anytime algorithms in terms of quality and efficiency.

Original languageEnglish
Pages (from-to)1682-1691
Number of pages10
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number2
Publication statusPublished - 2023 Feb 1

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


Dive into the research topics of 'One-Way Search Algorithm for Route Planning with Multiple Requests'. Together they form a unique fingerprint.

Cite this