| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-03-04 13:40 特定範囲の経路長を達成する経路集合の生成 ○武藤 慧・天野雄樹・今井桂子（中大）  COMP2025-24 |
|
| 抄録 | （和） | 日常的な散歩において,毎日似たような道を歩くことに単調さを感じることがある. 本研究では, 経路長範囲を満たす多様な経路集合を生成する手法を提案する. 2経路間で共有される辺の長さの総和を類似度として導入し, 生成した経路の全経路対の期待類似度を最小化する問題を扱う. 期待類似度は, 生成した経路をランダムに並び替えた際, 連続する2経路が共有する総辺長の平均を小さくすることに相当する. この問題はNP困難であるため, 本研究では局所探索をベースとした発見的解法を提案する. これは, 暫定経路の一部を削除し, 双方向幅優先探索を用いて経路を再接続することで近傍経路を生成する手法である. 東京と京都の実道路ネットワークを利用した計算機実験では, 各経路で使用される辺が適切に分散され, 提案手法が多様な経路集合を効率良く生成できることを確認した. この手法は, 日々の散歩経路推薦, 自動運転システムのテスト用経路の生成, および, その他の多様性が求められる経路計画問題に応用できる. |
| （英） | This study addresses a common problem: people often use similar walking routes, resulting in monotony in their daily strolling experience. In this study, we propose a method for generating diverse routes of lengths within a specified range. We define the ``similarity'' between two routes as the total length of the shared edges, and formulate the problem as one of minimizing the total similarity across all pairs in the generated route set. This means minimizing the average shared edge length between consecutive routes when routes are selected based on random permutations. As the problem is NP-hard, we introduce a heuristic algorithm based on a local search that reconnects routes using a bidirectional breadth-first search. Experimental results using real-world road network data from Tokyo and Kyoto demonstrate that the proposed method effectively generates diverse route sets with well-distributed edge usage patterns. The proposed approach has several practical applications, including daily strolling route recommendation, test scenario generation for autonomous driving systems, and other route scheduling problems requiring diversity. |
|
| キーワード | （和） | 経路生成 / 経路計画 / 経路長 / 道路ネットワーク / 複数経路 / 多様性 / / |
| （英） | route generation / route planning / route length / road network / multiple routes / diversity / / | |
| 文献情報 | 信学技報, vol. 125, no. 390, COMP2025-24, pp. 14-21, 2026年3月. | |
| 資料番号 | COMP2025-24 | |
| 発行日 | 2026-02-25 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2025-24 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2026-03-04 - 2026-03-04 |
| 開催地（和） | 中央大学後楽園キャンパス 6号館4階6402 |
| 開催地（英） | Chuo University Korakuen Campus Building 6 4F Room 6402 |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, General |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2026-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 特定範囲の経路長を達成する経路集合の生成 |
| サブタイトル（和） | |
| タイトル（英） | Generating diverse routes with lengths within a specified range |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 経路生成 / route generation |
| キーワード(2)（和/英） | 経路計画 / route planning |
| キーワード(3)（和/英） | 経路長 / route length |
| キーワード(4)（和/英） | 道路ネットワーク / road network |
| キーワード(5)（和/英） | 複数経路 / multiple routes |
| キーワード(6)（和/英） | 多様性 / diversity |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 武藤 慧 / Satoru Mutoh / ムトウ サトル |
| 第1著者 所属（和/英） | 中央大学 (略称： 中大) Chuo University (略称： Chuo Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 天野 雄樹 / Yuki Amano / アマノ ユウキ |
| 第2著者 所属（和/英） | 中央大学 (略称： 中大) Chuo University (略称： Chuo Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 今井 桂子 / Keiko Imai / イマイ ケイコ |
| 第3著者 所属（和/英） | 中央大学 (略称： 中大) Chuo University (略称： Chuo Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-03-04 13:40:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2025-24 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.390 |
| ページ範囲 | pp.14-21 |
| ページ数 | 8 |
| 発行日 | 2026-02-25 (COMP) |
[研究会発表申込システムのトップページに戻る]