ルート割り当て

ルート割り当て、ルート選択、または交通割り当ては、輸送ネットワークにおける出発地と目的地の間のルート (パスとも呼ばれる) の選択に関するものです。これは、旅行生成、旅行分布、モード選択に続く、従来の輸送予測モデルの 4 番目のステップです。旅行分布のゾーン インターチェンジ分析により、出発地と目的地の旅行表が提供されます。モード選択分析により、どの旅行者がどのモードを使用するかがわかります。施設のニーズとコストと利点を判断するには、ネットワークの各ルートとリンク (ルートは、出発地と目的地を結ぶ一連のリンクにすぎません) の旅行者数を知る必要があります。交通 (または旅行) 割り当てを行う必要があります。高速道路と交通システムのネットワークがあり、追加が提案されているとします。まず、現在の交通遅延のパターンを知り、次に追加が行われた場合何が起こるかを知りたい と考えます。

ウィキブックオペレーションズリサーチには、輸送と割り当て問題に関するページがあります。

各ルートの利用者数を推定するという問題は、長年の懸案事項です。 フリーウェイや高速道路の開発が始まると、計画担当者はこの問題に真剣に取り組み始めました。フリーウェイは、地元の道路網よりも優れたレベルのサービスを提供し、地元の道路網から交通を迂回させました。当初は、迂回が手法でした。移動時間の比率が使用され、コスト、快適さ、サービス レベルが考慮されました。

シカゴ地域交通研究(CATS) の研究者は、高速道路と一般道路の迂回曲線を開発しました。カリフォルニア州でも多くの作業が行われました。カリフォルニア州は高速道路計画の初期の実績があったからです。迂回作業に加えて、CATS は複雑なネットワークを扱う際に生じるいくつかの技術的問題に取り組みました。その結果の 1 つが、ネットワーク上の最短経路を見つけるためのベルマン・フォード・ムーア アルゴリズムでした。

迂回アプローチが対処できなかった問題は、リンクとルート上の交通量からのフィードバックでした。多くの車両が施設を利用しようとすると、施設は混雑し、移動時間が長くなります。フィードバックを考慮する方法がないため、初期の計画研究 (実際には、1960 年から 1975 年にかけてのほとんどの研究) ではフィードバックが無視されました。彼らはムーア アルゴリズムを使用して最短経路を決定し、すべての交通を最短経路に割り当てました。これは、 iからjへのすべての交通がルートに沿って移動するか、または移動しないかのいずれかであるため、全か無かの割り当てと呼ばれます。

すべてまたはゼロまたは最短パスの割り当ては、技術的および計算的な観点からは簡単ではありません。各トラフィック ゾーンはn - 1 個のゾーンに接続されているため、考慮すべきパスは多数あります。さらに、最終的にはリンク上のトラフィックに関心があります。リンクは複数のパスの一部である場合があり、パスに沿ったトラフィックはリンクごとに合計する必要があります。

オール・オア・ナッシング方式を支持する議論もできます。その考え方は次のとおりです。計画調査は、すべてのリンクで良好なレベルのサービスが利用できるように投資を支援することです。計画されたサービス レベルに関連する移動時間を使用して、改善が実施された後の交通の流れが計算によって示されます。リンク上の交通量がわかれば、希望するサービス レベルを満たすために供給する容量を計算できます。

交通負荷が移動時間と交通均衡に与える影響を考慮するために、いくつかのヒューリスティックな計算手順が開発されました。 1 つのヒューリスティックは段階的に進行します。割り当てる交通を部分に分割します (通常は 4 つ)。交通の最初の部分を割り当てます。新しい移動時間を計算し、交通の次の部分を割り当てます。最後の手順は、すべての交通が割り当てられるまで繰り返されます。 CATS では、このバリエーションを使用して、OD テーブルで行ごとに割り当てました。

FHWAのコンピュータ プログラム コレクションに含まれるヒューリスティックは、別の方法で実行されます。

