第 58 回土木計画学研究発表会・講演集

149

ZDDを用いた複数の推奨バスルート抽出のための評価関数の推定
高根
1学生会員

2正会員

大毅1・岩倉成志2

芝浦工業大学大学院 理工学研究科（〒135-8548 東京都江東区豊洲3-7-5）
E-mail: me18074@shibaura-it.ac.jp

芝浦工業大学 教授 工学部土木工学科（〒135-8548 東京都江東区豊洲3-7-5）
E-mail: iwakura@sic.shibaura-it.ac.jp

東日本大震災の被災地である三陸地域では復興計画により土地利用や人口移動が急速に変化した．これらの変化に対応可能なバスネットワークの構築は被災地の復興を促進させていく上で喫緊の課題であるとされる．しかしながらバスネットワーク計画の多くは事業者側の経験則で意思決定がなされ，加えてバス起終点間の候補ルートを短時間且つ安定的に抽出する方法は確立されていない．本研究ではこれらの問題に対処すべく「ゼロサプレス型二分決定グラフ（ZDD）」と呼ばれるグラフ列挙探索技法を用い，短時間で且つ安定的に起終点間のバスルート候補を全列挙するとともに，列挙させたバスルート候補を選択肢集合としてバス事業者側の利得関数を設定し，そのパラメータ推定を試みる．

Key Words : zero-suppressed binary decision diagram, Mobile spatial statistics, Bus route planning

1. はじめに出せる点にある．
本研究の最終的なゴールは，ZDDを用いて被災地復興過程における急速な土地利用に対応できるバスネットワークの構築，また既存のバスルートの改善を逐次行うことが出来る計算ツールの開発であるが，本稿はその前段として，首都圏のバス事業者を対象にバス事業者の利得関数の推定方法の検討とパラメータの推定を行う．利得関数の推定は先述したZDDの技法から計算される膨大なバスルート候補を選択肢集合とし，実際のバスルートを再現する離散選択モデルを用いて行う．本研究ではその利得関数のパラメータ推定を目的とし，選択肢集合ごとに幾つかのケースに分け，パラメータ感度の妥当性を分析し，最終的なゴールである被災地におけるバスネットワーク計画へと発展させたい．
ZDDを用いて起終点間の最適なバス運行経路を抽出する研究例は既に存在する．吉野・羽藤3)らはディマンド交通の輸送経路問題を念頭に，ZDDを用いて起点から終点までの全経路数を列挙させた後，全経路の中で起点から終点までの所要時間が最小となるルートの探索を行い，ノード数の増加に伴う計算コストの特性や，追加的利用者が全体に与える影響度の評価を行っている．今後の課題では，目的変数を所要時間のみとしているため，利便2011年に発生した東日本大震災により甚大な被害を受けた三陸地域では，仮設住宅の建設や高台移転事業などにより，土地利用が急速に変化していった．復興事業が進むにつれ，住民の移動パターンや人口分布が大きく変化していった．このような急速な土地利用の変化と人口移動に迅速に対応できるバスネットワークの構築は，地域住民の生活利便性の向上，さらには被災地の復興を促進させていく上で重要な課題であり，社会的意義が高いと考える1)．
しかし従来のバスネットワーク計画の多くは，バス事業者の経験則の中で多くの意思決定がなされてきた．本
研究ではバス事業者側の経験則を客観的に表現し路線バスルート候補の抽出を図るべく，「ゼロサプレス型二分決定グラフ：zero-suppressed binary decision diagram（以下ZDD）」と呼ばれるグラフ列挙探索技法を取り扱う．
ZDDとは1993年に湊2)によって考案されたグラフ列挙探索技法であり，極めて短時間で且つ安定的にグラフの経路の列挙が可能である．本研究においてZDDを用いる利点として挙げられるのは，バス発着地間の全候補ルートを極めて短時間で抽出させ，これまでのような経験則に任せるのではなく後述する評価関数（以下，利得関数）を用いることにより運行経路の最適解及び次善解を導き1

