予算制約をもつ離散型交通ネットワークデザイン問題のラグランジュ緩和を用いた解法

概要

論文の詳細を見る
交通ネットワークデザイン問題は, 交通渋滞・エネルギー消費や自動車公害を減少させるために, 交通ネットワーク内の道路の新設や改良計画をするための計画案を作成する問題である.交通ネットワーク内の道路の新設や改良は, たとえば小規模でも多額の費用がかかるため, 新設や改良箇所の選択を誤ると交通混雑が緩和されないばかりでなく, 多額の費用の無駄を生ずることになる.そこで, 計画者は, 与えられた予算を効果的に使用する道路の新設・改良計画案を作成しなければならない.本研究では, 走行時間が交通量に依存し, 建設費用を制約式にもち, 交通需要量が固定型, 目的関数が交通の走行時間の和の最小化である離散型交通ネットワークデザイン問題を扱う.分枝限定法のための新しい下界値を提案し, ラグランジュ緩和問題の目的関数を変形することによって, この下界値が簡単に求めることができることを示す.また, 従来のLeBlancの下界値よりも提案する下界値が良いことの証明を行い, ラグランジュ乗法の求め方と近似解法も提案する.簡単な数値例によって, 提案した下界値の有効性を示す.
社団法人日本経営工学会の論文
1989-10-15