(57)【要約】      （修正有）【課題】大量輸送サービスの拠点から各乗客の最終目的地まで人々を送り届けるラストマイル乗客輸送において、自律走行車両の使用を提供する。【解決手段】通勤用車両（ＣＶ）及び定時運行車両を有するマルチモード輸送ネットワークにおいて乗客にＣＶを割り当てるシステムは、乗客から旅程要求を受信する。乗客の旅程要求は、出発地、目的地、出発地からの出発時刻及び目的地における期限を含む到着時間窓を含む。システムは、グループ分けプログラム、ルート探索プログラム、ＣＶの運用ルートマップ及び通勤者割当てプログラムを含む。ステップ４００は、乗客を１組のグループにグループ分け４２０することと、通勤者割当てプログラムを実行することによってグループにＣＶを割り当てる４３０ことと、利用可能なＣＶの中から割り当てられたＣＶの割当て情報を生成する４４０ことと、を含む。【選択図】図４
2020004404.tif 000002
【特許請求の範囲】
【請求項１】
通勤用車両（ＣＶ）及び定時運行車両を有するマルチモード輸送ネットワークにおいて乗客に前記ＣＶを割り当てるシステムであって、
前記乗客から旅程要求を受信するインターフェースであって、前記旅程要求は出発地、目的地、前記出発地からの出発時刻、及び前記目的地における期限を含む到着時間窓を含む、インターフェースと、
グループ分けプログラム、ルート探索プログラム、前記ＣＶの運用ルートマップ、及び通勤者割当てプログラムを含む、コンピューター実行可能プログラムを記憶するメモリと、
前記メモリに関連して前記コンピューター実行可能プログラムを実行するプロセッサと、
を備え、前記グループ分けプログラムは、
前記乗客の前記目的地に基づいて、前記乗客のグループを決定し、前記乗客のための前記定時運行車両及び前記ＣＶによる前記出発時刻を決定する最適化問題を定式化することと、
前記最適化問題を解いて、前記乗客のグループと、前記乗客のための前記定時運行車両及び前記ＣＶによる前記出発時刻とを規定する解を生成することと、
前記最適化問題を解くことから得られた前記解を前記メモリに記憶することであって、前記定式化すること、前記解くこと、及び前記記憶することは、１組の重み付け係数と、前記乗客の総移動時間とグループ数との組み合わせとに関する解を得るために繰り返される、記憶することと、
前記乗客の前記総移動時間及び前記グループ数の線形結合のために得られた前記解の中の１つの解を選択することと、
前記通勤者割当てプログラムを実行することによって、前記グループに前記ＣＶを割り当て、前記ＣＶに関するルートを割り当てることと、
前記選択された解に基づいて、前記ＣＶの中の割り当てられたＣＶの割当て情報を生成することであって、前記割当て情報は、前記グループに割り当てられたＣＶ、前記ＣＶに割り当てられたルート、中継地、及び前記中継地からの前記割り当てられたＣＶの出発時刻を含む、生成することと、
前記割当て情報を、前記インターフェースを介して、前記割り当てられたＣＶに送信することと、
を含む、システム。
【請求項２】
前記最適化問題は、全ての前記乗客の前記総移動時間の和と、前記グループ数との線形結合を最小化するように定式化され、前記結合は重み付け係数を用いて実行される、請求項１に記載のシステム。
【請求項３】
前記最適化問題は、前記乗客の前記到着時間窓内に乗客が目的地に達するのを確実にする制約と、前記グループ内の前記乗客の数が前記ＣＶ内の座席数より少ないことを確実にする制約とを含み、前記ルート探索プログラム及び前記運用ルートマッププログラムは、前記ＣＶに関するそれぞれの移動時間を与え、前記制約は、同時に運用しているＣＶの数が前記メモリに記憶される利用可能なＣＶの全数より少ないことを確実にする、請求項１に記載のシステム。
【請求項４】
前記グループは、前記ＣＶの前記運用ルートマップを用いて前記ルート探索プログラムを実行することによって、前記ルート及び前記中継地を割り当てられ、前記ルートはそれぞれ、前記中継地から前記グループの前記目的地に達し、前記グループは前記中継地における前記出発時刻を割り当てられ、それにより、前記グループの前記乗客が前記中継地において前記定時運行車両から前記ＣＶに乗り換え、前記到着時間窓内に前記目的に達することができるようにする、請求項１に記載のシステム。
【請求項５】
前記グループ分けにおいて、前記グループ分けプログラムは、前記乗客の前記目的地ごとに決定図（ＤＤ）を構成及び計算することによって実行され、前記ＤＤはそれぞれ、共通の目的地まで移動している前記乗客の数と、前記乗客の前記到着時間窓と、前記ＣＶのそれぞれの座席定員とに基づいて構成される、請求項１に記載のシステム。
【請求項６】
前記グループ分けプログラムは、前記グループ分けされた乗客を前記到着時間窓内の期限の昇順に並べ替える、請求項１に記載のシステム。
【請求項７】
乗客の旅程要求が前記乗客によって支払われることになる最小総コストを示す好ましいオプションを含むとき、前記乗客は、予定車両及び割り当てられるＣＶのコストの和を最小化するための別の制約を満たすグループに割り当てられる、請求項１に記載のシステム。
【請求項８】
前記ＣＶの運用状況が、前記情報インターフェースを介して、前記ＣＶのそれぞれから状況情報を受信することによって監視及び更新され、前記運用状況は、前記ＣＶの場所と、前記ＣＶのそれぞれの利用可能な座席数とを含み、前記更新された運用状況は、前記メモリに記憶される、請求項１に記載のシステム。
【請求項９】
前記メモリは、前記中継地において停車する前記定時運行車両の運賃及び時刻表を記憶する、請求項１に記載のシステム。
【請求項１０】
前記乗客が前記割り当てられたＣＶのうちの１つの前記出発時刻の前に前記中継地に達するように、前記インターフェースを介して、前記乗客のそれぞれに、出発地からアクセス可能な定時運行車両の出発時刻と、前記中継地のうちの１つと、前記割り当てられたＣＶのうちの１つとを伴う旅程を送信することを更に含む、請求項１に記載のシステム。
【請求項１１】
前記最適化問題は、前記総移動時間と前記ＣＶによって消費されることになるエネルギーとの線形結合、前記乗客によって支払われることになる全運賃、前記総移動時間と前記全運賃との線形結合、又は前記総移動時間と、前記定時運行車両によって消費されることになるエネルギーとの線形結合を最小化するように定式化される、請求項１に記載のシステム。
【請求項１２】
前記旅程は全運賃を含み、前記最適化問題は、前記制約のうちの１つとして前記全運賃を満たすように解かれる、請求項１に記載のシステム。
【請求項１３】
グループ分けするステップ、割り当てるステップ、確実にするステップ、及び評価するステップは、前記プロセッサにおいて所定の制限時間に達するまで繰り返される、請求項１に記載のシステム。
【請求項１４】
前記インターフェースは、前記ネットワークを介して、前記運用ルートマップ上の交通渋滞、交通事故及び工事中を含む、交通条件に関する情報を受信し、前記ルート探索プログラムは、前記交通条件を回避するように、前記グループの前記ルートを探索する、請求項１に記載のシステム。
【請求項１５】
前記通勤者割当てプログラムは、前記乗客の総移動時間に関する制約、前記乗客を輸送する際に前記割り当てられたＣＶによって使用されるエネルギーに関する制約、及び前記総移動時間と前記乗客を輸送する際に使用される前記エネルギーとの線形結合に関する制約のうちの１つに基づいて、前記最適化問題を解く、請求項１に記載のシステム。
【請求項１６】
同一のグループに割り当てられる前記乗客は同一のＣＶを共有する、請求項１に記載のシステム。
【請求項１７】
前記乗客はそれぞれ、総移動時間を有する、請求項１に記載のシステム。
【請求項１８】
前記システムは、各乗客に、前記乗客が環境に優しい移動スケジュールを選択する場合に、前記定時運行車両の運賃がどれだけ割引されるかに関する情報を送信する、請求項１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は包括的には、マルチモード輸送ネットワークをスケジューリングするシステムに関し、より詳細には、通勤用車両（ＣＶ：commuter vehicle）及び定時運行車両（fixed schedule vehicle）を有するマルチモード輸送ネットワークにおいて、乗客にＣＶを割り当てるシステムに関する。
【背景技術】
【０００２】
マルチモード輸送ネットワークを経由してマルチモードルートを取得するには、いくつかの課題がある。そのような輸送ネットワークは通常、異なるタイプのサブネットワーク、すなわち、異なる輸送モードに関連付けられるサブネットワークを含む。従来のルート選択及び／又はスケジューリング方法は或る特定のタイプの輸送ネットワークに特化する傾向があるので、異なるタイプのネットワークの特性のこれらの違いが、両方のタイプのネットワークにわたるマルチモードルートを生成するのを困難にする。マルチモードルートを取得する現在の試みは、異なるネットワークを経由するルートを決定するために、それらのネットワークを別々に検討することを伴う。例えば、或る出発点から、或る輸送モードに関連付けられるネットワークを経由して、別の輸送モードの出発点までのルートを決定し、その後、当前記別の輸送モードの出発点から、当前記別の輸送モードに関連付けられるネットワークを経由して、所定の目的地までのルートを決定することができる。
【０００３】
自家輸送ルート選択、例えば、自動車ルート選択アルゴリズム、及び公共輸送ルート選択は、それらのネットワークの特性が異なる結果として異なる傾向があり、結果として、それらのルート選択は、真の意味でのマルチモードルートプランナーを提供するために容易に統合することができない。しかしながら、公共輸送ネットワーク及び自家輸送ネットワークに関して同時に最適化することに関する言及はない。
【０００４】
したがって、例えば、システム及び乗客が対象の起点と目的地との間で自家輸送及び公共輸送の使用を統合できるようにするために、より効率的な全体行程を提供するために、及び／又は環境への影響を少なくするために、マルチモードルートを生成することが必要とされている。
【発明の概要】
【０００５】
本開示は、マルチモード輸送ネットワークの少なくとも一部を形成する輸送機関のスケジュールを共同管理するシステム及び方法に関する。
【０００６】
本開示は、大量輸送サービスの拠点から各乗客の最終目的地まで人々を送り届けるサービスと定義されるラストマイル乗客輸送において、自律走行車両の使用を提供する。
【０００７】
本開示の実施形態は、複数の輸送モードにわたって乗客のための旅程を計画する問題に対処するシステム及び方法を提供する。いくつかの実施形態は、定時運行車両及び通勤用車両を含む、マルチモード輸送ネットワークにおいて車両を管理するシステム及び方法を提供する。具体的には、空輸、船、バス又は列車等の定時運行車両による大量輸送ネットワークの第１のモードと、運転者によって操作される自動車、無人車両、ミニバス、電動プラットフォーム等の定員が少ない車両からなる、柔軟にスケジューリングされる通勤用車両による輸送ネットワークの第２のモードとからなる、２つ以上の輸送モードにわたって乗客をスケジューリングする。
【０００８】
定時運行車両は、対応するサービスの輸送拠点間で１組の乗客を輸送するために、決まったスケジュール及び制約されない乗客定員を有する。例えば、列車は、鉄道駅間でのみ乗客を輸送し、一方、バスは停留所間で乗客を輸送する。本明細書において参照されるときに、制約されない乗客定員は、スケジューリング及び管理の解において考慮に入れられない、定時運行車両の最大定員と理解することができる。対照的に、通勤用車両は、乗客の目的地に応じて選択されるルートを介して、乗客を輸送拠点まで、又は輸送拠点から輸送するために、制約されないスケジュール及び最大乗客定員を有する。
【０００９】
本開示の実施形態によれば、通勤用車両（ＣＶ）及び定時運行車両を有するマルチモード輸送ネットワークにおいて乗客にＣＶを割り当てるシステムは、乗客から旅程要求を受信するインターフェースを含み、旅程要求は出発地、目的地、出発地からの出発時刻、及び目的地における期限を含む到着時間窓を含む。また、本システムは、グループ分けプログラム、ルート探索プログラム、ＣＶの運用ルートマップ、及び通勤者割当てプログラムを含む、コンピューター実行可能プログラムを記憶するメモリと、メモリに関連してコンピューター実行可能プログラムを実行するプロセッサとを備える。グループ分けプログラムは、乗客の目的地に基づいて、乗客グループを決定し、乗客のための定時運行車両及びＣＶによる出発時刻を決定する最適化問題を定式化することと、最適化問題を解いて、乗客グループと、乗客のための定時運行車両及びＣＶによる出発時刻とを規定する解を生成することと、最適化問題を解くことから得られた解をメモリに記憶することであって、定式化すること、解くこと、及び記憶することは、１組の重み付け係数と、乗客の総移動時間とグループ数との組み合わせとに関する解を得るために繰り返される、記憶することと、乗客の総移動時間及びグループ数の線形結合のために得られた解の中の１つの解を選択することと、通勤者割当てプログラムを実行することによって、グループにＣＶを割り当て、ＣＶに関するルートを割り当てることと、選択された解に基づいて、ＣＶの中の割り当てられたＣＶの割当て情報を生成することであって、割当て情報は、グループに割り当てられたＣＶ、ＣＶに割り当てられたルート、中継地、及び中継地からの割り当てられたＣＶの出発時刻を含む、生成することと、割当て情報を、インターフェースを介して、割り当てられたＣＶに送信することとを含む。
【００１０】
ここに開示されている実施形態は、添付図面を参照して更に説明される。示されている図面は、必ずしも一律の縮尺というわけではなく、その代わり、一般的に、ここに開示されている実施形態の原理を示すことに強調が置かれている。
【図面の簡単な説明】
【００１１】
【図１】本開示の実施形態による、統合ラストマイルシステムを示す概略図である。
【図２】複数の輸送モードをスケジューリングするシステムを示すブロック図である。
【図３Ａ】本開示のいくつかの実施形態による、通勤用車両割当てシステムのブロック図である。
【図３Ｂ】本開示のいくつかの実施形態による、ルート探索プログラムのブロック図である。
【図４】本開示の実施形態による、定時運行車両及び通勤用車両に共同で乗客をスケジューリングする主要ステップを示すフローチャートである。
【図５】本開示の実施形態による、整数計画法を用いて、定時運行車両及び通勤用車両への乗客のスケジューリングを最適化する際の主要ステップを示すフローチャートである。
【図６】本開示の実施形態による、整数計画法の出力を用いて乗客に通勤用車両を割り当てることを示すフローチャートである。
【図７】本開示の実施形態による、ネットワークフロー法を用いて、定時運行車両及び通勤用車両への乗客のスケジューリングを最適化する際の主要ステップを示すフローチャートである。
【図８】本開示の実施形態による、ネットワークフロー法の出力を用いて乗客に通勤用車両を割り当てることを示すフローチャートである。
【図９】本開示の実施形態による、通勤用車両における乗客のグループ分けの決定図表現の一例を示す図である。
【図１０Ａ】本開示の実施形態による、分枝価格法を用いて、定時運行車両及び通勤用車両への乗客のスケジューリングを最適化する際の主要ステップを示すフローチャートである。
【図１０Ｂ】本開示の実施形態による、分枝価格法の解を用いて、乗客ごとに定時運行車両及び通勤用車両による出発時刻を割り当てる際の主要ステップを示すフローチャートである。
【図１１】本開示の実施形態による、ネットワークフロー法を用いて、２つの目的地まで移動している定時運行車両及び通勤用車両への乗客のスケジューリングを最適化する際の主要ステップを示すフローチャートである。
【図１２】本開示の実施形態による、通勤用車両が２つの目的地まで移動するときに、ネットワークフロー法の出力を用いて乗客に通勤用車両を割り当てることを示すフローチャートである。
【図１３】本開示の実施形態による、２つの目的地まで移動するときの通勤用車両における乗客のグループ分けの決定図表現の一例を示す図である。
【図１４】本開示の実施形態による、１組のテスト事例に関してＢＰ法及びＮＦ法を比較する、性能の累積分布のプロット図である。
【図１５】本開示の実施形態による、ＢＰ法を用いて、１００００人の乗客、５０の目的地、６００台のＣＶの場合の数分間のパレートフロンティアの計算結果を示す図である。
【図１６】本開示の実施形態による、ＢＰ法及びＮＦ法を比較する散布図である。
【図１７】目的関数における重み付け係数αの異なる設定の場合の、総乗客移動時間及び平均ＣＶ数を表す散布図である。
【発明を実施するための形態】
【００１２】
上記で明らかにされた図面は、ここに開示されている実施形態を記載しているが、この論述において言及されるように、他の実施形態も意図されている。この開示は、限定ではなく代表例として例示の実施形態を提示している。ここに開示されている実施形態の原理の範囲及び趣旨に含まれる非常に多くの他の変更及び実施形態を当業者は考案することができる。
【００１３】
以下の説明は、例示的な実施形態のみを提供し、本開示の範囲も、適用範囲も、構成も限定することを意図していない。そうではなく、例示的な実施形態の以下の説明は１つ以上の例示的な実施形態を実施することを可能にする説明を当業者に提供する。添付の特許請求の範囲に明記されているような開示された主題の趣旨及び範囲から逸脱することなく要素の機能及び配置に行うことができる様々な変更が意図されている。
【００１４】
以下の説明では、実施形態の十分な理解を提供するために、具体的な詳細が与えられる。しかしながら、当業者は、これらの具体的な詳細がなくても実施形態を実施することができることを理解することができる。例えば、開示された主題におけるシステム、プロセス、及び他の要素は、実施形態を不必要な詳細で不明瞭にしないように、ブロック図形式の構成要素として示される場合がある。それ以外の場合において、よく知られたプロセス、構造、及び技法は、実施形態を不明瞭にしないように不必要な詳細なしで示される場合がある。さらに、様々な図面における同様の参照符号及び名称は、同様の要素を示す。
【００１５】
また、個々の実施形態は、フローチャート、フロー図、データフロー図、構造図、又はブロック図として描かれるプロセスとして説明される場合がある。フローチャートは、動作を逐次的なプロセスとして説明することができるが、これらの動作の多くは、並列又は同時に実行することができる。加えて、これらの動作の順序は、再配列することができる。プロセスは、その動作が完了したときに終了することができるが、論述されない又は図に含まれない追加のステップを有する場合がある。さらに、特に説明される任意のプロセスにおける全ての動作が全ての実施形態において行われ得るとは限らない。プロセスは、方法、関数、手順、サブルーチン、サブプログラム等に対応することができる。プロセスが関数に対応するとき、その関数の終了は、呼び出し側関数又はメイン関数へのその機能の復帰に対応することができる。
【００１６】
さらに、開示された主題の実施形態は、少なくとも一部は手動又は自動のいずれかで実施することができる。手動実施又は自動実施は、マシン、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、又はそれらの任意の組み合わせを用いて実行することもできるし、少なくとも援助することができる。ソフトウェア、ファームウェア、ミドルウェア又はマイクロコードで実施されるとき、必要なタスクを実行するプログラムコード又はプログラムコードセグメントは、マシン可読媒体に記憶することができる。プロセッサ（複数の場合もある）が、それらの必要なタスクを実行することができる。
【００１７】
一例として、マルチモード輸送ネットワークは、公共輸送サブネットワークと、自家輸送によって使用するための自家輸送サブネットワーク、例えば、道路ネットワーク（本明細書において「自家輸送サブネットワーク」と呼ばれる）とを含むことができる。これらのタイプのネットワークは異なる特性を有する。公共輸送ネットワークを経由する場合の進入時刻、退出時刻及び移動時間は制約を受け、特定の時刻においてのみ、すなわち、そのネットワークに関連付けられるスケジュールに従ってのみ、ネットワークを経由して進入、退出及び移動を行うことができるようになる。対照的に、自家輸送を使用するとき、道路ネットワーク等の自家輸送ネットワークに関して、そのような制約はない。自家輸送ネットワークでは、ユーザーが、自らが選択する時点において、ネットワークへの進入、ネットワークからの退出又はネットワーク内の移動を自由に選択することができる。
【００１８】
公共輸送の例は種々の定時運行車両、すなわち、定時及び／又は所定のスケジュールを有し、ユーザーの都合又は要件に合わせて変更することができない車両を含む。定時運行車両の例は、列車、バス、船及び飛行機のうちの１つ又はその組み合わせを含む。自家輸送の例は、自律走行車両、半自律走行車両及び運転者によって操作される車両等の種々の、柔軟にスケジューリングされる通勤用車両を含む。柔軟にスケジューリングされる通勤用車両は、乗客の要求に応じて、ルート及び時刻を指定できるようになる。
【００１９】
概説
本開示は、マルチモード輸送ネットワークの少なくとも一部を形成する輸送機関のスケジュールを共同管理するシステム及び方法に関する。
【００２０】
本開示の実施形態は、複数の輸送モードにわたって乗客のための旅程を計画する問題に対処するシステム及び方法を提供する。いくつかの実施形態は、定時運行車両及び通勤用車両を含む、マルチモード輸送ネットワークにおいて車両を管理するシステム及び方法を提供する。
【００２１】
具体的には、飛行機、船、バス又は列車等の定時運行車両による大量輸送ネットワークの第１のモードと、人間によって運転されるか、又は自律走行する自動車、バン、ポッド、電動プラットフォーム等の定員が少ない車両からなる通勤用車両による輸送ネットワークの第２のモードとからなる、２つ以上の輸送モードにわたって乗客をスケジューリングする。
【００２２】
定時運行車両は、中継地まで、又は中継地から１組の乗客を輸送するために、乗客の要求に合わせることができるスケジュールと、制約されない乗客定員とを有することができる。本明細書において参照されるときに、制約されない乗客定員は、スケジューリング及び管理の解において考慮に入れられない、定時運行車両の最大定員と理解することができる。対照的に、通勤用車両は、１組の所定のルートから選択されるルートのうちの１つを介して、乗客を中継地まで、又は中継地から輸送するために、制約されないスケジュールと、最大乗客定員とを有することができる。
【００２３】
複数の輸送モードにわたって乗客のための旅程を計画する問題に対処する際に、本開示は、或る時刻に到着するために、定時運行車両の１組の発着所から１組の建物まで移動する乗客を考える。乗客の目的地建物から、又は目的地建物まで乗客を乗せる１組の通勤用車両（ＣＶ）が存在する。少なくとも１つの態様は、乗客の到着時間窓を満たすように、乗客の要求に合わせて、スケジュールを計画することである。本開示の別の実施形態は、乗客が或る時刻までに建物を出発したい場合に、それらの建物から定時運行車両の１組の発着所まで移動する乗客を考える。
【００２４】
本発明の一実現形態は、ＣＶを共有する乗客のグループが指定されると、定時運行車両及びＣＶのスケジューリングを切り離すことができることを含む。その問題の解決に至るために、その解決プロセスは、乗客の目的地に達するために同乗するＣＶの定員に満たない数の乗客のサブセットとしてグループを定義する第１のステップを含むことができる。グループ分けプロセスにおいて、各グループが複数の目的地の中の同一の目的地に割り当てられ、乗客の到着時間窓が少なくとも１つの共通の時間インスタンスを含むように、目的地及び到着時間窓に基づいて、乗客が１組のグループにグループ分けされ、それらのグループは、ＣＶの運用ルートマップを用いてルート探索プログラムを実行することによって、ルート及び中継地を割り当てられ、ルートはそれぞれ、それらの中継地からそのグループの目的地に達し、グループは中継地における出発時刻を割り当てられ、それにより、グループの乗客が中継地において定時運行車両からＣＶに乗り換え、到着時間窓内に目的地に達することができるようにする。乗客のグループ分けは、決定図表現における経路の選択によって成し遂げられる。
【００２５】
第２のステップでは、１組のグループを与えられると、第２のステップは、グループごとに、（ｉ）そのグループへのＣＶの割当て、及び（ｉｉ）そのグループが、割り当てられたＣＶに乗車して、鉄道駅又は鉄道ターミナルを出発する時刻を決定する。その際に、メモリからロードされる割当てアルゴリズムが以下のように実行される。ＣＶは、以下のステップ：出発時刻、到着時間窓の期限及びグループに割り当てられたルートに基づいて、各時点において使用されるＣＶの数を決定するステップと、目的地に達するグループを表す変数に基づいて最適化問題を定式化するステップと、グループ内の乗客の総移動時間を計算するステップと、全ての乗客の総移動時間の和を最小化するステップと、乗客の到着時間窓を含むとともに、各時点において使用されるＣＶの数が利用可能なＣＶの全数より少ないのを確実にする所定の制約を満たすように最適化問題を解くことによって解値を生成するステップと、最小総移動時間を有する１組のグループが得られ、所定の制約が満たされるまで、解くことの一部として、ＣＶのグループ分け及び割当てを繰り返すステップとに従ってグループに割り当てられる。この場合、各乗客は、出発時刻から到着時刻までの移動中に費やされる時間に対応する、その乗客によって消費される総移動時間を有する。
【００２６】
図１は、本開示の実施形態による、統合ラストマイルシステムを示す概略図である。その図は、乗客１０１が列車等の定時運行車両１０５に乗車することと、中継発着所１１５に到着することと、中継発着所において乗客が通勤用車両に乗車することと、通勤用車両によって移動して目的地１２０に達することと、指定された到着時間窓１３０内に目的地１１０に到着することとを示す。
【００２７】
図２は、定時運行車両と効率的に接続するために通勤用車両を割り当てることができるシステム３００を示す概略図である。本開示の実施形態による、システム３００の一例が図３Ａに示されており、乗客がシステム３００と通信し、自らのスケジュールを受信する。図２は、ＣＶ割当てシステムの一例を示し、ユーザー２０１、２０２、２０３が、起点発着所、目的地建物、及び目的地の到着時間窓を要求する入力をシステム３００に与える。各ユーザー２０１、２０２、２０３は、それぞれのスマートフォン又はコンピューター２０１Ａ、２０２Ａ、２０３Ａを用いて、システム３００と通信する。システム３００は、ユーザーのためのＣＶスケジュール及び通勤用車両２２０を決定する。システム３００は、スマートフォン２０１Ａ又はコンピューター等の好ましい通信デバイスを通して、全ての乗客２０１のための最適なスケジュールを通信する。ユーザー２０１、２０２、２０３は、乗客が起点発着所を出発する列車時刻、ユーザーが乗車して移動する通勤用車両のＩＤ、通勤用車両における行程の出発時刻及び到着時刻に関する情報を受信する。
【００２８】
図３Ａは、本開示のいくつかの実施形態による、システム３００のブロック図を示す。システム３００は、キーボード３１１及びポインティングデバイス／媒体３１２と接続可能なヒューマンマシンインターフェース（ＨＭＩ）３１０と、１つ以上のプロセッサ３２０と、記憶デバイス３３０と、メモリ３４０と、ローカルエリアネットワーク及びインターネットネットワークを含むネットワーク３９０と接続可能なネットワークインターフェースコントローラー３５０（ＮＩＣ）と、ディスプレイインターフェース３６０と、マイクロフォンデバイス３７５と接続可能なオーディオインターフェース３７０と、印刷デバイス３８５と接続可能なプリンタインターフェース３８０とを含むことができる。メモリ３４０は、プロセッサ３２０に関連してコンピューター実行可能プログラム（アルゴリズムコード）を記憶する記憶装置３３０とともに動作する１つ以上のメモリユニットとすることができる。ＣＶ割当てシステム３００は、ＮＩＣ３５０に接続されるネットワーク３９０を介して、乗客（ユーザー）２００からの旅程要求データ（図示せず）、公開データベースからの定時運行車両のルート探索データ、又は一般公開されたルート探索アプリケーション３９５の探索結果を受信することができる。ＮＩＣ３５０は、有線ネットワークを介して、及びワイヤレスネットワーク（図示せず）を介してネットワーク３９０に接続する受信機及び送信機を含む。場合によっては、旅程要求データは、最低運賃、最短移動時間又は最短移動距離等の条件を有するユーザーの好ましいオプションを含むことができる。システム３００がユーザーの好ましいオプションを受信するとき、ＣＶ割当てシステム３００は、好ましいオプションの条件に基づいて、グループ分けプログラムモジュール３０４及びＣＶ割当てプログラムモジュール３０８を実行する。例えば、好ましいオプションが最低運賃を示すとき、ＣＶ割当てシステム３００は、中継地（発着所）及び中継地からのＣＶの出発時刻を与える旅程スケジュールを生成し、その旅程スケジュールは、出発地から目的地まで輸送するために乗客によって支払われることになる最低（最安）総運賃の条件を満たす。システム３００は、通勤用車両２２０の情報、旅程の出発時刻、通勤用車両が辿るルート、及びそれらの旅程において輸送される乗客に関する情報を与えることができる。
【００２９】
場合によっては、乗客２００が、出発地と、出発地から中継地より１駅近い停車場である発着所（隣接発着所）との間で利用可能な通勤定期を所有する場合には、出発地から目的地までの総運賃をより安価にできるように、システム３００はその隣接発着所を中継地として設定する。そのような場合、システム３００は、乗客の通勤定期の情報、例えば、通勤定期の利用可能な発着所の情報を要求するように構成される。さらに、システム３００は、ネットワーク３９０を介して、定時運行車両運行管理システム３９６と通信することができる。例えば、定時運行車両運行管理システム３９６が、定時運行車両の最新変更スケジュールに関する情報を定時に取得するとき、インターフェース３５０は、既に割り当てられているか、又は割り当てられることになるＣＶスケジュールに関連する変更スケジュールの情報を受信することができ、システム３００は、別の割当て情報を取得し、乗客に送信するために、グループ分けプログラム及びＣＶ割当てプログラムを再実行する。したがって、初期割当て情報が乗客に送信された後に、定時運行車両のスケジュールが変更された場合であっても、乗客は適切なＣＶ割当てを取得することができる。これは、乗客に極めて実効的で円滑な輸送を提供する。
【００３０】
場合によっては、システム３００は、乗客に予定車両を割り当てる前に、ネットワーク３９０を介して、定時運行車両運行管理システム３９６から、予定車両の現在の運行状況に関する情報を受信することができる。例えば、ラッシュアワーの時間帯に、定時運行車両運行管理システム３９６は、システム３００に、時間帯に応じた各定時運行車両上の推定乗客分布（混雑状態）を提供する。言い換えると、定時運行車両運行管理システム３９６は、その運行区間に関して一日の中の異なる時間スケジュールにおいて運行される各定時運行車両の推定エネルギー消費量を与えることができる統計データを含む。例えば、定時運行車両が、ラッシュアワーに混雑した運行区間において運行されるとき、その定時運行車両のエネルギー消費量は、混雑していない運行区間において非ラッシュアワー時に運行される定時運行車両のエネルギー消費量より大きい。したがって、定時運行車両運行管理システム３９６は、乗客が最初に割り当てられた出発時刻を別の出発時刻又は／及び別のルートに切り替える場合に、中継地（例えば、発着所）への別の到着時間を選ぶと、エネルギー消費量がどれだけ削減されるかという情報を与えることができる。
【００３１】
本開示の一実施形態によれば、システム３００は、乗客が、割り当てられた出発時刻及びルートを他の出発時刻及び他のルートに変更する場合に、エネルギー消費量をどれだけ削減できるかに関する情報を生成することができ、その情報を乗客に送信することができる。これは、定時運行車両によって消費される総エネルギーを削減するのに極めて有益であり、極めて環境に優しいシステムとすることができる。さらに、定時運行車両運行管理システム３９６は、ラッシュアワー関連動的価格決定システムを含むことができる。この場合、定時運行車両運行管理システム３９６と通信することによって、システム３００は、定時運行車両の運賃をどれだけ割り引くことができるかに関する情報を生成し、その情報を乗客に送信することができ、運賃の割引は、定時運行車両運行管理システム３９６に含まれる所定の計算方法に従って、定時運行車両のエネルギー消費量の削減に関連付けられる。これは、乗客が、システム３００から送信される環境に優しい移動スケジュールを選択する大きなインセンティブとなり得る。
【００３２】
さらに、そのインターフェースは、ネットワークを介して、運行ルートマップ上の交通渋滞、交通事故及び工事中を含む、交通条件に関する情報を受信し、ルート探索プログラムは、それらの交通条件を回避するように、グループのルートを探索する。この特徴は、乗客の移動時間を短縮し、ＣＶのエネルギー消費量を削減するのに極めて有益である。
【００３３】
定時運行車両に関する乗客のスケジューリングは、定時運行車両に関する混雑の程度、及び混雑が生じる定時運行車両旅程も明らかにする。定時運行車両に関する混雑は、乗客が窮屈な思いをし、疲労を感じるので、サービス品質の低下につながる。それゆえ、混雑に関する情報は、定時運行車両運行者とって大きな価値がある。そのような情報を用いて、定時運行車両運行者は、混雑の一因になる特定の顧客を対象にして、必要に応じて、金銭的なインセンティブ又はディスインセンティブを与えることができる。例えば、定時運行車両運行者は、特定の時刻における移動にディスインセンティブを与えるために、より高い運賃を課金することができるか、又は乗客が後の時点で移動することを申し出る場合には、割引運賃を提示することができる。したがって、定時運行車両運行者は、より良好なサービス品質を乗客に提供するために、乗客の移動時間に影響を及ぼすように乗客とやりとりすることができる。
【００３４】
記憶デバイス３３０は、グループ分けプログラムモジュール３０４、ルート探索プログラムモジュール３０２、通勤用車両割当てプログラムモジュール３０８及びＣＶ運用ルートマップデータベース３３４を含む。ポインティングデバイス／媒体３１２は、コンピューター可読記録媒体上に記憶されるプログラムを読み出すモジュールを含むことができる。ＣＶ運用ルートマップデータベース３３４は、ＣＶ運用エリアのロードマップデータを含み、ロードマップデータは、旅程要求に応答してＣＶのルートを計算する（算出する）ために使用される。
【００３５】
プログラムモジュール３０２、３０４及び３０８を実行するために、キーボード３１１を用いて、ポインティングデバイス／媒体３１２を用いて、又は他のコンピューター（図示せず）に接続されるネットワーク３９０を介して、システム３００に命令を送信することができる。システム３００は、ＨＭＩ３１０を介して命令を受信し、メモリ３４０に関連するプロセッサ３２０、記憶デバイス３３０に記憶されるグループ分けプログラムモジュール３０４、ルート探索プログラムモジュール３０２及び通勤用車両割当てプログラムモジュール３０８を用いて、乗客へのＣＶ割当てを実行するための命令を実行する。
【００３６】
本開示の実施形態によれば、システム３００は、通勤用車両（ＣＶ）及び定時運行車両を有するマルチモード輸送ネットワークにおいて乗客にＣＶを割り当てるために用いられる。システム３００は、乗客（ユーザー）２０１から旅程要求を受信するインターフェース３５０を含むことができ、旅程要求は出発地、目的地、出発地からの出発時刻、及び目的地における期限を含む到着時間窓を含むことができる。さらに、システム３００は、グループ分けプログラム、ルート探索プログラム、ＣＶの運用ルートマップ、及び通勤者割当てプログラムを含むコンピューター実行可能プログラムを記憶するメモリ（又は／及び記憶装置）と、メモリに関連してコンピューター実行可能プログラムを実行するプロセッサ３２０とを備える。グループ分けプログラムは、乗客の目的地に基づいて、乗客グループを決定し、乗客のための定時運行車両及びＣＶによる出発時刻を決定する最適化問題を定式化するステップと、最適化問題を解いて、乗客グループと、乗客のための定時運行車両及びＣＶによる出発時刻とを規定する解を生成するステップと、最適化問題を解くことから得られた解をメモリに記憶するステップであって、定式化するステップ、解くステップ、及び記憶するステップは、１組の重み付け係数と、乗客の総移動時間とグループ数との組み合わせとに関する解を得るために繰り返される、記憶するステップと、乗客の総移動時間及びグループ数の線形結合のために得られた解の中の１つの解を選択するステップと、通勤者割当てプログラムを実行することによって、グループにＣＶを割り当て、ＣＶに関するルートを割り当てるステップと、選択された解に基づいて、ＣＶの中の割り当てられたＣＶの割当て情報を生成するステップであって、割当て情報は、グループに割り当てられたＣＶ、ＣＶに割り当てられたルート、中継地、及び中継地からの割り当てられたＣＶの出発時刻を含む、ステップと、割当て情報を、インターフェースを介して、割り当てられたＣＶに送信するステップとを含む。
【００３７】
システム３００において実行可能プログラム内で実行されるステップでは、最適化問題は、全ての乗客の総移動時間の和と、グループ数との線形結合を最小化するように定式化することができ、結合は重み付け係数を用いて実行される。この場合、最適化問題は、乗客の到着時間窓内に乗客が目的地に達するのを確実にする制約と、グループ内の乗客の数がＣＶ内の座席数より少ないことを確実にする制約とを含み、ルート探索プログラム及び運用ルートマッププログラムは、ＣＶに関するそれぞれの移動時間を与え、制約は、同時に運用しているＣＶの数がメモリに記憶される利用可能なＣＶの全数より少ないことを確実にする。この場合、各乗客は、或る総移動時間を有すると考えることができる。
【００３８】
システム３００において実行可能プログラムを実行することによって、計算時間を大幅に短縮することができ、それゆえ、計算電力消費量を大幅に削減することができる。さらに、システム３００において、グループは、ＣＶの運用ルートマップを用いてルート探索プログラムを実行することによって、ルート及び中継地を割り当てられ、ルートはそれぞれ、中継地からグループの目的地に達し、グループは中継地における出発時刻を割り当てられ、それにより、グループの乗客が中継地において定時運行車両からＣＶに乗り換え、到着時間窓内に目的地に達することができるようにする。さらに、同一のグループに割り当てられた乗客は、同一のＣＶを共有する。これはシステムのより簡単なデータ処理方法を提供し、そのデータ処理方法は、高速のグループ分け及び移動スケジューリング方法を可能にし、結果として、計算電力消費量が削減される。
【００３９】
本開示の実施形態によれば、上述したグループ分けにおいて、グループ分けプログラムは、乗客の目的地ごとに決定図（ＤＤ）を構成及び計算することによって実行することができ、ＤＤはそれぞれ、共通の目的地まで移動している乗客の数と、乗客の到着時間窓と、ＣＶのそれぞれの座席定員とに基づいて構成される。その方法は、グループ分けプロセスの計算速度を大幅に改善することができ、単数又は複数のプロセッサを含む、コンピューターシステムの電力消費量を削減する。
【００４０】
場合によっては、グループ分けプログラムは、グループ分けされた乗客を到着時間窓内の期限の昇順に並べ替えることができる。これは、グループ分けプロセスに関して、より簡単な方法を提供することができ、乗客の数が増加するときに極めて効率的である。さらに、乗客の旅程要求が乗客によって支払われることになる最小総コストを示す好ましいオプションを含むとき、乗客を、予定車両及び割り当てられるＣＶのコストの和を最小化するための別の制約を満たすグループに割り当てることができる。これは、乗客の選択に応じて、乗客に低運賃の移動スケジュールを提供することができる。
【００４１】
場合によっては、システム３００は、ＣＶの運用状況が、情報インターフェースを介して、ＣＶのそれぞれから状況情報を受信することによって監視及び更新されるように、ＣＶと通信することができ、運用状況は、ＣＶの場所と、ＣＶのそれぞれの利用可能な座席数とを含み、更新された運用状況は、メモリに記憶される。これにより、システム３００は、ＣＶの利用可能な座席に乗客を適切に割り当てることができるのを確実にすることができる。一実施形態によれば、メモリ３４０及び／又は記憶装置３３０は、中継地に停車する定時運行車両の運賃及び時刻表を記憶する。これは、より良好な交通条件を有する、柔軟なルートを提供することができる。
【００４２】
さらに、実行可能プログラムのステップは、乗客が割り当てられたＣＶのうちの１つの出発時刻の前に中継地に達するように、インターフェースを介して、乗客のそれぞれに、出発地からアクセス可能な定時運行車両の出発時刻と、中継地のうちの１つと、割り当てられたＣＶのうちの１つとを伴う旅程を送信することを含むことができる。
【００４３】
場合によっては、最適化問題は、総移動時間とＣＶによって消費されることになるエネルギーとの線形結合、乗客によって支払われることになる全運賃、総移動時間と全運賃との線形結合、又は総移動時間と、定時運行車両によって消費されることになるエネルギーとの線形結合を最小化するように定式化することができる。これは、乗客に、より安価なサービスを提供する。
【００４４】
さらに、旅程が全運賃を含むとき、最適化問題は、制約のうちの１つとして全運賃を満たすように解かれる。これは、乗客に、移動スケジュールに関して、より柔軟な選択肢を提供する。
【００４５】
場合によっては、時間的に効率の良い計算サイクルを実行して、解を得るために、プロセッサ上で所定の期限に達するまで、グループ分けするステップ、割り当てるステップ、確実にするステップ及び評価するステップが繰り返される。
【００４６】
さらに、インターフェースは、ネットワークを介して、運用ルートマップ上の交通渋滞、交通事故及び工事中を含む、交通条件に関する情報を受信することができ、ルート探索プログラムは、交通条件を回避するように、グループのルートを探索する。これは、乗客に、より良好な（目的地までに要する時間が短い）サービスを提供し、ＣＶによって費やされることになる総エネルギー（燃料）も削減し、ＣＶのエネルギー消費量を削減する。
【００４７】
実施形態において、通勤者割当てプログラムは、乗客の総移動時間に関する制約、乗客を輸送する際に割り当てられたＣＶによって使用されるエネルギーに関する制約、及び総移動時間と乗客を輸送する際に使用されるエネルギーとの線形結合に関する制約のうちの１つに基づいて、最適化問題を解く。これは、乗客に、ＣＶを少ないエネルギー消費量で運用できるようにする柔軟な選択肢を提供することができる。さらに、そのシステムは、乗客が環境に優しい移動スケジュールを選択する場合に、定時運行車両の運賃がどれだけ割引されるかに関する情報を各乗客に送信することができる。これは、乗客に、環境に優しい移動に貢献する経済的なインセンティブを与えることができる。これは、定時運行車両の環境に優しい運行に関して大きな利点である。
【００４８】
図３Ｂは、要求される乗客目的地に達する際に通勤用車両によって使用されることになるルートを計算するためのルート探索プログラムの要素からなるフローチャートを示す一例である。ルート探索プログラム３０２は、メモリ内にＣＶの運用エリアのマップ３２１を有し、運用マップは、ＣＶが移動できる道路、道路間の交差点、異なる時間帯にこれらの各道路を移動するのに要する時間を表す。マップ上の情報はステップ３２２においてグラフとして表示され、グラフのノードは中継発着所、道路交差点及び目的地であり、グラフ内のエッジは道路である。グラフ表現を用いて、ステップ３２３において、中継発着所と目的地との間の最短経路が、よく知られたダイクストラアルゴリズムを用いて、乗換発着所からの異なる移動時間において計算され、戻るのに要する時間も同様にして計算される。そのような最短時間ルートに関する情報は、乗客のスケジューリングにおいて後に使用するために、ステップ３２４においてデータベースに記憶される。さらに、ルート探索プログラムを用いてルートが選択又は決定されると、ＣＶ運賃計算プログラム（図示せず）に基づいて、ＣＶの運賃が与えられ、そのプログラムは、決定されたルートの距離と、定時運行車両の発着所によって決定される中継地から目的地に達するのに要する予想時間とに基づいて、ＣＶの運賃を計算する。
【００４９】
場合によっては、システム３００は、対応する距離を含む、ルート情報を提供する外部ネットワークから、最短時間ルートに関する情報を取得することができる。外部ネットワークは第三者によって運用することができる。
【００５０】
図４は、本開示の実施形態による、複数の輸送モードにおいて乗客をスケジューリングする主要手順４００を示すフローチャートである。手順４００は入力ステップ４１０を実行し、入力データは、乗客ｊ∈Ｊごとの、起点ｓ（ｊ）、目的地ｄ（ｊ）及び到着時間窓
【数１】
2020004404.tif 000003
に関する情報を含む。この情報を用いて、手順４００は、乗客の総移動時間及びＣＶトリップ数の線形結合等の目的関数を最小化するために、ステップ４２０において、乗客の最適なスケジューリング及びグループ分けを計算する。その後、計算された解を用いて、ステップ４３０において、乗客への通勤用車両の割当てを特定する。最後に、割り当てられた定時運行車両、出発時刻及び割り当てられた通勤用車両の情報が、ステップ４４０において乗客に通信される。
【００５１】
問題記述
Ｔ０が、乗客が定時運行車両から柔軟にスケジューリングされる通勤用車両（ＣＶ）に乗り換える中継発着所を表すものとする。ＤをＣＶが停車する１組の目的地とし、ただし、Ｔ０∈Ｄである。目的地ｄ∈Ｄごとに、
【数２】
2020004404.tif 000004
を、ＣＶに乗車してＴ０を出発し、ｄまで移動し（ｔ１（ｄ，ｔ０）によって表される）、ｄにおいて乗客が下車するために停車し（ｔ２（ｄ，ｔ０）によって表される）、ＣＶが時刻ｔ０においてＴ０を出発するときにＴ０に戻る（ｔ３（ｄ，ｔ０）によって表される）のに要する総時間とする。
【数３】
2020004404.tif 000005
を両方のシステムの運用時刻の添数集合とする。Ｔ０において乗客をＣＶに乗車させるのに要する時間は、ｔ１（ｄ，ｔ０）に組み込まれる。さらに、乗客は、時刻ｔ０においてターミナルを出発してからｔ１（ｄ，ｔ０）時間単位後に目的地に到着したとされる。
【００５２】
定時運行車両の運行が、Ｃによって表される、１組のトリップによって記述される。各トリップｃ∈Ｃは、集合ｓ∈Ｓ内の発着所を起点とし、Ｔ０を終点とする。トリップｃが発着所ｓを出発する時刻は
【数４】
2020004404.tif 000006
であり、Ｔ０に到着する時刻は、
【数５】
2020004404.tif 000007
である。
【００５３】
Ｊを１組の乗客とする。各乗客ｊ∈Ｊは、時間間隔
【数６】
2020004404.tif 000008
内に到着するように、発着所ｊ∈ＪからＴ０までの輸送と、その後に、ＣＶによる目的地ｄ（ｊ）∈Ｄまでの輸送とを要求する。目的地ｄまでのサービスを要求する１組の乗客は、Ｊ（ｄ）によって表される。ｎ＝｜Ｊ｜及びｎｄ＝Ｊ（ｄ）とする。
【００５４】
Ｖを１組のＣＶとする。ただし、ｍ：＝｜Ｖ｜である。ｖｃａｐによって、単一のＣＶトリップに割り当てることができる乗客の最大数を表す。各ＣＶトリップは、１組の乗客がＣＶに乗車すること、Ｔ０から目的地ｄ∈Ｄまで移動すること、その後、Ｔ０に戻ることからなる。
【００５５】
異なる輸送モードにおいて乗客をスケジューリングする問題は、目的関数が最小化されるように、各乗客に定時運行車両及びＣＶによるトリップを割り当てることと同じである。例えば、目的関数の一例が、総移動時間とＣＶトリップ数との線形結合である。乗客の総移動時間及びＣＶトリップ数の最小化は相反しており、重み付け係数α、０≦α≦１を指定することによって、その両方のバランスが達成される。それゆえ、バランスがとれた目的関数はｆ（α）と表される。ただし、ｆ（α）＝α（総移動時間）＋（１−α）（ＣＶトリップ数）である。
【００５６】
場合によっては、目的関数は、定時運行車両及びＣＶのエネルギー消費量を含むことができる。システム３００は、定時運行車両及びＣＶのエネルギー消費量を削減するか、又は最小化することができる、出発時刻及びルートを含む移動スケジュールを示す情報を生成及び送信することができる。
【００５７】
重み付け係数αの選択は、システム運用者の優先傾向に基づいて、又はメモリに記憶される所定の数（図示せず）に基づいて、任意に選択することができる。さらに、システム運用者は、重み付け係数の異なる選択肢、例えば、α∈｛０，０．５，１．０｝の場合に乗客をスケジューリングする問題を解くことができる。その際、システム運用者は、２つの相反する目的関数間の妥当なトレードオフに基づいて、解のうちの１つを選択することができる。
【００５８】
乗客の実現可能なスケジューリングは、区分ｇ＝ｇ１，．．．，ｇγからなり、各ｇｌは出発時刻ｔ０（ｇｌ）に関連付けられ、ただし、ｌ＝１，．．．，γであり、出発時刻は、全ての要求時間及び運用制約を満たして、ｇｌにおいて乗客を乗せたＣＶが出発する時刻を示す。任意の乗客ｊ∈Ｊの場合に、ｇ（ｊ）を、その乗客ｊが属するグループとする。
【００５９】
乗客の実現可能なスケジューリングにおいて、グループの数はＣＶトリップ数と同じである。
【００６０】
整数計画法
本発明の一実施形態において、複数の輸送モードにおいて乗客をスケジューリングする問題は、整数計画（ＩＰ）として定式化することができる。ＩＰ変数は以下のものからなる。
【数７】
2020004404.tif 000009
−乗客ｊに関する総移動時間
【数８】
2020004404.tif 000010
−乗客ｊが定時運行トリップｃに割り当てられるか否かの指示子
【数９】
2020004404.tif 000011
−乗客ｊが時刻ｔにおいてＴ０を出発するか否かの指示子
【数１０】
2020004404.tif 000012
−時刻ｔにおいてＴ０に駐車されるＣＶの数
【数１１】
2020004404.tif 000013
−時刻ｔにおいてＴ０を出発するために目的地ｄに割り当てられるＣＶの数
【００６１】
ＩＰ法の目的関数は、
【数１２】
2020004404.tif 000014
であり、それは、重み付け係数α∈［０，１］を伴う、全ての乗客に関する総移動時間と、乗客を輸送するために必要とされるＣＶトリップ数との線形結合である。
【００６２】
ＩＰ法の制約は以下の通りである。
【数１３】
2020004404.tif 000015
その制約は、乗客ｊが発着所ｓ（ｊ）においてトリップｃに乗車し、時刻ｔにおいてターミナルを出発するＣＶにおいて目的地ｄ（ｊ）に到着する時間を結び付ける。
【数１４】
2020004404.tif 000016
その制約は、乗客ｊが１つのＣＶに割り当てられることを指定する。
【数１５】
2020004404.tif 000017
その制約は、乗客ｊがトリップのうちの１つに割り当てられることを指定する。
【数１６】
2020004404.tif 000018
その制約は、乗客ｊの到着時刻が、目的地ｄ（ｊ）における乗客の到着時間窓内にあることを指定する。
【数１７】
2020004404.tif 000019
その制約は、既にサービス中であるＣＶと、その時点ｔでサービスに向けて出発している数とに基づいて、Ｔ０において利用可能である車両の数を追跡する。
【数１８】
2020004404.tif 000020
その制約は、ＣＶの定員が満たされるのを確実にする。
【数１９】
2020004404.tif 000021
その制約は、割り当てられるＣＶの数が、移動している乗客の数を最低限満たすだけの数であるのを確実にする。
【数２０】
2020004404.tif 000022
その制約は、乗客ｊの移動時間に関する非負要件を指定する。
【数２１】
2020004404.tif 000023
その制約は、乗客が割り当てられるトリップｃのＴ０への到着後の或る時刻ｔにおいて、乗客ｊがＣＶトリップを開始することを指定する。
【数２２】
2020004404.tif 000024
それは、その変数がバイナリであることを指定する。
【数２３】
2020004404.tif 000025
その制約は、その変数がバイナリであることを指定する。
【数２４】
2020004404.tif 000026
その制約は、その変数が非負であることを指定する。
【数２５】
2020004404.tif 000027
その制約は、その変数が非負であることを指定する。
【数２６】
2020004404.tif 000028
その制約は、初期時刻ｔ＝０においてＴ０に駐車されるＣＶの数を指定する。
【００６３】
ＩＰ問題の定式化は、以下のように表すことができる。
【数２７】
2020004404.tif 000029
【００６４】
図５は、整数計画法を用いて乗客の最適なスケジューリングを取得するために図４のステップ４２０を実施する例示的なアルゴリズム５００の概略図である。アルゴリズム５００は、最適化変数を定義し（５１０）、目的関数を定式化し（５２０）、最適化問題における制約を規定し（５３０）、最適化問題を解いて、最適な解を取得する（５４０）。その後、取得された最適解を用いて、乗客ごとに、定時運行車両による出発時刻、及び通勤用車両による出発時刻を決定する（５５０）。
【００６５】
図６は、全ての乗客のための通勤用車両による出発時刻を入力として与えられるときに（５５０）、乗客への通勤用車両の割当てを決定するために図４のステップ４３０を実施する例示的なアルゴリズム６００の概略図である。そのアルゴリズムは、全てのＣＶ、Ｖ＝｛１，．．．，ｍ｝に関して、各通勤用車両にラベルｖａｌ（ｖ）＝０を割り当てることによって開始する（６１０）。これらのラベルを用いて、低いｖａｌ（ｖ）を有する方の車両が待ち行列の先頭にあるような、優先度付き待ち行列Ｑ＝｛（ｖ，ｖａｌ（ｖ））｜ｖ∈Ｖ｝が作成される（６２０）。ループが、運用時点
【数２８】
2020004404.tif 000030
ごとに（６３０）、目的地ｄ∈Ｄごとに（６４０）、実行される。そのアルゴリズムは、待ち行列の先頭にある車両を選択し（６５０）、Ｊ∈Ｊ（ｔ，ｄ）６７０から、通勤用車両による出発時刻がループ６３０内のｔの現在値と同じである乗客を順次に割り当てる。そのような乗客ごとに、現在の通勤用車両の定員に達したか否かがチェックされる（６７５）。達していない場合には、乗客がその車両に割り当てられ、車両の現在の占有率を増加させる（６８０）。定員を超えていた場合には、ラベルｖａｌ（ｖ）の値を増加させて（６８５）、待ち行列にプッシュする。待ち行列の先頭から新たな車両が取り出され、乗客に割り当てられ、占有率が更新される（６８５）。
【００６６】
状態空間分解
本発明の一実施形態において、複数の輸送モードにおける乗客のスケジューリングは、決定図（ＤＤ：decision diagram）分解を通して実行される。そのような実施形態において、コンパクトな決定図を用いて、特定の目的地に関する乗客の可能なグループ分けを表し、それは単一目的地決定図（ＤＤ）と呼ばれる。
【００６７】
単一目的地ＤＤ
目的地ｄ∈Ｄごとに、決定図Ｄｄが構成される。ＤＤ  Ｄｄは階層非循環有向グラフ（layered-acyclic directed graph）Ｄｄ＝（Ｎｄ，Ａｄ）である。ただし、ＮｄはＤＤ内の１組のノードであり、ＡｄはＤＤ内の１組のアークである。１組のノードＮｄは（ｎｄ＋２）個の順序付き階層
【数２９】
2020004404.tif 000031
に分割される。ただし、ｎｄ＝｜Ｊ（ｄ）｜である。階層
【数３０】
2020004404.tif 000032
及び
【数３１】
2020004404.tif 000033
は、根及び末端をそれぞれ表す１つのノードからなる。ノード
【数３２】
2020004404.tif 000034
の階層は、
【数３３】
2020004404.tif 000035
と定義される。各アークａ∈Ａｄは、自らのアーク−根ψ（ａ）から自らのアーク−末端ω（ａ）に向けられる。ただし、
【数３４】
2020004404.tif 000036
である。ａのアーク−階層は、
【数３５】
2020004404.tif 000037
と表される。ＤＤの階層
【数３６】
2020004404.tif 000038
は、ｔｒ（ｊｋ）≦ｔｒ（ｊｋ）のようなｔｒの非減少順（nondecreasing order）に順序付けられる乗客
【数３７】
2020004404.tif 000039
に対応する。各ノードｕは、ＤＤにおいてＣＶに既に乗車している乗客の数を表す状態
【数３８】
2020004404.tif 000040
に関連付けられる。ＤＤは２つのクラスの車：それぞれφ（ａ）＝１，０によって示される、１−アーク及び０−アークからなる。１−アークは、η（ａ）と、ＣＶによる出発時刻を表すアーク−出発時刻ｔ０（ａ）とを記憶する。アークのアーク−コストは、１組の乗客が負う全目的関数に対応し、アーク−出発時刻は、ＣＶにおいてＴ０から乗客が出発する時刻を示す。０−アークは、これらの属性を有しない。
【００６８】
目的地ｄに関するＤＤ  Ｄｄは、乗客の順序付けに基づいてＣＶに乗車することができる乗客のグループへのＪ（ｄ）の全ての実現可能な分割を表す。集合Ｐｄは、Ｄｄ内のアーク−指定されたｒｄ−ｔｄ間経路の集合である。任意の経路ｐ∈Ｐｄに関して、ｐによって規定される区分を構成するグループｇ（ｐ）は以下の通りである。ｐ内の全ての１−アークａがグループ
【数３９】
2020004404.tif 000041
に、すなわち、サイズ
【数４０】
2020004404.tif 000042
の添字
【数４１】
2020004404.tif 000043
において終了する、連続して添字を付される乗客の集合に対応する。ｐによって規定される区分は、
【数４２】
2020004404.tif 000044
である。全てのアーク−指定されたｒｄ−ｔｄ間の場合に、各乗客ｊ∈Ｊ（ｄ）の厳密に一度の発生を有する、すなわち、ｇ（ｊ）∈ｇ（ｐ）が一意であるように、ＤＤが構成される。
【００６９】
また、１−アークはＣＶによる出発時刻を有するので、その経路は、各グループｇ∈ｇ（ｐ）がＴ０を出発する時刻も決定付ける。時刻ｔ０（ａ）はＣＶによる出発時刻を示し、それゆえ、ＣＶは、時点
【数４３】
2020004404.tif 000045
において、引き続きサービス中である。そのＤＤの構成は、全てのｊ∈ｇ（ａ）の場合に、グループごとに目的地ｄへの到着時刻が実現可能であること、すなわち、
【数４４】
2020004404.tif 000046
であることを確実にする。
【００７０】
アークに関する目的関数値は、
【数４５】
2020004404.tif 000047
として取得することができる。ただし、第１の項はαによって増減され、総移動時間を重視し、第２の項はトリップ数を重視する。
【００７１】
経路ｐ∈Ｐｄのコストは、
【数４６】
2020004404.tif 000048
と表される。
【００７２】
ＤＤ生成
目的地ｄ∈Ｄごとに、次に記述される手順を用いて、決定図Ｄｄが構成される。ＤＤ内の０−アークが以下のように追加される。ｉ＝１，．．．，ｎｄ−１及び
【数４７】
2020004404.tif 000049
の場合に、階層
【数４８】
2020004404.tif 000050
上の状態
【数４９】
2020004404.tif 000051
を有するノードを階層
【数５０】
2020004404.tif 000052
上の状態
【数５１】
2020004404.tif 000053
を有するノードに接続する０−アークが追加される。乗客ｊごとに、ｔｅ（ｊ，ｔ），ｔｌ（ｊ，ｔ）が、時刻ｔにおいて出発するＣＶにおいて乗客が移動する場合の、Ｔ０からの最も早い可能な出発時刻及び最も遅い可能な出発時刻を表すものとする。これは、
【数５２】
2020004404.tif 000054
と計算することができる。
【００７３】
ＤＤ内の１−アークは以下のように追加される。ｉ＝１，．．．，ｎｄ及び
【数５３】
2020004404.tif 000055
の場合に、状態
【数５４】
2020004404.tif 000056
を有するノード
【数５５】
2020004404.tif 000057
を考える。
【数５６】
2020004404.tif 000058
の場合に、ｕから、状態０を有する階層
【数５７】
2020004404.tif 000059
上のノードまでの１−アークａが追加される。ｔ０（ａ）＝ｔを設定し、アークコストη（ａ）が式（ＤＤ．１）において定義されるように計算される。任意のｒｄ−ｔｄ間経路に属さないＤＤ内のアークは削除される。
【００７４】
ネットワークフロー法
ｄ∈Ｄごとに、決定図Ｄｄを与えられると、乗客の最適なスケジューリングは、無矛盾経路問題（consistent path problem）として提起される。各ＤＤにおいて、任意の時点
【数５８】
2020004404.tif 000060
において、｜Ｖ｜台より多くのＣＶが乗客を目的地に輸送するために使用中とならないように、経路が選択される。これは、形式的には、ｔごとに、
【数５９】
2020004404.tif 000061
である１−アークの数が｜Ｖ｜以下であるような、ｄ∈Ｄごとの、経路ｐｄ∈Ｐｄと述べることができる。Ｘ（ａ，ｔ）∈｛０，１｝は、時刻ｔにおいてＣＶが稼働中であることを示すものとする。すなわち、
【数６０】
2020004404.tif 000062
の場合、Ｘ（ａ，ｔ）＝１であり、それ以外の場合、Ｘ（ａ，ｔ）＝０である。乗客の最適なスケジューリングは、ネットワークフロー法として提起することができる。その定式化における変数は
【数６１】
2020004404.tif 000063
であり、アークａの選択肢を示す。目的関数は、
【数６２】
2020004404.tif 000064
のように定式化することができる。ネットワークフロー法における制約は以下の通りである。
【数６３】
2020004404.tif 000065
その制約は、各ＤＤの根ノードから厳密に１つのアークが選択されることを強制する。
【数６４】
2020004404.tif 000066
その制約は、各ＤＤの末端ノードへの厳密に１つのアークが選択されることを強制する。
【数６５】
2020004404.tif 000067
その制約は、或る特定のノードに関して、入って来るアークが選択される場合には、そのノードに関して、出て行くアークも選択されることを強制する。
【数６６】
2020004404.tif 000068
その制約は、任意の時点で使用中であるＣＶの数が｜Ｖ｜以下であることを強制する。
【数６７】
2020004404.tif 000069
その制約は、その変数がバイナリ値であることを強制する。
【００７５】
ネットワークフロー法のための最適化問題は以下のように表すことができる。
【数６８】
2020004404.tif 000070
【００７６】
図７は、本開示の実施形態による、図４のステップ４２０を実施する別の例示的なアルゴリズム７００の概略図である。アルゴリズム７００は、ネットワークフロー法を使用する乗客の最適なスケジューリングに伴うステップのフローチャートを用いて示される。その手順は最初に、目的地によって乗客を分ける（７１０）。そのような目的地ごとに、決定図が構成される（７２０）。最適化問題のための決定変数が定義される（７３０）。目的関数式（ＮＦ．１）が定式化され（７４０）、制約が定義される（７５０）。最適化問題式（ＮＦ）が解かれ（７６０）、最適解が得られる。その解を用いて、乗客グループを規定し（７７０）、乗客ごとに、通勤用車両による出発時刻及び定時運行トリップ時刻を割り当てる（７８０）。
【００７７】
図８は、本開示の実施形態による、図４のステップ４３０を実施する別の例示的なアルゴリズム８００の概略図である。アルゴリズム８００は、ネットワークフロー法を解くことから取得された、１組の乗客グループ及び通勤用車両出発時刻に基づいて、乗客への通勤用車両の割当てを提供する。アルゴリズム８００は、全てのＣＶ  Ｖ＝｛１，．．．，ｍ｝に関して、各通勤用車両にラベルｖａｌ（ｖ）＝０を割り当てることによって開始する（８１０）。これらのラベルを用いて、低いｖａｌ（ｖ）を有する方の車両が待ち行列の先頭にあるような、優先度付き待ち行列Ｑ＝｛（ｖ，ｖａｌ（ｖ））｜ｖ∈Ｖ｝が作成される（８２０）。グループ
【数６９】
2020004404.tif 000071
ごとにループが実行され（８３０）、グループのためのループに従って、ＣＶの目的地及び出発時刻が選択される（８４０）。そのアルゴリズムは、待ち行列の先頭にある車両を選択し（８５０）、ラベルｖａｌ（ｖ）の値を増加させて（８５０）、待ち行列にプッシュする（８５０）。
【００７８】
図９は、本開示の実施形態による、通勤用車両における乗客のグループ分けを表す決定図の一例である。同じ目的地までのサービスを要求する２人の乗客がいると仮定し、それらの乗客は時間窓内に目的地に到着するよう要求し、起点発着所の到着時刻は以下の通りである。
・乗客１：到着時間窓：［１０，１２］、起点発着所：１
・乗客２：［１２，１４］、起点発着所：２
定時運行車両は２つのトリップからなり、異なる発着所における出発時刻は以下の通りである。
・トリップ１：発着所３：４、発着所２：６、発着所１：８、Ｔ０＝１０
・トリップ２：発着所３：８、発着所２：１０、発着所１：１２、Ｔ０＝１４
通勤用車両による目的地到着時刻は２であり、通勤用車両の定員は２である。
【００７９】
乗客１は、トリップ１において到着し、１２において通勤用車両において移動した後に目的地に達することによって、単独で移動することができる。総移動時間は４であり、通勤用車両において唯一可能な出発時刻は１０である。これが、決定図において、総移動時間及び通勤用車両による出発時刻を表すラベル（４，１０）を有するアーク９５０によって表される。このアークは階層１の０−ノード９１０から階層２の０−ノード９２０まで描かれ、１−アークである。
【００８０】
乗客２は、トリップ１において到着し、１２において通勤用車両において移動した後に目的地に達することによって、単独で移動することができる。総移動時間は６であり、通勤用車両における可能な出発時刻は１０、１１、１２である。これらの異なる出発時刻の場合に、総移動時間はそれぞれ６、７、８である。したがって、ラベル（４，１０）９６１、（５，１１）９６２、（６，１２）９６３をそれぞれ有する３つの異なるアークがある。これらのアークは、階層２上の０−ノードから階層３の末端−ノード９４０まで描かれる。０−アーク９５５は、階層２上の０−ノードと階層３上の１−ノードとの間に描かれ、通勤用車両において乗客１及び２が一緒に移動することを示す。２人の乗客は、トリップ１において到着し、時刻１０において出発して通勤用車両において移動することによって、通勤用車両において一緒に移動することができる。このグループに関する総移動時間は１０であり、これが、階層２上の１−ノードを階層３上の末端ノードに接合する１−アークにおいて示される。
【００８１】
分枝価格法
本発明の別の実施形態では、いわゆる、指数関数法（ＥＦ）を用いて、乗客の最適なスケジューリングを見つけることができる。ＥＦ法では、変数は、
【数７０】
2020004404.tif 000072
であり、ＤＤ  Ｄｄからの経路の選択肢を示す。さらに、経路ごとに、特定の時点ｔにおいて使用されるＣＶの数を表すｋ（ｐ，ｔ）に関連付けられる。すなわち、
【数７１】
2020004404.tif 000073
である。ＥＦ法における目的関数は、
【数７２】
2020004404.tif 000074
である。ＥＦ法における制約は以下の通りである。
【数７３】
2020004404.tif 000075
その制約は、各ＤＤ  Ｄｄから厳密に１つの経路が選択されることを強制する。
【数７４】
2020004404.tif 000076
その制約は、任意の時点において使用中のＣＶの数が、ＣＶの利用可能な数以下であることを強制する。
【数７５】
2020004404.tif 000077
その制約は、変数がバイナリ値であることを強制する。ＥＦ法は、
【数７６】
2020004404.tif 000078
として提起することができる。
【００８２】
（ＥＦ）における最適化の定式化は、指数関数的な数の変数を有し、上記のように効率的に解くことはできない。この問題に対処するために、分枝価格（ＢＰ）アルゴリズムが開示される。
【００８３】
ＢＰアルゴリズムは、分枝決定のない初期探索木ノードを定義することによって開始し、ｄ∈Ｄごとに、経路のサブセット
【数７７】
2020004404.tif 000079
が選択される。
【数７８】
2020004404.tif 000080
である。経路のサブセットを用いて、制限付き主問題（ＲＭＰ：restricted master problem）と呼ばれる最適化問題が定義される。ＲＭＰ内の変数は、
【数７９】
2020004404.tif 000081
であり、ＤＤ  Ｄｄからの経路の選択肢を示す。ＲＭＰ法における目的関数は、
【数８０】
2020004404.tif 000082
である。ＲＭＰ法における制約は以下の通りである。
【数８１】
2020004404.tif 000083
その制約は、各ＤＤ  Ｄｄから厳密に１つの経路が選択されることを強制する。
【数８２】
2020004404.tif 000084
その制約は、任意の時点において使用中のＣＶの数が、ＣＶの利用可能な数以下であることを強制する。
【数８３】
2020004404.tif 000085
その制約は、その変数がバイナリ値であることを強制する。ＲＭＰ法は、
【数８４】
2020004404.tif 000086
として提起することができる。（ＲＭＰ．４）のバイナリ要件を
【数８５】
2020004404.tif 000087
に置き換えることによって、ＬＰＲＭＰと呼ばれる、ＲＭＰの線形計画緩和が得られる。
【００８４】
ＬＰＲＭＰは列生成を用いて解かれ、（ＥＦ）内の関連する変数が、
【数８６】
2020004404.tif 000088
において選択された経路に関するＬＰＲＭＰに対応する解において負である削減コストを有する場合に、経路
【数８７】
2020004404.tif 000089
が追加される。これは、以下に説明される価格決定問題を用いて成し遂げられる。
【００８５】
μｄ∀ｄ∈Ｄによって、ＬＰＲＭＰの最適解における（ＲＭＰ．２）に関連付けられるラグランジュ乗数を表す。
【数８８】
2020004404.tif 000090
によってＬＰＲＭＰの最適解における（ＲＭＰ．３）のためのラグランジュ乗数を表す。
【００８６】
負の削減コストを有する経路を特定する価格決定問題（ＰＰ）は以下の通りである。
・ｄ∈Ｄごとに、１−アークに関するアーク−コストθ（ａ）を
【数８９】
2020004404.tif 000091
と定義する。
・ｄ∈Ｄごとに、最小コスト経路ｒｄ−ｔｄ間において、アークコストθ（ａ）を用いてＤｄ内のＰｄが決定される。そのような計算は、よく知られたダイクストラアルゴリズムを用いて実行することができる。
・ｄ∈Ｄごとに、削減コストが
【数９０】
2020004404.tif 000092
と定義される場合には、経路ｐｄが
【数９１】
2020004404.tif 000093
に追加される。
【００８７】
（ＲＭＰ）を整数計画として解く結果として、乗客のスケジューリングに対する実行可能解が生じる。ＢＰアルゴリズムを完了するために、分岐限定探索が行われる。探索木ノードの待ち行列Γが定義され、シングルトンγ’として初期化される。アルゴリズムの実行中の任意の時点において、各探索ノードγ∈Γが、１組の分岐決定ｏｕｔ（γ），ｉｎ（γ）によって規定される。分岐限定探索は、最良の既知の解ｚ＊と、その目的値ｆ＊とを保持する。
【００８８】
【数９２】
2020004404.tif 000094
であるとき、探索ノードγが、調査するために選択される。選択されたノードは、それが作成された探索ノードの最悪のＬＰＲＭＰ緩和を有するノードである。探索ノードγに関するＬＰＲＭＰ緩和は、上記のような列生成を用いて解かれる。ＬＰＲＭＰ（γ）の最適な目的値がｆ＊より大きい場合には、そのノードは切り取られ、Γ内の別のノードを選択することによって探索が継続される。そうでない場合には、（ＲＭＰ）の整数計画が解かれ、目的値ｆ’を有する解ｚ’が得られる。ｆ’がｆ＊より小さい場合には、ｚ＊、ｆ＊がそれぞれｚ’、ｆ’に置き換えられる。
【数９３】
2020004404.tif 000095
がＬＰＲＭＰに対する最適値を表すものとする。最も大きい小数である経路
【数９４】
2020004404.tif 000096
が分岐するために選択される。２つのノードγ０、γ１が作成され、ただし、ｉｎ（γ０）＝ｉｎ（γ）、ｏｕｔ（γ０）＝ｏｕｔ（γ)∪｛ｐ｝、及びｉｎ（γ１）＝ｉｎ（γ）∪｛ｐ｝、及びｏｕｔ（γ１）＝ｏｕｔ（γ)であり、探索木が、
【数９５】
2020004404.tif 000097
のように更新される。
【００８９】
初期実行可能解を見つける
ＲＭＰに対する初期実行可能解が、乗客が割り当てられないｄ∈Ｄごとに経路ｐｄ，０を定義することによって得られ、すなわち、経路内の全てのアークに関してχ（ａ、ｔ）＝０であり、乗客スケジューリング問題に対する実行可能解より大きい目的値を有する。これを用いて、ＬＰＲＭＰが解かれ、価格決定問題（ｐｐ）において使用されるラグランジュ乗数が得られ、ｄ∈Ｄごとに負の削減コストを有する経路が得られる。そのような経路が特定されると、この経路ｐｄ，０がサブセット
【数９６】
2020004404.tif 000098
から削除される。
【００９０】
実行可能解を特定する
【数９７】
2020004404.tif 000099
がＬＰＲＭＰの最適解であり、その解が整数でないと仮定する。
【数９８】
2020004404.tif 000100
によって、その解内の最も大きい小数値を有する経路を表す。ｇ（ｐｄ）によって経路ｐｄによって定義されるグループを表す。グループｇ∈ｇ（ｐｄ）に関する最も早いＣＶ出発時刻ｔｅ（ｇ）及び最も遅いＣＶ出発時刻ｔｌ（ｇ）を
【数９９】
2020004404.tif 000101
と定義する。特定の出発時刻ｔ∈[ｔｅ（ｇ），ｔｌ（ｇ）]に関連付けられる目的値は、
【数１００】
2020004404.tif 000102
と表される。χ（ｇ，ｔ，ｔ’）∈｛０，１｝によって、時刻ｔにおいてＴ０から出発した後に、時点ｔ’においてグループｇによってＣＶが使用されるか否かを示す指示子を表す。
【００９１】
その最適化問題における変数は、時刻ｔにおいてそのグループがＣＶトリップを開始するか否かを指示するｘｇ，ｔ∈｛０，１｝である。その最適化問題における制約は以下の通りである。
【数１０１】
2020004404.tif 000103
その制約は、グループごとに、ＣＶのための厳密に１つの出発時刻が選択されることを強制する。
【数１０２】
2020004404.tif 000104
その制約は、同時に使用中のＣＶの数が、利用可能なＣＶの数以下であることを強制する。
【数１０３】
2020004404.tif 000105
その制約は、変数がバイナリ値であることを強制する。
【００９２】
実行可能解を見つけるための最適化問題は、
【数１０４】
2020004404.tif 000106
である。
【００９３】
図１０Ａは、ＢＰにおいて分枝価格法を用いて、複数の輸送モードにおける乗客のスケジューリングを最適化するためのフローチャートの例示である。その手順は、目的地によって乗客をグループに分けることによって開始する。目的地ごとに決定図が構成され（１００６）、探索木Γ＝｛（γ，ＬＢ（γ）｝であり、ただし、
【数１０５】
2020004404.tif 000107
であり、低い方のＬＢ（γ）が待ち行列の先頭にある（１０１０）。その問題に関する下限及び上限が初期化される（１０１３）。そのアルゴリズムは、１０１６において、下限及び上限が互いに近いか否かをチェックする。これが当てはまる場合には、そのアルゴリズムは、目的地ごとの決定図において最適経路を出力する。当てはまらない場合には、そのアルゴリズムは、探索木内の先頭の要素を選択する（１０２３）。最適化問題ＲＭＰ（γ）１０２６及び線形緩和問題によって定義されるアルゴリズムが解かれ（１０３０）、線形計画の最適解が得られる。ＬＰＲＭＰ（γ）の目的値が下限ＬＢ（γ）に割り当てられる（１０３３）。そのアルゴリズムは、そのノードのための下限が木のための上限以上であるか否かをチェックする（１０３６）。当てはまる場合には、このノードが突き止められ、アルゴリズムは、別のノードを選択することに進む（１０４０）。当てはまらない場合には、そのアルゴリズムは、線形計画の解が整数であるか否かをチェックする（１０４３）。その解が整数である場合には、そのアルゴリズムは、ノードのための上限を設定し（１０４６）、ノードための上限が探索木のための上限より良好であるか否かをチェックする（１０５０）。これが当てはまる場合には、探索木のための上限が更新され、各決定図内の最適経路が更新される（１０５３）。そのアルゴリズムは、分岐すべき経路を選択し（１０５６）、２つの子ノードを作成し（１０６０）、これらのノードを探索木に追加し（１０６３）、そのアルゴリズムは探索木内の次のノードに進む。線形緩和の解が整数でない場合には、そのアルゴリズムは、最適化問題（ＦＩＰ）を解くことによって、実行可能解を見つけるようと試みる（１０６６）。（ＦＩＰ）のための最適な目的値が、探索木のための上限に対してチェックされる（１０７０）。その上限が木のための上限より良好である場合には、最適解が更新される（１０７３）。そのアルゴリズムは、上記で説明されたように、分岐を開始する（１０５６）。その上限が木のための上限より良好でない場合、ここでも、アルゴリズムは、上記で説明されたように、分岐を開始する（１０５６）。
【００９４】
図１０Ｂは、通勤用車両及び定時運行車両による出発時刻の乗客への割当て、及び乗客のグループ分けの決定の一例を示す。そのアルゴリズムは、入力として、異なる決定図内の最適経路をとる（１０２０）。乗客のグループ分けは経路に基づいて決定され（１０２１）、定時運行車両及び通勤用車両の出発時刻が決定される（１０２２）。
【００９５】
乗客の最適なグループ分けを用いて、図８のフローチャートに略述される手順を使用して、乗客に割り当てられる車両を決定することができる。
【００９６】
２目的地ＤＤ
本発明の別の実施形態では、乗客は、目的地に関する制約を受けることなくグループ分けされる。例えば、各ＣＶは、異なる目的地に移動している乗客を含むことができる。システム３００が、近い距離の目的地、近い時間窓を示す割当て結果に基づいて、２つ以上の目的地が近い距離にあり、計算されたルートが類似であると判断し、乗客が利用可能な十分な座席をＣＶが有すると判断する場合には、又は割り当てられたＣＶの割当て情報が、同一の中継地と、その中継地からの割り当てられたＣＶの出発時刻とを含み、目的地及び到着時間窓が所定の時間を満たすと判断する場合には、システム３００は、グループ分けプログラム及び通勤者割当てプログラムの代わりに、多目的地グループ分けプログラム及び多目的地ＣＶ割当てプログラムを選択し、実行する。以下において、グループが２つ以下の目的地にサービスを提供するときの決定図の表現が説明される。以下に説明されるステップは、３つ以上の目的地のための決定図を構成するために適用することもできる。
【００９７】
Ｄ２が、その対間に重なりがない場合、すなわち、
【数１０６】
2020004404.tif 000108
の場合の目的地対の集合を表すものとする。（ｄ１，ｄ２）∈Ｄ２ごとに、決定図
【数１０７】
2020004404.tif 000109
が構成される。
【数１０８】
2020004404.tif 000110
は階層非循環有向グラフ
【数１０９】
2020004404.tif 000111
である。ただし、
【数１１０】
2020004404.tif 000112
はＤＤ内の１組のノードであり、
【数１１１】
2020004404.tif 000113
はＤＤ内の１組のアークである。１組のノード
【数１１２】
2020004404.tif 000114
は    
【数１１３】
2020004404.tif 000115
個の順序付き階層
【数１１４】
2020004404.tif 000116
に分割される。ただし、
【数１１５】
2020004404.tif 000117
である。階層
【数１１６】
2020004404.tif 000118
及び
【数１１７】
2020004404.tif 000119
は、根及び末端をそれぞれ表す１つのノードからなる。ノード
【数１１８】
2020004404.tif 000120
の階層は
【数１１９】
2020004404.tif 000121
と定義される。各アーク
【数１２０】
2020004404.tif 000122
は自らのアーク−根ψ（ａ）から自らのアーク−末端ω（ａ）に向けられる。ただし、
【数１２１】
2020004404.tif 000123
である。ａのアーク−階層は、
【数１２２】
2020004404.tif 000124
と表される。ＤＤの階層
【数１２３】
2020004404.tif 000125
は、ｔｒ（ｊｋ）≦ｔｒ（ｊｋ）のようなｔｒの非減少順に順序付けられる乗客
【数１２４】
2020004404.tif 000126
に対応する。各ノードｕは、ＤＤにおいてＣＶに既に乗車している乗客の数を表す状態
【数１２５】
2020004404.tif 000127
に関連付けられる。ＤＤは２つのクラスのアーク：それぞれφ（ａ）＝１，０によって示される、１−アーク及び０−アークからなる。１−アークは、η（ａ）と、ＣＶによる出発時刻を表すアーク−出発時刻ｔ０（ａ）とを記憶する。アークのアーク−コストは、１組の乗客が負う全目的関数に対応し、アーク−出発時刻は、ＣＶにおいてＴ０から乗客が出発する時刻を示す。０−アークは、これらの属性を有しない。
【００９８】
目的地（ｄ１，ｄ２）に関するＤＤ
【数１２６】
2020004404.tif 000128
は乗客の順序付けに基づいて、ＣＶに乗車することができる乗客のグループへの
【数１２７】
2020004404.tif 000129
の全ての実現可能な分割を表す。集合Ｐｄは、
【数１２８】
2020004404.tif 000130
内の１組のアーク−指定された
【数１２９】
2020004404.tif 000131
間経路である。任意の経路
【数１３０】
2020004404.tif 000132
に関して、ｐによって規定される区分を構成するグループｇ（ｐ）は以下の通りである。ｐ内の全ての１−アークａがグループ
【数１３１】
2020004404.tif 000133
に、すなわち、サイズ
【数１３２】
2020004404.tif 000134
の添字
【数１３３】
2020004404.tif 000135
において終了する、連続して添字を付される乗客の集合に対応する。ｐによって規定される区分は、
【数１３４】
2020004404.tif 000136
である。全てのアーク−指定された
【数１３５】
2020004404.tif 000137
間の場合に、各乗客
【数１３６】
2020004404.tif 000138
の厳密に一度の発生を有する、すなわち、ｇ（ｊ）∈ｇ（ｐ）が一意であるように、ＤＤが構成される。
【００９９】
また、１−アークはＣＶによる出発時刻を有するので、その経路は、各グループｇ∈ｇ（ｐ）がＴ０を出発する時刻も決定付ける。時刻ｔ０（ａ）はＣＶによる出発時刻を示し、それゆえ、ＣＶは、時点
【数１３７】
2020004404.tif 000139
において、引き続きサービス中である。ただし、ｔ（ｄ１，ｄ２，ｔ０（ａ））は、時刻ｔ０（ａ）においてＣＶがＴ０から出発するときに、目的地ｄ１、その後、目的地ｄ２までサービスを提供し、そして、Ｔ０に戻るのに要する最短移動時間である。ＤＤの構成は、全てのｊ∈ｇ（ａ）の場合に、グループごとに、目的地ｄへの到着時刻が実現可能である、すなわち、
【数１３８】
2020004404.tif 000140
であるのを確実にする。ただし、ｔ１（ｄ１，ｄ２，ｔ０（ａ）；ｄ（ｊ））は、目的地ｄ（ｊ）∈｛ｄ１，ｄ２｝に達するのに要する時間である。
【０１００】
アークに関する目的関数値は、
【数１３９】
2020004404.tif 000141
として取得することができる。ただし、第１の項はαによって増減され、総移動時間を重視し、第２の項はトリップ数を重視する。
【０１０１】
経路
【数１４０】
2020004404.tif 000142
のコストは、
【数１４１】
2020004404.tif 000143
と表される。
【０１０２】
ＤＤ生成
目的地（ｄ１，ｄ２）∈Ｄ２ごとに、次に記述される手順を用いて、決定図
【数１４２】
2020004404.tif 000144
が構成される。ＤＤ内の０−アークが以下のように追加される。
【数１４３】
2020004404.tif 000145
及び
【数１４４】
2020004404.tif 000146
の場合に、階層
【数１４５】
2020004404.tif 000147
上の状態
【数１４６】
2020004404.tif 000148
を有するノードを階層
【数１４７】
2020004404.tif 000149
上の状態
【数１４８】
2020004404.tif 000150
を有するノードに接続する０−アークが追加される。乗客ｊごとに、ｔｅ（ｊ，ｔ），ｔｌ（ｊ，ｔ）が、時刻ｔにおいて出発するＣＶにおいて乗客が移動する場合の、Ｔ０からの最も早い可能な出発時刻及び最も遅い可能な出発時刻を表すものとする。これは、
【数１４９】
2020004404.tif 000151
と計算することができる。
【０１０３】
ＤＤ内の１−アークは以下のように追加される。ｉ＝１，．．．，ｎｄ及び
【数１５０】
2020004404.tif 000152
の場合に、状態
【数１５１】
2020004404.tif 000153
を有するノード
【数１５２】
2020004404.tif 000154
を考える。
【数１５３】
2020004404.tif 000155
の場合に、ｕから、状態０を有する階層
【数１５４】
2020004404.tif 000156
上のノードまでの１−アークａが追加される。ｔ０（ａ）＝ｔを設定し、アークコストη（ａ）が式（ＤＤ．１）において定義されるように計算される。任意の
【数１５５】
2020004404.tif 000157
間経路に属さないＤＤ内のアークは削除される。
【０１０４】
ネットワークフロー法
（ｄ１，ｄ２）∈Ｄ２ごとに、決定図Ｄ２を与えられると、乗客の最適なスケジューリングは、無矛盾経路問題として提起される。各ＤＤにおいて、任意の時点
【数１５６】
2020004404.tif 000158
において、｜Ｖ｜台より多くのＣＶが乗客を目的地に輸送するために使用中とならないように、経路が選択される。これは、形式的には、ｔごとに、
【数１５７】
2020004404.tif 000159
である１−アークの数が｜Ｖ｜以下であるような、（ｄ１，ｄ２）∈Ｄ２ごとの、経路
【数１５８】
2020004404.tif 000160
と述べることができる。Ｘ（ａ，ｔ）∈｛０，１｝が、時刻ｔにおいてＣＶが稼働中であることを示すものとする。すなわち、
【数１５９】
2020004404.tif 000161
の場合、Ｘ（ａ，ｔ）＝１であり、それ以外の場合、Ｘ（ａ，ｔ）＝０である。乗客の最適なスケジューリングは、ネットワークフロー法として提起することができる。その定式化における変数は
【数１６０】
2020004404.tif 000162
であり、アークａの選択肢を示す。目的関数は、
【数１６１】
2020004404.tif 000163
のように定式化することができる。ネットワークフロー法における制約は以下の通りである。
【数１６２】
2020004404.tif 000164
その制約は、各ＤＤの根ノードから厳密に１つのアークが選択されることを強制する。
【数１６３】
2020004404.tif 000165
その制約は、各ＤＤの末端ノードへの厳密に１つのアークが選択されることを強制する。
【数１６４】
2020004404.tif 000166
その制約は、或る特定のノードに関して、入って来るアークが選択される場合には、そのノードに関して、出て行くアークも選択されることを強制する。
【数１６５】
2020004404.tif 000167
その制約は、任意の時点で使用中であるＣＶの数が｜Ｖ｜以下であることを強制する。
【数１６６】
2020004404.tif 000168
その制約は、その変数がバイナリ値であることを強制する。
【０１０５】
ネットワークフロー法のための最適化問題は以下のように表すことができる。
【数１６７】
2020004404.tif 000169
【０１０６】
図１１は、本開示の実施形態による、図４のステップ４２０を実施する別の例示的なアルゴリズム１１００の概略図である。アルゴリズム１１００は、式（ＮＦ２）における定式化を使用する、通勤用車両が２つの目的地まで移動するときに乗客を最適にスケジューリングするためのフローチャートを用いて示される。１組の乗客が目的地対によってサービスを提供される乗客に分けられる（１１１０）。目的地対ごとに、決定図が構成される（１１２０）。決定図に基づいて、最適化変数が定義され（１１３０）、目的関数（１１４０）、制約（１１５０）が定義される。最適化問題、式（ＮＦ２）を解いて（１１６０）、最適解を得る。最適解を用いて、乗客の最適なグループ分け（１１７０）と、通勤用車両、定時運行車両による出発時刻（１１８０）とを規定する。
【０１０７】
図１２は、本開示の実施形態による、図４のステップ４３０を実施する別の例示的なアルゴリズム１２００の概略図である。アルゴリズム１２００は、２目的地ネットワークフロー法において乗客に通勤用車両を割り当てるためのフローチャートによって示される。アルゴリズム１２００は、入力として、式（ＮＦ２）を解くことによって得られる乗客の最適なグループ分けをとる。そのアルゴリズムは、全てのＣＶ  Ｖ＝｛１，．．．，ｍ｝に関して、各通勤用車両にラベルｖａｌ（ｖ）＝０を割り当てることによって開始する（１２１０）。これらのラベルを用いて、低いｖａｌ（ｖ）を有する方の車両が待ち行列の先頭にあるような、優先度付き待ち行列Ｑ＝｛（ｖ，ｖａｌ（ｖ））｜ｖ∈Ｖ｝が作成される（１２２０）。グループ
【数１６８】
2020004404.tif 000170
ごとにループが実行され（１２３０）、グループのためのループに従って、ＣＶの目的地及び出発時刻が選択される（１２４０）。そのアルゴリズムは、待ち行列の先頭にある車両を選択し（１２５０）、ラベルｖａｌ（ｖ）の値を増加させて（１２５０）、待ち行列にプッシュする（１２５０）。
【０１０８】
図１３は、本開示の実施形態による、２つの目的地まで移動するときの通勤用車両における乗客のグループ分けを表す決定図の例である。２つの目的地までのサービスを要求する３人の乗客がいると仮定し、それらの乗客は時間窓内に目的地に到着するよう要求し、起点発着所の到着時刻は以下の通りである。
・乗客１：到着時間窓：［１０，１２］、起点発着所：１、目的地：１
・乗客２：［１０，１２］、起点発着所：１、目的地：２
・乗客３：［１５，１７］、起点発着所：１、目的地：１
定時運行車両は２つのトリップからなり、異なる発着所における出発時刻は以下の通りである。
・トリップ１：発着所３：４、発着所２：６、発着所１：８、Ｔ０：１０
・トリップ２：発着所３：８、発着所２：１０、発着所１：１２、Ｔ０：１４
ターミナルＴ０から通勤用車両において目的地１又は目的地２に達するのに要する時間は１であり、かつ、目的地１から目的地２に達するのに要する時間は１である。
【０１０９】
乗客１は、トリップ１において到着し、１０において通勤用車両において移動した後に目的地に達することによって、単独で移動することができる。総移動時間は３であり、通勤用車両において可能な出発時刻は１０である。これが、決定図において、総移動時間及び通勤用車両による出発時刻を表すラベル（３，１０）を有するアーク１３１１によって表される。このアークは階層１の０−ノード１３１０から階層２の０−ノード１３２０まで描かれ、１−アークである。１１の通勤用車両による出発時刻及び４の総移動時間を示す別の１−アーク１３１２も描かれる。
【０１１０】
乗客２は、トリップ１において到着し、通勤用車両において移動した後に目的地２に達することによって、単独で移動することができる。総移動時間は３，４であり、通勤用車両における可能な出発時刻は１０、１１である。したがって、ラベル（３，１０）１３２１、（４，１１）１３２２をそれぞれ有する２つの異なる１−アークがある。これらのアークは、階層２上の０−ノード１３２０から階層３の０−ノード１３４０まで描かれる。
【０１１１】
０−アーク１３１３は、階層２上の０−ノードと階層３上の１−ノードとの間に描かれ、通勤用車両において乗客１及び２が一緒に移動することを示す。２人の乗客は、トリップ１において到着し、時刻１０において出発して通勤用車両において移動することによって、通勤用車両において一緒に移動することができる。このグループに関する総移動時間は７であり、これが、階層２上の１−ノード１３３０を階層３上の０−ノード１３４０に接合する１−アークにおいて示される。
【０１１２】
乗客３は、トリップ２において到着した後に、目的地１に達するのに通勤用車両において単独で移動することができる。このトリップに関して可能な出発時刻は１４であり、総移動時間は３である。これは、階層３上の０−ノード１３４０を階層４上の末端−ノード１３６０に接合する１−アーク１３４１によって示される。１５の通勤用車両による出発時刻を示す付加的な１−アーク１３４２及び１６の通勤用車両による出発時刻を示す付加的な１−アーク１３４３も描かれる。
【０１１３】
乗客２及び３は、任意の時刻において出発する通勤用車両においてのみ一緒に移動することができる。それゆえ、階層３上に１−ノードは存在しない。
【０１１４】
数値評価
図１４は、本開示の実施形態による、１組のテスト事例においてＢＰ法及びＮＦ法を比較する、性能の累積分布プロットである。そのプロットは、任意の所与のタイムバジェットにおいて解かれる問題の数に関して、分枝価格法に基づく定式化が優れていることを明確に示す。ＢＰは、全ての問題を３分未満で解く。
【０１１５】
図１５は、本開示の実施形態による、ＢＰ法を用いて、１００００人の乗客、５０の目的地、６００台のＣＶの場合の数分間のパレートフロンティアの計算結果を示す。パレートフロンティアは、目的関数のうちの１つにおける小さなトレードオフの結果として、他の目的関数において大きい改善が生じる可能性があることを示す。曲線全体を、数分のうちに生成することができ、運用中に適切なトレードオフが選択されるので、これはシステム運用者にとって重要である。
【０１１６】
図１６は、本開示の実施形態による、ＢＰ法及びＮＦ法を比較する散布図である。座標はＮＦのランタイム及びＢＰのランタイムである。ドットのサイズは、ｎに対応し（ｎが増加すると、サイズが大きくなり）、ドットの色は乗客数と目的地数との比（すなわち、目的地あたりの乗客の平均数）に対応する。このプロットは、わずか数個の事例においてＢＰの利点をより容易に明らかにし、ＮＦのランタイムはＢＰのランタイムより短い。
【０１１７】
図１７は、目的関数における重み付け係数αの異なる設定の場合の、総乗客移動時間及び平均ＣＶ数を表す散布図である。全てのドットの座標は、得られた解におけるＣＶトリップ数及び総乗客移動時間に対応する。円のサイズは、テストされた全ての事例にわたる平均解答時間に対応する。それらの事例は時間窓によって分割され、Ｔｗ＝１０の場合に青色、Ｔｗ＝２０の場合にオレンジ色である。このプロットは、時間窓を広くしても、得られる解の質がわずかに異なるだけであることを示す。全事例を平均すると、Ｔｗ＝１０及びＴｗ＝２０の場合にそれぞれ、ＣＶトリップ数は８８８及び８７７であり、総移動時間は２１３２３９及び１９８４０６である。それは、１．２１％のＣＶトリップ数の減少、及び６．９６％の総移動時間の減少を表す。解答時間の増加ははるかに大幅であり、６８．２４秒から１５３．３２秒に増加し、平均して、１２３．２１％の増加である。これは、到着時間制約に関する柔軟性を高められるようにすると、問題が著しく難しくなるが、その結果として、運用上の決定がわずかに良好になることを示す。それゆえ、これは、運用者が、相対的に長い時間窓で問題を解こうと試みる場合があるが、解を得る必要がある場合に、この柔軟性を下げると、計算時間が短くなることを示す。したがって、本開示のいくつかの実施形態は、コンピューター（プロセッサ）の電力消費量を削減し、計算システムの機能を改善することができる。
【０１１８】
本開示のいくつかの実施形態において、通勤用車両割当てシステムが使用されるとき、又は上記の実行可能プログラムモジュールがコンピューターシステムにインストールされるとき、通勤用車両割当てを、より短い時間及びより低い計算能力で実効的かつ正確に実行することができ、それゆえ、本開示において記述される通勤用車両割当て方法又はシステムの使用は、中央処理ユニット使用量及び電力消費量を削減することができる。
【０１１９】
上述した本開示の実施形態は、数多くの方法のうちの任意のもので実施することができる。例えば、実施形態は、ハードウェア、ソフトウェア又はそれらの組み合わせを用いて実施することができる。請求項の要素を修飾する、特許請求の範囲における「第１」、「第２」等の序数の使用は、それ自体で、１つの請求項の要素の別の請求項の要素に対する優先順位も、優位性も、順序も暗示するものでもなければ、方法の動作が実行される時間的な順序も暗示するものでもなく、請求項の要素を区別するために、単に、或る特定の名称を有する１つの請求項の要素を、同じ（序数の用語の使用を除く）名称を有する別の要素と区別するラベルとして用いられているにすぎない。
【０１２０】
本開示は、幾つかの特定の好ましい実施形態に関して説明されてきたが、本開示の趣旨及び範囲内において様々な他の適応及び変更を行うことができることが理解されるべきである。したがって、添付の特許請求の範囲の態様は、本開示の真の趣旨及び範囲に含まれる全ての変形及び変更を包含するものである。
【図１】
2020004404.tif 000171
【図２】
2020004404.tif 000172
【図３Ａ】
2020004404.tif 000173
【図３Ｂ】
2020004404.tif 000174
【図４】
2020004404.tif 000175
【図５】
2020004404.tif 000176
【図６】
2020004404.tif 000177
【図７】
2020004404.tif 000178
【図８】
2020004404.tif 000179
【図９】
2020004404.tif 000180
【図１０Ａ】
2020004404.tif 000181
【図１０Ｂ】
2020004404.tif 000182
【図１１】
2020004404.tif 000183
【図１２】
2020004404.tif 000184
【図１３】
2020004404.tif 000185
【図１４】
2020004404.tif 000186
【図１５】
2020004404.tif 000187
【図１６】
2020004404.tif 000188
【図１７】
2020004404.tif 000189