制約付き最短路問題に対する実験的解析
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,移動に要する費用の和が与えられた上限以下でなければならないという条件の下で,始点から終点への最短パスを見つける最短路問題を扱う.これは制約付き最短路問題と呼ばれるものの1つでありNP-困難である.その問題に対し擬多項式時間厳密解法を提案する.併せて計算実験の結果も報告する.計算実験に用いた問題例は最大で点数4900,枝数約20000である.
- 社団法人情報処理学会の論文
- 2002-09-19
著者
関連論文
- 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
- 最短路検索(OR事典Wiki)
- 最短路問題(OR事典Wiki)
- 最短路高速検索のための階層メッシュ疎化法
- 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- 制約付き最短路問題に対する実験的解析
- 自動販売機に対する在庫配送計画の事例
- VMIへの招待(サービスシステムのスケジューリング)
- メタ解法の新しいフレームワーク - 階層的積木法を中心として -
- TD-1-8 配送計画最適化システムMETROと巡回セールスマン問題ソルバーTST Solve
- 自動販売機補充問題に対する組合せ最適化アプローチ
- 自動販売機コラム割当問題(組合せ最適化)
- Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
- 三角格子点上の単位円グラフに対する多重彩色
- 三角格子点上の単位円グラフに対する多重彩色
- 3101 小物FMSの自律的運用法の基礎的研究(OS3-1 生産管理)
- 主双対近似解法(新・ORの図解,学会創立50周年記念号)
- チャンネル割当問題の解法
- 自動販売機に対する在庫配送計画の事例
- 2-A-3 一人で歩く距離に着目したMin-Sum型とMin-Max型のネットワークフローモデルと安全下校問題への応用(特別セッション 震災復興・日本再生-都市のOR研究による道筋-(3))
- 1-C-2 交差点干渉を考慮した道路ネットワーク設計による渋滞改善(輸送・交通(1))
- はじめての列生成法(はじめよう整数計画)
- 1-C-4 リスク最小化に着目したネットワークフローモデルと安全下校問題への展開(都市のOR(1))
- 数理最適化入門(1) : 線形計画(チュートリアル)
- 数理最適化入門(3) : ラグランジュ緩和と劣勾配法(チュートリアル)