均衡配分を用いた少子高齢化による鉄道利用変化予測

(1)

中央大学理工学部情報工学科卒業論文

均衡配分を用いた少子高齢化による鉄道利用変化予測

学籍番号

01D8102001C

川口真由

指導教員田口東教授

2005年3月

(2)

あらまし

近年，日本では，出生率・死亡率が低下し，少子高齢化が進んでいる．今後も，少子高齢化が進み，生産年齢人口は減少していくことが予測されている．少子高齢化の影響として，経済や年金問題が大きく取り上げられるが，その一つとして，利用者のほとんどが通勤・通学客で占められている鉄道は，需要が大幅に減少し，収益が減少すると考えられる．

本研究では，将来推計人口と大都市交通センサスより，平成12年から平成42年までの5 年おきに，OD交通量(O: Origin(起点)，D: Destination(終点))を推計する．対象とするのは，

東京首都圏の電車を利用する定期券利用者のうち，朝6時から 9時半の間に駅を出発し，

目的駅まで到着する，約700万人の乗客と，首都圏のJR線私鉄線合計128路線の通勤・

通学時間帯の電車のほとんどである．将来OD交通量推計結果より，総鉄道利用者数は30

年で 10%強減少する，という結果が得られた．駅別乗降車人数と路線別のべ利用者数の経

年変化を求めた結果，駅毎の乗車人数の増減には，地域によって差が見られるが，駅毎の降車人数の増減には，地域によって差は見られない．路線別にのべ利用者数の経年変化を見ると，平成42年には，平成12年と比較して，対象128路線のほとんどの路線でのべ利用者数は減少する．その減少幅は路線によって異なり，特に大きく減少するのは，東武伊勢崎線，東武東上線，東京メトロ日比谷線，東京メトロ千代田線，JR常磐線，東武野田線である．

また，OD交通量の経年変化による影響を見るため，利用者均衡配分を行なう．結果として，各利用者が最善の経路を選択するため，乗客分布に大きな変化は見られないが，乗車率は減少することがわかる．

キーワード：少子高齢化，将来推計人口，OD交通量，利用者均衡配分

(3)

第

1

章はじめに

現在，日本では，出生率・死亡率の低下により，少子高齢化が進んでいる．少子高齢化に伴い，経済の基盤である生産年齢(15〜64歳)人口は，減少すると考えられている．文献[10]

によれば，生産年齢人口は，平成12年に8,638万人(総人口のおよそ68.1%)であったが，

平成27年には7,730万人(総人口のおよそ61.2%)，平成42年には6,958万人(総人口のお

よそ59.2%)に減少する(図1.1)．

一方，東京首都圏では，通勤・通学手段として，広く鉄道が利用されているため，通勤・

通学時間帯には利用者が集中し，混雑している．文献[9]によると，首都圏では鉄道利用者のうち，およそ70%が定期券利用者である．

以上より，鉄道需要は今後，少子高齢化の影響を大きく受け，変化すると考えられる．

よって，本研究では，人口の変化を用いて，OD交通量を推計するモデルを構築することを目的とする．

0 2 4 6 8 10 12 14

平成12年平成17年平成22年平成27年平成32年平成37年平成42年

歴年

人口[千万人]

65歳以上 15〜64歳 0〜14歳

図1.1 日本の将来人口

(5)

第

2

章ネットワークモデル

東京首都圏の鉄道網は，環状に走るJR山手線を境界として，外側へは放射状に，内側へはくもの巣状に張りめぐらされている．本研究の対象範囲を図2.1に示す．この範囲は，128 路線1815駅で構成されている．

本研究では，乗り換え，待ち時間，優等列車(各駅停車以外の列車)等の効果を考慮するために，図2.1のような空間ネットワークに時間の概念を加えた，時間‐空間ネットワークを利用する．時間を表現するためには，各ノードの時刻座標，すなわち，各電車の時刻表が必要となる．しかし，電子媒体の時刻表は非常に高額であるため，入手することは金銭的に困難である．一方，紙媒体の時刻表をすべて手作業で入力することは，莫大な時間を必要とし，研究の本質とは異なる．そこで，本研究では，運転パターン毎に代表電車を選び，

