(57)【要約】  本発明は、ルートプランニングのための方法であって、それぞれが多くの場所で停止することを含み、当該場所の順序は、当該場所間の距離に基づいて決定され、最初のルートの最初の場所間の距離は、前記最初のルートの決定と併せてメモリユニットに記憶され、そしてそれに続く２番目のルートは前記メモリユニットに記憶された前記２番目のルートの場所間の距離に基づいて、そして前記２番目のルートの追加された場所間の距離に基づいて、決定され、当該追加された距離は前記メモリの中で更新される、ルートプランニングのための方法を提供する。また、この方法を実行するのに適したルートプランニングのための装置を提供する。この発明は特に、郵便物の集配のルートプランニングを行うのに用いることができる。【選択図】  図１
2013543123.tif 000002
【特許請求の範囲】
【請求項１】
ルートプランニングのための方法であって、それぞれが多くの場所で停止することを含み、当該場所の順序は、当該場所間の距離に基づいて決定され、最初のルートの最初の場所間の距離は、前記最初のルートの決定と併せてメモリユニットに記憶され、そしてそれに続く２番目のルートは前記メモリユニットに記憶された前記２番目のルートの場所間の距離に基づいて、そして前記２番目のルートの追加された場所間の距離に基づいて、決定され、当該追加された距離は前記メモリの中で更新される、ルートプランニングのための方法。
【請求項２】
請求項１に記載の方法であって、前記２番目のルートの場所間の記憶された距離は、前記メモリの中で利用可能な場合、前記２番目のルートを決定するのに用いられる、方法。
【請求項３】
請求項１又は請求項２に記載の方法であって、前記２番目のルートの決定と併せて、当該２番目のルートの追加された場所が、当該追加された場所に関連付けられる距離が前記メモリの中に含まれていないときに決定され、これらの追加された場所に関連する距離が決定され前記メモリに記憶される、方法。
【請求項４】
請求項１から請求項３までのいずれか一項に記載の方法であって、前記追加された場所間の距離及び／又は前記追加された場所と前記メモリに既に含まれている場所との間の距離が決定され前記メモリの中で更新される、方法。
【請求項５】
請求項１から請求項４までのいずれか一項に記載の方法であって、前記距離は時間に関連した距離である、方法。
【請求項６】
請求項１から請求項５までのいずれか一項に記載の方法であって、前記場所間の距離は、前記場所間の決定されたルートに応じて、決定される、方法。
【請求項７】
請求項１から請求項６までのいずれか一項に記載の方法であって、前記メモリに記憶された前記距離は、交通情報に応じて、決定され及び／又は更新される、方法。
【請求項８】
請求項１から請求項７までのいずれか一項に記載の方法であって、前記距離は、前記ルートが通行されているときに獲得された測定値に基づいて決定され、そしてその後前記メモリの中で更新される、方法。
【請求項９】
請求項１から請求項８までのいずれか一項に記載の方法であって、少なくとも２つの場所について、当該場所間の複数の距離が前記メモリに記憶され、これらの距離は異なる期間において有効である、方法。
【請求項１０】
請求項１から請求項９までのいずれか一項に記載の方法であって、少なくとも２つの場所について、当該場所間の複数の距離が前記メモリに記憶され、これらの距離は異なる輸送手段に適用される、方法。
【請求項１１】
請求項９又は請求項１０に記載の方法であって、前記最初の及び／又は前記２番目のルートは前記期間に適用される前記距離に基づいて決定され、前記場所の１つは到達され及び／又は用いられる輸送手段に適用される、方法。
【請求項１２】
請求項１から請求項１１までのいずれか一項に記載の方法であって、郵便物を配達し及び／又は集荷するための前記ルートがプランニングされ、前記場所は郵便物が配達され及び／又は集荷される住所である、方法。
【請求項１３】
請求項１から請求項１２までのいずれか一項に記載の方法をデータプロセッシングシステムにおいて実行するためのコマンドを含むソフトウェアコードを備えるコンピュータプログラム。
【請求項１４】
ルートプランニングのための装置であって、それぞれが多くの場所で停止することを含み、前記場所間の距離に基づいてルートにおける前記場所の順序を決定するように構成されメモリユニットに接続されるルートプランニングユニットを備え、
当該ルートプランニングユニットは、最初のルートの決定と併せて、当該最初のルートの最初の場所間の距離がメモリユニットに記憶されるように構成され、
そしてそれに続く２番目のルートは、前記メモリユニットに記憶された前記２番目のルートの場所間の距離に基づいて、そして追加された場所間の距離に基づいて、決定され、
前記ルートプランニングユニットは、前記追加された場所への前記距離を前記メモリユニットにおいて更新するように構成される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルートプランニングに関し、とりわけ郵便配達員のルートに関する。この関連において、本発明は、ルートプランニングのための方法及びシステムに関し、それぞれは多くの場所において停止することを含み、場所の順序は場所間の距離に基づいて決定される。
【背景技術】
【０００２】
ルートプランニングは、商品を配達し及び／又は多くの場所で停止しなければならない多くの部門において取り組まれ、それには、特定の仕事を行わなければならない場所にサービスが提供される最適な順序を決定することが含まれる。ルートプランニングが非常に重要となる部門の例としては、荷物や小包又はその他の郵便物の配達及び集荷があり、そのために配達員は一日に一回又はそれ以上の住所の変更を含むルートに従う。
【０００３】
ルートプランニングは特に、サービスが提供されるべき住所を考慮して実行される。ルートプランニングの入力変数は特に場所間の距離である。場所間の距離は、例えば距離マトリックスにより示され、これは実際のルートがプランニングされる前に算出することができる。
【０００４】
独国特許発明第１０２００４０１９２３２号明細書には、ルートプランニングのための方法が示されており、その方法では特に、物品が配達及び／又は集荷されるべき住所の順所は、各ルートが地理的データに基づいてプランニングされるように決定される。
【０００５】
ルートプランニングを地理的データに基づいて実行することを可能とするためには、サービスが提供されるべき住所間の距離が決定されなければならない。しかしながら、荷物及び小包及び／又はその他の郵便物の配達のルートプランニングに際して典型的に考慮されるべき数多くの住所を考慮すると、これには膨大な計算作業が必要であり、非常に時間を費やすものであった。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】独国特許発明第１０２００４０１９２３２号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００７】
そこで、本発明の課題は、ルートプランニングに含まれる作業、とりわけ考慮されるべき場所間の距離を決定する作業を、軽減することである。
【課題を解決するための手段】
【０００８】
この課題は、請求項１の特徴を有する方法により、そして請求項１４の特徴を有する装置により、達成される。当該方法及び当該装置の実施形態は、従属請求項により提案される。
【０００９】
最初の態様によれば、本発明は、それぞれが多くの場所で停止することを含み、当該場所の順序が当該場所間の距離に基づいて決定される、ルートプランニングの方法を提案する。最初のルートの最初の場所間の距離は、前記最初のルートの決定と併せてメモリに記憶される。それに続く２番目のルートは、前記メモリに記憶された前記２番目のルートの場所間の距離に基づいて、そして前記２番目のルートの場所間の追加された距離に基づいて、決定される。ここで、前記追加された距離は前記メモリの中で更新される。
【００１０】
他の一つの態様によれば、それぞれが多くの場所で停止することを含むルートプランニングのために、装置が提案される。当該装置は、前記場所間の距離に基づいてルートにおける前記場所の順序を決定するように構成され、メモリユニットに接続されるルートプランニングユニットを備える。当該ルートプランニングユニットは、最初のルートの決定と併せて、当該最初のルートの最初の場所間の距離がメモリユニットに記憶されるように構成される。そしてそれに続く２番目のルートは、前記メモリユニットに記憶された前記２番目のルートの場所間の距離に基づいて、そして追加された場所間の距離に基づいて、決定される。また、前記ルートプランニングユニットは、前記距離を前記メモリユニットの追加された場所に更新するように構成される。
【００１１】
前記メモリ又は前記メモリユニットに記憶される前記２番目のルートの場所間の前記距離は、アドヴァンテージとして、前記最初のルートのプランニングと併せて既に決定されている。すなわち、これらは前記２番目のルートの場所であり、前記最初のルートの構成要素でもある。
【００１２】
距離が１つのルートと併せて決定された後、追加されたルートプランニングに備えて前記メモリ又は前記メモリユニットに記憶されたままとされるやり方は、ルートプランニングに要する仕事を軽減する。とりわけ、前記ルートに含まれる前記場所間の距離の決定に必要とされる仕事を軽減する。新しいルートをプランニングするためには、前記メモリに含まれていない場所と関係する距離を決定するので足りる。これらは以前のルートでは構成要素ではなかったからである。このようにして、前記メモリは継続的に住所で満たされているので、ルートプランニングのために新たに決定することが必要となる距離は次第に少なくなっていく。
【００１３】
さらに、前記メモリに含まれる前記場所は、今までに既に少なくとも一度はルートに含まれたことがあるものであるため、ルートプランニングに適している。一方、プランニングされたルート上でサービスが提供されない無関係の場所のための距離は、決定されなくてもよい。これは、当該方法及び当該装置により提供される、必要に応じて距離を決定することのもう１つの利点である。
【００１４】
距離を決定するために必要な仕事を可能な限り軽減するために、前記２番目のルートの前記場所の間の記録された距離は、前記メモリの中で利用可能であれば、前記２番目のルートを決定するのに用いられる。この実施形態においては、前記２番目のルートのルートプランニングを実行するために、前記メモリの中に既に記憶されていなかった距離のみが新たに決定される。
【００１５】
これを達成するために、当該方法及び装置の一つの実施形態においては、前記２番目のルートの決定と併せて、前記２番目のルートの追加された場所が、当該追加された場所に関連付けられる距離が前記メモリの中に含まれていないときに決定され、これらの追加された場所に関連する距離が決定され前記メモリに記憶される。関連付けられる距離が前記メモリの中に含まれていないような、前記２番目のルートの追加された場所は、前記２番目のルートの前記場所と、前記メモリに既に記憶されている距離についての前記場所と、を比較することにより決定される。このような確認の過程は、例えば、前記ルートプランニングユニットに前記２番目のルートの前記場所が報告されたときに、実行することができる。
【００１６】
当該方法及び当該装置の他の一つの実施形態においては、前記メモリの中で決定され更新される距離は、追加された場所の間の距離及び／又は追加された場所と、前記メモリに既に含まれている場所と、の間の距離である。これらは同様に、前記２番目のルートの構成要素である場所となり得る。同様に、前記メモリに含まれる他の場所への距離を付加的に決定することができる。結果として、前記２番目のルート上でサービスが提供されない場所に関連する距離を決定し更新することができる。しかしながら、更新は、これらの距離が使用される起こりうる将来のルートプランニング過程に目を向けて実行される。
【００１７】
前記メモリに記憶された距離は、複数の変数で表すことができる。好ましくは、前記ルートは、例えば、通行されるべき距離及び／又は1つ又はそれ以上の（同時にプランニングされた）ルートを完了させるのに要する時間等の所定の変数が可能な限り小さくなるようにプランニングされる。メモリに記憶された距離は、最適化されるべき変数に適用することができる。当該方法及び当該装置の一つの実施形態においては、前記距離は、前記場所の間の時間に関連した距離である。このことは、最初の及び２番目の場所の間の距離は、最初の場所から２番目の場所へと移動するのにどれだけの時間を要するのかを示すことを意味する。時間に関連した距離はとりわけ、所要時間を最小限とするルートをプランニングするのに用いることができる。
【００１８】
場所間の時間に関連した距離を決定するために、当該方法及び当該装置の一つの実施形態においては、前記場所間の距離は、前記場所間の決定されたルートに応じて、決定される。前記ルートは、少なくとも可能な限り最適化基準を満たすように決定することができる。これらは特に、最短のルート又は最速のルートとなり得る。
【００１９】
例えば交通渋滞又は道路遮断のような交通障害に起因して距離は増加し得るため、交通状況は実際に通行された距離に影響する。交通状況を考慮に入れるために、当該方法及び当該装置の改良版においては、前記メモリに記憶された前記距離は、交通情報に応じて決定され及び／又は更新される。前記メモリに既に記憶されている距離を更新することにより、交通状況の変化及び距離の変化結果が考慮に入れられる。
【００２０】
これに加えて又はこれに代えて、当該方法及び当該装置の一つの実施形態においては、前記距離は、前記ルートが通行されているときに取得された測定値に基づいて決定され、そしてその後前記メモリの中で更新される。結果として、実際に通行された距離を前記メモリに記憶することができる。これは好ましくは、例えば、前記ルートが通行される前に、算出された距離を更新することにより実行される。これらの測定値は、例えば、検出位置や取得時間とすることができる。これらに基づいて、前記ルートの場所間の時間に関連した距離を決定することができる。
【００２１】
さらに、当該方法及び当該装置の一つの実施形態においては、少なくとも２つの場所について、当該場所間の複数の距離が前記メモリに記憶され、これらの距離は異なる期間において有効であることを特徴とする。特に、これらの期間は、一日の中の時間的間隔及び／又は一週間の中の時間的間隔とすることができる。異なる時間について複数の距離を記憶しておくことにより、一般に一日又は一週間の中で異なる期間の間に生じる異なる交通状況を考慮に入れることができる。
【００２２】
当該方法及び当該装置の他の一つの実施形態においては、少なくとも２つの場所について、当該場所間の複数の距離が前記メモリに記憶され、そしてこれらの距離は異なる輸送手段に適用されることが含まれる。このように、全てのルートが同じ輸送手段により通行される訳ではないことを考慮に入れることができ、そして例えば、到達することができる速度により、及び／又は利用できる道路により、異なる輸送手段につき場所間の距離が異なることを考慮に入れることができる。
【００２３】
上述の２つの変形例と関連する一つの実施形態においては、前記最初の及び／又は前記２番目のルートは前記期間に適用される前記距離に基づいて決定され、前記場所の１つは到達され及び／又は用いられる輸送手段に適用される。
【００２４】
当該方法及び当該装置の一つの実施形態においては、プランニングされたルートは郵便物を配達し及び／又は集荷するためのルートであり、そして前記住所は郵便物が配達され及び／又は集荷されるべき場所である。ルートプランニングには、好ましくは、配達員によりサービスが提供される住所の順番の決定が含まれ、また、配達されるべき郵便物及び／又は集荷の注文が利用可能な配達員に割り当てられる過程も含まれ得る。
【００２５】
他の態様によれば、本発明はデータプロセッシングシステムにおいて当該方法及びその変形例を実行するためのコマンドを含むソフトウェアコードを備えるコンピュータプログラムを提案する。
【００２６】
本発明の上述の及び他の利点、特別な特徴、及び実質的な改良点は、以下に図を参照して説明する実施形態に基づいて説明される。
【図面の簡単な説明】
【００２７】
【図１】配送所、関連するプランニングユニット、及び前記配送所に使われる運搬車両を描いた図。
【図２】（ａ）最初のバージョンの距離マトリックスの略図。（ｂ）他のバージョンの距離マトリックスの略図。
【発明を実施するための形態】
【００２８】
図１に概略的に示される郵便業務プロバイダーの配送所１０１から始まって、郵便物は配送所１０１に関連付けられる地理的領域１０２内に配達される。さらに、送り主が配送所１０１に又は他の郵便業務プロバイダーに関連する集荷の注文を送ったとき、配送所１０１に関連付けられた配達員が地理的領域１０２内の送り主から郵便物を集荷することとすることができる。郵便物は、荷物や小包であってもよく、又は例えば手紙のような他の郵便物であってもよい。
【００２９】
配送所１０１には一定数の又は可変数の配達員がいて、当該配達員には運搬車両１０３を割り当てることができる。当該運搬車両１０３はそれから郵便物の集配のために配達員によって使われる。好ましくは、運搬車両１０３を割り当てられた複数人の配達員が雇用される（しかしながら、図１では、例示のために一つの運搬車両１０３のみが示してある）。運搬車両１０３は、四輪の又は複数車輪の乗用車又はトラックとして構成することができる。基本的には、配送所１０１に関連する全ての配達員がこのような運搬車両１０３を使用することができる。しかしながら、少なくとも数人の配達員が郵便集配のための他の輸送手段を使用しているものとすることもできる。他の輸送手段とは、例えば、二輪車、自転車、又は徒歩での配達のための郵便車等である。
【００３０】
配達員又は配送所１０１で使用される運搬車両１０３は毎日、郵便物を集配するために少なくとも一つのルートを移動する。さらに、少なくとも数人の配達員は、一日のうちに複数のルートを移動することもできる。ルートは、配送所１０１で始まり、配送所１０１で終わり、その間には、配達員に割り当てられた住所での停止が含まれる。そこで、郵便物が配達され及び／又は集荷される。これらの住所は、以下では、配達員の行程又はルート上の停止と言うこととする。
【００３１】
ルートをプランニングするために、プランニングユニット１０５が設けられている。当該プランニングユニット１０５は配送所１０１の中に据付けられていてもよく、あるいは図１で例示したように分離して設けられていてもよい。データ処理システムとして、プランニングユニット１０５はルートプランニングを実行するためのコンピュータプログラムを備えている。プランニングユニット１０５で実行されるルートプランニングには、好ましくは、配達される郵便物を、配達員達の間で、又は配送所１０１で使用できる運搬車両１０３の間で、分配する過程が含まれる。同様に、受領された集荷の注文は、配達員達の間で分配される。さらに、プランニングユニット１０５は、同様に、郵便物が集配される住所に個々の配達員がサービスを提供する順序を決定する。
【００３２】
一つの実施形態においては、配達員達は、配送所１０１に付随するプランニングユニット１０５とワイヤーレスで通信することができる。これは例えば図１に示すように、移動通信ネットワーク１０８を経由して行われる。通信の目的で、運搬車両１０３は通信装置（図示せず）を備えるものとすることができる。しかしながら、同様に、配達員は、プランニングユニット１０５とのデータ接続を確立するために、例えばスマートフォンやノートパソコンのような携帯通信装置を持ち歩くこととしてもよい。通信接続によって、例えば、配達される郵便や、集荷の注文や、プランニングユニット１０５によって決定された停止の順序等の情報の、とりわけルートデータを、配達員又は運搬車両１０３に伝達することができる。これは特に、ルートが新しくプランニングされたときに行うことができ、そして、配達員が彼の／彼女のルートを開始した後に、集荷を注文されたルートにまとめるために実行することができる。
【００３３】
さらに、好ましくは、配達員は自分たちのいる位置を決定するための測位装置１０７を備えている。当該装置は、前記運搬車両に常設されているか、又は携帯装置として配達員に持ち歩かれている。測位装置１０７は、衛星支援型測位装置１０７として構成することができる。当該衛星支援型測位装置１０７は、例えば全地球測位システム（ＧＰＳ）のような当業者により通常知られる方法で、衛星測位システムのシグナルに基づいて、運搬車両１０３の位置を決定する。運搬車両１０３の測定された位置は、ルートの途中でもプラニングユニット１０５が運搬車両１０３の現在の位置を入手することができるように、プランニングユニット１０５に伝達できるようになっている。以下に説明する一つの実施形態においては、この位置データは配達員のルートを監視するのにも用いられる。測位装置１０７は、運搬車両１０３の位置から目的地までの領域１０２の道路網内のルートを決定するための、携帯用の又は常設のナビゲーションシステムの構成要素ともなり得るものであり、これは運搬車両１０３の運転手を目的地（これは、とりわけ停止する住所となり得る）へのルートに案内するための聴覚的及び／又は視覚的なナビゲーション指示を生成し得るものである。
【００３４】
地理的領域１０２内で配達されるべき郵便物は、郵便業務プロバイダーのロジスティックシステム１０４を経由して、配送所１０１に運搬される。これは、例えば、一日に一回又は数回行われるものとすることができる。一つの実施形態においては、ロジスティックシステム１０４には複数の郵便物仕分けセンター（図示せず）が含まれる。当該郵便物仕分けセンターでは、郵便物が送り主から受取人へと送られる途中で仕分けされ転送される（配送所１０１は同様にロジスティックシステム１０４の仕分けセンターとなり得る。又は、複数の分離した配送所であって、共同してロジスティックシステム１０４の一つの仕分けセンターとして機能する配送所のうちの、一つとなり得る。）。配達されるべき郵便物の住所は、ロジスティックシステム１０４において既に検出することができ、そしてプランニングユニット１０５に伝達される。あるいはそうでなければ、住所は、配送所１０１に受け取られたときに当該配送所１０１の中で検出され、そしてプランニングユニット１０５へと伝達される。一つの実施形態においては、ルートの開始前に配送所１０１に到達した郵便物の配達住所は、ルートプランニングに含まれる。
【００３５】
集荷の注文は、送り主から郵便業務プロバイダーへと伝達され、例えば中央装置により検出される。伝達は、例えば、電話、オンライン、ウェブサイトを経由して、又は例えば電子メールのような電気的に送信されるメッセージに基づいて、行われる。配送所１０１と関係付けられる地理的領域１０２内の住所への集荷の注文は、中央装置からプランニングユニット１０５へと伝達される。一つの実施形態においては、プランニングユニット１０５がルートをプランニングするとき、それにはルートが開始される前のある時点までに受領された集荷の注文が含まれる。同様に、プランニングユニット１０５に後から受領された集荷の注文も、既にプランニングされたルートの中に含め、まとめることができる。これは、配達員が彼の／彼女のルートを開始した後であっても、行うことができる。この場合、注文だけではなく、（例えば、注文により変化したであろう停止の順序に起因して）この注文により変化したであろうルートデータも、移動通信ネットワーク１０８を経由して配達員に伝達される。
【００３６】
配達員によりサービスが提供されるべき住所に基づいて、そして当該住所間の距離に基づいて、ルートプランニングがプランニングユニット１０５において実行される。この過程で、停止と配達員との関連付けが、一つ又はそれ以上の最適化基準に基づいて行われる。例えば、ルートの総合継続時間又は総距離が最小となるように、配達員の仕事量が均等に分配されるようにするといった方法である。ルートプランニングには、個々の配達員のルートにおける停止の順序を決定することも含まれる。ルートプランニングの目的のために、好ましくは発見的アルゴリズムがプランニングユニット１０５において用いられ、これは当業者により通常知られる方法により実行される。
【００３７】
ルートが算出されて、その距離がプランニングユニット１０５の不揮発性メモリユニット１０９に記憶される前に、ルートプランニングにおいて使用される距離がプランニングユニット１０５において決定される。経路計算を実行するために、プランニングユニット１０５はメモリユニット１０９からサービスが提供されるべき住所間の距離を読み取り、これらの距離をルートプランニングアルゴリズムの入力変数として使用する。この過程において、サービスが提供されてルートプランニングに含まれるべき住所の各々について、サービスが提供されるべき他のすべての住所までの距離が提供される。続いて、各住所について、とりわけ他の住所からこの住所までの距離を考慮に入れることができる。
【００３８】
これらの距離は好ましくは時間に関連した距離であり、一つの住所から他の住所へと移動するのにどれほどの時間がかかるのかを示唆する。しかしながら、別の方法として、住所間の距離や他の変数が示唆されるものとすることもできる。好ましくは、距離が委ねられる変数は、ルートプランニングの基礎とされる最適化基準に適用される。こうして、距離はとりわけ最適化されるべき変数の値とされる。
【００３９】
距離は、所定のデータ構造で、好ましくは距離マトリックスの形で、メモリユニット１０９に記憶される。このマトリックスは項目ｄｉｊを含む。各項目ｄｉｊは、住所ｉから住所ｊまでの距離を示す。距離マトリックスの主対角線上の項目、すなわち項目ｄｉｉは、値が０である。距離マトリックスは一般的には対称とはなっていない。なぜならば、どんな場合でも、住所ｉから住所ｊまでの距離は、必ずしも住所ｊから住所ｉまでの距離に一致していないからである。これらの距離の間で差異が生じるのは、例えば、住所ｉから住所ｊまでのルートは、一方通行等の理由により逆走ができないようになっているから、等の理由による。
【００４０】
プラニング計算機１０５における各ルートプランニング過程の前に新しく距離マトリックスを決定する必要がないということがもたらされる。その代わり、一度算出された距離は基本的にはメモリユニット１０９に記憶されたままとされ、これを複数のルートプランニング過程に用いることができる（しかしながら、一つの実施形態においては、以下で説明するように、距離を更新することができる）。距離の算出は、好ましくは、関連した住所が最初にサービスの提供を受けるべきときに実行される。距離マトリックスに含まれない新しい住所にサービスを提供しなければならなくなったときは、新しい住所間の距離と、新しい住所と距離マトリックスの中の他の住所との間の距離と、が算出され、距離マトリックスに追加されるものとする。
【００４１】
最初は、考慮されるべき住所に基づいて信頼できるルート計算過程を用意するために、距離マトリックスを決定することができる。そして、これはそれからメモリユニット１０９に記憶される。図２ａは、第一回の決定に基づいて取得することのできる距離マトリックスの略図を示している。示された距離マトリックスにおいては、Ａ１からＡＮまでのＮ個の住所が、距離マトリックスの第一回の計算のためのルートプランニングプロセスが実行されるのに基づいて、検討されている。距離の値を含む距離マトリックスの項目は、図２ａにおいて斜交平行模様の図で示してある。
【００４２】
後のルートプランニング過程に含まれるべき一つ又はそれ以上の住所がプランニングユニット１０５に伝達されたとき、プランニングユニット１０５は、これらの住所がメモリユニット１０９に記憶された距離マトリックスのバージョンに既に含まれているか否かを見るために点検する。もしこれが一つ又はそれ以上の受信された住所である場合、使用された距離は、この住所を参照してメモリユニット１０９に記憶されたものである。一つ又はそれ以上の受信された住所が、記憶されたバージョンの距離マトリックスに含まれていないことを、プランニングユニット１０５が確かめた場合、問題になっている住所間の距離と、新しい住所と既に距離マトリックスに含まれている住所との間の距離と、が算出され、距離マトリックスに記憶される。これにより、メモリユニット１０９に記憶されている距離マトリックスが新しいバージョンのものとなる。
【００４３】
図２ｂは、あるバージョンの距離マトリックスの略図を示している。このバージョンは、図２ａに示されたバージョンを基礎として、その後にプランニングユニット１０５に追加の住所が報告された場合に決定される、バージョンである。例示した状況では、追加のアドレスＭには住所Ｂ１からＢＭが含まれ、これらはＡ１からＡＮまでの住所のいずれとも一致しない。その結果、追加のアドレスＭは先行するバージョンの距離マトリックスには含まれていない。図２ｂに示すように、住所Ｂ１〜ＢＭ同士の間の距離と、住所Ｂ１〜ＢＭと住所Ａ１〜ＡＮとの間の距離と、が距離マトリックスの中に更新される。更新された項目は、図２ｂにおいて、元からある項目に付されている斜交平行模様とは異なる斜交平行模様で示してある。
【００４４】
配送所１０１の配達員によりサービスが提供されるべきアドレス、及び、プランニングユニット１０５のルートプランニングに含まれるべきアドレスが、プランニングユニットに報告されたときは、距離の最初の追加のときと同様の方法で、距離マトリックスがいつでも更新される。このようにして、郵便物が配達及び／又は集荷されるべき住所に関連付けられる距離は、距離マトリックスの中で更新され続けるのである。時間が経つにつれ、配送所１０１に関連付けられるが未だ距離マトリックスに包含されていないような地理的領域１０２内の住所は少なくなっていくので、これに伴い追加される距離は小さくなっていく。
【００４５】
このようにして、ある期間が経過したら、距離マトリックスは、郵便物の集配において考慮されるべき基本的に全て又はほとんどの住所が距離マトリックスに掲載されている程度の範囲にまで成長する。その一方で、例えば関連する場所が使用されていない等の理由により、郵便物の集配が一度も行われていないような住所は、距離マトリックスの中には含まれない。これは、距離マトリックスを必要に応じて更新することの利点である。つまり、郵便物の集配に関連する住所間の距離のみを算出するので足りる、という事実を招く。
【００４６】
別の一つの実施形態は、上で説明した実施形態とは以下の点で異なる。すなわち、ルートプランニングの過程のために伝達された新しい住所についてであり、既に、すべての住所への距離が算出された距離マトリックスに含まれているのではなく、むしろ、ルートプランニングに含まれる必要のある距離のみが距離マトリックスに含まれている。プランニングユニットは、好ましくは、新しい住所と、距離マトリックスに既に含まれている他の住所と、が共にルートプランニングに含まれるべきときは、これらの間の距離を算出する。
【００４７】
別の実施形態においては、プランニングユニット１０５がルートプランニング過程を実行する前に、プランニングユニット１０５は、含まれるべき住所間の距離が距離マトリックスの中に記憶されているか否かを点検する。そこに含まれていない距離については、プランニングユニット１０５により更新され、ルートプランニング過程を終えた後でさえも、更なるルートプランニング過程を実行するのに備えることを目的として、これらはメモリユニット１０９に記憶されたままとされる。点検の過程は特に、ルートプランニングに含まれるべき住所が伝達されたときに実行される。ここで、ルートプランニングに含まれるべき報告された住所と既に含まれている住所との間の距離が、メモリユニット１０９内に記憶されているか否かに関して、決定が行われる。一つ又はそれ以上の既に含まれた住所ではない場合、その後距離が更新される。この実施形態でも、存在しない距離が距離マトリックスに次々に足されるが、時間が経つにつれて、足される住所の数が小さくなる。
【００４８】
前述した別の実施形態においては、より少ない数の距離を算出するので足りるので、個々のルートをプランニングするのに必要となる計算能力は低減される。しかしながら、最新のルートプランニングには含まれる必要のない住所（特に、距離マトリックスに含まれるその他の全ての住所への距離）への距離も決定されたら、さらなる計算を必要とすることなく、後に使用することが可能な距離によって、距離マトリックスをより早く満たすことができる。
【００４９】
一つの実施形態においては、距離マトリックスに含まれる最初の住所と２番目の住所との間の距離を決定するために、プラニングユニット１０５は地理的領域１０２の道路網内において、最初の住所から２番目の住所までのルートを算出する。ルート算出手段１０６がこの目的のために設けられる。ルート算出手段１０６では、ルートは一つ又はそれ以上の所定の最適化基準に適合するように算出される。とりわけ、一番速い又は一番短いルートを算出することができる。好ましくは、ルート算出のために用いられる最適化基準は、プランニングユニット１０５においてルートプランニングが実行される際の基礎を形成する最適化基準と調和される。具体的には、同じ最適化基準を用いることができる。プランニングユニット１０５は、最適ルートの結果得られた距離を距離マトリックスに取り入れる。
【００５０】
一つの実施形態においては、距離決定の基礎となる算出された最適ルートは運搬車両１０３へと伝達される。当該運搬車両１０３はその後、これに基づいたルートに沿ってガイドされる。この目的のために、ルートは、例えば運搬車両１０３のナビゲーションシステムの中に取り入れることができる。そうすることにより、ナビゲーション指示に基づいたルートに沿って運搬車両をガイドすることができる。しかしながら、同様に、個々の停止の間のルートは、距離を決定するためのルート決定とは無関係に、運搬車両１０３において決定することもできる。このように、配達員のナビゲーションシステムは、プランニングユニット１０５により供給された仕様とは無関係にルートを決定することができ、そして／又は配達員は、地域についての土地の知識に基づいて、停止の間のルートを決定する。
【００５１】
最適なルートは、プランニングユニット１０５において、地理的領域１０２の道路網の記憶されたマップデータを参考にすることにより決定される。マップデータには、例えば、個々の距離が関連付けられる又は、道路区画と関連付けられるデータを基礎として距離が算出される道路網の道路区間が含まれるものとすることができる。例えば、各道路区画について、長さ及び平均速度を示すことができる。これらに基づいて、プランニングユニット１０５は、その道路区画を通過するのに必要な平均的な時間に関連した距離を算出することができる。このように、最初の住所から２番目の住所への最適なルートが得られるように、最初の住所から２番目の住所へのルートが決定されるときには、道路網の個々の道路区画が互いに関連付けられる。この目的のために、当業者に通常知られているアルゴリズムを用いることができる。
【００５２】
さらに、一つの実施形態においては、ルートは交通情報を用いて算出され、これに基づいて距離マトリックスに入力される距離が決定される。ここで、例えば道路上の防塞及び／又は迂回路のような長期間にわたる交通障害が考慮に入れられるし、また、例えば交通渋滞のような比較的短期間の交通障害も考慮に入れられる。より長期にわたる交通障害がある場合には、例えば、ある道路の一部をルートプランニングから除外することができる。上述した短期間の交通障害がある場合、道路区画を通行する際により長距離を通行する必要が生じ、結果として、このことは距離を決定する際に考慮に入れられる。例えば、距離の決定の基礎となるルートの算出をするとき、交通渋滞がこれらの道路の部分について報告されている場合、これらの個々の道路の部分に代えてより長い距離を用いることができる。
【００５３】
地理的領域１０２の道路網の至る所で交通状況が時間の経過と共に変化するので、交通情報に基づいて算出された距離は距離マトリックスの中で更新されるものとすることができる。例えば、プランニングユニット１０５に伝達することができる交通情報の範囲で交通状況に変化があった場合、距離マトリックスの中の距離を更新することができる。一つの実施形態においては、受信した交通情報に基づいてプランニングユニット１０５が交通状況に変化があったことを確かめたら直ちに、距離が更新されるものとすることができる。最初の住所と２番目の住所との間の距離を更新するためには、変化した交通情報又は交通状況に基づいて、新たに住所間の距離を算出することが好ましい。
【００５４】
交通情報を含めること及び距離マトリックスの中の距離の結果更新に変えて又はこれに追加して、完成したルートにおける配達員の進み具合を取得し評価することにより距離を決定するものとすることができる。取得した位置情報及び、取得した時間（その位置に到達した時間）に基づいて、配達員が彼の／彼女のルート上の停止に到達する時間を決定することができ、また停止の住所間で通行された時間に関連した距離を算出することができる。距離の値が他の変数を表している場合、例えば停止の間で通行された距離のような、ルートが通行されているときに取得された、追加の又は異なる測定値も考慮に入れることができる。
【００５５】
位置情報は、そして適切な場合には配達員又は運搬車両１０３からの追加のデータも、プランニングユニット１０５に伝達される。そうすることにより、配達員を追跡することができ、通行されたルートを評価することができる。同様に、例えばルートが完了する度に、運搬車両１０３の位置だけではなく、関連付けられる概算時間も、そして適切な場合には追加の情報も、位置装置に記録され、そしてプランニングユニット１０５に伝達される。
【００５６】
配達員又は運搬車両１０３により取得されたデータを含むことにより、最初の住所から２番目の住所までの通行ルートで配達員が実際に通行した最初の住所と２番目の住所の間の距離を、入力することができる。このような方法で、とても実際的な値がマトリックスの中に与えられる。同じルートが数回にわたって通行される場合、個々の配達ルートにおける特別な事情による影響を軽減するために、実際に通行された距離の平均値を算出し、これを距離の値として距離マトリックスの中に組み込むこともできる。
【００５７】
実際に通行された距離に基づいて決定された距離の値は、好ましくは、距離マトリックスの中に含まれた算出された距離を更新することにより入力される。換言すれば、配達員が２つの住所の間のルートを通行する前は、そして、関連する位置データが利用可能となる前は、コンピュータで算出された距離が距離マトリックスに入力されている。これはその後、配達員が住所間のルートを通行した後に、取得されたデータに基づいて決定された距離に置換される。
【００５８】
さらに、交通情報が距離マトリックスの中で考慮に入れられた場合、距離マトリックスの中に含まれる住所間の距離は一般的に、１日の中の時間帯及び／又は週の中の曜日に応じて、変化する。これの理由は、例えばラッシュアワーには他の時間帯と比べて大きくなる交通密度の正常変動による。距離の変動を考慮に入れるために、複数の距離マトリックスがメモリユニット１０９に記憶されているものとすることができる。複数の距離マトリックスのそれぞれは、特定の期間の間（に限り）有効であり、特に、１日の中の特定の時間帯及び／又は週の中の特定の曜日に限って有効である。これに代えて、距離マトリックスの個々の項目は複数の成分を含み、これら複数の成分はそれぞれ異なる期間において有効なものとすることもできる。この実施形態においては、距離マトリックスは２つ又はそれ以上の次元を有するように構成することができる。様々な期間に関連付けられる距離は、好ましくは平均距離である。平均距離は、有効期間中に問題となる住所間のルートを通行するのに典型的に必要となる距離である。これらは、交通情報及び／又は取得した測定値に応じて決定することができる。
【００５９】
配達員が郵便物の集配のために異なる輸送手段を用いる他の一つの実施形態においては、複数の距離マトリックスがメモリユニット１０９に記憶されていて、各距離マトリックスが与えられた輸送手段と関連付けられているものとすることができる。又はこれに代えて、距離マトリックスの項目はそれぞれ複数の成分を含み、それぞれの成分は与えられた輸送手段と関連付けられているものとすることができる。これらの実施形態は、異なる期間において異なる距離が示される上述の実施形態と結合することができる。
【００６０】
上述したように、一つ又はそれ以上の距離につき複数の値が与えられた場合、関連付けられた位置がプランニングユニット１０５に報告されたら、好ましくは全ての距離の値が付加される。しかしながら、同様に、必要に応じて（すなわち、ルートプランニングに距離の値が必要となる場合に限り）決定が行われるものとすることもできる。
【００６１】
上述の方法により算出された距離マトリックスでは、配送所１０１と関連付けられた地理的領域１０２の数多くの住所間の現実的な距離は、ルートプランニングのためにプランニングユニット１０５においていつでも利用可能である。各ルートプランニングの過程において距離を新たに算出する必要がなく、その結果、ルートプランニングをより早く実行することができる。
【００６２】
また、急に一つ又はそれ以上のルートのために新たなプランニングを実行することが必要となったときに、必要となる距離を利用することも可能である。
【００６３】
このような新しいプランニングは、例えば、配達ルートを開始させた後にプランニングユニット１０５に受信された集荷の注文が、配達ルートに統合されるように、構成することができる。集荷の注文の住所があらかじめ距離マトリックスの中に含まれていない場合には、ルートの新しいプランニングにおいては、単に、この住所と、距離マトリックスに含まれる他の住所と、の間の距離を決定することが要求されるに過ぎない。住所が距離マトリックスの中に既に含まれている場合には、配達ルートの新たなプランニングを実行するために距離を算出する必要は全くない。
【００６４】
本発明を図面及び上述の説明において詳細に説明したが、この説明は実例であり例として示しただけのものと考えられるべきである。ただし、その本質を制限するように解釈されるべきものではない。特に、本発明は明瞭にされた実施形態に制限されるべきものではない。当業者は、先行する開示、図面、及び特許請求の範囲から、本発明の更なる変異型及びその実行を探り出すことができる。
【００６５】
特許請求の範囲においては、「包含する」、「備える」、「含む」、「有する」等の用語は、追加された要素又はステップの存在を排除するものではない。不定冠詞の使用は、複数存在する場合を除外するものではない。個々の装置は、特許請求の範囲に引用された複数のユニット又は装置の機能を実行することができる。特許請求の範囲に示された参照符号は、採用される手段及びステップを制限するものと解釈されるべきものではない。
【図１】
2013543123.tif 000003
【図２ａ】
2013543123.tif 000004
【図２ｂ】
2013543123.tif 000005
【国際調査報告】
2013543123.tif 000006
2013543123.tif 000007
2013543123.tif 000008
2013543123.tif 000009