第 58 回土木計画学研究発表会・講演集性や採算性の組み込みの必要性が述べられている．
吉野・羽藤・柳沼4)らはZDDとCross-Entropyを組み合わせてバスネットワークの最適化問題アルゴリズムを提案している．需要パターンとリンク条件に合致した路線選定が行われていることが確認されている．陸前高田市におけるバス路線計画に適用して，震災前後と，将来の需要変動下での路線延長等の各種制約付きのバス路線最適化計算がおこなわれている．
以上の研究では拡張性があることは示されているものの，目的関数は利用者の所要時間の最小または一人当たり所要時間の最小化であり，最適な経路抽出を行うためのアルゴリズムの設計と言える．一方，本研究のポイン
トは，バス事業者側の観点から複数の説明変数を組み込んだ利得関数を推定することと，ZDDの全経路列挙の特徴を活かし，最適解の抽出のみならず，複数路線の解を得て，事業者が路線計画を行う際に，人為的な意思決定の余地を残す方法を提案する点にある．以下では第2章では利得関数の設定とパラメータ推定に至る分析手法をまとめ，第3章ではパラメータの推定結果をもとに実際のバスルートとの乖離を分析し，第4章では本研究の知見と課題についてまとめる．

図-1 大宮・浦和地区内のリンクとノード(2) 利得関数の検討
ZDDで全経路の算出を行った後，バス事業者の意思決定を反映した利得計算を行う．ここではZDDで計算された膨大なバスルート候補を選択肢集合とし，その中から実際のバスルートを当てに行く離散選択モデルを用いて行う．ここで選択肢集合の設定方法であるが，今回のような大規模な道路ネットワークでは選択肢集合（全経路数）が数十万から数百万通りもあり，パラメータを推定する上で計算負荷がかかる．そこで膨大な選択肢集合からランダムに25通り，50通り，100通り抽出させ（順にケース1，ケース2，ケース3とする）それぞれのケースにおいてパラメータ推定を行う．
バス事業者 iがバスルート候補 rを選択する際の選択確率𝑝𝑖𝑟 は式(1)のようなロジットモデル型の選択確率式とし，利得関数はバスルート別の利得関数𝑉𝑖𝑟 とし，以下式(2)を構築する．（式(1)では選択肢集合を100とした時の選択確率式を表している．）

2. 分析手法(1) ZDDによる起終点間の全経路列挙について
本研究では先述の通り，被災地における最適な運行経路抽出の予備的検討として，東京都北部（北区周辺）と埼玉県南部（さいたま市大宮区から川口市にかけてのエリア）のバスネットワークを対象とし，起終点間の経路数算出とその後の利得関数の検討へと移る．本研究では対象エリアを大宮・浦和地区，川口地区，赤羽地区の3地区に分け，3地区ごとにエリア内の国道や県道・都道などを含む主要幹線道路（リンク）と交差点（ノード）をZDD上に展開させ起終点間の経路数算出を行う．図-1
は大宮・浦和地区のリンク（黒線）とノード（赤点）を示した図で，大宮・浦和地区には全19路線のバス路線がある為（川口地区は13路線，赤羽地区には11路線），始点Sと終点Gをそれぞれ19箇所定める．起終点間のルート候補となる経路数を算出させた結果，例えばS1（大宮駅東口）からG1（浦和学院高校前）が4174080通り，S2

ここで𝜃1 から𝜃4 はパラメータを表し，利得関数の説（東浦和駅北口）からG2（さいたま東営業所）が788654
通りとその数は数十万から数百万にも及ぶ．このようにして大宮・浦和地区，川口地区，赤羽地区内の全43バス路線を対象とし，始点S，終点Gを43箇所定めてから起終点間の経路数を列挙させる．この経路数を利得関数の選択肢集合として用いる．

明変数𝑄𝑖𝑟 𝐷𝑖𝑟 𝐶𝑖𝑟 𝑅𝐿𝑖𝑟 は順に潜在的利用者数，営業距離，渋滞距離，右左折回数である．1つめの潜在的利用者数はバス事業者の収益に大きく影響し，2つめの営業距離はバスの燃料費や目的地までの速達性に，3つめの渋滞距離，4つめの右左折回数はバスの定時性にそれぞれ影響していることから利得関数の説明変数に選定した．こexp⁡(𝑉 )𝑝𝑖𝑟 = ∑100 exp⁡𝑖𝑟(𝑉 )(1)

