ハブ・アンド・スポークネットワーク設計問題の近似解法(学生論文賞受賞論文要約)
スポンサーリンク
概要
- 論文の詳細を見る
航空会社にとって,ハブ空港を中心としたネットワークを適切に構築することは重要な課題である.米国では1978年の航空規制緩和をきっかけに,O'Kelly[3]をはじめとする多くの研究がハブ・アンド・スポークネットワーク設計問題に対して行われてきた.近年になりSohn and Park[4]は,ハブ空港の配置が既知であるとき,非ハブ空港からハブ空港への接続を決定する問題を2次整数計画問題として定式化している.ハブ空港数が3つ以上のとき,この問題はNP困難であるが,現在まで精度保証付き近似解法は知られていなかった.本論文では,Sohn and Park[4]により定式化された問題に対する精度保証付き近似解法を提案する.具体的には,ハブ空港数が一般の場合に対してロバストな3-近似解法と独立ラウンディングに基づく2-近似解法を提案し,ハブ空港数が3つの場合に対しては(5/4)-近似解法を提案する.本論文ではまた,Kleinberg and Tardos[2]により定義されたメトリックラベリング問題に対して,ラベル数が3つの場合に適用できる(4/3)-近似解法を提案する.本論文ではさらに,メトリックラベリング問題の特殊ケースであるユニフォームラベリング問題に対して,ラベル数が4つの場合に適用できる(5/3)-近似解法を提案する.これにより,ラベル数が4つのユニフォームラベリング問題に対する現在の最善の近似率11/6を改善することができる.
- 2007-12-01