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

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

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

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

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

ＪＲ路線図の分析（2000年7月現在） 本州： 3,332 駅 14424.9km 北海道： 478 駅 2499.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 x2 x3 max. ∑｛di ・xi ｜i は区間｝ x4 di は区間i の距離

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

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

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

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

タイプＬの整数計画問題 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回の再計算 → タイプＬが最適解！

最長片道きっぷのルート 経路：稚内（北海道） →本州→ 肥前山口（佐賀） 総路線距離： 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，

「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｝．