その運行スケジュールを始発駅出発時刻に沿って平行移動する手法を用いて得られた時刻表を利用する[6]．

2.1

単一路線のネットワーク

駅をノード，鉄道による駅間の移動をリンクで表すと，単一路線のネットワークは図2.2 のように表すことができる．

また，列車種別を考慮すると，図2.3のように表すことができる．図2.3において，青いリンクが各駅停車による移動，赤いリンクが優等列車による移動，破線のリンクが異なる種別の列車へ乗り換える移動を表している．

2.1

(6)

図2.2 単一路線の鉄道ネットワーク図2.3 単一路線の鉄道ネットワーク (列車種別を考慮したもの)

乗り換え，待ち時間，優等列車等の効果を考慮し，鉄道利用者の移動を表現するためには，駅間の移動のような空間的な移動はもちろん，それに伴う時間の変化も考える必要がある．時間の変化を考える場合，動的に問題を解く必要があるが，本研究で扱う首都圏鉄道網のように，大規模なネットワークフロー問題を，動的に解くことは非常に困難である．

しかし，ネットワークを構築する際，駅毎にノードを定義するのではなく，駅で電車が発車する毎にノードを定義することで，ネットワークを時間方向に拡張することができ，動的な利用者の流れを静的なネットワークの流れとして表現することができる[4, 6, 7]．この方法を用いると，ネットワークの規模が非常に大きくなってしまうが，動的に問題を解くことに比べ，容易に解を得ることができる．

図2.2，図2.3のように表される単一路線のみで構成された鉄道ネットワークを，時間‐

空間ネットワークに拡張する．

単一路線のみのネットワークを考える場合，利用者はネットワーク上で，以下のような行動を取ると考えられる．

・発駅(最初の乗車駅)から電車に乗車する行動．

・駅で，次の電車を待つ行動．

・電車に乗車して，次の駅へ移動する行動．

・電車から降車して，異なる種別の電車に乗り換える行動．

・着駅(最後の降車駅)で電車から降車する行動．

このような行動を，ネットワークにおけるノードとリンクとして定義する．

駅ノード：各駅における各電車の停車．

出発ノード：利用者の鉄道利用開始．

到着ノード：利用者の鉄道利用終了．

乗車リンク：発駅から電車に乗車する行動．

降車リンク：着駅で電車から降車する行動．

電車リンク：電車に乗車して，駅間を移動する行動．

待ちリンク：駅で，次の電車を待つ行動．

(7)

電車リンクと待ちリンクのリンクコストは所要時間，乗車リンクと降車リンクのリンクコストは0とする．

ここで，出発ノード・到着ノード・乗車リンク・降車リンクは，各利用者に固有なものであり，これらのノードとリンクは利用者によって変更される．よって，これらを除いたネットワーク(以下，単一路線乗り換えネットワークとする)を構築する(図2.4)．

次に，単一路線乗り換えネットワークに流入する利用者に対応するソースと，同ネットワークから流出する利用者に対応するシンクを付加したネットワーク(以下，利用者ネットワークとする)を構築する．

まず，各駅を出発する利用者を15分毎にまとめ，ソースを作る．そして，対応する時間帯に発車する電車を表すすべての駅ノードへリンク(乗車リンク)を張る．シンクは，駅毎に作成し，その駅に到着するすべての電車を表すノードからシンクへリンク(降車リンク)を張る(図2.5)．

+1

a 駅 a+2駅 a+3駅 a+4駅 a駅

図2.4 単一路線乗り換えネットワーク

電車リンク(普通) 電車リンク(優等) 待ちリンク駅ノード +1

n 本目電車

+2

n 本目電車

n本目電車

