Linear Relaxation for Hub Network Design Problems 東京大学 齋藤廣大 東京大学 松浦史郎 東京大学 松井知己

Hub Network

線形緩和問題→Hitchcock 型輸送問題 計算実験 Hub Network Problem ここで扱う問題： ハブ空港は与えられている｡ 各非ハブ空港は, 唯一のハブ空港に接続｡ 非ハブ空港間の輸送はハブを経由する｡ 全てのハブ空港対は直接繋がっている｡ 目的関数：総輸送費用の最小化 研究内容： 非凸2次計画としての定式化 線形緩和問題→Hitchcock 型輸送問題 計算実験

+ ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) 定式化 H，N：ハブ空港, 非ハブ空港 の集合 cij ：空港 i から j への単位輸送費用 wij ：空港 i から j への需要量 min. ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) s. t. ∑i∈H xpi =1 (∀p∈N), ：どこかに接続 xpi∈｛0,1｝（∀(p,i)∈N×H). xpi =1⇔ 非ハブ p はハブ i に接続する

+ ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) + ハブi からハブ j へ 目的関数 ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) ∑全ての非ハブペア(p,q) (pからqへの需要) (pから接続するハブi へ + ハブi からハブ j へ + qに接続するハブ j からqへ ) p i j q cij cpi cjq hub

fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 2次項の線形化 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 fpq 1 x1 x2 gpq x2 1 1 x1

+ ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) 線形化と連続緩和 min. ∑(p,q)∈N×N wpq (∑i∈H cpi xpi + ∑ (i,j)∈H×H cij xpi xqj + ∑j∈H cjq xqj ) s. t. ∑i∈H xpi =1 (∀p∈N), xpi∈｛0,1｝（∀(p,i)∈N×H). 線形化＋連続緩和 + gpq(x) + ∑j∈H cjq xqj ) 1≧xpi≧0 （∀(p,i)∈N×H).

Primal Approach

xq3 =1 xp1 =1 fpq(x)= c13 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 非hub 空港 非hub 空港 1 2 3 4 p q xq3 =1 xp1 =1 fpq(x)= c13

xq2 =1 xp3 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 非hub 空港 非hub 空港 1 2 3 4 p q xq2 =1 xp3 =1 fpq(x)= c32

xq2 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 0.2 0.7 非hub 空港 非hub 空港 1 2 3 4 p q 0.2 0.2 0.3 0.2 0.3 0.2 0.1 xq2 =1 0.5 0.1 fpq(x)= c32

xq2 =1 fpq(x)= c32 線形化＝Hitchcock 型輸送問題 fpq(x)=∑ (i,j)∈H×H cij xpi xqj hub 空港 hub 空港 0.2 0.7 非hub 空港 非hub 空港 1 2 3 4 p q 0.2 0.3 0.2 0.3 0.2 xq2 =1 0.5 0.2 0.1 fpq(x)= c32 0.1

∑ i∈H yij = xqj (∀j∈H）, fpq(x)=∑ (i,j)∈H×H cij xpi xqj 線形化 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 ＝下記のHitchcock型輸送問題の最適値 min. ∑ (i,j)∈H×H cij yij ∑ i∈H yij = xqj (∀j∈H）, ∑ j∈H yij = xpi (∀i∈H）, yij ≧0 (∀(i,j)∈H×H ) .

輸送問題の内包 輸送問題の内包 Hub 空港 非hub空港

Dual Approach

fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 線形不等式 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の整数点での関数値の， 下側凸包をとった関数 これらの線形不等式を 直接記述する. 1 x1 x2 fpq gpq

fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 線形不等式 fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 これらの線形不等式を 直接記述する. 1 x1 x2 gpq 線形不等式 ⇔ Hitchcock型輸送問題の 双対許容端点解 線形不等式の列挙 ⇔ 双対許容端点解の列挙

定理 [Balinski] 非退化の仮定のもとでは, n×n Hitchcock 型輸送問題の双対許容端点解は 2n-2Cn-1存在する. 線形不等式の列挙 ⇔ 双対許容端点解の列挙 定理 [Balinski] 非退化の仮定のもとでは, n×n Hitchcock 型輸送問題の双対許容端点解は 2n-2Cn-1存在する.

fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 等式不等式系のサイズ fpq(x)=∑ (i,j)∈H×H cij xpi xqj gpq(x)：関数fpq(x)の下側凸包をとった関数 . 変数 等式制約 不等式制約 (k : hub の数） Primal k2 2k ー1 k2 Dual 0 0 2k-2Ck-1 k=2 4 3 0 . 0 0 2 ． k=3 9 7 0 . 0 0 6 ． k=4 16 7 0 . 0 0 20 ．

Skorin-Kapov, Skorin-Kapov, O’kelly[1994] 既往の研究との関連 Primal Approach Skorin-Kapov, Skorin-Kapov, O’kelly[1994] ハブが固定されていない問題について，定式化を提案．ハブの変数を固定すると，Primal Approach と同じ定式化になる Dual Approach Sohn and Park [1998] ハブが2個で固定されているとき，線形不等式系で整数解多面体を記述（多項式時間解法）．Dual Approach での不等式系を採用

CAB data: O’kelley : アメリカ ２５空港間データ 25空港から3つを選んでHub空港として計算機実験を行った． すべての計算実験例において，線形緩和問題を解く事で整数最適解が選ばれた. Primal Approach と Dual Approach では， Primal Approach の方が計算機時間は早い． どの問題も5~8分程度で解ける． (lp solve)

おわり