最長片道きっぷの厳密解を求める 東京大学大学院 宮代隆平，葛西隆也 本資料の概要 「最長片道きっぷ」のルートを求める ・ 最長片道きっぷとは？ ・ 路線図の分析 ・ 整数計画問題としてのモデル化 ・ 求めた最長ルートの紹介 「最長片道きっぷ」とは？ ・ 最長距離のルートをたどる「片道きっぷ」 ・ 最長路問題と似ているが，若干異なる（後 述） ・ 最長片道きっぷのルートを求める問題：ＬＯＰ （Longest One-way ticket Problem） ＬＯＰに関するメモ ＬＯＰの最適解（＝最長片道きっぷのルート） → ｛出発駅，到着駅，その間の最長片道経 路｝ の三つ組みを決定する 東大旅行研（1962，中央公論社） ー 手作業 山路，林（1994，OR学会誌） ー 近似解法 目標：数理的手法により，最適解を求める 片道きっぷとなる条件 ・ 折り返しを含まない → 引き返せない ・ ループ一周を超えない → 同じ駅に二度たどりついたら，そこで終了 タイプＬ タイプＯ タイプＰ 日本では，最適解はタイプＯではない ＪＲ路線図の分析（2000年7月現在） 本州： 3,332 駅 14424.9km 北海道： 478 駅 2499.8km 九州： 570 駅 2101.1km 四国： 259 駅 855.8km 本州と他三島とは，一路線で接続している → 最適解は本州上の駅を含む 駅の分類 ● ● ● ● 終端駅（行止りの駅，81個） 分岐駅（路線が分岐している駅，269個） 隣接駅（分岐駅の隣の駅，約800個） その他の駅（以上に属さない駅，約3,500個） 駅の削除 ＬＯＰの最適解の形状は Ｌ Ｐ のいずれか → 「その他の駅」は最適解の発着駅ではない 考慮すべき駅数 4,639 → 約1,150 タイプＬに関する考察 タイプＬ（一本道）の発着駅の候補は？ ・ 分岐駅●は最適解の発着駅ではない ・ 隣接駅●も最適解の発着駅ではない → タイプＰ 発着駅の候補は 終端駅●の み！ タイプＰに関する考察 タイプＰの場合，到着駅＝分岐駅 出発駅は二つの可能性がある ・ 終端駅 （タイプＰｅ；end） ・ 隣接駅 （タイプＰｎ；neighbor） 計算の方針 タイプ別に場合分けし，ＩＰを作成して解く ・ タイプＬ （厳密解を求める） ・ タイプＰｅ （緩和問題） ・ タイプＰｎ （緩和問題） 計算環境：PentiumⅡ400ＭＨｚ PC IPソルバー：CPLEX6.0 路線図の定式化 ＬＯＰを整数計画問題として定式化 → 路線図（終端駅と分岐駅のみ）において 各区間に0-1整数変数を割り当てる xi ＝1（区間i を使う）， xi ＝0（区間i を使わな い） 目的関数 x1 max. ∑｛di ・xi ｜i は区間｝ di は区間i の距離 x2 x4 x3 駅変数の導入 終端駅と分岐駅にも整数変数を定義 終端駅をei ，分岐駅をbi とする 駅変数：駅に接続している区間を何回使うか e1＝x1, e2＝x3, e1 x1 b1 b1＝x1＋x2＋x4, b2＝x2＋x3＋x4． x2 x4 b2 x3 e2 変数節約の工夫 変数節約のため，まず本州以外の三島に関し 最適解をそれぞれ求め，路線図を統合 最終的なＩＰの規模： 区間変数399個，駅変数289個 （タイプＰｅ，Ｐｎではさらに人工変数460個） タイプＬの制約条件 タイプＬの発着駅は終端駅 →∑｛ei｜i は終端駅｝＝2， 任意の分岐駅i についてbi ∈｛0，2｝． ループは除去 bi ∈｛0，2｝の線形制約による表現 bi （＝x1＋x2＋x3）∈｛0,2｝を線形制約で表現 x1 bi x2 x3 x3 → －x1＋x2＋x3≧0， 1 ＋x1－x2＋x3≧0， ＋x1＋x2－x3≧0， x1 ＋x1＋x2＋x3≦2， x2 1 1 x1，x2，x3∈｛0，1｝． タイプＬの整数計画問題 max. ∑｛di ・xi ｜i は区間｝ s. t. ∑｛ei｜i は終端駅｝＝2， 任意の分岐駅i についてbi ∈｛0，2｝， 任意の区間i についてxi ∈｛0，1｝． → 部分巡回路が含まれる解が得られる 部分巡回路の除去，計算結果 タイプＬのＩＰを解くと，部分巡回路を含む → 部分巡回路除去制約を加える 切除平面法を実行 45本の除去制約，9回の再計算（1回3分未満） タイプＬの最適解 11925.9km タイプＰｅの整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝1， 任意の分岐駅i についてbi ∈｛0，2，3｝， 「bi ＝3となるi は高々1個」， 任意の区間i についてxi ∈｛0，1｝． 「bi ＝3となるi は高々1個」 「bi ＝3となるi は高々1個」という条件を 線形制約で表現 → 新たな0-1変数fi を定義 任意の分岐駅i についてfi ≧bi －2， fi ∈｛0，1｝， ∑｛fi ｜i は分岐駅｝＝1． タイプＰｅの計算結果 タイプＰｅのＩＰは，実際には緩和問題 （部分巡回路を含む） タイプＰｅ（緩和問題）の最適解 11286.5km （＜ タイプLの最適解11925.9km） 計算時間156秒 → タイプPeはＬＯＰの最適解ではない タイプＰｎの緩和問題 タイプＰｎは隣接駅（約800個）も考える必要有 → タイプＰｎを緩和し，タイプＢを定義する タイプＢ：2つのループを1本の線で結んだ形 タイプＰｎの緩和，変数の減少！ タイプＢの整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝0， 任意の分岐駅i についてbi ∈｛0，2，3｝， 「bi ＝3となるi は高々2個」， 任意の区間i についてxi ∈｛0，1｝． タイプＢの計算結果 タイプＢのＩＰは，実際には緩和問題 （部分巡回路を含む） タイプＢ（緩和問題）の最適解 11916.3km （＜ タイプLの最適解11925.9km） 計算時間40秒 → タイプＰｎはＬＯＰの最適解ではない 実験結果 統合した路線図において タイプＬの最適解（ループ無）：11925.9 km 計算時間：1回3分未満，9回の再計算 タイプＰｅ：11286.5km（156秒，緩和問題） タイプＢ：11916.3 km（40秒，緩和問題） → タイプＬが最適解！ 最長片道きっぷのルート 経路：稚内（北海道） →本州→ 肥前山口（佐 賀） 総路線距離： 11925.9km （60％，4.6倍） 運賃： 93,870円 （学割75,090円） 有効日数： 59日 （途中下車可） 日程： 乗換え150回以上，最速で約15日， 42都道府県（四国，沖縄以外） まとめ ＬＯＰに対し，詳細な分析と適切なモデル化を 行うことにより，最適解を求めることに成功した 興味を持たれた方は… 解法詳細 http://www.swa.gr.jp/lop/ 旅行報告 http://www.swa.gr.jp/plop/ 資料をご覧いただき，ありがとうございました． 以下は追加のスライドです． bi ∈｛0，2｝（4分岐以上） bi （＝x1＋x2＋x3＋x4）∈｛0,2｝ → －x1＋x2＋x3＋x4≧0， ＋x1－x2＋x3＋x4≧0， ＋x1＋x2－x3＋x4≧0， ＋x1＋x2＋x3＋x4≦2， x1，x2，x3，x4∈｛0，1｝． 「bi ＝3となるi は高々2個」 「bi ＝3となるi は高々2個」という条件を 線形制約で表現 → 新たな0-1変数fi を定義 任意の分岐駅i についてfi ≧bi －2， fi ∈｛0，1｝， ∑｛fi ｜i は分岐駅｝＝2． bi ＝3となるi は高々1個（4分岐以 上） 「bi ＝3となるi は高々1個」という条件 分岐駅i が4分岐以上だったら？ （例） b1＝x1＋x2＋x3＋x4 f11≧x1＋x2＋x3－2， f12≧x1＋x2＋x4－2， f13≧x1＋x3＋x4－2， f14≧x2＋x3＋x4－2， fi ∈｛0，1｝，∑｛fi ｜i は分岐駅｝＝1． タイプＢ（8の字）の整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝0， 任意の分岐駅i についてbi ∈｛0，2，4｝， 「bi ＝4となるi は高々1個」， 任意の区間i についてxi ∈｛0，1｝．
© Copyright 2024 ExpyDoc
