文献

J-GLOBAL ID：201902217892107810   整理番号：19A1787191

総コストを最小化するための距離制約付き車両経路選定問題【JST・京大機械翻訳】

Distance Constrained Vehicle Routing Problem to Minimize the Total Cost

著者 (3件)： Yu Wei (Department of Mathematics, East China University of Science and Technology, Shanghai, China) ,  Liu Zhaohui (Department of Mathematics, East China University of Science and Technology, Shanghai, China) ,  Bao Xiaoguang (College of Information Technology, Shanghai Ocean University, Shanghai, China)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11653  ページ： 639-650  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 三角形不等式とデポット頂点[数式:原文を参照]に従う非負のエッジ重み関数を有する無指向完全グラフ[数式:原文を参照],[数式:原文を参照]と各サイクル[数式:原文を参照]がrを含み,ほとんどの[数式:原文を参照]の長さを持つ場合,サイクルのセット[数式:原文を参照]を[数式:原文を参照]-有界r-サイクルカバーと呼ぶ。総コスト(DVRP-TC)を最小化する目的での距離制約車両ルーティング問題は,サイクルと[数式:原文を参照]の合計長さの合計が最小化される[数式:原文を参照]-有界r-サイクルカバー[数式:原文を参照]を見出すことを目的としている。ここで[数式:原文を参照]は単一サイクルの割当コストを示す入力である。ツリーメトリック上のDVRP-TCに対して,既存の結果により意味される2近似アルゴリズムを示し,積分ギャップが5/2の上限を持つLP緩和を与えた。特に,[数式:原文を参照]がこの限界を2に改善できることを証明した。DVRP-TCの非根付版に対して,5近似アルゴリズムを考案し,NagarajanとRavi(2008)によって与えられた丸め手順を用いて,自然の集合をカバーするLP緩和が25の一定の積分ギャップを持つことを示した。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 不等式 ,  重み関数 ,  完全グラフ ,  積分 ,  *経路選定 ,  *総原価 ,  緩和現象
準シソーラス用語： 近似アルゴリズム ,  輸送経路 ,  有界 , 【Automatic Indexing@JST】

著者キーワード (5件)： 車両経路選定 ,  サイクルカバー ,  パスカバー ,  近似アルゴリズム ,  完全性ギャップ

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 総コスト ,  最小化 ,  制約 ,  経路選定