𝑉𝑖𝑟 = 𝜃1 𝑄𝑖𝑟 + 𝜃2 𝐷𝑖𝑟 + 𝜃3 𝐶𝑖𝑟 + 𝜃4 𝑅𝐿𝑖𝑟

(2)

𝑡=1

𝑖𝑟

こで潜在的利用者数𝑄𝑖𝑟 であるが，途中のバス停で乗降する人数も考慮しており，Nested Logit Modelを用いて人数の計算を行う．例として図-2の赤線をバス路線とし，

2

第 58 回土木計画学研究発表会・講演集

利用者が2から途中のノード（1,4,7,8）を経由してバスに乗車し，終点の9までの移動を考える．この時いずれかのノードからバスに乗車する人の効用を式(3)，バス以外の交通手段で移動する人の効用を式(4)，バスの乗車確率（式(5)）にOD記号Qを乗じて最終的な潜在的利用者数を式(6)で表す．
𝑉𝑏𝑢𝑠 = 𝛽𝑇2→9 + 𝜇𝑙𝑛 ∑4𝑛=1 𝑒 𝛾𝑎𝑐𝑐𝑛
𝑉𝑜𝑡ℎ𝑒𝑟 = 𝛽𝑇2→9(3)(4)
図-2 2×2格子グラフ

𝑒 𝑉𝑏𝑢𝑠𝑃𝑏𝑢𝑠 = ⁡ 𝑒 𝑉𝑏𝑢𝑠 +𝑒 𝑉𝑜𝑡ℎ𝑒𝑟(5)

𝑄𝑏𝑢𝑠1 = 𝑄 × 𝑃𝑏𝑢𝑠1(6)

β μ γ：パラメータ，𝑇2→9 ：node2→node9 の時間距離

𝑎𝑐𝑐𝑛 : バス停nへのアクセス距離 𝑄𝑏𝑢𝑠 :潜在的利用者数（node2→9）
また本研究の研究対象エリアである大宮・浦和地区，川口地区，赤羽地区では同一経路で終点まで向かうバス系統が複数散見される．例えば大宮駅東口から東方向に延びる幹線道路では，大宮地区内の各方面から大宮駅東
図-3 競合関係にあるバス路線の一例
口へと向かうバスがこの幹線道路に集中している．このような競合関係にある路線が存在した場合，潜在的利用出来るデータである．三陸地域の被災地においても適用者数はそれらの路線の便数に比例しているものとして考可能で，メッシュ間の移動量から地域住民の移動パターえる．例として図-3のような仮想のバスネットワークをンを把握できる利点もある．
構築する．AからDまではノードを表しており，路線1は本研究ではモバイル空間統計の居住地住所と時刻別の起点をC，終点をAとし，路線2は起点をD，終点をAと滞在場所のデータを基に，居住地住所を発地点，滞在場する．また路線1，路線2はBで合流し，路線1は4便，路所を着地点として，発着地点それぞれの500メートルメ線2は6便それぞれ運行されているものとする．この時Bッシュ番号を抽出させ，500メートルメッシュ間OD表をからAまでの潜在的利用者数は便数比から4/10の利用者作成した．（なおこのOD表は終日のものとする）次にが路線1を，残る6/10が路線2を利用するものと考える．
このOD表から，研究対象エリア内の各ノードが属する
以上よりBからAまでの潜在的利用者数を式(7)で表す．
メッシュ番号を抜き出して，ノード間OD表を作成した．
本研究では，このノード間OD表を基に，候補経路の潜𝑓(ℎ)
在的利用者数を算出する．
′
𝑄𝐵→𝐴= ∑ 𝑓(ℎ) 𝑄𝐵→𝐴
(7)ℎ(4) 営業距離，渋滞距離，右左折回数の算出方法
営業距離𝐷𝑖𝑟 はGoogle Mapの距離測定機能を用いて，各ノード間の距離を測定し，渋滞距離𝐶𝑖𝑟 は同じく
Google Mapの交通状況で低速部分を示す距離を測定後，各リンクに営業距離・渋滞距離の情報を与えて，各候補ルートの起終点間の営業距離・渋滞距離を測定する．右左折回数𝑅𝐿𝑖𝑟 はプログラム上で自動判別して計算をした．

