容量制約をもつ多品種流ネットワークデザイン問題 : 妥当不等式を用いた下界値の解法

概要

論文の詳細を見る
複数の品種をもち, リンクの容量に制約があるネットワークを構成する問題(通信ネットワーク, 道路ネットワーク, 配送ネットワーク問題など)は, 現実にしばしば現れる.このような問題は, 容量制約をもつ多品種流ネットワークデザイン問題と考えることができ, リンクの設置費用とフロー費用の和を最小化する問題となる.本研究では, このような問題の中で, 特にリンクの容量が一定である問題を取り上げ, その目的関数値の下界値を求めるための解法を提案する.下界値は, 最適解を求める分枝限定法や, ヒューリスティック解の精度の保証のためなどに用いられる.本研究は, 緩和問題の双対問題を考え, この実行可能解の目的関数値がもとの問題の下界値となることを利用して, 1)ネットワーク上のカットセットからカットセット制約式を求め, 2)変数の整数性を用いて, カットセット制約式から妥当不等式を求め, 3)双対問題の目的関数値が増加するように, 妥当不等式に対応する双対変数の値を更新していく, ことによって, 精度の良い下界値を求めるものである.また, 最後に, 数値例によって, 提案した下界値の解法の有効性を示す.
社団法人日本経営工学会の論文
1993-08-15