• 0. すべてまたは何もしない手順を使用して、すべてのトラフィックをロードすることから始めます。
• 1. 結果として得られる移動時間を計算し、交通を再割り当てします。
• 2. 次に、重みを使用して再割り当てを開始します。前の 2 つの負荷の重み付けされた移動時間を計算し、次の割り当てに使用します。最新の反復には 0.25 の重みが与えられ、前の反復には 0.75 の重みが与えられます。
• 3. 続行します。

これらの手順は「かなりうまく」機能しているように見えますが、正確ではありません。

Dafermos (1968) は、交通均衡問題に対処するために使用できるFrank-Wolfe アルゴリズム(1956、Florian 1976) を適用しました。高速道路ネットワークを考えてみましょう。各リンクには、交通抵抗と交通量の関係を示す関数があります。公道局(BPR) は、リンク (アーク) の混雑 (または交通量遅延、またはリンク パフォーマンス) 関数を開発しました。これを S _a (v _a )と呼びます。

${\displaystyle S_{a}\left({v_{a}}\right)=t_{a}\left({1+0.15\left({\frac {v_{a}}{c_{a}}}\right)^{4}}\right)}$

• t _{a = リンク}a上の単位時間あたりの自由流移動時間
• v _a =単位時間あたりのリンクa上のトラフィック量（より正確には、リンクa を使用しようとするフロー）。
• c _a =単位時間あたりのリンクaの容量
• S _a (v _{a )はリンク}a上の車両の平均移動時間である。

他にも輻輳関数はあります。CATS では以前から BPR とは異なる関数が使われてきましたが、CATS と BPR の関数を比較すると結果にほとんど違いがないようです。

パスとリンクにトラフィックを割り当てるにはルールが必要で、よく知られているウォードロップ均衡条件があります。^[1] これらの本質は、旅行者が出発地から目的地までの最短（抵抗が最も少ない）パスを見つけようと努力し、新しいパスに変更することで旅行の労力を減らすことができない旅行者がいる場合にネットワーク均衡が発生することです。これらはユーザー最適条件と呼ばれ、システムが均衡状態になると、どのユーザーも旅行パスを変更しても利益を得られないからです。

ユーザの最適均衡は、次の非線形計画問題を 解くことによって見つけることができます。

${\displaystyle \min \sum _{a}{\int _{0}^{v_{a}}{S_{a}\left(x\right)}}dx}$

以下を条件とする:

${\displaystyle v_{a}=\sum _{i}{\sum _{j}{\sum _{r}{\alpha _{ij}^{ar}x_{ij}^{r}}}}}$

${\displaystyle \sum _{r}{x_{ij}^{r}=T_{ij}}}$

${\displaystyle v_{a}\geq 0,\;x_{ij}^{r}\geq 0}$

ここで、 出発地iから目的地jまでの経路r 上の車両の数です。したがって、制約 (2) は、すべての移動が i = 1 ... n、j = 1 ... n で行われなければならないことを示しています。${\displaystyle x_{ij}^{r}}$

${\displaystyle \alpha _{ij}^{ar}}$= リンク a が i から j へのパス r 上にある場合は 1、それ以外の場合は 0 です。したがって、制約 (1) は各リンクのトラフィックを合計します。ネットワーク上の各リンクには制約があります。制約 (3) は負のトラフィックがないことを保証します。

Eash、Janson、および Boyce (1979) の例は、非線形計画問題の解決方法を示しています。ノード 1 からノード 2 へのリンクが 2 つあり、各リンクに抵抗関数があります (図 1 を参照)。図 2 の曲線の下の領域は、式 1 の 0 からaまでの積分に対応し、合計は 220,674 になります。リンクbの関数は逆方向にプロットされていることに注意してください。

${\displaystyle S_{a}=15\left({1+0.15\left({\frac {v_{a}}{1000}}\right)^{4}}\right)}$

${\displaystyle S_{b}=20\left({1+0.15\left({\frac {v_{b}}{3000}}\right)^{4}}\right)}$

