(57)【要約】      （修正有）【課題】マルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを提供する。【解決手段】方法は、オリジントリップの各ステーションに対し、最先の到着／変更時刻を計算する段階、到着可能なステーションへの実現可能な乗り換えのセットの内の少なくとも１つの乗り換えに対し、到着可能なステーション以降に最先の到着／変更時刻の値を計算する段階、最先の到着／変更時刻の各計算された値が乗り換えにより改善されないと判定された場合にのみ、乗り換えを排除する段階、実現可能な乗り換えのセットを出力する段階及び最初トリップから最終トリップへのメイン部分の内、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数又は最も遅い出発時刻及び乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズムを実行する段階を有する。【選択図】図４
2020193974.tif 000002
【特許請求の範囲】
【請求項１】
マルチモーダル交通ネットワークの２つのステーション間のマルチモーダル交通ネットワーク内の各トリップｔ、すなわち、オリジントリップに対し、所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理する方法であって、
（ａ）前記オリジントリップｔの各ステーションｐｔｉに対し、該当のステーションｐｔｉで前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数４８】
2020193974.tif 000050
または最先の変更時刻
【数４９】
2020193974.tif 000051
の値を計算する段階、
（ｂ）前記オリジントリップｔ上のステーションｐｔｉからターゲットトリップｕ上の到着可能なステーションｐｕｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え
【数５０】
2020193974.tif 000052
に対し、前記到着可能なステーションｐｕｊ以降に前記ターゲットトリップｕの各ステーションｐｕｋ＞ｊで、前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻
【数５１】
2020193974.tif 000053
または最先の変更時刻
【数５２】
2020193974.tif 000054
の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数５３】
2020193974.tif 000055
または最先の変更時刻
【数５４】
2020193974.tif 000056
の値を計算する段階、
（ｃ）最先の到着時刻
【数５５】
2020193974.tif 000057
または最先の変更時刻
【数５６】
2020193974.tif 000058
の各計算された値が前記乗り換え
【数５７】
2020193974.tif 000059
によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え
【数５８】
2020193974.tif 000060
を排除する段階、および
（ｄ）前記マルチモーダル交通ネットワークの少なくとも１つの旅程を計算するために、前記実現可能な乗り換えのセットを出力する段階
を含む、方法。
【請求項２】
スケジュールの関数として、最先の到着時刻または最先の変更時刻を初期化する段階
をさらに含む、請求項１に記載の方法。
【請求項３】
前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻または最先の変更時刻の値は、前記交通モードｍｕまたは前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔだけを使用するとき、最先の到着時刻または最先の変更時刻に対応する、請求項１に記載の方法。
【請求項４】
前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻または最先の変更時刻の値は、前記交通モードｍｕまたは前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔだけを使用するとき、最先の到着時刻または最先の変更時刻に対応する、請求項２に記載の方法。
【請求項５】
前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）を繰り返し実行する段階
をさらに含む、請求項１に記載の方法。
【請求項６】
前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）を繰り返し実行する段階
をさらに含む、請求項２に記載の方法。
【請求項７】
前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）を繰り返し実行する段階
をさらに含む、請求項３に記載の方法。
【請求項８】
前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）を繰り返し実行する段階
をさらに含む、請求項４に記載の方法。
【請求項９】
前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回するとき、前記オリジントリップの各連続的なステーションからの乗り換えを繰り返し考慮する段階
をさらに含む、請求項５に記載の方法。
【請求項１０】
前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回するとき、前記オリジントリップの各連続的なステーションからの乗り換えを繰り返し考慮する段階
をさらに含む、請求項６に記載の方法。
【請求項１１】
前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回するとき、前記オリジントリップの各連続的なステーションからの乗り換えを繰り返し考慮する段階
をさらに含む、請求項７に記載の方法。
【請求項１２】
前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回するとき、前記オリジントリップの各連続的なステーションからの乗り換えを繰り返し考慮する段階
をさらに含む、請求項８に記載の方法。
【請求項１３】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項１に記載の方法。
【請求項１４】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項２に記載の方法。
【請求項１５】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項３に記載の方法。
【請求項１６】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項４に記載の方法。
【請求項１７】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項５に記載の方法。
【請求項１８】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項６に記載の方法。
【請求項１９】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項７に記載の方法。
【請求項２０】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項８に記載の方法。
【請求項２１】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項９に記載の方法。
【請求項２２】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項１０に記載の方法。
【請求項２３】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項１１に記載の方法。
【請求項２４】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項１２に記載の方法。
【請求項２５】
（ｅ）可能な最初トリップのセットに属する最初トリップから可能な最終トリップのセットに属する最終トリップへのメイン部分を有する旅程のうち、選択された交通モードを有する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズムを実行する段階
をさらに含む、請求項１に記載の方法。
【請求項２６】
前記ルーティング最適化アルゴリズムは、パレート効率性を計算する、請求項２５に記載の方法。
【請求項２７】
前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加的なトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素あたり少なくとも１つの最適ソリューションを計算する、請求項２６に記載の方法。
【請求項２８】
出発地から到着地までの少なくとも１つの旅程を計算する方法であって、各旅程は、所定のステーションのマルチモーダル交通ネットワーク内のメイン部分（前記マルチモーダル交通ネットワーク内の可能なトリップのセットからのトリップ、および前記マルチモーダル交通ネットワーク内の実現可能な乗り換えのセットからの乗り換えのシーケンスとして定義される）を含み、前記旅程は、前記マルチモーダル交通ネットワークの可能な交通モードのうちから選択された交通モードの組み合わせに制限され、
（ａ）実現可能な乗り換えのサブセットを取得するために、前記マルチモーダル交通ネットワーク内の前記実現可能な乗り換えのセットを前処理する段階、
（ｂ）前記マルチモーダル交通ネットワーク内で、前記出発地の関数として可能な最初トリップのセット、および前記到着地の関数として可能な最終トリップのセットを決定する段階、および
（ｃ）前記可能な最初トリップのセットに属する最初トリップから前記可能な最終トリップのセットに属する最終トリップへのメイン部分を有する旅程のうち、前記選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズムを実行する段階
を含む、方法。
【請求項２９】
前記ルーティング最適化アルゴリズムは、パレート効率性を計算する、請求項２８に記載の方法。
【請求項３０】
前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加のトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素あたり少なくとも１つの最適ソリューションを計算する、請求項２９に記載の方法。
【請求項３１】
出発地から到着地までの少なくとも１つの旅程を計算するために、所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理するコンピュータプログラムであって、当該コンピュータプログラムは、プロセスを実行するようにコンピュータ上で実行され、
前記プロセスは、
（ａ）オリジントリップｔの各ステーションｐｔｉに対し、該当のステーションｐｔｉで前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数５９】
2020193974.tif 000061
または最先の変更時刻
【数６０】
2020193974.tif 000062
の値を計算する段階、
（ｂ）前記オリジントリップｔ上のステーションｐｔｉからターゲットトリップｕ上の到着可能なステーションｐｕｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え
【数６１】
2020193974.tif 000063
に対し、前記到着可能なステーションｐｕｊ以降に前記ターゲットトリップｕの各ステーションｐｕｋ＞ｊで、前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻
【数６２】
2020193974.tif 000064
または最先の変更時刻
【数６３】
2020193974.tif 000065
の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数６４】
2020193974.tif 000066
または最先の変更時刻
【数６５】
2020193974.tif 000067
の値を計算する段階、
（ｃ）最先の到着時刻
【数６６】
2020193974.tif 000068
または最先の変更時刻
【数６７】
2020193974.tif 000069
の各計算された値が前記乗り換え
【数６８】
2020193974.tif 000070
によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え
【数６９】
2020193974.tif 000071
を排除する段階、および
（ｄ）前記マルチモーダル交通ネットワークの少なくとも１つの旅程を計算するために前記実現可能な乗り換えのセットを出力する段階
を含む、コンピュータプログラム。
【請求項３２】
前記プロセスは、スケジュールの関数として、最先の到着時刻または最先の変更時刻を初期化する段階
をさらに含む、請求項３１に記載のコンピュータプログラム。
【請求項３３】
前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻または最先の変更時刻の値は、前記交通モードｍｕまたは前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔだけを使用するとき、最先の到着時刻または最先の変更時刻に対応する、請求項３２に記載のコンピュータプログラム。
【請求項３４】
前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）が繰り返し実行される、請求項３１に記載のコンピュータプログラム。
【請求項３５】
（ｂ）および（ｃ）は、前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回するとき、前記オリジントリップの各連続的なステーションからの乗り換えを繰り返し考慮する、請求項３２に記載のコンピュータプログラム。
【請求項３６】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に、前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣のステーションでも計算される、請求項３３に記載のコンピュータプログラム。
【請求項３７】
前記プロセスは、（ｅ）可能な最初トリップのセットに属する最初トリップから可能な最終トリップのセットに属する最終トリップのメイン部分を有する旅程のうち、選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズムを実行する段階
をさらに含む、請求項３１に記載のコンピュータプログラム。
【請求項３８】
前記ルーティング最適化アルゴリズムは、パレート効率性を計算する、請求項３７に記載のコンピュータプログラム。
【請求項３９】
前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加のトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素あたり少なくとも１つの最適ソリューションを計算する、請求項３８に記載のコンピュータプログラム。
【請求項４０】
当該コンピュータプログラムは、コンピュータ読み取り可能な媒体である、請求項３１に記載のコンピュータプログラム。
【請求項４１】
出発地から到着地までの少なくとも１つの旅程を計算するために所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理するコンピュータプログラムであって、当該コンピュータプログラムは、プロセスを実行するようにコンピュータ上で実行され、
前記プロセスは、
（ａ）実現可能な乗り換えのサブセットを取得するために、前記マルチモーダル交通ネットワーク内の前記実現可能な乗り換えのセットを前処理する段階、
（ｂ）前記マルチモーダル交通ネットワーク内で、前記出発地の関数として可能な最初トリップのセット、および前記到着地の関数として可能な最終トリップのセットを決定する段階、および
（ｃ）前記可能な最初トリップのセットに属する最初トリップから前記可能な最終トリップのセットに属する最終トリップへのメイン部分を有する旅程のうち、前記選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズムを実行する段階
を含む、コンピュータプログラム。
【請求項４２】
前記ルーティング最適化アルゴリズムは、パレート効率性を計算する、請求項４１に記載のコンピュータプログラム。
【請求項４３】
前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加のトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素あたり少なくとも１つの最適ソリューションを計算する、請求項４２に記載のコンピュータプログラム。
【請求項４４】
当該コンピュータプログラムは、コンピュータ読み取り可能な媒体である、請求項４１に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、３５  Ｕ．Ｓ．Ｃ．§１１９（ａ）に基づき、２０１９年５月２９日付で出願された欧州特許出願ＥＰ１９３０５６８７．６の先出願日および優先権の利益を主張し、その内容すべては参照としてここに統合される。
【背景技術】
【０００２】
旅行プランナー（ｊｏｕｒｎｅｙ  ｐｌａｎｎｅｒ）（または、トリッププランナーとも呼ばれる）とは、１つおよび／またはそれ以上の交通モード、特に、公共交通モード（例えば、地下鉄、路面電車、バスなど）を利用して交通の出発地（最初の出発地（ｏｒｉｇｉｎ））から到着地（目的地）までの最適な旅程を決めるために利用されるサービスである。旅行プランナーは、多種類の交通モードをカバーし、モード同士の連結を許容するとき（すなわち、所定のモードから他のモードへの乗り換え）を「マルチモーダル」と呼ぶ。検索は、例えば、最速、最短、最小回数の乗り換え（ｃｈａｎｇｅ）、および／または最安値のような異なる基準によって最適化される。これらは、例えば、特定の時刻に出発および／または到着するためや、特定の中間地点（ｗａｙｐｏｉｎｔ）を回避するためなどにより制限されてよい。
【０００３】
公共交通モードは、一般公開されたスケジュールに基づいて動く。公共交通サービスは、（いつでも出発可能な自家用車の運転、徒歩、および／または自転車のようなプライベートモードとは異なり）特定の時刻に限って出発するという点を考慮するとき、旅行プランナーアルゴリズムは目的地までの経路だけを探索するのではなく、時間に従属的な設定内で到着時間を最小化するように経路を最適化しなければならない。
【０００４】
このために利用される最高性能のアルゴリズムの１つとして「トリップ基盤の公共交通ルーティング」アルゴリズム（「Ｔｒｉｐ−Ｂａｓｅｄ  Ｐｕｂｌｉｃ  Ｔｒａｎｓｉｔ  Ｒｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍ」および／または「ＴＢアルゴリズム」）が挙げられる。これは、グラフの幅優先探索（Ｂｒｅａｄｔｈ−Ｆｉｒｓｔ  Ｓｅａｒｃｈ：ＢＦＲ）と同じように繰り返しを基盤とした方法であって、ある１つのトリップがある１つの繰り返しを採択すること（ｔａｋｉｎｇ  ａ  ｔｒｉｐ）に対応する。これは非特許文献１に記載されている。
【０００５】
ＴＢアルゴリズムは、パレート効率性（Ｐａｒｅｔｏ  ｆｒｏｎｔ）と、（最初の）出発地（ｏｒｉｇｉｎ）、到着地、および出発時刻を考慮し、ステーション間の乗り換え（ｔｒａｎｓｉｔ）と徒歩だけに制限されていたマルチモーダルネットワークにおける２種類の基準に対し、パレート効率性内の各値に対し、このような値を有する最適な経路をともに計算するためのアルゴリズムである。考慮される２種類の基準は、最小到着時刻（Ｍｉｎ  ａｒｒｉｖａｌ  ｔｉｍｅ）（すなわち、出発時刻を考慮した
最先の（ｅａｒｌｉｅｓｔ）到着時刻）と、最小乗り換え回数（Ｍｉｎ  ｔｒａｎｓｆｅｒ  ｎｕｍｂｅｒ）（すなわち、最小連結回数、言い換えれば、同じネットワーク（例えば、地下鉄から他のもの）内、および／またはインタモーダル（ｉｎｔｅｒｍｏｄａｌｌｙ）公共交通モードの変更（乗り換え）（ｃｈａｎｇｅｓ）の回数）である。
【０００６】
最先の到着時刻クエリは、トリップが頂点となり、実現可能な乗り換えがアーク（ａｒｃ）となる時間−独立的なグラフ内で、幅優先探索と同じような探索によって構成される（すなわち、次の深さレベルのトリップに移動する前に、現在の深さ（ｄｅｐｔｈ）で、該当のグラフ上で隣り合うすべてのトリップを探索する）。したがって、各繰り返しにおいて、追加的なトリップが、目的地への到達のために各ソリューション（ｓｏｌｕｔｉｏｎ）として採択される。
【０００７】
最も遅い（ｌａｔｅｓｔ）出発時刻クエリで構成されるＴＢアルゴリズムの拡張が考慮される場合もある。最も遅い出発時刻クエリにおいては、所期の到着時刻が開始時刻の代りに与えられ、パレート経路を計算するために考慮される２種類の基準は、最大出発時刻（Ｍａｘ  ｄｅｐａｒｔｕｒｅ  ｔｉｍｅ）（すなわち、終了時刻を考慮した最も遅い出発時刻）と、最小乗り換え回数（Ｍｉｎ  ｔｒａｎｓｆｅｒ  ｎｕｍｂｅｒ）となる。
【０００８】
最も遅い出発時刻クエリは、トリップが頂点となり、実現可能な乗り換えがアーク（ａｒｃ）となる、前記で定義した時間−独立的なグラフの逆方向探索（ｂａｃｋｗａｒｄ  ｓｅａｒｃｈ）と同じような探索で構成される。
【０００９】
ＴＢアルゴリズムは、トリップ内の実現可能な乗り換えの前処理およびプルーニング（ｐｒｕｎｉｎｇ）を基盤とする。パレート効率性内の任意の最適値に対して前処理された隣り合うセットが、最適経路内において、あるトリップおよびその隣との間で乗り換え（ｔｒａｎｓｉｔｉｏｎ）を含むように、このような最適値を有する最適経路が存在するようにする方式により、各トリップに対して到着可能なトリップの隣を構築することを目標とする。
【００１０】
実際には正確な結果的方法も知れないが、探索段階中のトリップ同士で実現可能な乗り換えの完全なセットを使用することは、それが膨大（ｌａｒｇｅ）である上に、無駄なアークが探索時間に影響を及ぼすようにもなるという点において好ましくない。
【００１１】
例えば、韓国の交通ネットワークでの利用時に、ＴＢアルゴリズムによるプルーニングは、各路線への
最先の（ｅａｒｌｉｅｓｔ）実現可能な乗り換えだけを考慮するとき、９本のうちから約８本の実現可能な乗り換えを排除する。
【００１２】
事実、１つのトリップと他の路線（同じ停止シーケンスを有する、全体的に整列された（ｏｒｄｅｒｅｄ）トリップのセット）との間のすべての実現可能な乗り換えが考慮されると、最先のトリップ（路線順序（ｌｉｎｅ  ｏｒｄｅｒ）に関する最小トリップ）だけが、前記定義されたパレートクエリと関連するようになるであろう。
【００１３】
したがって、すべての最適値（すなわち、パレート効率性）およびパレート効率性内の各要素（ｅｌｅｍｅｎｔ）に対し、このような値を有する少なくとも１つの最適経路を計算するために、十分な乗り換えを維持しながら実現可能な乗り換えのセットをプルーニングすることが好ましい。このために、２種類のプルーニング方法として、（１）各トリップに対し、Ｕターン乗り換え（誰かを（トリップを採択する前の停止点の到着時刻よりも後の時刻において）トリップ内の以前の停止点（ｓｔｏｐ）に連れて行くだけの乗り換え）は排除すること、および（２）到着時刻の改善に繋がらない乗り換え（以後の（ｌａｔｅｒ）乗り換え（または、現在のトリップ上に残っているもの）が同等および／またはさらに優れた到着時刻に繋がり、該当の乗り換えによって到着可能なすべてのトリップは、前記以後の乗り換えによって到着される）を排除することが提供される。
【００１４】
例えば、図２において、トリップｔの停止点ｐｔｉからトリップｕの停止点ｐｕｊへの乗り換えは、トリップｕの次の停止点ｐｕｊ＋１への乗り換えよりも常に優れた到着時刻に繋がるはずであり、したがって、乗り換え
【数１】
2020193974.tif 000003
はプルーニングされてよい。
【００１５】
最先の到着時刻クエリ対して正しい乗り換えのセット（すなわち、どのような場合であっても、パレート効率性およびこのような値を有する各最適値に対する少なくとも１つの最適経路を計算するために十分な乗り換えを含むこと）は、最も遅い出発時刻クエリに対しても正しいということに留意する。これについては、非特許文献２に記載されている。
【００１６】
現在のＴＢアルゴリズムの限界は、クエリ時点で、ユーザがどのモードの組み合わせを含もうとするか、および／または排除しようとするかを正確に指定することができないという点にある。より具体的に、ユーザがバスに十分な信頼性がないと考慮してバスの利用を回避しようとしたり、または／追加的に、他の脈絡から路面電車の混雑を考慮して路面電車を回避しようとしたりする。
【００１７】
実際に、プルーニングは、モードが特定の組み合わせに制限される場合、実際には有用となる乗り換えを排除させることがあり、これにより、モード選択時に検索されたソリューションが最適ではない場合が存在する。
【００１８】
例えば、図３において、３つのトリップｔ１、ｔ２、およびｔ３が、例えば、バス３０２、路面電車３０４、および地下鉄（ｍｅｔｒｏ）３０６のような異なるモードであると仮定する。トリップｔ１からの乗り換えを考慮するとき、ステーションｐでｔ１からｔ３への乗り換えが可能であり、ステーションｐおよびｑの間を徒歩で移動することによりｔ１からｔ２への乗り換えが可能となる（徒歩による経路は、図３において実線で表記）。
【００１９】
プルーニングは、トリップｔ１からトリップｔ２への乗り換えを、それが所定のステーションで到着時刻を改善せずに、トリップｔ３に乗り換えすることがより効率的であるため、排除する。しかし、（ユーザが地下鉄を利用しようとしない）トリップｔ３が排除される構成においては、トリップｔ２が追加的な停止点に到着するために採択されなければならない。
【００２０】
ＴＢアルゴリズムで信頼性が備わるようにモード選択を管理するためには、前処理が選択されたモードの可能な各組み合わせに対して実行されなければならない。このためには、前処理の度重なる（ｍｕｌｔｉｐｌｅ）繰り返しと、このようなクエリを扱うために実行する複数のサーバが必要となり、組み合わせの数はモードの数にともなって指数的に増加する。
【００２１】
これにより、ユーザの所期の交通モードを考慮するマルチモーダル交通ネットワークにおいて旅程を計算するための方法が求められている。
【図面の簡単な説明】
【００２２】
添付の図面は、多様な実施形態を説明することを目的としており、限定的に理解されてならない。
【図１】後述する方法を実行するアーキテクチャの例を示した図である。
【図２】トリップおよび乗り換えの構成例を示した図である。
【図３】トリップおよび乗り換えの構成例を示した図である。
【図４】所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理する方法を示した図である。
【図５】図４で実行されたように処理された、実現可能な乗り換えの前処理されたセットに基づいて出発地から到着地への少なくとも１つの旅程を計算する方法を示した図である。
【図６】交通のユーザ希望（ｄｅｓｉｒｅｄ）モードを有するマルチモーダル交通において、乗り換えのセットをプルーニングする方法を示した図である。
【発明を実施するための形態】
【００２３】
図４、図５、および図６に示すように、方法４０３は、所定のステーションのマルチモーダル交通ネットワーク内において各トリップに対して実現可能な乗り換えのセット（すなわち、実現可能な乗り換え）を前処理し、方法４１０は、前処理された実現可能な乗り換えのセットに基づき、出発地から到着地までの少なくとも１つの旅程を計算する（これに関する詳細は、図４で説明する）。より具体的に、前処理は、すべての実現可能な乗り換えのセットをサブセットとして減らし、旅程は、このような実現可能な乗り換えのサブセットの乗り換えだけを利用する。
【００２４】
乗り換えのセットは正しいという点に留意する（すなわち、任意の入力、およびこのような入力に対応する任意の最適値に対し、乗り換えのセットは、このような値を有する最適ソリューションの部分となるすべての乗り換えを含む）。
【００２５】
マルチモーダル交通ネットワークは、好ましくは、公共交通モードのネットワーク、特に、「スケジューリングされた（ｓｃｈｅｄｕｌｅｄ）」交通モードのネットワークであり、すなわち、（ステーションの所定のシーケンスのような）路線としてそのタイムテーブルは公開されている。スケジューリングされた公共交通モードの例としては、バス、地下鉄、路面電車（ｔｒａｍｗａｙ）、汽車、ウォーターシャトル、カープーリング（ｃａｒｐｏｏｌｉｎｇ）などを含む。
【００２６】
代案的な実施形態において、マルチモーダル交通ネットワークは、航空機、バンシャトル、船舶、フェリー（ｆｅｒｒｙ）など、これらの単独および／または公共交通モードのネットワークと結合するものを含む、スケジューリングされたプライベート交通モードのネットワークが含まれてもよい。
【００２７】
マルチモーダル交通ネットワークは、貸し切りバス（ｏｎ−ｄｅｍａｎｄ  ｂｕｓ）、ライドヘイリング（ｒｉｄｅ−ｈａｉｌｉｎｇ）、または共有自転車（ユーザが制約なく手軽にステーションから他のステーションに行くために自転車に乗ることができる）の単独または公共およびプライベート交通モードに結合されるもののような、非スケジューリングされた交通モードがさらに含まれてもよいが、以下で提供する説明の目的のために、スケジューリングされた公共交通モードだけがマルチモーダル交通ネットワークに関与するものとする。複数の交通モード、すなわち、これらのうちの少なくとも２つが関与するという点に留意する。
【００２８】
ステーションおよび／または「停止点」とは、与えられた位置の施設を意味し、マルチモーダル交通ネットワークの交通モードのうちの少なくとも１つが乗客を搭乗または下車させるために定期的に停止する、例えば、バス停、地下鉄駅、汽車駅、（例えば、バス停および汽車駅を含む）などの交通ハブ（ｔｒａｎｓｐｏｒｔ  ｈｕｂ）を意味する。
【００２９】
マルチモーダル交通ネットワーク内の「変位（ｄｉｓｐｌａｃｅｍｅｎｔ）」は、マルチモーダル交通ネットワークのステーションからステーションの間で交通モードを変更することと関連するか、関連しない他のステーションへの各トリップのシーケンスとして定義される。
【００３０】
「トリップ」は、交通モードのうちのバスのように、すなわち、路線に沿った単一の１つを使用する変位を意味する。一般的に、あらゆる変位は、２つの連続的なトリップの間における、（すなわち、トリップおよび乗り換えの変更（ａｌｔｅｒｎａｔｉｏｎ）として見なされる）乗り換えを含む。
【００３１】
乗り換えとは、交通モードから他の交通モードへの連結を意味し、例えば、トリップが終了するステーションと新たなトリップが始まるステーションとの間の変位を意味する。
【数２】
2020193974.tif 000004
（以下を参照）として表現される乗り換えは、ステーションｐｔｉでトリップｔを出発してステーションｐｕｊでトリップｕに乗ることができればトリップｔに対して「実現可能な」ものとなり、すなわち、乗り換え存続期間（ｄｕｒａｔｉｏｎ）は、トリップｔおよびｕのスケジュールと両立される。
【００３２】
以下の説明において、乗り換えの前および後のトリップｔおよびｕそれぞれは、これらを区分するために「オリジン（ｏｒｉｇｉｎ）」トリップおよび「ターゲット」トリップと呼ぶ。言い換えれば、ユーザは、オリジントリップｔからターゲットトリップｕに乗り換える。ターゲットトリップは、追加の乗り換えのためのオリジントリップにもなり得るという点に留意する。
【００３３】
このような乗り換えは「第１交通モード」によって実行される。これは、ネットワークの公共交通モードではなく、一般的には、徒歩、キックボード、および／またはスケートのようなポータブルまたはウェアラブル補助機器（ａｓｓｉｓｔｓ）も使用可能なものに含まれる。
【００３４】
第１交通モードは、非スケジューリングされてステーションがない（ｓｔａｔｉｏｎ−ｆｒｅｅ）モードであり、ユーザが制限なく自由に利用可能である。通常、第１交通モードは、普遍的なもの（ｕｎｉｖｅｒｓａｌ）であり、いかなる車両も要求しない（最悪の場合は、スケートのような「軽くて」運送可能なものを要求）。乗り換えは、必ずしも変異と関連するものでないということに留意する（ステーションは、例えば、２つの地下鉄路線のように、同じ交通モードの２つのトリップに対して共通であってよい）。
【００３５】
以下の説明の目的のために、第１交通モードは徒歩が仮定されてよく、すなわち、ネットワーク内の変位は、ステーション間の乗り換え（ｔｒａｎｓｉｔ）および徒歩に制限される。
【００３６】
すべての実現可能な乗り換えのセットＴを考慮し、前処理の目的は、上述したようにサブセットＴ’を出力するために、このようなセットＴをプルーニングすることによって、クエリに対して最適な結果を承認しながら（ｇｒａｎｔｉｎｇ）、これに基づいて旅程を計算するときに探索時間を著しく減らすことができる。トリップのセットは変更されないため、前処理は、頂点（トリップ）間のアーク（乗り換え）を排除するためのグラフの簡略化に対応するという点に留意する。
【００３７】
旅程がネットワーク内で計算されなければならないとき、旅程は、順に、出発地から所定のステーションのマルチモーダル交通ネットワークの最初のステーションまでの開始部分と、（マルチモーダル交通ネットワークの交通モードを使用するトリップの変更（ａｌｔｅｒｎａｔｉｎｇ）および交通の第１モードを使用する乗り換えの変更として定義される）マルチモーダル交通ネットワークのメイン部分と、マルチモーダル交通ネットワークの最終ステーションから到着地までの終了部分とを含む。
【００３８】
出発地および到着地は地理的位置であり、通常は、住所、関心地点（ｐｏｉｎｔ  ｏｆ  ｉｎｔｅｒｅｓｔ）、座標などによって定義されるマップ上の位置である。
【００３９】
旅程の開始部分および終了部分は、ユーザをネットワークのステーションと「連結」することを許容する。これらは、特に、出発地／到着地が孤立したステーションの場合に「ヌル（ｎｕｌｌ）」となってよく、このようなステーションは、最初／最終のステーションとして使用されてよい。しかし、このような場合にも、ユーザは、他のステーションに徒歩で移動する可能性もある。
【００４０】
メイン部分は、本旅程のためのマルチモーダル交通ネットワークへの進入地点である最初ステーションからの最初トリップとして始まり（用語「ソース停止点」が発見される）、マルチモーダル交通ネットワークの出口地点であるステーションまでのターゲット路線上最終トリップで終了する（用語「ターゲット停止点」が発見される）。
【００４１】
旅程は、好ましくは（より早い（ｅａｒｌｉｅｒ））到着時刻、（最も低い）旅程のデュレーション、（最も遅い）出発時刻、（最も短い）旅程の長さ、（最も少ない）乗り換えの回数、（最も低い）費用などのような、少なくとも１つの基準による最適なもの（または、このような最適なものなどに少なくとも近い、すなわち、最適値の近似値）となる。
【００４２】
以下で詳しく説明するトリップ基盤の公共交通乗り換えルーティングアルゴリズム（Ｔｒｉｐ−Ｂａｓｅｄ  Ｐｕｂｌｉｃ  Ｔｒａｎｓｉｔ  Ｒｏｕｔｉｎｇ  Ａｌｇｏｒｉｔｈｍ）の例においては、到着時刻および乗り換え数の２つの基準がともに考慮される。
【００４３】
開始部分および終了部分は、第１交通モード（すなわち、徒歩）によって、または可能な代案的として、第２交通モード（第１交通モードよりも長い範囲を有する任意の非スケジューリングされた、ステーションのないモード（マルチモーダル交通ネットワークのモードのうちの１つではない）であってよい）によって実行される。
【００４４】
第２交通モードは、通常はタクシーであるが、同等の交通モード、特に、カーライド（通常は、友達によるリフト、パークアンドライド（ｐａｒｋ−ａｎｄ−ｒｉｄｅ）、ライドヘイリングなど）のような、プライベート車への乗車、バイク乗車、および／またはヘリコプタなどであってよい。
【００４５】
第２交通モードの例は、２０１９年１２月２日付で出願された「出発地から到着地への少なくとも１つの旅程を計算する方法」という名称の特許文献１で開示されている。特許文献１の内容のすべては、ここで参照として統合される。
【００４６】
第１および／または第２交通モードは、地図作成法（ｃａｒｔｏｇｒａｐｈｙ）、すなわち、道（特に、道路）、接近などの存在だけによって制限されるものと理解されなければならず、ステーションの所定のリストに依存するマルチモーダル交通ネットワークのモードとは対照的に、どこかの位置に到着することのできるものと見なされる。
【００４７】
要約すると、考えられる所定の旅程は、ユーザを出発地から最初のステーションに移動させる開始部分から始まり、その次に、メイン部分で乗り換えのために多様な公共交通モード（マルチモーダル交通ネットワーク）および徒歩（第１交通モード）をユーザが利用し、最終ステーションから到着地までユーザを移動させる終了部分で旅程を終えるために、最終ステーションまでネットワーク（マルチモーダル交通ネットワーク）で移動する（ｔｒａｖｅｌ）。
【００４８】
上述した方法は、サーバ１、モバイルコンピュータ２ａ、またはモバイルフォン２ｂによって実行され、図１で示すようなアーキテクチャ内で実現される。
【００４９】
このようなデバイスのそれぞれは、データ交換のためのインターネットのような拡張されたネットワーク２０に接続する。各デバイスは、プロセッサのようなデータ処理手段１１、２１ａおよび２１ｂ、およびコンピュータメモリ、例えば、ハードディスクのようなストレージ手段１２、２２ａ、および２２ｂを含む。
【００５０】
より具体的に、サーバ１は、乗り換えのセットの前処理を実行し、ユーザは、一般的にスマートフォンのような携帯電話（モバイルフォン）２ｂを、旅程に対する要求（出発地、到着地、および出発時刻）を入力するために所有する。旅程に対する要求は、携帯電話２ｂが直接処理してもよいし、処理のためにサーバ１に送信されてもよい。本方法は、特定の実現に制限されてはならない。
【００５１】
上述したように、プルーニングは、モードが特定の組み合わせに制限される場合、実際に有用となる乗り換えが排除される場合がある。結果的に、本前処理方法は、プルーニング段階を実行し、乗り換えが、単に関連するモードが異なれば、他の乗り換えが前記乗り換えよりも優れた結果を示すという理由だけでプルーニングされないようにする。
【００５２】
トリップｔのステーションシーケンスは
【数３】
2020193974.tif 000005
で表現され、したがって、オリジントリップｔ上のステーションｐｔｉ（ｉｔｈステーション）からターゲットトリップｕ上の到着可能なステーションｐｕｊ（ｊｔｈステーション）への乗り換えは
【数４】
2020193974.tif 000006
で表現されてよい。説明したように、乗り換え
【数５】
2020193974.tif 000007
は、ステーションｐｔｉからトリップｔを出発してステーションｐｕｊからトリップｕに乗ることができれば実現可能となる。
【数６】
2020193974.tif 000008
が実現可能であれば、ｔから同じ路線の以後のいかなるトリップへの乗り換えも可能となる。
【００５３】
図４は、一般的に、段階４０２で受信された実現可能な乗り換えのシートの前処理方法４０３を記述し、前記方法４０３は、マルチモーダル交通ネットワークの２つのステーション間で、マルチモーダル交通ネットワーク内のオリジントリップｔの各ステーションｐｔｉに対し、最初に、段階４０４で、オリジントリップｔの各ステーションｐｔｉに対し、このようなステーションｐｔｉでマルチモーダル交通ネットワークのすべての交通モードと関連する最先の（ｅａｒｌｉｅｓｔ）到着時刻
【数７】
2020193974.tif 000009
および／または最先の変更時刻
【数８】
2020193974.tif 000010
の値を「初期化」することと、その次に、段階４０６で、ターゲットトリップｕ上の到着可能なステーションｐｕｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え（および、好ましくは各実現可能な乗り換え）に対し、到着可能なステーション後のターゲットトリップ上の各ステーション（すなわち、ｋ＞ｊを有するトリップｕ上のステーションｐｕｊ）で最先の到着時刻
【数９】
2020193974.tif 000011
および／または最先の変更時刻
【数１０】
2020193974.tif 000012
（ステーションｐの変更時刻
【数１１】
2020193974.tif 000013
は、一般的にこのようなステーションｐの最先の到着時刻
【数１２】
2020193974.tif 000014
に該当のステーションｐの２つのトリップ間の最小変更時間
【数１３】
2020193974.tif 000015
を加えたことに対応する）を（好ましくは、２つとも）計算することを含む。
【００５４】
前処理において、各オリジントリップに対して、以後の（ｌａｔｅｒ）乗り換えを採択することは、ソリューションで到着時刻および／または乗り換えの回数を改善することができないため、ターゲット路線の与えられたステーションで各路線のターゲットトリップにおける最先の（ｅａｒｌｉｅｓｔ）実現可能な乗り換えだけが考慮される。その次に、段階４０７で、すべての実現可能な乗り換えのセットは（以後の処理のために出力される前に）、現在のオリジントリップの以前に追加された乗り換えと比べ、乗り換えがネットワークの任意の停止点で到着時刻を改善するようにする場合にのみ、検索グラフで該当の乗り換えを維持することによって減少される。
【００５５】
本前処理方法４０３は、交通モードにしたがって最先の到着時刻
【数１４】
2020193974.tif 000016
および／または最先の変更時刻
【数１５】
2020193974.tif 000017
を有するように提案する。言い換えれば、可能な交通モードが存在することにより、それだけステーションで最先の到着／変更時刻の多くの値が存在するようになり、各値は交通モードに具体的に関連する。
【００５６】
好ましくは、マルチモーダル交通ネットワークの与えられた交通モードに関連する最先の到着／変更時刻の各値は、交通モードおよび／またはオリジントリップｔの交通モードだけを使用するときに最先の到着／変更時刻に対応する。実際に、トリップｔおよびｕの交通モードは、このような乗り換えが起こるように許容されなければならない。このような方法は、最先の到着／変更時刻が使用された交通モードと独立的に定義された、他の方法とは対照となる。
【００５７】
例えば、Ｍが可能な交通モードのセット（およびｍｔがトリップｔと関連する交通モード）であれば、
【数１６】
2020193974.tif 000018
でモードｍおよび／またはオリジントリップｔのモードｍｔだけを使用するステーションｐの最先の到着／変更時刻
【数１７】
2020193974.tif 000019
が計算される。現実的に、ターゲットトリップｕを考慮するとき、計算される最先の到着／変更時刻の値は、ターゲットトリップｕによって使用された交通モードと関連したものとなる。
【００５８】
したがって、段階４０７で、乗り換えは、それがオリジントリップｔに対して計算された最先の到着／変更時刻の値のうちのいずれかに対しても、改善を提供しないときだけに排除されるようになる。すなわち、該当の乗り換えは、各交通モードに対し、このような交通モードと関連する到着時刻および／または変更時刻が前記交通によっては改善しないと判定された場合（または、最初および目的地のトリップの交通モードが同じ場合において、いずれかのモードに対して改善が存在しない場合）にだけ、実現可能な乗り換えのセットから排除される。言い換えれば、最先の到着／変更時刻が改善されたターゲットトリップｕのステーション（または、ターゲットトリップｕのこのようなステーションと隣り合うステーション）が存在すれば、乗り換えは維持される。
【００５９】
これにより、他のモードに対してではないが、あるモードに対しては、最先の到着時刻および／または最先の変更時刻を改善する乗り換えがプルーニングされないようになる。
【００６０】
各モードに対してステーションで到着時刻および変更時刻の値をチェックすることは、最適ソリューションに属することができるすべての乗り換えが前処理によって維持されたことを保障する。
【００６１】
ステーションで到着／変更時刻の改善に基づいて前処理のプルーニング部分だけが変更されることに留意し、したがって、周知の前処理の原理はそのまま維持可能となる。
【００６２】
実際に、図６に示したアルゴリズム５０２が、与えられた実現可能な乗り換えのセットＴおよび可能な乗り換えモードのセットＭをプルーニングするために使用されてよい。
【００６３】
アルゴリズム５０２で、プルーニングのアイディアは、好ましくは、各オリジントリップｔに対し、スケジュールの最後のステーションからプルーニングを開始し（ｉ値は
【数１８】
2020193974.tif 000020
から繰り返し減少する）、スケジュールの到着時刻（スケジュールによって定義されたように、オリジントリップｔのｉｔｈステーションｐｔｉの到着時刻は
【数１９】
2020193974.tif 000021
と表現される）から最先の到着／変更時刻を初期化し、乗り換えによって該当のステーションからすべての可能な隣り合うステーションｑに到着するようにすることである。
【００６４】
「隣り合う（ｎｅｉｇｈｂｏｒｉｎｇ）」とは、それ自体がステーションｐｔｉから追加的な実現可能な乗り換えによって到着可能になること、すなわち、（例えば、歩行者の徒歩経路によって）第１交通モードを使用して到着可能になることを意味する。
【数２０】
2020193974.tif 000022
は（第１交通モードの関数であって、通常は徒歩デュレーションである）ステーションｐおよびステーションｑ間の乗り換えデュレーションを表現するために使用される。結果的に、これは、これらのステーションに対して最先の到着および変更時間を初期化する。
【００６５】
その次に、各ターゲットトリップｕは、乗り換え
【数２１】
2020193974.tif 000023
が実現可能になるように（好ましくは、ｕが、
【数２２】
2020193974.tif 000024
が実現可能になる該当の路線の最先の（ｅａｒｌｉｅｓｔ）トリップｖとなるように）、順にターゲットトリップｕおよびこれらの隣り合うステーションｕのよりも多くのステーションｐｕｋに到着するようにスキャンされ、（再び、隣り合うステーションｑは、ターゲットトリップｕのステーションｐｕｋからの追加的な実現可能な乗り換えによって到着可能となるステーションとなる）、または／追加的に既に到着されたステーションの最先の到着／変更時間をアップデートするようにスキャンされる。交通モードが変更されると、到着可能なステーション（ｐｕｋおよび／またはｑ）に対し、ターゲットトリップｕの運送ボードと関連する値
【数２３】
2020193974.tif 000025
だけがアップデートされる。アップデートは、与えられた交通モードに対して最先の到着および／または変更時刻の現在の値を、乗り換えを使用することがオリジントリップｔおよび以前に維持された乗り換えに比べて改善に繋がるときに計算された値に代替されることを意味する。比較は、改善（および、これによるアップデート）が発生するか否かを知るためになされてよい。ブーリアンキープ（Ｂｏｏｌｅａｎ  ｋｅｅｐ）が、少なくとも１つの改善が発生したかをモニタリングするために使用されてよい。
【００６６】
ｍｔ＝ｍｕである、すなわち、乗り換え
【数２４】
2020193974.tif 000026
が交通モードを変更しない（言わば、トリップｔおよびｕが同じモードである）場合、オリジントリップｔのモードｍｔがｔからの乗り換えを考慮するときに必ず許容されるため、
【数２５】
2020193974.tif 000027
に対してもアップデートされてよい。
【００６７】
図４および図５で示した第２側面によると、方法４１０は、段階４０９で受信された最先の到着時刻クエリに対する出発地、到着地、および出発時刻から少なくとも１つの旅程を計算する。
【００６８】
上述したように、各旅程は、マルチモーダル交通ネットワーク内の可能なトリップのセットからのトリップ、およびマルチモーダル交通ネットワーク内の実現可能な乗り換えのセットからの乗り換えのシーケンスとして定義された、所定のマルチモーダル交通ネットワーク内のメイン部分を含む。
【００６９】
特別なことは、旅程がマルチモーダル交通ネットワークの可能な交通モードのうち、例えば、ユーザインタフェース２３ｂを使用して図１のクライアントデバイス２ｂ上でユーザによって選択された交通モードの組み合わせに制限されるという点である。
【００７０】
いずれかの交通モードの組み合わせを許容するために、サーバ１のデータプロセッサ１１によって実現された、段階４１２は、第１側面により、マルチモーダル交通ネットワーク内の実現可能な乗り換えのセットを前処理し、選択された交通モードのいずれかの組み合わせと両立される、実現可能な乗り換えのサブセットを取得する。
【００７１】
前処理の変更だけで、特に、ＴＢアルゴリズムである、後続するルーティングアルゴリズムが、それ以降に適用可能となることに留意する。唯一の差は、クエリ時点において、許容可能なトリップおよびトリップ間の乗り換え（すなわち、段階４０８で受信された、選択された交通モードと両立可能なもの）だけが要求に対して考慮されなければならないという点にある。実際に、本前処理は、乗り換えのさらにスマートなプルーニングを簡単に提供し、したがって、ルーティングアルゴリズムが、信頼性のある方式によって交通モードのあらゆる組み合わせを処理することができるようになる。より具体的に、前処理は、認定された（ａｕｔｈｏｒｉｚｅｄ）交通モードのいずれかのセットを有する任意のクエリに対して有用となり、乗り換えがプルーニングされず、したがって、一部の最適ソリューションが失われないようにすることを保障する。
【００７２】
上述したように、ＴＢアルゴリズム（または、いずれかの他の適したルーティングアルゴリズム）は、目的地に到着することのできる路線のセットＬと、最初の出発地から到着することのできる最先のトリップのセットが計算される初期化段階によって始まる。言い換えれば、サーバ１のデータプロセッサ１１またはクライアントデバイス２ｂのデータプロセッサ２１ｂによって実行された、段階４１４で、マルチモーダル交通ネットワーク内において、可能な最初トリップのセットは、出発地の関数として決定され、可能な最終トリップのセットは、到着地の関数として決定される。（最先の到着時刻クエリに対する）出発時刻および／または（プロファイルであるクエリに対する）出発時刻範囲は、最終的なトリップを決定するために（最も遅い出発時刻クエリに対し）、オリジントリップおよび／または到着時刻を決定するときにも考慮されるようにする。
【００７３】
上述したように、前記方法は、最も遅い出発時刻クエリを構成するＴＢアルゴリズムの拡張の脈絡においても考慮されてよく、所期の到着時刻が開始時刻の代りに与えられ、開始時刻以後および所期の到着時刻以前の最先の可能な到着時刻がともにタイブレーク（ｂｒｅａｋ  ｔｉｅ）のために使用される２次的な基準としてともに与えられる。
【００７４】
初期化段階は、任意の周知の方式によって実行されてよい。
【００７５】
段階４１４で、ＴＢのような周知の適したルーティング最適化アルゴリズムは、最初トリップおよび最終のトリップのセットに基づいて実行されてよい。
【００７６】
（マルチモーダル交通ネットワークですべての可能な交通モードのサブセットである）選択された交通モード４０８を使用して可能なトリップのセットからのトリップとトリップ４１２間で実現可能な乗り換えのサブセットからの乗り換えだけが、段階４１４で考慮されてよい。交通モードの組み合わせの選択は、この段階で実行されることに留意する。
【００７７】
好ましくは、いくつかの要求は、潜在的には選択された交通モードの異なる組み合わせに対応する、複数の最適な旅程を選択するために実行されてよい。
【００７８】
選択された旅程は、好ましくは、上述したように、到着時間である基準、および好ましくは、乗り換えの回数のような追加の基準に対する最適なものとなる。
【００７９】
最も遅い出発時刻クエリに対し、最先の到着時間クエリに対する乗り換えの同じセットが、探索において使用されてよい。
【００８０】
例えば、ＴＢアルゴリズムにおいて、各最先のトリップは一回だけ考慮されてよく、該当のトリップのステーションシーケンス内でより低いインデックスのステーションで始まる。それぞれの繰り返しに対し、追加のトリップが最終的なトリップへの試みおよび到達のために各ソリューション（ｓｏｌｕｔｉｏｎ）として採択される。
【００８１】
代案的な実施形態において、実現可能な乗り換えの前処理されたセット（例えば、乗り換えバス路線に対する）は、タイムテーブルを構築および評価するために使用されてよい。より好ましくは、実現可能な乗り換えのセットを使用して構築されたこのようなタイムテーブルは、トリップ間で長い待機時間を回避するために組み合わされてよく、遅延の場合における頑強性（ｒｏｂｕｓｔｎｅｓｓ）を評価することができ、したがって、乗り換えの失敗（ｍｉｓｓｅｄ）を最小化することができる。
【００８２】
また他の実施形態において、実現可能な乗り換えの前処理されたセットは、運送ネットワークリソースを管理するために（例えば、路線の一部の車両が遅延する場合、路線のどの車両が待機すべきかの決定をサポートするために）使用されてよい。
【００８３】
マルチモーダル交通ネットワークの２つのステーション間のマルチモーダル交通ネットワーク内の各トリップｔ（以下、オリジン（ｏｒｉｇｉｎ）トリップとする）に対し、所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理する方法において、（ａ）前記オリジントリップｔの各ステーションｐｔｉに対し、該当のステーションｐｔｉで前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の（ｅａｒｌｉｅｓｔ）到着時刻
【数２６】
2020193974.tif 000028
または最先の変更時刻
【数２７】
2020193974.tif 000029
の値を計算し、（ｂ）前記オリジントリップｔ上のステーションｐｔｉからターゲットトリップｕ上の到着可能なステーションｐｕｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え
【数２８】
2020193974.tif 000030
に対し、前記到着可能なステーションｐｕｊ以降に前記ターゲットトリップｕの各ステーションｐｕｋ＞ｊで前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻
【数２９】
2020193974.tif 000031
または最先の変更時刻
【数３０】
2020193974.tif 000032
の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数３１】
2020193974.tif 000033
または最先の変更時刻
【数３２】
2020193974.tif 000034
の値を計算し、（ｃ）最先の到着時刻
【数３３】
2020193974.tif 000035
または最先の変更時刻
【数３４】
2020193974.tif 000036
の各計算された値が前記乗り換え
【数３５】
2020193974.tif 000037
によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え
【数３６】
2020193974.tif 000038
を排除する。
【００８４】
上述した方法は、スケジュールの関数（ｆｕｎｃｔｉｏｎ）として、最先の到着時刻または最先の変更時刻をさらに初期化する。
【００８５】
前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻または最先の変更時刻の値は、前記交通モードｍｕまたは前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔだけを使用するときの最先の到着時刻または最先の変更時刻に対応する。
【００８６】
前記方法は、前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の（ｅａｒｌｉｅｓｔ）乗り換えである実現可能な乗り換えのセットの各乗り換えに対してさらに実行される。
【００８７】
前記方法は、前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回する（ｔｒａｖｅｌｌｉｎｇ）とき、前記オリジントリップの各連続的な（ｓｕｃｃｅｓｓｉｖｅ）ステーションからの乗り換えを繰り返しさらに考慮する。
【００８８】
最先の到着時刻および／または最先の変更時刻は、前記到着可能なステーション以降に、前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣り合うステーションでも計算される。
【００８９】
前記方法は、可能な最初トリップのセットに属する最初トリップから可能な最終トリップのセットに属する最終トリップのメイン部分を有する旅程のうち、選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズム（ｒｏｕｔｉｎｇ  ｏｐｔｉｍｉｚａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）をさらに実行する。
【００９０】
前記ルーティング最適化アルゴリズムは、パレート効率性（Ｐａｒｅｔｏ  ｆｒｏｎｔ）を計算してよい。前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加のトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素（ｅｌｅｍｅｎｔ）あたり少なくとも１つの最適ソリューションをさらに計算してよい。
【００９１】
出発地から到着地までの少なくとも１つの旅程を計算する方法において、各旅程は、所定のステーションのマルチモーダル交通ネットワーク内のメイン部分（前記マルチモーダル交通ネットワーク内の可能なトリップのセットからのトリップ、および前記マルチモーダル交通ネットワーク内の実現可能な乗り換えのセットからの乗り換えのシーケンスとして定義される）を含み、前記方法は、（ａ）実現可能な乗り換えのサブセットを取得するために、前記マルチモーダル交通ネットワーク内の前記実現可能な乗り換えのセットを前処理し、（ｂ）前記マルチモーダル交通ネットワーク内で、前記出発地の関数として可能な最初トリップのセット、および前記到着地の関数として可能な最終トリップのセットを決定し、（ｃ）前記可能な最初トリップのセットに属する最初トリップから前記可能な最終トリップのセットに属する最終トリップのメイン部分を有する旅程のうち、前記選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズム（ｒｏｕｔｉｎｇ  ｏｐｔｉｍｉｚａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）を実行する。
【００９２】
前記ルーティング最適化アルゴリズムは、パレート効率性（Ｐａｒｅｔｏ  ｆｒｏｎｔ）を計算する。前記ルーティング最適化アルゴリズムは、予め計算された乗り換えセットに基づいて各繰り返しから選択されたモードのセットの１つの追加的なトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、前記パレート効率性内の要素（ｅｌｅｍｅｎｔ）あたり少なくとも１つの最適ソリューションをさらに計算してよい。
【００９３】
出発地から到着地までの少なくとも１つの旅程を計算するために、所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理するコンピュータプログラム製品において、前記コンピュータプログラム製品は、プロセスを実行するようにコンピュータ上で実行され、前記プロセスは、（ａ）オリジントリップｔの各ステーションｐｔｉに対し、該当のステーションｐｔｉで前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の（ｅａｒｌｉｅｓｔ）到着時刻
【数３７】
2020193974.tif 000039
または最先の変更時刻
【数３８】
2020193974.tif 000040
の値を計算し、（ｂ）前記オリジントリップｔ上のステーションｐｔｉからターゲットトリップｕ上の到着可能なステーションｐｕｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え
【数３９】
2020193974.tif 000041
に対し、前記到着可能なステーションｐｕｊ以降に前記ターゲットトリップｕの各ステーションｐｕｋ＞ｊで、前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻
【数４０】
2020193974.tif 000042
または最先の変更時刻
【数４１】
2020193974.tif 000043
の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻
【数４２】
2020193974.tif 000044
または最先の変更時刻
【数４３】
2020193974.tif 000045
の値を計算し、（ｃ）最先の到着時刻
【数４４】
2020193974.tif 000046
または最先の変更時刻
【数４５】
2020193974.tif 000047
の各計算された値が前記乗り換え
【数４６】
2020193974.tif 000048
によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え
【数４７】
2020193974.tif 000049
を排除し、（ｄ）前記マルチモーダル交通ネットワークの少なくとも１つの旅程を計算するために前記実現可能な乗り換えのセットを出力する。
【００９４】
前記プロセスは、スケジュールの関数（ｆｕｎｃｔｉｏｎ）として、最先の到着時刻または最先の変更時刻をさらに初期化する。
【００９５】
前記マルチモーダル交通ネットワークの交通モードｍｕと具体的に関連する最先の到着時刻または最先の変更時刻の値は、前記交通モードｍｕまたは前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍｔだけを使用するときに、最先の到着時刻または最先の変更時刻に対応する。
【００９６】
前記プロセスは、前記オリジントリップ上のステーションから任意のターゲットトリップ上の任意の到着可能なステーションへの最先の（ｅａｒｌｉｅｓｔ）乗り換えである実現可能な乗り換えのセットの各乗り換えに対し、（ｂ）および（ｃ）をさらに繰り返し実行する。
【００９７】
前記プロセスは、前記オリジントリップ上のステーションを最終ステーションから最初ステーションに巡回する（ｔｒａｖｅｌｌｉｎｇ）とき、前記オリジントリップの各連続的な（ｓｕｃｃｅｓｓｉｖｅ）ステーションからの乗り換えをさらに繰り返し考慮する。
【００９８】
前記プロセスは、最先の到着時刻および／または最先の変更時刻を前記到着可能なステーション以降に前記オリジントリップおよび前記ターゲットトリップ上の各ステーションの各隣り合うステーションでさらに計算する。
【００９９】
前記コンピュータプログラム製品は、コンピュータ読み取り可能な媒体である。
【０１００】
出発地から到着地までの少なくとも１つの旅程を計算するために、所定のステーションのマルチモーダル交通ネットワーク内で実現可能な乗り換えのセットを前処理するコンピュータプログラム製品であって、前記コンピュータプログラム製品は、プロセスを実行するようにコンピュータ上で実行され、前記プロセスは、（ａ）実現可能な乗り換えのサブセットを取得するために、前記マルチモーダル交通ネットワーク内の前記実現可能な乗り換えのセットを前処理し、（ｂ）前記マルチモーダル交通ネットワーク内で、前記出発地の関数として可能な最初トリップのセットおよび前記到着地の関数として可能な最終トリップのセットを決定し、（ｃ）前記可能な最初トリップのセットに属する最初トリップから前記可能な最終トリップのセットに属する最終トリップのメイン部分を有する旅程のうち、前記選択された交通モードを使用する可能なトリップのセットからのトリップだけを考慮し、考慮されたトリップ間の実現可能な乗り換えのサブセットからの乗り換えだけを考慮するとき、最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数による少なくとも１つの最適旅程を構築するためにルーティング最適化アルゴリズム（ｒｏｕｔｉｎｇ  ｏｐｔｉｍｉｚａｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）を実行する。
【０１０１】
前記ルーティング最適化アルゴリズムは、パレートセットと、予め計算された乗り換えセットに基づき、各繰り返しから選択されたモードのセットの１つの追加のトリップを採択することにより、マルチモーダルネットワーク内で最先の到着時刻および乗り換えの回数、または最も遅い出発時刻および乗り換えの回数に対し、パレート効率性内の要素（ｅｌｅｍｅｎｔ）あたり少なくとも１つの最適ソリューションを計算する。
【０１０２】
前記コンピュータプログラム製品は、コンピュータ読み取り可能な媒体である。
【０１０３】
上述のように開示された実施形態とは異なる特徴および機能、および／またはこれらの代案の変形は、好ましくは、多くの他のシステムおよび／またはアプリケーションに結合されてもよいという点が理解されるであろう。また、現在の予想されない、および／または予測されない代案、変更、変形、および／またはその改善は、当該技術分野において通常の知識を有する者によって後続的になされてよく、これは上述した説明と添付の特許請求の範囲によって包括されるように意図される。
【先行技術文献】
【特許文献】
【０１０４】
【特許文献１】米国特許出願１６／７００，０９６号
【非特許文献】
【０１０５】
【非特許文献１】Ｓａｃｈａ  Ｗｉｔｔ．Ｔｒｉｐ−ｂａｓｅｄ  ｐｕｂｌｉｃ  ｔｒａｎｓｉｔ  ｒｏｕｔｉｎｇ．Ｉｎ  Ｎ．Ｂａｎｓａｌ  ａｎｄ  Ｉ．Ｆｉｎｏｃｃｈｉ，ｅｄｉｔｏｒｓ，ＥＳＡ  ２０１５，コンピュータサイエンス講義ノートボリューム  ９２９４，ベルリン，ハイデルベルク  ２０１５．スプリンガ
【非特許文献２】Ｖａｓｓｉｌｉｓｓａ  ＬｅｈｏｕｘおよびＤａｒｋｏ  Ｄｒａｋｕｌｉｃ，２０１９．Ｍｏｄｅ  Ｐｅｒｓｏｎａｌｉｚａｔｉｏｎ  ｉｎ  Ｔｒｉｐ−Ｂａｓｅｄ  Ｔｒａｎｓｉｔ  Ｒｏｕｔｉｎｇ．交通モデリング、最適化、およびシステムに対するアルゴリズム的接近方法に対する１９ｔｈシンポジウム（ＡＴＭＯＳ  ２０１９）．ＯＡＳＩｃｓ（Ｏｐｅｎ  Ａｃｃｅｓｓ  Ｓｅｒｉｅｓ  ｉｎ  Ｉｎｆｏｒｍａｔｉｃｓ），ボリューム７５，ページ１３：１〜１３：１５
【図１】
2020193974.tif 000072
【図２】
2020193974.tif 000073
【図３】
2020193974.tif 000074
【図４】
2020193974.tif 000075
【図５】
2020193974.tif 000076
【図６】
2020193974.tif 000077