最長片道きっぷの厳密解を求める
東京大学大学院
宮代隆平,葛西隆也
本資料の概要
「最長片道きっぷ」のルートを求める
・ 最長片道きっぷとは?
・ 路線図の分析
・ 整数計画問題としてのモデル化
・ 求めた最長ルートの紹介
「最長片道きっぷ」とは?
・ 最長距離のルートをたどる「片道きっぷ」
・ 最長路問題と似ているが,若干異なる(後
述)
・ 最長片道きっぷのルートを求める問題:LOP
(Longest One-way ticket Problem)
LOPに関するメモ
LOPの最適解(=最長片道きっぷのルート)
→ {出発駅,到着駅,その間の最長片道経
路}
の三つ組みを決定する
東大旅行研(1962,中央公論社) ー 手作業
山路,林(1994,OR学会誌) ー 近似解法
目標:数理的手法により,最適解を求める
片道きっぷとなる条件
・ 折り返しを含まない → 引き返せない
・ ループ一周を超えない
→ 同じ駅に二度たどりついたら,そこで終了
タイプL タイプO タイプP
日本では,最適解はタイプOではない
JR路線図の分析(2000年7月現在)
本州: 3,332 駅 14424.9km
北海道: 478 駅 2499.8km
九州: 570 駅 2101.1km
四国: 259 駅
855.8km
本州と他三島とは,一路線で接続している
→ 最適解は本州上の駅を含む
駅の分類
●
●
●
●
終端駅(行止りの駅,81個)
分岐駅(路線が分岐している駅,269個)
隣接駅(分岐駅の隣の駅,約800個)
その他の駅(以上に属さない駅,約3,500個)
駅の削除
LOPの最適解の形状は L P のいずれか
→ 「その他の駅」は最適解の発着駅ではない
考慮すべき駅数
4,639 → 約1,150
タイプLに関する考察
タイプL(一本道)の発着駅の候補は?
・ 分岐駅●は最適解の発着駅ではない
・ 隣接駅●も最適解の発着駅ではない
→ タイプP
発着駅の候補は
終端駅●の
み!
タイプPに関する考察
タイプPの場合,到着駅=分岐駅
出発駅は二つの可能性がある
・ 終端駅
(タイプPe;end)
・ 隣接駅
(タイプPn;neighbor)
計算の方針
タイプ別に場合分けし,IPを作成して解く
・ タイプL (厳密解を求める)
・ タイプPe (緩和問題)
・ タイプPn (緩和問題)
計算環境:PentiumⅡ400MHz PC
IPソルバー:CPLEX6.0
路線図の定式化
LOPを整数計画問題として定式化
→ 路線図(終端駅と分岐駅のみ)において
各区間に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
変数節約の工夫
変数節約のため,まず本州以外の三島に関し
最適解をそれぞれ求め,路線図を統合
最終的なIPの規模:
区間変数399個,駅変数289個
(タイプPe,Pnではさらに人工変数460個)
タイプLの制約条件
タイプLの発着駅は終端駅
→∑{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}.
タイプLの整数計画問題
max. ∑{di ・xi |i は区間}
s. t. ∑{ei|i は終端駅}=2,
任意の分岐駅i についてbi ∈{0,2},
任意の区間i についてxi ∈{0,1}.
→ 部分巡回路が含まれる解が得られる
部分巡回路の除去,計算結果
タイプLのIPを解くと,部分巡回路を含む
→ 部分巡回路除去制約を加える
切除平面法を実行
45本の除去制約,9回の再計算(1回3分未満)
タイプLの最適解 11925.9km
タイプPeの整数計画問題
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.
タイプPeの計算結果
タイプPeのIPは,実際には緩和問題
(部分巡回路を含む)
タイプPe(緩和問題)の最適解
11286.5km (< タイプLの最適解11925.9km)
計算時間156秒
→ タイプPeはLOPの最適解ではない
タイプPnの緩和問題
タイプPnは隣接駅(約800個)も考える必要有
→ タイプPnを緩和し,タイプBを定義する
タイプB:2つのループを1本の線で結んだ形
タイプPnの緩和,変数の減少!
タイプBの整数計画問題
max.∑{di ・xi |i は区間}
s. t. ∑ {ei|i は終端駅}=0,
任意の分岐駅i についてbi ∈{0,2,3},
「bi =3となるi は高々2個」,
任意の区間i についてxi ∈{0,1}.
タイプBの計算結果
タイプBのIPは,実際には緩和問題
(部分巡回路を含む)
タイプB(緩和問題)の最適解
11916.3km (< タイプLの最適解11925.9km)
計算時間40秒
→ タイプPnはLOPの最適解ではない
実験結果
統合した路線図において
タイプLの最適解(ループ無):11925.9 km
計算時間:1回3分未満,9回の再計算
タイプPe:11286.5km(156秒,緩和問題)
タイプB:11916.3 km(40秒,緩和問題)
→ タイプLが最適解!
最長片道きっぷのルート
経路:稚内(北海道) →本州→ 肥前山口(佐
賀)
総路線距離: 11925.9km (60%,4.6倍)
運賃: 93,870円 (学割75,090円)
有効日数: 59日 (途中下車可)
日程: 乗換え150回以上,最速で約15日,
42都道府県(四国,沖縄以外)
まとめ
LOPに対し,詳細な分析と適切なモデル化を
行うことにより,最適解を求めることに成功した
興味を持たれた方は…
解法詳細
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.
タイプB(8の字)の整数計画問題
max.∑{di ・xi |i は区間}
s. t. ∑ {ei|i は終端駅}=0,
任意の分岐駅i についてbi ∈{0,2,4},
「bi =4となるi は高々1個」,
任意の区間i についてxi ∈{0,1}.
ダウンロード

ppt file