最短路高速検索のための階層メッシュ疎化法

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では最短路を高速に検索するためのデータ構造とアルゴリズムの工夫,階層メッシュ疎化法,を提案する.最短路に頻出する枝をあらかじめ抽出することで,応答する経路の最適性を保証しつつ,検索時間の大幅な短縮に成功した.全米道路(約2400万点,約5800万枝)に適用した実験結果も報告する.階層メッシュ疎化法は,関連する既存手法に比べてメモリ使用量が少ないのが長所である.

• 社団法人情報処理学会の論文
• 2008-09-05

著者

• 宮本 裕一郎

  上智大学

• 宮本 裕一郎

  上智大学理工学部

• 久保 幹雄

  東京海洋大学海洋工学部

• 宇野 毅明

  国立情報学研究所

• 宇野 毅明

  東京工業大学 システム科学専攻

• 宇野 毅明

  情報学研究所

• 宇野 毅明

  東京工業大学経営工学専攻

• 宇野 毅明

  東京工業大学システム科学

• 久保 幹雄

  東京海洋大

• 宇野 毅明

  東京工業大学社会理工学研究科

• 宮本 裕一郎

  上智大

• 宇野 毅明

  国立情報学研

• 宇野 毅明

  国立情報学研究所:総合研究大学院大学

関連論文