電車リンク(普通) 電車リンク(優等) 待ちリンク乗車リンク降車リンク駅ノードソースシンク図2.5 単一路線の利用者ネットワーク

(8)

2.2

乗り換えネットワーク

本研究では，首都圏128路線を対象とするので，2.1節のような単一路線のネットワークを，複数路線に拡張する必要がある．複数路線を考えると，利用者はネットワーク上で，

2.1 節で挙げた行動以外に，「異なる路線に乗り換える」という行動を取ると考えられる．

よって，2.1節で定義したリンクに加え，乗り換えリンクを以下のように定義する．

乗り換えリンク：電車から降車して，異なる路線のホームへ移動し，電車を待つ行動．

乗り換えは，異なる 2 本以上の路線が停車する駅，または，徒歩で移動が可能な駅対において行なわれる．各駅の構造によって，乗り換えにかかるコストは異なる．同一構内にあって，ほとんど時間をかけずに乗り換えができる駅対では，乗り換えリンクは，図2.6のように待ちリンクとして表現することができる．このような駅を同一駅と呼ぶ．

電車リンク(路線A) 電車リンク(路線B) 待ちリンク

駅ノード図2.6 乗り換えネットワーク

(同一構内で乗り換え可能)

電車リンク(路線A) 電車リンク(路線B) 待ちリンク

乗り換えリンク駅ノード(路線A) 駅ノード(路線B) 図2.7 乗り換えネットワーク

(9)

一方，改札を経由して乗り換えを行なう駅対(乗り換え可能駅と呼ぶ)のネットワークを，

図2.7に示す．また，JR東京駅の山手線から京葉線への乗り換えは，改札を経由しないが，

乗り換えに5分以上を要する．このようなものは乗り換え可能駅とする[7]．

乗り換え可能駅間における乗り換えリンクのリンクコストは，駅間の距離を時間に換算して与える．乗り換え可能駅対の座標を，それぞれ(x1, y1) (, x2, y2)^{とし，駅間の移動時間}

を，

( ) ( )

55 2

2 2 1 2 2

1−x + y − y +

x (分) (2.1)

とする．式(2.1)において，利用者の歩行速度を，分速 55m(時速 3.3km)とした．また，改札を経由することを考慮し，2分加算する．乗換リンクコストは，式(2.1)で求められる駅間移動時間に，移動後の駅で次の電車が到着するまでの待ち時間を加算した値とする．

乗り換え可能駅間における乗り換えリンクは，乗り換え前の駅ノードから，乗り換え後の駅ノードのうち式(2.1)で求めた駅間移動時間を足して間に合う最早の駅ノードへのリンクとする．

以上より，地表面に垂直な方向に時間軸を取り，首都圏の鉄道網を時間‐空間ネットワークで表すと，図2.8のようになる．

図2.8 時間‐空間ネットワーク

(10)

第

3

章交通量配分

道路や鉄道を利用して，利用者がある目的地までの移動を考えるとき，複数の経路があるとする．この場合，各利用者は所要時間・混雑度・料金などのネットワーク上のコストを考慮し，経路を選択すると考えられる．各利用者が各々の判断に従い経路を選択すると，

ネットワーク全体としてバランスが取れた状態(均衡状態)になる．この均衡状態を求める問題は，ある目的関数を最小化する数理最適化問題と等価であることが，Beckmannら(1956) によって示されている．ネットワークの均衡状態を求める問題を，交通量配分問題という．

3.1

利用者均衡配分

交通量配分原則は，Wardrop(1952)により提唱され，以下のように定義されている．

Wardropの第1原則

利用される経路の旅行時間は皆等しく，利用されない経路の旅行時間よりも小さいか，

せいぜい等しい(等時間原則)．

この配分原則は，

① すべての利用者は常に旅行時間を最小とするように行動する(最小費用経路選択仮説)

② 利用者は常に利用可能な経路についての完全な情報を得ている(完全情報仮説)

