頂点容量制約付き有向全域木パッキング問題に対する近似解法

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では,頂点容量制約付き有向全域木パッキング問題に対する近似解法を提案する.この問題では入力として,有向グラフ,ルート頂点,頂点容量,辺の始点側と終点側にそれぞれ消費量が与えられる.目的は, ルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし,有向全域木の各頂点に対する消費量の合計は,与えられた頂点容量を超えてはいけない.この問題は NP 困難であることが知られている.提案手法ではこの問題を,(1) パッキングに用いる木の候補を探す,(2) それぞれの木に対してパッキング回数を決定する,という 2 つの段階に分けて考えている.前者に対しては,整数計画問題として定式化した後に,その線形緩和問題に対して列生成法を適用する.後者に対しては,線形緩和問題の解を修正したものに貪欲アルゴリズムを適用することを考案した.既存研究で用いられているグラフと,ランダムに生成したグラフに対して計算実験を行い,提案したアルゴリズムの効果について比較検討を行った.その結果,既存研究より良い結果が得られ,提案アルゴリズムがうまく動作していることを確認した.

• 一般社団法人情報処理学会の論文
• 2009-05-04

著者

• 佐々木 美裕

  南山大学

• 柳浦 睦憲

  名古屋大学大学院 情報科学研究科

• 柳浦 睦憲

  名古屋大学

• 田中 勇真

  名古屋大学大学院情報学研究科

• 田中 勇真

  名古屋大学大学院情報科学研究科

• 柳浦 睦憲

  名古屋大学情報科学研究科計算機数理科学専攻

• 田中 勇真

  名古屋大学大学院情報科学研究科計算機数理科学専攻

• 柳浦 睦憲

  名古屋大学大学院情報科学研究科計算機数理科学専攻

関連論文