${\displaystyle v_{a}+v_{b}=8000}$

図1: 2ルートネットワーク

図2: 均衡割り当て問題のグラフィカルな解

図3: 均衡条件を満たさない車両の配分

均衡状態では、リンクAには 2,152 台の車両があり、リンクBには 5847 台の車両があります。各ルートの移動時間は同じで、約 63 分です。

図 3 は、均衡解と一致しない車両の割り当てを示しています。曲線は変更されていません。ただし、ルートへの車両の新しい割り当てでは、影付きの領域をソリューションに含める必要があるため、図 3 のソリューションは、影付きの領域の面積分だけ図 2 のソリューションよりも大きくなります。

都市交通計画モデルは、従うべき一連の手順として進化し、各手順で使用するモデルが進化しました。ローリー モデルの最初のステートメントの場合のように、手順の中に手順が存在することもあります。手順を統合できる場合もあることが指摘されています。より一般的には、手順は同時に行われる可能性のある決定を抽象化するため、分析ではそれをより適切に再現することが望ましいでしょう。

非集計需要モデルは、当初は移動手段の選択問題を扱うために開発されました。この問題は、旅行をすること、その旅行の行き先、旅行の時刻が決まっていることを前提としています。このモデルは、暗黙のより広いコンテキストを扱うために使用されてきました。通常、ネストされたモデルが開発されます。たとえば、旅行が行われる確率から始めて、場所の選択、そして移動手段の選択を検討します。旅行の時刻を扱うのは、少し難しいです。

ウィルソンの二重制約エントロピーモデルは、集計レベルでの取り組みの出発点となっている。このモデルには制約が含まれている。

${\displaystyle t_{ij}c_{ij}=C}$

ここで、はリンクの移動コスト、はリンク上の交通量、C はモデルをデータに適合させるときにサイズ設定するリソース制約です。この形式の制約を使用する代わりに、交通量割り当てで使用される単調に増加する抵抗関数を使用できます。結果によってゾーン間の移動が決定され、ネットワークに交通量が割り当てられます。これは、システムが機能する仕組みから想像される方法からすると理にかなっています。ゾーン間の交通量は、混雑によって生じる抵抗量に依存します。 ${\displaystyle c_{ij}}$${\displaystyle t_{ij}}$

あるいは、リンク抵抗関数を目的関数に含めることもできます（そして、総コスト関数を制約から削除します）。

一般化された非集計選択アプローチは、一般化された集計アプローチと同様に進化してきました。大きな問題は、それらの関係です。マクロ モデルを使用する場合、それが表す非集計動作を知りたいと思うでしょう。ミクロ分析を行う場合、分析の集計的意味を知りたいと思うでしょう。

ウィルソンは、出発地と目的地の魅力について何かを語る重み付けパラメータを持つ重力のようなモデルを導き出しました。あまり数学を使わなくても、魅力に基づいて選択の確率を記述することができ、これはいくつかの種類の非集計需要モデルに似た形式をとります。

交通需要がネットワーク供給に左右されることは、以前から認識されてきました。以前は存在しなかった橋が新たに開通し、交通量が増えるという例は、何世紀にもわたって注目されてきました。予測システムでこの現象を直接考慮できるようにする方法の開発には、多くの研究が行われました。Evans (1974) は、重力分布モデルと均衡割り当てモデルを数学的に厳密に組み合わせた博士論文を発表しました。この統合に関する最も古い引用は、Irwin と Von Cube の研究であり、Florian ら (1975) は Evans の研究について次のようにコメントしています。