という前提条件の下で成立する．Wardropの第1原則は，利用者が各々の経路選択行動を最適化した結果到達する均衡状態を表すものであることから，利用者均衡配分(UE: user equilibrium assignment)と呼ばれる．

3.2

利用者均衡の定式化

Wardropの第1原則を満たす利用者均衡は，配分モデルとして以下のように定式化され

る．

>0

rs

fk のとき c_k^rs =c_rs ∀k∈K_rs, ∀rs∈Ω (3.1a)

=0

rs

fk のとき c_k^rs≧c_rs ∀k∈K_rs, ∀rs∈Ω (3.1b) 制約条件：

(11)

=0

∑ −

∈ rs

K k

rs

k Q

f

rs

Ω

∈

∀rs (3.1c)

≧0

rs

fk ∀k∈K_rs, ∀rs∈Ω (3.1d)

ここで，

：ODペア間第経路の経路交通量 f_krs

k

rs k

：ODペア間第経路の経路所要時間で，

crs rs k

リンク所要時間，リンク交通量の関数

：ODペア間の最短経路所要時間

crs rs

：ODペア間分布交通量

Qrs rs

：ODペア間の有効経路集合

Krs rs

：ODペアの集合

Ω rs

である．

式(3.1)は，利用されている経路( )の所要時間は，に皆等しく，利用されて

いない経路( )の所要時間よりも小さいか，せいぜい等しい，という利用者均衡の条件を表している．また，式(3.1)は以下の式と等価である．

>0

rs

fk c_k^rs c_rs

=0

rs

fk

(

⁻ rs

)

⁼⁰

rs k rs

k c c

f ∀k∈K_rs, ∀rs∈Ω (3.2a)

(

rs

)

^≧⁰

rs

k c

c − ∀k∈K_rs, ∀rs∈Ω (3.2b)

既述の式は，経路交通量および経路所要時間による記述である．経路が幾つかのリンクから構成される一般のネットワークで表記する場合，経路所要時間を以下のように置き換えればよい．

rs

ck

∑ ( )

∈

=

A

a a a

rs k a rs

k t x

c δ _, ∀k∈K_rs, ∀rs∈Ω (3.3a)

∈∑ ∑∈Ω

=

Krs

k rs

rs k rs

k a

a f

x δ _, ∀a∈A (3.3b)

(12)

ここで，

：リンクaのリンクコスト関数

( )a a x t

：リンクaのリンク交通量 xa

：リンクaの集合 A

⎩⎨

=⎧

を含まないとき経路がリンク

間第ペア

を含むとき経路がリンク

間第ペア

a k

rs

a k

rs rs

k

a 0 :OD

OD : 1 δ ,

である．

3.3

非線形最適化問題

3.2節で述べた利用者均衡は，等価な最適化問題として以下のように表される[8]．

最小化 _{∑ ∫} ( )

∈

=

A a

x a p

at w w

Z ₀ d (3.4a)

制約条件 ∑ − =0

∈K_rs k

rs rs

k Q

f ∀rs∈Ω (3.4b)

∈∑ ∑∈Ω

=

Krs

k rs

rs k rs

k a

a f

x δ _, ∀a∈A (3.4c)

(3.4d)

≧0

rs

fk

(3.4e)

≧0 xa

これは，前述の利用者均衡の式(3.1)および式(3.2)を，目的関数を持つ最小化問題として置き換えたものであり，式(3.4a)を最小化することによって，式(3.1)の利用者均衡の条件が得られる．この式は，制約条件付き非線形最適化問題であり，最適性条件である

Kuhn-Tucker条件より算出される解は，利用者均衡を満足するフローである．このことを，

以下に示す．

まず，式(3.4)をLagrangian関数として再定義し，非負制約式(3.4d), (3.4e)以外に制約条件を持たない， f_k^rsに関する最適化問題に置き換える．

(3.5a)

( ) ( ) ∑ ∑

Ω

∈ ∈ ⎭⎬⎫

⎩⎨

⎧ −

−

=

rs rs

K k

rs k rs

