文献

J-GLOBAL ID：201202273009435275   整理番号：12A1377714

道路網距離での旅行計画の為のインクリメンタル検索方式

An Incremental Query Algorithm for Trip Planning Queries in Road Network Distance

著者 (5件)： 大沢裕 (埼玉大 大学院理工学研究科) ,  大沢裕 (国立情報学研) ,  HTOO Htoo (埼玉大 大学院理工学研究科) ,  曽根原登 (国立情報学研) ,  坂内正夫 (国立情報学研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 172(DE2012 16-26)  ページ： 1-6  発行年： 2012年07月25日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 現在地から最終目的地に至る途中でいくつかの種類のPOIを1つずつ訪れる際のコスト最小の経路を求める検索は,旅行計画と呼ばれている。この旅行計画は訪れるPOIの種類が増えると,また訪れる順番の自由度が増えると最適解を得る計算は困難になるため,従来近似解法が提案されてきた。また,従来の研究はユークリッド距離での巡回路長が最小の解を求めることにとどまっていた。本稿では,道路網上を移動する際の最適解を得る為に,まずユークリッド距離での候補を探し,それを道路網距離で検証するアプローチを採用する。この枠組みでは,ユークリッド距離での候補を最適なものから順番に任意個求める必要がある。本稿ではこの際に必要になる,ユークリッド距離でのインクリメンタルな検索アルゴリズムを提案する。(著者抄録)

シソーラス用語： *経路探索 ,  道路網 ,  Euclid空間 ,  *最適化 ,  最小化問題 ,  原価 ,  近似法 ,  計算機アルゴリズム ,  *旅行
準シソーラス用語： コスト最小化 ,  近似解法 ,  検索アルゴリズム

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  システム最適化手法  (IA02050Z)

引用文献 (7件)：

• SHARIFZADEH, M. The optimal sequenced route query. 2005
• LI, F. On trip planning queries in spatial data bases. Proc. SSTD 2005. 2005, 273-290
• CHEN, H. The multi-rule partial sequenced route query. ACM GIS '08. 2008, 65-74
• PAPADIAS, D. Query processing in spatial network databases. Proc. 29th VLDB. 2003, 790-801
• SHARIFZADEH, M. The optimal sequenced route query. The VLDB Journal. 2008, 765-787

タイトルに関連する用語 (4件)： 道路網 ,  旅行 ,  計画 ,  検索