最長片道きっぷの厳密解を求める 東京大学大学院 宮代隆平，葛西隆也.

Presentation on theme: "最長片道きっぷの厳密解を求める 東京大学大学院 宮代隆平，葛西隆也."— Presentation transcript:

1 最長片道きっぷの厳密解を求める 東京大学大学院 宮代隆平，葛西隆也

2 本資料の概要 「最長片道きっぷ」のルートを求める ・ 最長片道きっぷとは？ ・ 路線図の分析 ・ 整数計画問題としてのモデル化
・ 求めた最長ルートの紹介

3 （Longest One-way ticket Problem）
「最長片道きっぷ」とは？ ・ 最長距離のルートをたどる「片道きっぷ」 ・ 最長路問題と似ているが，若干異なる（後述） ・ 最長片道きっぷのルートを求める問題：ＬＯＰ （Longest One-way ticket Problem）

4 ＬＯＰに関するメモ ＬＯＰの最適解（＝最長片道きっぷのルート） → ｛出発駅，到着駅，その間の最長片道経路｝ の三つ組みを決定する
東大旅行研（1962，中央公論社） ー 手作業 山路，林（1994，OR学会誌） ー 近似解法 目標：数理的手法により，最適解を求める

5 片道きっぷとなる条件 ・ 折り返しを含まない → 引き返せない ・ ループ一周を超えない → 同じ駅に二度たどりついたら，そこで終了
タイプＬ タイプＯ タイプＰ 日本では，最適解はタイプＯではない

6 ＪＲ路線図の分析（2000年7月現在） 本州： 3,332 駅 14424.9km 北海道： 478 駅 2499.8km
本州と他三島とは，一路線で接続している → 最適解は本州上の駅を含む

7 駅の分類 ● 終端駅（行止りの駅，81個） ● 分岐駅（路線が分岐している駅，269個） ● 隣接駅（分岐駅の隣の駅，約800個）
● その他の駅（以上に属さない駅，約3,500個）

8 駅の削除 ＬＯＰの最適解の形状は Ｌ Ｐ のいずれか → 「その他の駅」は最適解の発着駅ではない 考慮すべき駅数
4,639 → 約1,150

9 タイプＬに関する考察 タイプＬ（一本道）の発着駅の候補は？ ・ 分岐駅●は最適解の発着駅ではない ・ 隣接駅●も最適解の発着駅ではない
→ タイプＰ 発着駅の候補は 終端駅●のみ！

10 タイプＰに関する考察 タイプＰの場合，到着駅＝分岐駅 出発駅は二つの可能性がある ・ 終端駅 （タイプＰｅ；end） ・ 隣接駅
（タイプＰｎ；neighbor）

11 計算の方針 タイプ別に場合分けし，ＩＰを作成して解く ・ タイプＬ （厳密解を求める） ・ タイプＰｅ （緩和問題）
・ タイプＰｎ （緩和問題） 計算環境：PentiumⅡ400ＭＨｚ PC IPソルバー：CPLEX6.0

12 路線図の定式化 ＬＯＰを整数計画問題として定式化 → 路線図（終端駅と分岐駅のみ）において 各区間に0-1整数変数を割り当てる
xi ＝1（区間i を使う）， xi ＝0（区間i を使わない） 目的関数 x x x3 max. ∑｛di ・xi ｜i は区間｝ x4 di は区間i の距離

13 駅変数の導入 終端駅と分岐駅にも整数変数を定義 終端駅をei ，分岐駅をbi とする 駅変数：駅に接続している区間を何回使うか
e1＝x1, e2＝x3, e1 x1 b1 x2 b2 x3 e2 b1＝x1＋x2＋x4, b2＝x2＋x3＋x4． x4

14 変数節約の工夫 変数節約のため，まず本州以外の三島に関し 最適解をそれぞれ求め，路線図を統合 最終的なＩＰの規模：
区間変数399個，駅変数289個 （タイプＰｅ，Ｐｎではさらに人工変数460個）