p f f Q

Z f

L

rs

λ λ

,

(3.5b)

≧0 f_krs

(13)

ここで，λ_rsはODペアに対するLagrangian乗数である．このLagrangian関数の最適性条件はKuhn-Tucker条件より，以下のようになる．

rs

( ^*^, ^*)₌₀

∂

rs k rs

k f

f

f L λ

and ( ^*^, ^*)_≥₀

∂

rs

fk

f

L λ _,

≧0

rs

fk ∀k, ∀rs (3.6a)

( ^*^, ^*)₌₀

∂

rs

f L

λ

λ ∀rs (3.6b)

式(3.6b)は等式制約条件式(3.4b)となることがわかる．また，式(3.6a)は次式を意味する．

のとき

≧0

rs

fk =0

∂

rs

fk

L

Krs

k∈

∀ , ∀rs∈Ω (3.7a)

のとき

=0

rs

fk ≧0

rs

fk

L

∂

Krs

k∈

∀ , ∀rs∈Ω (3.7b)

ここで，

rs

fk

L

∂

∂ ( )

rs k

rs k K rs

rs k rs rs

k A a

x a

f

Q f f

dw w t

rs a

∂

⎥⎦

⎢ ⎤

⎣

⎡

⎭⎬

⎫

⎩⎨

⎧ −

∂

∂ −

⎭⎬

⎫

⎩⎨

∂⎧

=

∑ ∑

∑ ∫ _∈_Ω _∈

∈ 0 λ

{

( )

}

rs A

a rs

k a a

x a

f x x

dw w t

a

λ

∂ −

⋅ ∂

= ∑ ∫

∈ d

d ₀

Krs

k∈

∀ , ∀rs∈Ω (3.8a)

である．

また，

rs k

a

f x

∂

∂ rs

k rs a

k rs k K

rs k rs

k a

f f

rs

, ,

δ δ

∂ =

⎭⎬

⎫

⎩⎨

∂⎧

=

∑ ∑∈Ω ∈

∀k∈K_rs, ∀rs∈Ω, a∈A (3.8b)

より，

(14)

rs

fk

L

∂

∂ ( ) _rs

A

a a a

rs k

a t x λ

δ −

= ∑

∈ , ∀k∈Krs, ∀rs∈Ω (3.8c)

である．また，は経路所要時間を表している．以上より，式(3.7)は以下のように書き換えることができる．

( )

∑∈A

a a a

rs k a_, t x

δ c_k^rs

のとき

≧0

f_krs c_k^rs −λ_rs =0 ∀k∈K_rs, ∀rs∈Ω (3.9a)

のとき

=0

f_krs c_k^rs −λ_rs≧0 ∀k∈K_rs, ∀rs∈Ω (3.9b)

ここで，は経路所要時間である．よって，式(3.9a)は，利用されている経路( ) の経路所要時間は，すべて

rs

ck f_k^rs≧0

λrsに等しいことを意味する．一方，式(3.9b)は，利用されていない経路( f_k^rs =0)の経路所要時間は，λ_rsより大きいか，せいぜい等しいことを意味する．

また，経路所要時間はλ_rsより小さいものはないことから，λ_rsはODペア間の最短経路所要時間と解釈できる．すなわち，式(3.9)は，利用者均衡の定義(式(3.1))そのものである．

よって，最適化問題(3.4)を解くことで，利用者均衡を満足する解を得ることができる．

rs

次に，この問題の解の一意性を証明する．最適化問題が唯一の解を持つためには，

① 制約条件式によって示される変数の実行可能領域が凸である

② 目的関数が狭義の凸関数である

ことが証明されればよい．まず，制約条件式がすべて線形であることから①変数の実行可能領域の凸性は保証される．また，②目的関数Zが狭義凸関数であることを証明するには，

リンク交通量に関する Hessian(2 次の偏微分マトリックス)が正定値行列となっていることを示せばよい．式(5.4a)より，

xa

( )a a a

