文献

J-GLOBAL ID：202002253105022205   整理番号：20A0197214

最も速い多商品k分割可能フロー問題を解くための分岐と価格アルゴリズム【JST・京大機械翻訳】

A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem

著者 (4件)： Melchiori Anna (Sapienza Universita di Roma, Pzz.le Aldo Moro 5, Rome, Italy) ,  Melchiori Anna (Istituto per le Applicazioni del Calcolo “Mauro Picone”, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, Rome, Italy) ,  Sgalambro Antonino (Sheffield University Management School, Conduit Road, Sheffield S10 1FL, United Kingdom) ,  Sgalambro Antonino (Istituto per le Applicazioni del Calcolo “Mauro Picone”, Consiglio Nazionale delle Ricerche, Via dei Taurini 19, Rome, Italy)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 282  号： 3  ページ： 846-857  発行年： 2020年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ネットワーク最適化に関する文献において,k分割可能フローを導入して,各商品のためのサポート経路の数に関する上限が課せられる場合のモデリング精度を強化し,したがって,実用化の数を増やすためにネットワークフローツールの適合性を拡張した。このようなモデリング特徴は最近,新しい強NP困難Quickest多商品k分割可能フロー問題(QMCkFP)の導入により動的フローに拡張されている。そのようなフローは,時間ステップ当たりのアーク容量を持つ動的ネットワークにおける多くのkの異なる経路を通して,各商品需要の経路選定とスケジューリングのために,全体的なプロセスに必要な時間を最小化する。本研究では,QMCSFPを解くための最初の正確なアルゴリズムを提案した。開発された技術は,ブランチとイネのクラス内にあり,オリジナルの緩和,価格決定,および分岐手順に基づいている。線形化と可変置換を用いて,QMCSFPの経路ベースの定式化から緩和問題を得た。価格決定問題を,元の有向グラフの時間展開に関する追加のノード集合資源を有するForbidden Pathsを有するShortest経路問題としてモデル化して,調整された動的計画法アルゴリズムを通して解明した。2つの分岐規則を,k分割可能または2値可変領域制約が違反されるとき,実現可能性を復元するために設計した。小規模から中規模の参照事例について行った計算実験の広範なバッチの結果を示し,提案したアルゴリズムの非常に満足できる性能を示した。本論文は,研究の更なる系統に関する議論によって結論を下した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ネットワーク ,  有向グラフ ,  NP困難 ,  経路選定 ,  アーク放電 ,  *アルゴリズム ,  モデリング ,  価格決定 ,  ロット ,  順路問題 ,  動的計画法 ,  スケジューリング ,  緩和現象 ,  定式化 ,  時間発展

著者キーワード (5件)： ネットワーク ,  時間上の流れ ,  最も速い流れ ,  k分割可能フロー ,  分岐と価格

分類 (3件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  数理計画法  (KA03030M) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (5件)： 商品 ,  フロー ,  分岐 ,  価格 ,  アルゴリズム