2026-05-11T08:46:26Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00017361 2025-01-22T23:22:31Z 934:989:1019:1021

チャネル割当問題の解法 Algorithms for channel assignment problems 宮本, 裕一郎 松井, 知己 Yuichiro, Miyamoto Tomomi, Matsui オリジナル論文 本論文では 携帯電話の基地局に対するチャネル割当問題を組合せ最適化問題として定式化した. そして厳密解法 近似解決 発見的解法を提案した. またそれぞれの解法について同心円グラフを入力とする計算実験を行い 考察を行った. 厳密解法の章では 既存のパッケージソフトウェアを用いるため 整数線形計画問題へ帰着する定式化を提案した. 近似解法の章では 特定のグラフに対して5-近似の精度を保証する解法を提案した. 発見的解決の章では 2つの構築法と2つの改善法を提案し それらを組み合わせたいくつかの発見的解法を提案した. In this paper, we present algorithms for channel (frequency) assignment problems. We formulate channel assignment problems as combinatorial optimization problems. We propose an exact method, an approximation algorithm and heuristic algorithms. We also report the results of computational experiences. We formulated the problem as an integer linear programming problem and applied a package software. We present a 5-approximation algorithm for particular graphs which are similar to real instances. We propose two construction methods and two improvement methods. Our heuristic algorithms are combinations of construction methods and improvement methods. 情報処理学会 1999-02-15 jpn journal article https://ipsj.ixsq.nii.ac.jp/records/17361 1882-7780 AA11464803 情報処理学会論文誌数理モデル化と応用（TOM） 40 SIG02(TOM1) 23 32 https://ipsj.ixsq.nii.ac.jp/record/17361/files/IPSJ-TOM4002005.pdf application/pdf 919.7 kB 2001-02-15