One-Way Search Algorithm for Multi-Request Route Planning

論文翻譯標題: 單向搜尋演算法應用於多需求路線規劃
  • ? 心獻

學生論文: Doctoral Thesis

摘要

適地性服務(Location-Based Service,LBS)普遍存在於我們的日常生活當中,使得我們的生活更加便利。其中一項熱門的主題為城市中興趣點(Point of Interest,POI)的路線規劃,即給予一個起點和目的地,以及使用者想去的地點或類型,路線規劃服務會給予使用者一或數條在距離或時間等評估方面上好的路線。在過去的相關研究僅考慮POI屬於一種類別,然而,一個POI可以提供多種服務以滿足使用者的需求,而考慮此特性的路線規劃即稱為多需求路線規劃(Multi-Request Route Planning,MRRP)。由於此類服務注重查詢的即時性,在過去的研究僅提供最佳路線的近似解;在本文中,我們提出單向搜尋(One-Way Search)演算法回答MRRP查詢,它結合分支定界法(Branch and Bound)與貪心演算法(Greedy Algorithm)的特點,因此能快速返回一個可行解;然而,如果讓此方法持續計算,最後可以得到最優解。據我們所知,這是第一項以最優解的方式回答MRRP查詢的工作。在實驗中,我們與近年也是找最優解的APTS/ANA*演算法做比較,實驗結果顯示我們的方法在執行時間和記憶體使用量上優於競爭方法。
獎項日期2019
原文English
監督員Hsueh-Chan Lu (Supervisor)

引用此

'