最短ツリーの記憶による交通量配分の経路探索の効率化

• 鷹尾 和享

  （社）システム科学研究所

• 朝倉 康夫

  神戸大学大学院 工学研究科

書誌事項

タイトル別名

• Acceleration of Shortest-Path Search in Traffic Assignment by Memorizing Shortest-Path Trees

抄録

Frank-Wolfe法の繰り返しループの間、最短経路探索が何度も繰り返し実行されるが、本稿は、前回の最短ツリーを記憶することによって最短経路探索を高速化する方法について述べる。記憶しておいた最短ツリーのリンクコストは今回の繰り返し回用に更新する必要があるが、ラベル修正法において、大きなコストのラベルが付くのを阻止するための足切りラインとして利用できる。本稿ではこの方法を実際的な表現の実ネットワークに適用し、大幅に高速化することを確認した。この理由は、ラベル修正回数が劇的に減少するからである。その一方、必要メモリは増大するが、通常のネットワーク規模では最近のＰＣ上で実行できる程度に収まる。

収録刊行物

• 土木計画学研究・論文集

  土木計画学研究・論文集 26 (0), 527-533, 2009

  公益社団法人 土木学会

キーワード

• 交通ネットワーク分析
• 経路選択

詳細情報

• CRID: 1390282679613869312
• NII論文ID: 130006275058
• DOI: 10.2208/journalip.26.527
• ISSN: 18848303
• ISSN: 09134034
• Web Site: https://www.jstage.jst.go.jp/article/journalip1984/26/0/26_527/_pdf
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可