15 タイプＬの制約条件 タイプＬの発着駅は終端駅 →∑｛ei｜i は終端駅｝＝2， 任意の分岐駅i についてbi ∈｛0，2｝． ループは除去

16 bi ∈｛0，2｝の線形制約による表現 bi （＝x1＋x2＋x3）∈｛0,2｝を線形制約で表現 x1 bi x2 x3 x3

17 タイプＬの整数計画問題 max. ∑｛di ・xi ｜i は区間｝ s. t. ∑｛ei｜i は終端駅｝＝2，
任意の分岐駅i についてbi ∈｛0，2｝， 任意の区間i についてxi ∈｛0，1｝． → 部分巡回路が含まれる解が得られる

18 部分巡回路の除去，計算結果 タイプＬのＩＰを解くと，部分巡回路を含む → 部分巡回路除去制約を加える 切除平面法を実行
45本の除去制約，9回の再計算（1回3分未満） タイプＬの最適解 km

19 タイプＰｅの整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝1，
任意の分岐駅i についてbi ∈｛0，2，3｝， 「bi ＝3となるi は高々1個」， 任意の区間i についてxi ∈｛0，1｝．

20 「bi ＝3となるi は高々1個」 「bi ＝3となるi は高々1個」という条件を 線形制約で表現 → 新たな0-1変数fi を定義
任意の分岐駅i についてfi ≧bi －2， fi ∈｛0，1｝， ∑｛fi ｜i は分岐駅｝＝1．

21 タイプＰｅの計算結果 タイプＰｅのＩＰは，実際には緩和問題 （部分巡回路を含む） タイプＰｅ（緩和問題）の最適解
km （＜ タイプLの最適解 km） 計算時間156秒 → タイプPeはＬＯＰの最適解ではない

22 タイプＰｎの緩和問題 タイプＰｎは隣接駅（約800個）も考える必要有 → タイプＰｎを緩和し，タイプＢを定義する
タイプＢ：2つのループを1本の線で結んだ形 タイプＰｎの緩和，変数の減少！

23 タイプＢの整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝0，
任意の分岐駅i についてbi ∈｛0，2，3｝， 「bi ＝3となるi は高々2個」， 任意の区間i についてxi ∈｛0，1｝．

24 タイプＢの計算結果 タイプＢのＩＰは，実際には緩和問題 （部分巡回路を含む） タイプＢ（緩和問題）の最適解
km （＜ タイプLの最適解 km） 計算時間40秒 → タイプＰｎはＬＯＰの最適解ではない

25 実験結果 統合した路線図において タイプＬの最適解（ループ無）：11925.9 km 計算時間：1回3分未満，9回の再計算
→ タイプＬが最適解！

26 最長片道きっぷのルート 経路：稚内（北海道） →本州→ 肥前山口（佐賀） 総路線距離： 11925.9km （60％，4.6倍）
運賃： 93,870円 （学割75,090円） 有効日数： 59日 （途中下車可） 日程： 乗換え150回以上，最速で約15日， 42都道府県（四国，沖縄以外）

27 まとめ ＬＯＰに対し，詳細な分析と適切なモデル化を 行うことにより，最適解を求めることに成功した 興味を持たれた方は…
解法詳細 旅行報告

28 資料をご覧いただき，ありがとうございました．
以下は追加のスライドです．

29 bi ∈｛0，2｝（4分岐以上） bi （＝x1＋x2＋x3＋x4）∈｛0,2｝ → －x1＋x2＋x3＋x4≧0，

30 「bi ＝3となるi は高々2個」 「bi ＝3となるi は高々2個」という条件を 線形制約で表現 → 新たな0-1変数fi を定義
任意の分岐駅i についてfi ≧bi －2， fi ∈｛0，1｝， ∑｛fi ｜i は分岐駅｝＝2．

31 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．

32 タイプＢ（8の字）の整数計画問題 max．∑｛di ・xi ｜i は区間｝ s. t. ∑ ｛ei｜i は終端駅｝＝0，
任意の分岐駅i についてbi ∈｛0，2，4｝， 「bi ＝4となるi は高々1個」， 任意の区間i についてxi ∈｛0，1｝．