p t x

x Z =

∂

∂ ∀a∈A (3.10a)

( ) ( )

( )

⎢⎢

⎢

⎣

⎡

=

= >

∂

のとき

b a

b x a

x t x x

Z

a a a

b a

p

0 d 0

2 d

A b

a ∈

∀ , (3.10b)

よって，Hessianは以下のような対角行列(対角要素以外は0の行列)となる．

(15)

( )

⎥⎥

⎥

⎦

⎤

⎢⎢

⎢

⎣

⎡

=

∇

n n n a

a a p

x x t x

x t x

x t Z

d 0 d

d d d 0 d

1 1 1

2

L

M M

L

(3.11)

一般にリンクコスト関数は単調増加関数であるから，

( ) 0 d

d >

a a a

x x

t ∀a∈A (3.12)

となる．任意のベクトルh(≠0)に対して，

( ) ^{( )} 0

d

2 d

2 = ⋅ >

∇ ∑

∈A

a a

a a a p

T

x x h t

Z h

h (3.13)

となり，は正定値であることがわかる．よって，②目的関数が狭義の凸関数であることも示されたので，利用者均衡配分問題の解の一意性が証明された．

Zp

∇2 Z_p

3.4 Dijkstra

法

本節では，交通ネットワーク問題を解くにあたり，不可欠な最短経路探索法の一つであ

るDijkstra法について説明する．Dijkstra法は，起点ノードにより近いノードから順に，

全方向に向かって，最短経路を列挙していく方法で，一つの起点からすべての終点までの最短経路と最小コストを同時に求めることができる．

このアルゴリズムにおいて，全ノードは，

① K：起点からの最短経路と最小コストが既に確定されたノードの集合o

② K：起点からの最小コストが確定されていないノードの集合 o

に分けられる．計算の進行とともに，起点を中心として，各ノードまでの最小コストが一つずつ確定し，これに伴い，ノードiが

o c_i

K に移される．すべてのノードがK に移されるまで，計算を繰り返す．

以上をまとめ，アルゴリズムを以下に示す．

Dijkstra法のアルゴリズム

(16)

Step 1 すべてのノード{j}について，仮の最小コストc_j =∞(実際の計算においては，十分

に大きな値), 最短経路においてノードの直前のノードj F_j =0, j∈K とする．

起点をとする．o

ノードに関して，o c_o =0,i=o,o∈Kとする．

Step 2 ノードから出るすべてのリンクの終点ノードi { }m について

imならば，

i

m c t

c > + c_m =c_i +t_im,F_m =iとする．

ただし，t_imは，ノードから出てノードi mに入るリンクのコストである．

Step 3 Kに含まれるすべてのノードについて， ( )p

p

j c

c =min

{

^p^:^p^∈^K

}

^なる ^と，その

ノードを求め，とする．

cj

j j∈K

Step 4 c_p =∞以外のすべてのノードがKに移っていれば終了．

そうでなければ，i= jとしてStep 2へ．

3.5 all-or-nothing

法

all-or-nothing法とは，各ODペアについて，間で最小コストをもつ経路に間の

OD交通量をすべて配分し，その他の経路には全く配分しない配分方法である．以下にアルゴリズムを示す．

rs rs rs

all-or-nothing法のアルゴリズム

Step 0 ODペアの数をN とし，通し番号n=1,2,K,Nで区別する．

Step 1 n=0とする．

すべてのリンクのリンク交通量x_ijを，x_ij =0とする．

ただし，iはリンクの始点ノード，はリンクの終点ノードである． j

Step 2 n番目のODペアの起点をとする．o

起点oから他のすべてのノードiに対して，最短経路探索を行ない，起点から他のすべてのノードへの最短コスト

o i {C_min[o→i]}と各ノードに対する先行ポインタを求める．

i Fi

Step 3 の値の降順( から遠い順)にノードを考える．ノードに流入し，か

つ最短経路ツリーに含まれるリンク

[o j

C_min → ] o j j

