文献

J-GLOBAL ID：201002257458727809   整理番号：10A1607354

デポ間輸送問題に対するグラフアルゴリズムの研究

著者 (1件)： 泉奈央美 (慶応大 大学院理工学研究科)
資料名： オペレーションズ・リサーチ
巻： 55  号： 12  ページ： 790-791  発行年： 2010年12月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 多くの宅配業者の集荷・配達ルートは,個人宅・企業-営業所-デポ-宛先デポ-営業所-個人宅・企業となっており,2つの組合せ最適化問題が内在する。営業所内の集荷・配達問題とデポ間移動問題の内,後者について論じた。各デポ間で定められた荷量を,l台以下のトラックで時間内に運べるかを判定する問題をデポ間輸送問題と定義した。この問題を,制限を限った条件でグラフ理論の問題(k-ラインカバー問題)に変換し,以下1)-6)の結果を得た。1)2-ラインカバー問題:多項式時間可解,2)3-ラインおよび3-ライン(重複):NP完全,3)3-ライン(重複):4/3近似アルゴリズムの存在,4)3-ライン:5/3近似アルゴリズムの構築,5)k-ライン:(2k-1)/k近似アルゴリズムの構築,6)k-ライン:多項式時間可解であるための十分条件。

シソーラス用語： *グラフ理論 ,  *輸送問題 ,  宅配 ,  *組合せ最適化問題 ,  決定問題 ,  計算理論 ,  NP完全問題 ,  近似法 ,  計算機アルゴリズム ,  有向グラフ ,  最大化問題 ,  近傍探索法 ,  Euler方程式
準シソーラス用語： 判定問題 ,  多項式時間

分類 (2件)： 計算理論  (JB02000A) ,  ネットワーク法  (KA03040X)

引用文献 (3件)：

• DUH, R. Approximation of k-set cover by semi-local optimization. STOC'97 (El Paso, TX). 1999, 256-264
• GAREY, M. R. Computers and intractability, a guide to the theory of NP-completeness. 1979
• LEVIN, A. Approximating the unweighted k-set cover problem : greedy meets local search. SIAM J. Discrete Math. 2008, 23, Issue 1, 251-264

タイトルに関連する用語 (4件)： デポ ,  輸送問題 ,  グラフアルゴリズム ,  研究