式(3)の𝑓(ℎ)はバス路線hの便数を表し，𝑄𝐵→𝐴 はノードBからのノードAまでの利用者数を表している． ただ
新規ルートのバス路線の便数は，ルートが確定した後，バス運転手の人員やバスの台数，また他路線との運用の兼ね合いなど事業者側の事情を総合的に加味して決定されるため，競合路線における潜在的利用者数の推計方法については今後検討が必要である．

3. パラメータの推定と再現性(3) 使用データ
候補経路の潜在的利用者数は2017年10月調査のモバイ
ル空間統計のデータを基に，各ノード間のトリップOD表を用いて算出する．モバイル空間統計とはNTTドコモ(1) 選択肢集合毎のパラメータ推定結果選択肢集合（バスルート候補数）毎に式(2)の利得関数のパラメータ推定を行った．推定結果を表-1に示す．の携帯電話の運用データを基にして作成される人口統計情報で，居住地住所と滞在場所のデータを基に500メートルメッシュ間の移動量を1時間ごとに把握することが3ケースとも「潜在的利用者数」「営業距離」「右左折回数」のパラメータに関しては符号の整合性を確認できたが，「渋滞距離」については3ケースとも符号が正と3

第 58 回土木計画学研究発表会・講演集

説明変数
潜在的利用者数（人）
営業距離（km）
渋滞距離（km）
右左折回数（回）
初期尤度
最終尤度
尤度比
サンプル数（路線数）

表-1 パラメータ推定結果
選択肢集合25 （ケース1）
選択肢集合50（ケース2）
パラメータ
t値
パラメータt値
0.000249.86
0.00027
8.24-0.587-3.95-0.636-5.440.029
1.290.032
2.97-0.522-4.40-0.563-4.37-138.4-168.2-73.49-107.8
0.469
0.359
4343

80