j F

i(= _j)→ の交通量x_ijをとする．

n ij

ij x Q

x = +

(17)

ただし，Q_nは番目のn ODペアのOD交通量である．

Step 4 n=Nであれば終了．

そうでなければ，n=n+1として，Step 2へ．

このアルゴリズムは，3.6節で述べるFrank-Wolfe法をはじめとする利用者均衡配分の解法の一部として頻繁に用いられる．

3.6 Frank-Wolfe

法

利用者均衡配分が，凸の非線形計画問題として表されることから，凸計画問題を解くアルゴリズムを用いて利用者均衡配分を解く．

凸性が保証された非線形最適化問題を解く上では，

① 自分で与えた点(初期値など)における目的関数の勾配の状況

② 目的関数が小さくなる方向に向かっていけば，必ず最小値が見つかる，という数学的証明

③ 実行可能解である 2 点を結んだ線上の点は，すべて実行可能解となる，という凸集合の性質

の3点がわかっている.この3点を用いて凸計画問題の最適解を求めるには，

Step A 現在の点から，目的関数が降下する方向の探索

Step B どれだけ進めるかの決定

の2段階のステップを繰り返す．この 2段階のステップを利用者均衡配分に適用し，以下に示す．

Step A 降下方向ベクトルの探索

回目の計算ステップにおいて与えられた点において，目的関数の勾配が大きく，より目的関数を低く降下することができると考えられる方向を探索する．制約条件によって囲まれた凸領域で，点近傍において目的関数値が降下する方向を指すように，dを決定する．交通量配分問題のように変数が多数ある次元の大きな問題では，降下方向が無数に存在するため，より効果的な方向ベクトルを選択する必要がある．また，点が制約条件上にある場合には，降下可能な方向も制約を受ける．これらのことを考慮すると，主問題の目的関数の点における 1 次のテーラー展開によって得られる近似問題を補助問題 (最適化問題)として再定義し，それを解くことによって方向ベクトル上の任意の点を求め，

降下方向ベクトルd( )を決定する．

n x⁽ⁿ⁾

)

x(n

d x⁽ⁿ⁾

)

x(n

y

)

x(n

y−

=

回目の計算ステップにおいて与えられたリンク交通量ベクトルの点において，式

(3.4a)を線形近似する．

n x⁽ⁿ⁾

(18)

( )^y ^Z^'( )^y

Z_p ≈ ( )⁽ ⁾ p( ) (⁽ⁿ⁾ ^T ⁽ⁿ⁾)

n

p Z

Z x +∇ x y−x

=

( ) (∑ ) ( )

∈ ∂

− ∂ +

=

A

a n

a n n p

a a n

p x

x x Z

y

Z ₍ ₎

) ( )

( )

x(

( ) (∑ ) ( )

∈ −

+

=

A a

n a a n a a n

p y x t x

Z x⁽ ⁾ ⁽ ⁾ ⁽ ⁾

( ) ∑ ( ) ∑ ( )

∈

∈ +

−

=

A a

n a a a A

a

n a a n a n

p x t x y t x

Z x⁽ ⁾ ⁽ ⁾ ⁽ ⁾ ⁽ ⁾ (3.14)

式(3.14)の第1項Zp( )x⁽ⁿ⁾ と第2項 ∑ ( )

∈A a

n a a n

a t x

x⁽ ⁾ ⁽ ⁾ は定数であるから，目的関数を式

(3.4)の制約条件下で最小化するために，以下の補助問題を得る．

( )^y

' Z

最小化 ( ) ∑ ( )

∈

=

A a

n a a at x y

Z' y ⁽ ⁾ (3.15a)

制約条件 ∑ − =0

∈K_rs k

rs rs

k Q

f ∀rs∈Ω (3.15b)

∈∑ ∑∈Ω

=

Krs

k rs

rs k rs

k a

a f

y δ _, ∀a∈A (3.15c)

目的関数式(3.15a)は，

{

ta

( )

xa⁽ⁿ⁾

}

の下で，リンクコストの総和を最小とするを求めることを意味する．

y

( )

{

ta xa⁽ⁿ⁾

}

はn回目の計算において定数である．よって，この補助問題は，

リンクコスト

{

ta

( )

xa⁽ⁿ⁾

}

の下で，all-or-nothing 配分を行なうことによって解が得られる．

以上より，降下方向ベクトルが求まる．

y

)