「エヴァンスの研究は、トロントの交通調査のためにアーウィンとフォン・キューブが開発したアルゴリズム [「複数の移動モード割り当てプログラムにおける容量制限」HRB Bulletin 347 (1962)] に多少似ています。彼らの研究では、逐次的な手順を適用しながらも、混雑割り当てと移動配分の間のフィードバックが可能になっています。配分問題の初期ソリューションから始めて、ゾーン間の移動は最初の最短ルートに割り当てられます。その後の反復では、新しい最短ルートが計算され、その長さが配分モデルへの入力のアクセス時間として使用されます。その後、新しいゾーン間のフローは、すでに見つかったルートに比例して割り当てられます。その後の反復のゾーン間の時間がほぼ等しくなった時点で、手順は停止されます。」

Florian らは、Frank-Wolfe アルゴリズムを直接適用して、複合配布割り当てを解決するためのやや異なる方法を提案しました。Boyce ら (1988) は、弾力的な需要による割り当てを含むネットワーク均衡問題に関する研究をまとめています。

3 つのリンクの問題はグラフィカルに解くことができず、ほとんどの交通ネットワークの問題には多数のノードとリンクが関係します。たとえば、Eash らは、約 30,000 の一方通行リンクと 9,500 のノードがある DuPage 郡の道路網を調査しました。問題が大きいため、割り当て問題を解決するにはアルゴリズムが必要であり、Frank-Wolfe アルゴリズム (最初に公開されてからさまざまな現代的な変更が加えられています) が使用されます。すべてまたは何も割り当てない割り当てから始めて、Frank-Wolfe によって開発された規則に従って、目的関数の最小値に向かって反復します。(アルゴリズムは、連続した実行可能なソリューションを適用して、最適ソリューションへの収束を実現します。効率的な検索手順を使用して、計算を最適ソリューションに向けて迅速に進めます。) 移動時間は、このプログラミング問題における 2 つの変数に対応します。

フランク・ウルフアルゴリズムが 1956 年に利用可能だったことは興味深いことです。その応用は 1968 年に開発され、最初の均衡割り当てアルゴリズムが一般的な輸送計画ソフトウェア (モントリオールのフロリアンらが開発した Emme および Emme/2) に組み込まれるまでに、さらにほぼ 20 年かかりました。応用が遅いという観察から一般的な結論を導き出すことは望ましくありません。主な理由は、技術開発のペースとパターンに関する反例が見つかるからです。たとえば、線形計画問題の解決のためのシンプレックス法は、プログラミング理論の多くが登場する前から考案され、広く適用されていました。

問題の説明とアルゴリズムは、水力学、構造、建設 など土木工学全般にわたって一般的に応用できます。(Hendrickson と Janson 1984 を参照)。

経路割り当てモデルは、ネットワーク内で人々が経路を選択する方法についての実証的研究に少なくともある程度基づいています。このような研究は一般に特定のモードに焦点を当てており、表明された選好モデルまたは明らかにされた選好モデルのいずれかを利用しています。

自転車利用者は指定された自転車レーンを好み、急な坂道を避ける傾向があることが分かっています。^[2]

公共交通機関は長い間、経路割り当ての文脈で検討されてきました^[3]。また、公共交通機関の経路選択に関する研究も数多く行われてきました。公共交通機関の利用者は、他の要因の中でも、総移動時間、歩行時間または距離、乗り換え回数を最小限に抑えることを目指しています。^[4]

• ルート選択（曖昧さ回避）

• Dafermos, Stella. C. および FT Sparrow「一般的なネットワークのトラフィック割り当て問題」。国立標準局研究ジャーナル、73B、pp. 91-118。1969 年。
• フロリアン、マイケル編、交通均衡法、Springer-Verlag、1976年。
• イッシュ、ロナルド、ブルース・N・ジャンソン、デビッド・ボイス「均衡旅行割り当て：実践上の利点と意味」、交通研究記録728、pp.1-8、1979年。
• エヴァンス、スザンヌ P. 「旅行の配分と割り当てを統合するいくつかのモデルの導出と分析」 交通研究、第 10 巻、pp 37-57 1976
• Hendrickson, CT および BN Janson、「いくつかの土木工学問題に対する共通ネットワークフロー定式化」土木工学システム 1(4)、pp. 195–203、1984