車両配送問題のタブー探索による解法の実験的解析
スポンサーリンク
概要
- 論文の詳細を見る
車両配送問題は複数のトラックを使って品物を倉庫から複数の店に配送して戻って来る総巡回路長を最小化する問題であり、コンビニエンスストアチェーンのトラック配送計画等、数多くの重要な実用的応用を持つ。この問題はNP困難に属するため多くの近似解法の研究がなされてきたが、複数の手法の性能比較研究が多く、1つの手法で実際に良い性能を得るための知見はまだ充分とはいえない。本研究では有力なメタ戦略の1つであるタブー探索に基づいた車両配送問題の近似解法において、主要な設計要素が解にどう影響するかを実験的に明らかにした。これらの実験の知見により、目的に応じた近似解法設計の指針を得ることができる。
- 社団法人情報処理学会の論文
- 1997-01-23
著者
-
今井 浩
東京大学大学院情報理工学系研究科コンピュータ科学専攻
-
下浦 弘
住友電気工業
-
西村 茂樹
住友電気工業
-
天目 健二
住友電気工業
-
中出 元樹
東京大学大学院理学系研究科情報科学専攻
-
朴 成浩
東京大学大学院理学系研究科情報科学専攻
-
西村 茂樹
東京大学大学院理学系研究科情報科学専攻
-
下浦 弘
東京大学大学院理学系研究科情報科学専攻
-
天目 健二
東京大学大学院理学系研究科情報科学専攻
-
今井 浩
東京大学大学院情報理工学系研究科
-
今井 浩
東京大学大学院 情報理工学系研究科
関連論文
- 状態方程式に基づく市街地幹線道路の旅行時間予測
- 光ビーコンで収集した交通情報の解析とその応用の検討--交通の円滑化による経済的損失の低減を目指して
- 通過順序に基づく車群マッチングと旅行時間推定
- 2地点車両観測情報からの全域的交通流解析アルゴリズム
- 車両特徴量を用いた車群マッチングと旅行時間推定
- サイクル長の異なるサブエリア間の交通流の評価
- 車両配送問題のタブー探索による解法の実験的解析
- 地点相関手法による交通情報予測
- 双対変数を用いたA^*両方向探索アルゴリズムと経路誘導における最短路問題
- 経路誘導における最短路問題の解法について
- 連載：理学のキーワード : 第29回
- SIMD型計算機向けループ自動並列化手法
- 動的推定によるプリフェッチ量最適化
- Webブラウザを用いた長距離データ転送の高速化
- 自動分散制御による動的な信号機制御パラメータ制御モデルの提案
- コヒーレントでないメモリシステムへのアーキテクチャ支援
- メニーコアプロセッサ向き共有キャッシュ配分方式
- マップ型履歴を用いたプリフェッチ方式とキャッシュ置換方式の協調動作
- データに誤りのある場合のDNAチップを使った配列決定アルゴリズム
- PCR実験におけるプライマー数の最小化の計算量的性質と解法
- ICIAM'95に参加して
- オフライン環境における多様性の高い実行時自己改変ソフトウェア(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- マルチエージェントモデルによる信号機オフセット制御法の提案
- 自動分散制御による動的な信号機制御パラメータ制御モデルの提案
- 日米間QoSによるLFN高速化実験と分散KVSの構築(研究発表,ネットワーク研究開発テストベッド運用・利用,一般)
- 7.論文誌周辺の研究倫理(研究者・技術者の倫理観・人生観)
- 量子和回路の効率化とシミュレーションによるデコヒーレンス耐性の解析
- 因数分解量子アルゴリズムの全量子シミュレーション
- 量子情報技術の現状と展望--EQIS'02の話題から (特集 量子情報技術--最前線からの展望)
- 有向グラフの推移閉包問題に対するFully Dynamicアルゴリズムの再定式化と実装
- 並列量子計算シミュレータについて
- 量子エントロピーの離散構造
- PPM法を利用した日本語テキスト圧縮
- 閾値関数のBDDの並列実装
- periodic graphのstatic graphに関する一考察
- パケット喪失履歴に基づいたTCP幅輳制御方式(2010年並列/分散/協調処理に関する『金沢』サマー・ワークショップSWoPP2010)
- 複数生物学的配列のアラインメントのパラメトリック的考察
- 計算幾何を用いた1量子ビットの量子通信におけるHolevo容量計算のアルゴリズム
- "Peter Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing,Vol.26,No.5, pp.1484-1509, 1997 (20世紀の名著名論)
- 5.量子計算と最適化(量子情報処理パラダイム)
- 量子情報処理パラダイム : 1.量子計算の基礎
- ナビゲーションシステム
- 通過順序に基づく車群マッチングと旅行時間推定
- 通過順序に基づく車群マッチングと旅行時間推定
- 最小費用流問題の双対問題におけるトーリックイデアルの解析
- RL-001 FPGAを用いた広帯域高遅延ネットワーク向けの利用可能帯域推定(L分野:ネットワーク・セキュリティ,査読付き論文)
- ネットワークシステムの信頼性の定量的評価法 : 枝故障に対する連結性保持の信頼度計算法(ネットワークシステムのセキュリティ評価と危機管理)
- df-pnアルゴリズムの詰将棋を解くプログラムへの応用
- Toric idealのstandard pair分解と最小費用流問題
- 多次元特徴空間での近接履歴グラフを用いた最近傍点探索の実際
- 多次元空間での最近傍点探索アルゴリズムの実験的解析と拡張
- 高速道路の最適流入制御への進化計算手法の適用
- 交通流データによる突発事象検出アルゴリズム
- トラカンデータを用いた高速道路突発事象検出アルゴリズム
- 自動車 二次計画法を用いた高速道路流入制御アルゴリズムの開発
- 円弧接続コース上のロバスト自動操舵 -非線形低次元化スライディングモード制御器-
- 動的ランプ流入制御方式の高度化
- スライディングモードによる自動車の縦方向制御
- 低次元化スライディングモードと特異注視点による自動車の操舵制御
- 上空からの交通情報収集システムの開発
- 動的経路誘導に必要な旅行時間精度の検討と計測方法の評価
- 交通流シミュレ-ションを用いた動的経路誘導の評価
- 交通流シミュレーションを用いた動的経路誘導の評価
- ナビゲーションシステムの評価における3次元CGの応用 : 来るべき経路誘導システムの完全実用化を目指して
- トーナメントグラフのトーリックイデアルのGrobner基底
- 単一始点最短路問題(SSSP)線形時間アルゴリズムの実際的評価
- 2方向量子1カウンタオートマトン
- 1方向確率的可逆および1方向量子1カウンタオートマトン
- Groverの量子探索アルゴリズムの応用
- 絡み目のJones多項式計算の実際
- TD-1-3 量子計算シミュレーション
- Shorのアルゴリズム専用シミュレーションシステム
- 詰将棋を解くプログラムにおける効率的なハッシュの利用法について
- 安全性の証明可能なステガノグラフィに関する研究
- サブエリア間の交通流の評価
- CTW圧縮における重み付け変数の最適化
- PPM圧縮におけるエスケープ確率と算術符号の改良
- 道路網の動的経路誘導システム
- 高性能な8倍精度浮動小数点演算機構の実現
- 多種言語処理系性能の評価に適したベンチマークプログラム
- 不要キャッシュブロックのパーティショニングによる排除方式
- HPC Ruby:静的解析に基づくRubyの高度最適化コンパイラ
- BTBへのBimode Cascading手法適用による分岐先アドレス予測の高効率化
- 多様な履歴の利用による分岐予測精度の向上
- Tutte多項式とネットワーク信頼性の計算
- 2010年度論文賞の受賞論文紹介 : 低次キャッシュとプリフェッチ
- ナビゲーションシステムと経路探索 (次世代道路交通システム : ITS)
- 前輪操舵と直接ヨーモーメントの2入力スライディングモード操舵制御
- 実用的なRuby用AOTコンパイラ
- 2分決定グラフ、ガウスの消去法、グラフ理論
- ストカスティック経路探索アルゴリズムの開発
- Jones多項式の計算
- 有向ネットワーク信頼性のBDDによる計算
- df-pnアルゴリズムの詰将棋解答プログラムへの応用
- 1600万計算コア超メニーコアアーキテクチャのシミュレーション
- データマイニングでのクラスタリング
- 三値マトロイドの生成とWhiteの予想に関する実験
- 重み付きDelaunay三角形分割と離散的Ricciフローについて : 重み付きDelaunay三角形分割とサークルパッキングメトリックの関係
- 非対称数字表現に対する平均ハミング重みの最適化
- 三値マトロイドの生成と White の予想に関する実験