• 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
• 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
• 最短路検索(OR事典Wiki)
• 2-D-5 動的な安全在庫を考慮したロットサイズ決定モデル(離散・組合せ最適化(6))
• 最短路問題(OR事典Wiki)
• 最短路高速検索のための階層メッシュ疎化法
• 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
• LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
• 制約付き最短路問題に対する実験的解析
• 自動販売機に対する在庫配送計画の事例
• VMIへの招待(サービスシステムのスケジューリング)
• メタ解法の新しいフレームワーク - 階層的積木法を中心として -
• TD-1-8 配送計画最適化システムMETROと巡回セールスマン問題ソルバーTST Solve
• 自動販売機補充問題に対する組合せ最適化アプローチ
• 自動販売機コラム割当問題(組合せ最適化)
• 商業物流における配送計画シミュレーションの試み(交通・物流)
• 第18回RAMPシンポジウムルポ(情報の窓)
• 2302 生産管理システムの効率的導入のための仮想生産工場 : MRPシステムの導入(OS2-3 生産管理・プロセス最適化)
• 1106 自律型FMSスケジューリング法に関する研究(OS1-1 生産スケジューリング)
• 1204 格子状経路を持つAGVシステムにおけるオークション方式運用法(OS1-2 生産システムの運用)
• Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
• 三角格子点上の単位円グラフに対する多重彩色
• 三角格子点上の単位円グラフに対する多重彩色
• Multicoloring Unit Disk Graphs on Triangular Lattice Points
• 対角線付き格子グラフに対するマルチカラーリングの線形時間近似解法
• Weighted Lattice Graph with Diagonals に対するマルチカラーリングの線形時間近似解法(グラフ・ネットワーク)
• 2-D-24 集合分割を用いた鉄鋼製品輸送船の船舶スケジューリング(物流)
• 階層的積木法と列生成法の融合 : 輸送・船舶スケジューリングを例として
• 2007W-OS1-4 内航ケミカルタンカー船隊に対する配船計画問題(オーガナイズドセッション(OS1):船舶の環境負荷低減に向けた技術開発)
• ロジスティクスにおける最適化ツールの開発(交通・輸送(2))
• 3101 小物FMSの自律的運用法の基礎的研究(OS3-1 生産管理)
• 2-F-15 点容量付き内向木詰込問題の計算量(グラフ(2))
• 点容量付き内向木詰込問題の計算複雑度
• 自動車部品の混載輸送における輸送計画モデル(ORの適用事例)
• 自動車部品の混載輸送における輸送計画モデル(交通・輸送(2))
• 1-A-8 最短路検索の高速化と応用(計算と最適化(1))
• 第14回RAMPシンポジウムルポ(情報の窓)
• G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd編, 伊理正夫, 今野浩, 刀根薫監訳, 最適化ハンドブック, 朝倉書店, 1995
• Clusteringによるグラフ分割問題へのメタ解法(グラフ・ネットワーク(2))
• Experimental analysis of a semidefinite programming approach to the graph partitioning problem
• Fast Implementation and Experiments of n Queens' Problem
• Parameter Optimization of the Tabu Search for the Maximum Clique Problem
• Tabu Searchのグラフ分割問題への適用と実験的解析 (組合せ最適化)
• A Two-phase approach for a tramper ship scheduling problem(Summaries of Papers Published by Staff of National Maritime Research Institute at Outside Organizations)
• 内航ケミカルタンカー船隊に対する配船計画問題(所外発表論文等概要)
• グリッド技術を用いたサプライ・チェイン最適化システム(OR研究の最前線)
• サプライ・チェイン最適化システム(企業事例)
• サプライ・チェイン最適化雑感(サプライチェーン・マネジメントのフロンティア)
• 数理計画ソルバーを用いたメタ解法(堅く柔らかく…数理計画アプローチ再訪)
• 数理計画ソルバーを用いたメタ解法
• 2-C-8 枝長が不確実性をもつ最短路問題に対するロバスト最適化アプローチ(グラフ・ネットワーク(1))
• 2-C-7 最短路問題の拡張に対する高速アルゴリズム(グラフ・ネットワーク(1))
• グローバル・サプライ・チェイン最適化モデル
• 容量制約をもつ多品種フロー輸送ネットワーク設計問題に対する容量スケーリング法
• モデリングのための覚え書き(モデリング-最適化モデリング-)
• 安全在庫配置問題における混合整数計画による定式化の比較(組合せ最適化)
• 安全在庫配置を考慮したロジスティクス・ネットワーク設計モデルに対するWebアプリケーションの開発(サプライ・チェーン最適化(1))
• 容量制約をもつ多品種フローネットワーク設計問題に対する容量スケーリング法(グラフ・ネットワーク(1))
• 研究室割り当てシステムの開発(タイムテーブリング)
• 私の提言 インターネット時代のロジスティクス--研究進むロジスティクス工学,成果知らぬ実務者にWebで情報発信を
• サプライ・チェイン最適化システムの統合と連携について(数理計画の理論と実装)
• 物流と数理計画(第2章 環境対応型運航支援システム,物流)
• 確率的巡回セールスマン問題と施設配置問題
• 確率的組合せ最適化問題
• Julien Bramel/David Simchi-Levi著, The Logic of Logistics, Springer-Verlag, 1997年, 281頁, 8,500円
• 共同配送問題における費用分担
• 分割配送路問題 : ラグランジュ緩和を利用した解法について
• 配送計画支援システムMETRO(MEta Truck Routing Optimizer)とその適用事例
• 幹線配送計画問題(非分割財の場合)(スケジューリング(1))
• 幹線配送計画問題(組合せ最適化(1))
• 巡回セールスマン問題ゲームに関するいくつかの考察(ゲーム理論(1))
• 配送路問題における費用分担について(ゲーム理論(1))
• FMSの投入優先順序決定のためのシミュレーション : 最適化アプローチ(特別セッション(3)スケジューリング)
• 主双対近似解法(新・ORの図解,学会創立50周年記念号)
• チャンネル割当問題の解法
• 運搬スケジューリング問題とその周辺(サービスシステムのスケジューリング)
• サプライチェーン最適化(10)運搬スケジューリング問題とその周辺(2)
• サプライチェーン最適化--運搬スケジューリング問題とその周辺
• (4) : スケジューリングとTabu Search : スケジューリング問題の新解法
• 流通経路を考慮した都市内物流の効率化に関する分析
• 安全在庫を考慮したサプライ・チェイン・ネットワーク最適化モデル(流通・物流(1))
• 電力設備補修計画における切除平面/分枝限定法
• 交通管理政策が都市内貨物集配送に与える効果の定量的シミュレーション分析
• サプライ・チェイン最適化システム(統合オペレーション)
• 自動販売機に対する在庫配送計画の事例
• 2-A-3 一人で歩く距離に着目したMin-Sum型とMin-Max型のネットワークフローモデルと安全下校問題への応用(特別セッション 震災復興・日本再生-都市のOR研究による道筋-(3))
• 1-I-5 電圧降下制約を考慮した停電量最小化問題と輪番停電(離散最適化(1))
• 1-C-2 交差点干渉を考慮した道路ネットワーク設計による渋滞改善(輸送・交通(1))
• はじめての列生成法(はじめよう整数計画)
• 1-C-4 リスク最小化に着目したネットワークフローモデルと安全下校問題への展開(都市のOR(1))
• 最新物流戦略 サプライチェーン最適化(36)OPLモデル(2)
• 最新物流戦略 サプライチェーン最適化(35)OPLモデル(1)
• 1-D-7 モジュラリティの上界値算出(離散最適化(2))
• サプライ・チェイン最適化とその周辺(数理計画の理論と実装)
• Solving the Dynamic Lot-Sizing Problem with Safety Stocks and Limited Inventories based on New Properties〔含 質疑応答〕
• 私の提言 ロジスティクス工学とその教育の必要性--学問としての進化追えぬわが国研究・教育体制
• 1-C-5 SimRankを用いた協調フィルタリング(最適化・アルゴリズム(2))
• 2-C-3 不動点定理によるドロネー性の確認(離散最適化(2))
• 数理最適化入門(1) : 線形計画(チュートリアル)
• 数理最適化入門(3) : ラグランジュ緩和と劣勾配法(チュートリアル)

もっと見る 閉じる

スポンサーリンク