ネットワーク上の連続被覆:改良型混合整数計画法定式化【JST・京大機械翻訳】

Pelegrin Mercedes; Xu Liding

プレプリント

J-GLOBAL ID：202202215393119480 整理番号：22P0296934

ネットワーク上の連続被覆:改良型混合整数計画法定式化【JST・京大機械翻訳】

Continuous Covering on Networks: Improved Mixed Integer Programming Formulations

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年03月01日プレプリントサーバーでの情報更新日： 2023年01月16日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

カバー問題は,運転研究の分野でよく研究され,特に,位置科学で研究されている。位置空間がネットワークである場合,最も頻繁な仮定は,候補施設位置,カバーすべき点,あるいは両方を離散集合と考えることである。本研究では,候補位置と需要点の両方がネットワーク上の連続集合である場合,集合被覆位置問題を研究した。この変形は,ほとんど注目を受けず,不十分な既存のアプローチは,ツリーネットワークや整数被覆半径などの特定の事例に集中している。ここでは,一般的問題を研究し,カバー半径より大きくないエッジ長を持つネットワークに対する混合整数線形計画法定式化(MILP)を提示した。このモデルは,この問題を変化せずに適切な長さのサブエッジに分割できるので,一般性を失わなかった。MILPのサイズを低減する前処理アルゴリズムを提案し,この定式化を強化するために,タイトビッグM定数と有効不等式を考案した。さらに,第二のMILPを提案し,それはカバー半径より大きいエッジ長さをアドミットする。問題の既存の定式化(ここで提案された最初のMILPを含む)とは対照的に,この第2モデルの変数と制約の数は,ネットワークエッジの長さに依存しない。この第2のモデルは,そのエッジが通常カバー半径より大きい実世界ネットワークに適合するスケーラブルなアプローチを表す。著者らの計算実験は,実世界とランダムネットワークの両方に関する著者らの正確なアプローチの強度と限界を示した。また,著者らの定式化を既存の正確な方法に対して試験した。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

計算機網 , 水源,取水,送水,配水,給水 , 道路輸送・サービス一般 , システム最適化手法

前のページに戻る