頻度(回）

6050

80

選択肢100
選択肢50
選択肢25

頻度（回）

70

4030201070

選択肢10060

選択肢5050

選択肢25403020
1000

営業距離のパラメータ

潜在的利用者数のパラメータ808060504070

選択肢100
頻度（回）

頻度（回）

70

選択肢集合100（ケース3）
パラメータ
t値
0.00027
6.93-0.665
-2.71
0.033
2.52-0.590-3.53-198.0-136.10.31343選択肢50

選択肢253020

選択肢10060

選択肢5050

選択肢25403020101000

右左折回数のパラメータ

渋滞距離のパラメータ

図-4 各説明変数のパラメータ分布なった．これは渋滞距離が長ければ長い程バス事業者の利得値が高くなることを意味する結果である．ただは各説明変数のパラメータの変動の図を表しており，縦軸が度数，横軸をパラメータとしている．各説明変

本来であれば渋滞距離が長くなる程，バスの定時性が損なわれる為，バス事業者の利得が低くなると考えら数とも選択肢集合が大きくなるにつれて，パラメータのバラつきが大きいことが読み取れる．特に「潜在的れるため検討が必要である．尤度比は選択肢集合が多くなるにつれて，小さくなった．
(2) パラメータの変動分析
表-1のケース1からケース3は起点から終点までの膨大なバスルート選択肢集合からランダムに25通り，50通り，100通りのバスルートを抽出した．パラメータ推定

利用者数」は選択肢集合が25の場合は，パラメータが0.0002から0.0003の間に収束しているが，選択肢集合が100の場合はバラつきが大きく，符号が本来とは逆のマイナスになるケースもあった．また「渋滞距離」も選択肢集合が100の時のバラつきが大きく，符号がプラスになるケースも散見された．ただ各説明変数ともパラ例である選択肢集合をランダムに抽出する作業を30回繰り返してパラメータ推定を行い，各説明変数のパラメータの変動とパラメータの最頻値を分析する．図-4

メータは一定の値域に収束しており，パラメータの最頻値は明確にできた．

4

第 58 回土木計画学研究発表会・講演集(3) 実際のバスルートとの再現性評価

川口駅手前の小規模な迂回にとどまっており，重複率が高い．
ただ，図-8の利得値と重複率の関係図を見ると，大宮地区と比べて点がバラバラに分布しており，相関係数は0.691とやや低くとなった．その要因として重複率式（2）の利得関数の式にパラメータを与えた後，ZDDで列挙させた対象地域内の全バスルート候補の中で利得値𝑉𝑖𝑟 の最も高いルート，及び最適解だけでなく次善解を導き出せるというZDDの利点を活かして，利得値が高い上位40位までのルートの抽出を試みる．また抽出された上位40位までの各ルートにおいて実際に運行されているバスルートととの乖離を，重複率で分析する．重複率の計算は式(8)を用いて行う．
𝐿𝑖𝑗𝐷𝑟 =√𝐿𝑖 𝐿𝑗 ⁡は中間であるが利得値が低いルート群（図-8の青枠部分）と，重複率は低いが利得値が高いルート群（図-8の緑枠部分）とで二極化したことが考えられる．前者
は実際のバスルートとの重複率は4割から5割手前であるが，迂回により営業距離が長くなり，それに伴って利得値が低くとなった．後者は実際のバスルートとの重複率は2割程度にとどまっているが，潜在的利用者数の多いエリアを通りそれに伴って利得値が高くなった．
この2極化により相関図の点分布がばらつき相関係数もやや低い値を示した．
最後の赤羽地区では始点SをJR赤羽駅，終点Gを東武東上線のときわ台駅とした．実際のバスルートを図-9の赤実線，利得値1位のルートを緑点線で示しているが，終点のときわ台駅手前で乖離が見られた．ときわ台駅付近を走行するバスルート（他の系統も含む）は図-9の矢印のように時計回りに進みときわ台駅に到着する．その後そのまま折り返さずに時計回りで赤羽駅へと戻る進路をとるため，乖離が生じたと考えられる．
利得値2位のルートは，実際のバスルートとほぼ重複しているが，中間地点のあたりで乖離が見られた．この付近は都営三田線の志村坂上駅，志村三丁目駅付近にあたり，駅利用者で多くの人で賑わうエリアである．
またモバイル空間時計から作成したノード間OD表によると，この付近一帯のノード間OD量が高いことから，潜在的利用者数が多くなり，利得値が高くなったと考えられる．実際のバスルートと合致したのは利得値3位のルートであった．図-10は赤羽地区の重複度，利得値の相関図であるが，右上がりの直線上に分布してお(8)𝐷𝑟 : 重複率 𝐿𝑖 ：実際のバスルートの営業距離（㎞）𝐿𝑗 : バスルート候補rの営業距離(㎞)𝐿𝑖𝑗 ：𝐿𝑖 と𝐿𝑗 の共有区間（km）

本分析では実際のバスルートと利得値が1位のルートとの重複率，実際のバスルートと利得値が2位のルートとの重複率と続き，利得値上位40位までのそれぞれの重複率を計算し，利得値と重複率が相関しているかどうかを分析する．対象とする路線は大宮・浦和地区から1路線，川口地区から1路線，赤羽地区から1路線として乖離分析を行う．また使用するパラメータは先ほどの30回のパラメータ推定の中で尤度比が最も高いモデルのものを使用するものとする．使用する利得関数を以下に示す．
𝑉𝑖𝑟 = 0.00023𝑈𝑖𝑟 − 0.658𝐷𝑖𝑟 − 0.032𝐶𝑖𝑟 − 0.580𝑅𝐿𝑖𝑟(9)

𝑉𝑖𝑟 : 利得値 𝑈𝑖𝑟 ：潜在的利用者数（人）𝐷𝑖𝑟 ：営業距離（㎞）𝐶𝑖𝑟 : 渋滞距離(㎞)𝑅𝐿𝑖𝑟 ：右左折回数（回）

まず大宮地区では始点SをJR大宮駅，終点Gを浦和美園駅とした．利得値の最も高かったルートを図-5の緑点線，実際のバスルートを赤実線で示す．緑点線と赤実線が始点から終点まで全て重複していることから，利得値1位のルートは実際のバスルートと同一であることが分かる．
続く利得値2位，3位のルートも大宮駅周辺における小規模な迂回以外は実際のバスルートと同一であり，り，相関係数は0.747であった．

重複率も高い．図-6は大宮地区における利得値と重複率の関係を図で表したものである．相関係数は0.899と強い相関を示し，利得値が高い程，実際のバスルートとの重複率も高くなることが示されている．
続いて川口地区では始点S1をJR東浦和駅，終点G1をJR西川口駅とした．実際のバスルートを図-7の赤実線，技法を用いてバスルート候補を全列挙させ，列挙させた経路を選択肢集合としてバス事業者の利得関数の設定とパラメータの推定，更には実際のバスルートとの乖離分析を行った．その結果「潜在的利用者数」のパラメータの符号は正，「営業距離」「渋滞距離」「右左折回数」の符号は負となり符号の整合性を確認でき利得値1位のルートを緑点線で示す．川口地区も利得値1位のルートが始点から終点まで実際のバスルートと同一であることが分かった．利得値2位，3位ルートも西た．またパラメータの変動分析ではややバラつきはあったものの，各説明変数のパラメータが一定の値に収束した．またバスルートとの乖離分析では，利得値4. おわりに本研究では，首都圏のバス路線を対象としてZDDの5第 58 回土木計画学研究発表会・講演集

10.80.6

重複0.4 率

SG0.2
実ルート

利得値第1位

利得値第2位

利得値第3位0-50

図-5 実際のバスルートとの乖離（大宮地区）

S-40-30-20-10

利得値

0

図-6 利得値と重複度の相関図（大宮地区）

実ルート

1利得値第1位0.8

利得値第2位重複度中間
利得値低利得値第3位

0.6

重複0.4 率
重複度低利得値高0.2

G0-20
図-7 実際のバスルートとの乖離（川口地区）
実ルート

利得値第1位

利得値第2位

利得値第3位-15-10利得値-50

図-8 利得値と重複度の相関図（川口地区）

10.8
S0.6
重0.4 複率

赤羽駅へ

0.20G-12-10-8-6-4

利得値
図-9 実際のバスルートとの乖離（赤羽地区）

図-10 利得値と重複度の相関図（赤羽地区）

6

第 58 回土木計画学研究発表会・講演集

上位のルートに関しては実際のバスルートと概ね合致する結果となった．
今後の課題として，競合路線における潜在的利用者数の配分についての検討や，今回設定した4つの説明変数以外にもバスドライバーの勤務時間やバスの台数，参考文献

運用に関する変数など利得関数に組み込むべき説明変数がまだ存在するものと思われる．今後は本研究において統計学的に推計された利得関数のパラメータ感度の妥当性や利得関数に与えた説明変数の妥当性，更には組み込むべき説明変数について実際のバス会社の運行担当と議論を重ねていき，被災地のバスルート計画に適用できる計算ツールの開発を目指す．

3)

1)

2)

4)

5)

二川健吾，岩倉成志：三陸地域復興におけるモバイ
ル空間統計の活用可能性，第 69 回土木学会年次学術講演会概要集 CD-ROM,2014-9
ERATO 湊離散構造処理系プロジェクト：超高速列挙アルゴリズム，森北出版，2015.
吉野大介，羽藤英二：ゼロサプレス型二分決定グラ
フを用いたデマンド交通の運行経路の高速列挙手法の提案，土木学会論文集 D3，Vol.72，No.5，I_1229I_1239，2016.
吉野大介，羽藤英二，柳沼秀樹：列挙策引化技法を組み込んだ構造化処理による公共交通の逐次再編手法，第 55 回土木計画学研究発表会・講演集，2017.
高根大毅，岩倉成志，小山真弘：ゼロサプレス型二分決定グラフを用いたバス路線選定手法の予備的検討，土木学会第 73 回年次学術講演会，2018

謝辞： 本研究を行うにあたり，研究に対する数多くのご意見を頂いた，国際興業株式会社の小山真弘様に心より感謝申し上げます．

7