x(n

y d = −

Step B 降下距離の一次元探索

Step Aで決定された降下方向は，点近傍の目的関数の勾配のみで決定されたもの

であるため，ある程度降下すると，それ以上降下できなくなる点か，あるいは制約条件によって制約される境界に達する．よって，このいずれかの点を求める．

d x⁽ⁿ⁾

以下の式で表されるx⁽ⁿ⁺¹⁾を，もとの目的関数(3.4a)に代入し，目的関数^{Z x}( ⁽ⁿ⁺¹⁾)^を最小

(19)

化するx⁽ⁿ⁺¹⁾を得る．

(3.16a) d

x x⁽ⁿ⁺¹⁾ = ⁽ⁿ⁾ +α

ここで，d = y−x⁽ⁿ⁾なので，

( )

( ) ⁽ ⁾

) ( )

( ) 1 (

1 ⁿ

n n

n

x y

x y x

x

α α

α

− +

=

− +

+ =

(0≦α≦1) (3.16b)

である．

この計算においては，x⁽ⁿ⁾とは定数なので，式(3.16b)を代入した目的関数はy αのみを変数とする1次元最適化問題となる．α^による 1次元最適化を行なうことで，次の試行点

を求めることができる．点は実行可能解であるので，

) 1 (n+

x y 0≦α≦1上の点もまた

実行可能解となる．

) 1 (n+

x

上記Step A, Bより，Frank-Wolfe法のアルゴリズムをまとめ，以下に示す．

Frank-Wolfe法のアルゴリズム

Step 1 初期実行可能解の設定

全ODペアrsについて，各リンクの初期コスト{t_a( )0 }に基づく最短経路探索を行ない，OD 交通量をすべてこの最短経路に配分し，初期リンク交通量{ }^を

求める．( 状態でのall-or-nothing配分)

Qrs x_a⁽¹⁾

( ) {t_a 0 }

収束回数n=1^とする．

Step 2 リンクコストの更新

{ }

xa⁽ⁿ⁾ に対するリンクコスト

{

ta

( )

xa⁽ⁿ⁾

}

を計算する．

Step 3 降下方向の探索(前述Step A)

更新されたリンクコストに対してall-or-nothing配分を行ない，{ya}^{を求める．}

Step 4 降下距離の一次元探索(前述Step B)

( ) ⁽ ⁾

) 1

(ⁿ y 1 xⁿ

x_a ⁺ =α _a + −α _a (0≦α≦1)

とする．これを目的関数(3.4a)に代入し， ( ) p^{( )}^α n

a

p x Z

Z ⁽ ⁺¹⁾ = を得る．目的関数を最

α ( α )

{

⁺

}

(20)

Step 5 収束判定

あらかじめ設定したε₁,ε₂，任意に設定したK に対して，

① ( ) ( ) 1

) ( ) ( ) 1

( ≦ε

∑∈

+ −

A a

n a a n a n

a x t x

x (降下方向ベクトルに関する収束条件)

② ( )

) 2 (

) ( ) 1 (

max _n ^≦ε

a n a n a

a x

x

x ⁺ − (リンク交通量の解の変化に関する収束条件)

③ n>K (収束計算回数に関する条件) のいずれかの条件を満足すれば終了．

そうでなければ，n=n+1とおいて，Step 2へ．

Frank-Wolfe 法は，リンク交通量ベクトルをベースとして最適解を探索するため，列挙

した経路を記憶しておく必要がない．

均衡配分を用いた少子高齢化による 鉄道利用変化予測