• 2-C-6 ミニマックス型の階層型施設配置問題(施設配置)
• 2-F-3 New Formulation for Scheduling Problem in Multi-Hop Wireless Sensor Networks
• 局所探索法とその拡張 : タブー探索法を中心として
• A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
• 多制約配送計画問題に対する集合被覆アプローチ
• 分枝限定法 : さらなる計算効率の希求(堅く柔らかく…数理計画アプローチ再訪)
• 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
• 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
• MAX-2-SATに対する分枝限定法
• 矩形パッキング問題に対する厳密解法
• MAX-2-SATに対する分枝限定法(組合せ最適化(4))
• 時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整
• リアルタイムシステムの固定優先度スケジューリングに対する優先度周期探索法
• MAX-2-SATに対する分枝限定法
• ルール生成に必要なデータ量に関するランダム性に基づいた解析
• 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
• 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
• 5B1 A GUIDED LOCAL SEARCH ALGORITHM BASED ON A FAST NEIGHBORHOOD SEARCH FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
• オプションプライシングと凸計画問題の関係について(金融工学(3))
• 長方形詰込み問題に対する可変近傍探索法(組合せ最適化(4))
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
• Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (Captivation of Convexity : Fascination of Nonconvexity)
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法(組合せ(1))
• 段取り替え制約付きカッティングストック問題に対する列生成法を用いた局所探索法の提案(組合せ(1))
• シュタッケルベルグ型ハブ配置モデル
• 2-F-15 点容量付き内向木詰込問題の計算量(グラフ(2))
• 点容量付き内向木詰込問題の計算複雑度
• 長方形配置問題に対するbest-fit法の効率的な実現
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
• 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
• TD-1-6 組合せ最適化問題に対する局所探索アルゴリズムの開発について
• 配置コストをもつ二次元配置問題に対する局所探索について(組合せ最適化)
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
• 組込みシステムにおけるスケジューリングテーブル作成法 (最適化モデルとアルゴリズムの新展開)
• 排他制約付きナップサック問題における上界の計算法およびその有効性 (最適化モデルとアルゴリズムの新展開)
• 3次元パッキングに対する効率的なbottom-left法 (最適化モデルとアルゴリズムの新展開)
• Bottom-Left 安定点の効率的な列挙法とその応用 (最適化モデルとアルゴリズムの新展開)
• RA-006 3次元箱詰め問題に対する構築型解法の効率的実現法(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
• 2-C-3 センサネットワークにおけるデータ送受信スケジューリング問題(インフラストラクチャ)
• 2-A-3 クラスタツリーを用いたセンサネットワークの構成方法(都市・地域・国土(1))
• 1-A-12 センサネットワークにおけるクラスタリング手法の改良(都市・地域(3))
• A Quantitative Approach to the Design of the Center Console of Automobiles
• 2-E-19 日本OR学会研究発表会プログラムの自動作成(スケジューリング)
• 2-D-4 研究発表会プログラムの自動作成 : OR学会研究発表会を例として(整数計画)
• 2-A-7 都市のOR研究会(都市・地域・国土(2))
• ゲートウェイ空港配置モデル
• 2-A-5 ゲートウェイ空港の最適配置モデル(輸送・交通(1))
• 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
• 多点対カット問題に対する集合被覆アプローチに基づく近似解法
• LA-004 Analysis of an Edge Coloring Algorithm Using Chernoff Bounds
• Chernoff Bounds を用いた辺彩色アルゴリズムの解析
• DS-1-13 A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows
• 機械式立体駐車場入出庫スケジューリング
• 機械式立体駐車場出庫スケジューリング
• コンテナターミナルにおけるシフト計画
• 変動する環境下での1機械スケジューリング問題に対する遺伝アルゴリズムの適用について(組合せ最適化(3))
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案(組合せ最適化(2))
• カッティングストック問題におけるパターン生成法について(組み合わせ最適化(2))
• 段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法 (最適化のための連続と離散数理)
• パターン数最小化を目的とするカッテイングストック問題について
• 多重グラフにおける均等辺彩色を求める高速アルゴリズム
• 組合せ最適化問題に対するメタ戦略について(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
• メタ戦略のロバスト性について
• 遺伝アルゴリズムと局所探索法のロバスト性について
• 4A1 A LOCAL SEARCH ALGORITHM FOR ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW AND TRAVELING TIME CONSTRAINTS(Technical session 4A : Vehicle routing)
• 平成12年度春季研究発表会ルポ
• 織方図作成における最適化問題のグラフによる定式化 (数値最適化の理論と実際)
• 局所探索法 : 反復改善に基づく最適化の基本戦略(新・ORの図解,学会創立50周年記念号)
• 離散最適化問題に対するメタヒューリスティクス(ここまで使える数理計画法)
• Combinatorial Optimization : Theory and Algorithms (3rd Edition), B. Korte and J. Vygen 著, 出版社 Springer, 発行 2006年, 全ページ 597頁, 価格 53.45ユーロ, ISBN 3-540-25684-9
• 有効ターム数の確率的解析(不確実性の下での意思決定と数理モデル)
• 1-D-6 階層型施設配置問題の定式化について(都市・地域(2))
• 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
• 航空路のハブ・スポークシステムについて(組み合わせ最適化(2))
• 大規模な線形順序付け問題に対する高性能な局所探索アルゴリズム
• RA-004 An LP-Based Heuristic Algorithm for the Node Capacitated In-tree Packing Problem
• 頂点容量制約付き有向全域木パッキング問題に対する近似解法
• An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
• 一般化2次割当問題に対する大規模近傍探索法の適用について(数理計画(1))
• メタヒューリスティクスの枠組
• メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
• 一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用(組合せ最適化)
• 多資源一般化割当問題に対する大規模近傍探索法の適用について(組合せ最適化)
• 集合被覆問題に対する局所探索法について (最適化のための連続と離散数理)
• 時間枠制約付き配送計画問題に対する局所探索法の適用について (最適化のための連続と離散数理)
• 平成22年秋季研究発表会ルポ(情報の窓)
• 階層構造を持つミニサム型施設配置問題の厳密解
• 平成22年秋季研究発表会ルポ
• On a Location Problem of Relay Points in a Logistics System
• 1-I-3 大学授業時間割の自動編成システムについて(スケジューリング)
• 2-B-1 時間割自動編成システムの試作(スケジューリング(1))
• 大学時間割編成モデルの研究
• 2-D-9 大学授業時間割の自動編成システムの改良(スケジューリング(3))
• 2-B-8 呼損率を考慮した容量再配分による医療の地域格差の改善(特別セッション 都市とOR(4))
• 2-E-8 メガキャリアとの競合を考慮したLCCの航空路線編成モデル(輸送・交通(2))
• 1-D-4 大学の定期試験時間割作成問題(スケジューリング)
• 病院アクセシビリティを用いた疾病別需給バランスの視覚化(データから読み解く医療サービス)
• 2-C-1 連結制約と被覆制約を持つ施設配置問題とその解法(輸送・交通(3))

もっと見る 閉じる

スポンサーリンク