講演抄録/キーワード |
講演名 |
2012-08-01 10:00
道路網距離での旅行計画の為のインクリメンタル検索方式 ○大沢 裕・トウ トウ(埼玉大)・曽根原 登・坂内正夫(NII) DE2012-16 |
抄録 |
(和) |
現在地から最終目的地に至る途中でいくつかの種類のPOIを1つずつ訪れる際のコスト最小の経路を求める検索は,旅行計画と呼ばれている.この旅行計画は訪れるPOIの種類が増えると,また訪れる順番の自由度が増えると最適解を得る計算は困難になるため,従来近似解法が提案されてきた.また,従来の研究はユークリッド距離での巡回路長が最小の解を求めることにとどまっていた.本稿では,道路網上を移動する際の最適解を得る為に,まずユークリッド距離での候補を探し,それを道路網距離で検証するアプローチを採用する.この枠組みでは,ユークリッド距離での候補を最適なものから順番に任意個求める必要がある.本稿ではこの際に必要になる,ユークリッド距離でのインクリメンタルな検索アルゴリズムを提案する. |
(英) |
This paper proposes a fast trip planning query method in road network distance. In advance of the query, the current position, the final destination, and some number of POI categories visiting during the
trip are specified. Then the query searches the shortest route from
the current position, visiting one from each specified POI categories
before reaching the final destination. Though, several such kinds of
trip planning methods have been proposed, most of them only give
suboptimal solutions or the solutions in Euclidean distance. This
paper proposes an incremental algorithm for trip planning query,
which can be apply to incremental Euclidean restriction approach to
obtain optimal trip planning routes in road network distance. |
キーワード |
(和) |
旅行計画 / 経路探索 / 道路網 / インクリメンタル検索 / OSR / / / |
(英) |
Trip Planning Query / Path Search / Road Network / Incremental Search / OSR / / / |
文献情報 |
信学技報, vol. 112, no. 172, DE2012-16, pp. 1-6, 2012年8月. |
資料番号 |
DE2012-16 |
発行日 |
2012-07-25 (DE) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
DE2012-16 |