(57)【要約】      （修正有）【課題】正確な在庫追跡によって顧客注文に対応する小包を短時間で準備する方法を提供する。【解決手段】ｋ≧２として、ｋ個の供給元と、少なくとも１つの宛先と、ｋ個の供給元の１つから来る荷物をそれぞれ受け取るｋ個のＦＩＦＯタイプの供給元バッファデバイスと、ｋ個の供給元バッファデバイスから出る荷物を収集し、荷物を少なくとも１つの宛先に輸送するコレクタであって、供給元バッファデバイスの１つから出る荷物を収集するｋ個の連続するノードを含むコレクタと、顧客注文を処理する制御システムにおいて、各顧客注文が、所与の宛先のための荷物をリストし、宛先の順序番号にそれぞれ関連付けられる荷物を順序付けする方法であって、宛先の昇順の順序番号に対してｎ個の荷物の未整序を低減する収集リストを構築し、収集リストに準拠したコレクタでの荷物の収集を実施するために、コレクタおよび供給元バッファデバイスを制御する。【選択図】図３
2020129378.tif 000002
【特許請求の範囲】
【請求項１】
ｋ≧２として、ｋ個の供給元（Ｓ１〜Ｓ５）と、
少なくとも１つの宛先（Ｄ１〜Ｄ５）と、
それぞれが前記ｋ個の供給元の１つからの荷物を受け取る「先入れ先出し」タイプのｋ個の供給元バッファデバイス（Ｆ１〜Ｆ５）と、
前記ｋ個の供給元バッファデバイスから出る前記荷物を収集し、前記荷物を前記少なくとも１つの宛先に輸送するコレクタ（１）であって、前記供給元バッファデバイスの１つから出る前記荷物を収集するようにそれぞれ構成されたｋ個の連続するノード（Ｎ１〜Ｎ５）を含むコレクタ（１）と、
顧客注文を処理するように構成された制御システム（９０）であって、各顧客注文が、所与の宛先のための荷物をリストし、宛先の順序番号にそれぞれ関連付けられる、制御システム（９０）と
を備えてなる自動荷物配送システムにおいて制御システム（９０）によって実施される、荷物を順序付けする方法であって、
前記制御システムが、
収集すべきｎ個の荷物を含み、宛先の昇順の順序番号に対する前記ｎ個の荷物の未整序を低減する収集リストを構築するステップ（３１）であって、前記ｎ個の荷物が、前記供給元バッファデバイスに含まれ、
【数１】
2020129378.tif 000009
であり、ここで、ｐ（ｉ）が、第ｉの供給元バッファデバイスで収集すべき荷物の数である、ステップ（３１）と、
前記収集リストに準拠した前記コレクタでの荷物の収集を実施するために、前記コレクタおよび前記供給元バッファデバイスを制御するステップ（３２）と
を実施することを特徴とし、
前記収集リストを構築するための前記ステップ（３１）が、
（ａ）単一の状態ｅｉｎｉｔ＝（Ｕｉｎｉｔ，Ｌｉｎｉｔ）を有する第１の状態セットＥ１を初期化するステップであって、Ｕｉｎｉｔが、ｋ個のゼロを含むｋアプレットであり、Ｌｉｎｉｔが空のリストであるステップ（５０１）と、
（ｂ）第２の状態セットＥ２を空の値で初期化するステップ（５０２）と、
（ｃ）ｎ個の連続する構築ステップのうちの各構築ステップ（５０３）に関して、
（ｃ．１）ｅ＝（Ｕ，Ｌ）とし、ここでＵがｋ個の要素を含むｋアプレットであるとして、Ｅ１の各状態ｅについて（５０４）、Ｕ＝（ｚ１，…，ｚｋ）であり、ここでｚｉが、第ｉの供給元バッファデバイスから取られる荷物の数であり、ｉ∈｛１，…，ｋ｝であり、Ｌが、Ｕに関連付けられた荷物のリストであり、
（ｃ．１．１）ｆ∈｛１，…，ｋ｝の各値に関して（５０５）、
（ｃ．１．１．１）Ｕ（ｆ）が、Ｌに含まれる第ｆの供給元バッファデバイスの荷物の数であり、ｐ（ｆ）が、前記第ｆの供給元バッファデバイスに収集すべき荷物の数であるとして、Ｕ（ｆ）＜ｐ（ｆ）の場合（５０６）、
−ｉ−  ｅ＝（Ｕ，Ｌ）から始めて、Ｕ（ｆ）に１を追加し、Ｌの最後に、前記第ｆの供給元バッファデバイスに含まれる荷物の前記シーケンス中で第（Ｕ（ｆ）＋１）の位置を占める荷物を追加して、新たな状態ｅＮ＝（ＵＮ，ＬＮ）を作成するステップ（５０７）と、
−ｉｉ−  宛先の昇順の順序番号に対する未整序計算関数を用いて、前記新たな状態ｅＮの前記リストＬＮの未整序の値ｄを計算するステップ（５０８）と、
−ｉｉｉ−  Ｕ’Ｎ＝ＵＮ、およびｄ’をリストＬ’Ｎの未整序の値として、Ｅ２が別の新たな状態ｅ’Ｎ＝（Ｕ’Ｎ，Ｌ’Ｎ）を含む場合（５０１）、ｄ＜ｄ’のとき、ｅＮによってＥ２でのｅ’Ｎを置き換え（５１４）、ｄ≧ｄ’のとき、ｅＮがＥ２に挿入されないステップ（５１３）と、
−ｉｖ−  Ｅ２が前記他の新しい状態ｅ’Ｎを含まない場合、ｅＮがＥ２に挿入されるステップ（５１１）と、
（ｃ．２）前記構築ステップが第ｎの構築ステップでない場合、Ｅ２が前記新たな状態セットＥ１になり、前記方法が次の構築ステップに進むステップと、
（ｃ．３）前記構築ステップが前記第ｎの構築ステップである場合、Ｅ２が単一の最終状態ｅＦ＝（ＵＦ，ＬＦ）を含み、ＬＦが前記収集リストを形成するステップ（５１６）と
を含むことを特徴とする方法。
【請求項２】
前記ステップ（ｃ．１．１．１）において、前記制御システムが、Ｎ（ｆ）＜ｙｆであるかどうかも検証し（５０６ａ）、ここで、Ｎ（ｆ）が、Ｌに連続的に配置された第ｆの供給元バッファデバイスの荷物の最長シーケンスであり、ｙｆが所定の閾値であり、
前記ステップ（ｉ）〜（ｉｖ）が、Ｕ（ｆ）＜ｐ（ｆ）およびＮ（ｆ）＜ｙｆである場合にのみ実施される、
請求項１に記載の方法。
【請求項３】
前記ステップ−ｉｉ−の後に、
−ｉｉａ−  ｄＨを所定値としてｄ＞ｄＨである場合、前記新たな状態ｅ１がＥ２に挿入されず、前記ステップ（ｉｉｉ）および（ｉｖ）が実施されないステップ
が続く、請求項１または２に記載の方法。
【請求項４】
前記所定値ｄＨが、
−前記ｎ個の荷物を含み、
＊前記ｋ個の供給元バッファデバイスから出る準備が真にできている荷物のうち、ＬＨの第１の荷物が、宛先の最小の順序番号を有する荷物であり、
＊ＬＨの先行の荷物がｋ個の供給元バッファデバイスから出たと仮定して、前記ｋ個の供給元バッファデバイスから出る準備ができている荷物のうち、ＬＨの後続の各荷物が、宛先の最小の順序番号を有する荷物である
ように構築される参照リストＬＨを構築するステップと、
−前記未整序計算関数を用いて、リストＬＨの未整序の値としてｄＨを計算するステップと
によって計算される、請求項３に記載の方法。
【請求項５】
前記未整序計算関数が、ｑ個の荷物のリストＭに関して、
【数２】
2020129378.tif 000010
として書かれ、ここで、Ｋ（ｉ）が、リストＭの第ｉの荷物の前に配置されているリストＭの荷物の数であり、リストＭの第ｉの荷物の順序番号以下の宛先の順序番号を有する、
請求項１から４のいずれか一項に記載の方法。
【請求項６】
所与の顧客注文の前記荷物が、宛先の所与の昇順の順番で所与の宛先に到達しなければならず、前記制御システムが、前記コレクタと前記少なくとも１つの宛先との間に配置された少なくとも１つの順序付けデバイス（９１）を制御するためのステップ（３３）を実施して、前記ｎ個の荷物の未整序の訂正を行う、請求項１から５のいずれか一項に記載の方法。
【請求項７】
前記制御システムが、前記収集リストを構築するための前記ステップ（３１）の前に、Ｒを２以上の整数として、前記供給元バッファデバイスの１つに含まれるＲ個の連続する荷物の少なくとも１つのグループに関して、
前記Ｒ個の荷物の宛先の順序番号の関数として、宛先の代替順序番号を計算するステップ（３０）
を実施し、
前記収集リストを構築するための前記ステップ（３１）の実行に関して、前記制御システムが、前記Ｒ個の荷物のそれぞれについて、宛先の前記代替順序番号を使用する
請求項１から６のいずれか一項に記載の方法。
【請求項８】
前記Ｒ個の荷物の宛先の前記順序番号の関数としての、宛先の代替順序番号の前記計算が、
前記Ｒ個の荷物の宛先の順序番号の平均値を計算すること、
前記Ｒ個の荷物の宛先の前記順序番号の関数として前記Ｒ個の荷物の未整序の値を計算すること、
前記Ｒ個の荷物の未整序の前記値が所定の閾値よりも大きい場合、宛先の前記代替順序番号が、最も近い整数に切り上げられた平均値であり、そうでない場合、宛先の前記代替順序番号が、最も近い整数に切り捨てられた平均値であること
を含む、請求項７に記載の方法。
【請求項９】
前記供給元バッファデバイスの１つへの少なくとも１つの新たな荷物の投入が、前記供給元バッファデバイスで収集すべき前記荷物、したがって前記ｋ個の供給元バッファデバイスの前記セットで収集すべき前記ｎ個の荷物の修正（３４）を促す場合、前記方法の前記ステップの新たな実行が開始される、請求項１から８のいずれか一項に記載の方法。
【請求項１０】
前記プログラムがコンピュータ上で実行されるとき、請求項１から９のいずれか一項に記載の方法を実施するためのプログラムコード命令を含むコンピュータプログラム（９３０）。
【請求項１１】
請求項１０に記載のコンピュータプログラム（９３０）を記憶するコンピュータ可読の非一時的記憶媒体（９３）。
【請求項１２】
ｋ≧２として、ｋ個の供給元（Ｓ１〜Ｓ５）と、
少なくとも１つの宛先（Ｄ１〜Ｄ５）と、
前記ｋ個の供給元の１つからの荷物をそれぞれ受け取る「先入れ先出し」タイプのｋ個の供給元バッファデバイス（Ｆ１〜Ｆ５）と、
前記ｋ個の供給元バッファデバイスから出る前記荷物を収集し、前記荷物を前記少なくとも１つの宛先に向けて輸送するコレクタ（１）であって、前記ｋ個の供給元バッファデバイスの１つから出る前記荷物を収集するようにそれぞれ構成されたｋ個の連続するノード（Ｎ１〜Ｎ５）を含むコレクタ（１）と、
顧客注文を処理するように構成された制御システム（９０）であって、各顧客注文が、所与の宛先のための荷物をリストし、宛先の順序番号にそれぞれ関連付けられる、制御システム（９０）と
を備えてなる自動荷物配送システムであって、
前記制御システムが、
収集すべきｎ個の荷物を含み、宛先の昇順の順序番号に対する前記ｎ個の荷物の未整序を低減する収集リストを構築するステップであって、前記ｎ個の荷物が、前記供給元バッファデバイスに含まれ、
【数３】
2020129378.tif 000011
であり、ここで、ｐ（ｉ）が、第ｉの供給元バッファデバイスで収集すべき荷物の数である、ステップと、
前記収集リストに準拠した前記コレクタでの荷物の収集のために、前記コレクタおよび前記供給元バッファデバイスを制御するステップと
を行うように構成された計算機（９１、９２、９３）を含むことを特徴とし、
前記計算機（９１、９２、９３）が、
（ａ）単一の状態ｅｉｎｉｔ＝（Ｕｉｎｉｔ，Ｌｉｎｉｔ）を有する第１の状態セットＥ１を初期化するステップであって、Ｕｉｎｉｔが、ｋ個のゼロを含むｋアプレットであり、Ｌｉｎｉｔが空のリストであるステップ（５０１）と、
（ｂ）第２の状態セットＥ２を空の値で初期化するステップ（５０２）と、
（ｃ）ｎ個の連続する構築ステップのうちの各構築ステップ（５０３）に関して、
（ｃ．１）ｅ＝（Ｕ，Ｌ）と、ここでＵがｋ個の要素を含むｋアプレットであるとして、Ｅ１の各状態ｅについて（５０４）、Ｕ＝（ｚ１，…，ｚｋ）であり、ここでｚｉが、第ｉの供給元バッファデバイスから取られる荷物の数であり、ｉ∈｛１，…，ｋ｝であり、Ｌが、Ｕに関連付けられた荷物のリストであり、
（ｃ．１．１）ｆ∈｛１，…，ｋ｝の各値に関して（５０５）、
（ｃ．１．１．１）Ｕ（ｆ）が、Ｌに含まれる第ｆの供給元バッファデバイスの荷物の数であり、ｐ（ｆ）が、前記第ｆの供給元バッファデバイスに収集すべき荷物の数であるとして、Ｕ（ｆ）＜ｐ（ｆ）の場合（５０６）、
−ｉ−  ｅ＝（Ｕ，Ｌ）から始めて、Ｕ（ｆ）に１を追加し、Ｌの最後に、前記第ｆの供給元バッファデバイスに含まれる荷物の前記シーケンス中で第（Ｕ（ｆ）＋１）の位置を占める荷物を追加して、新たな状態ｅＮ＝（ＵＮ，ＬＮ）を作成するステップ（５０７）と、
−ｉｉ−  宛先の昇順の順序番号に対する前記未整序計算関数を用いて、前記新たな状態ｅＮの前記リストＬＮの未整序の値ｄを計算するステップ（５０８）と、
−ｉｉｉ−  Ｕ’Ｎ＝ＵＮ、およびｄ’をリストＬ’Ｎの未整序の値として、Ｅ２が別の新たな状態ｅ’Ｎ＝（Ｕ’Ｎ，Ｌ’Ｎ）を含む場合、ｄ＜ｄ’のとき、ｅＮによってＥ２でのｅＮを置き換え、ｄ≧ｄ’のとき、ｅＮがＥ２に挿入されない、ステップ（５１３）と、
−ｉｖ−  Ｅ２が前記他の新しい状態ｅ’Ｎを含まない場合、ｅＮがＥ２に挿入される、ステップ（５１１）と、
（ｃ．２）前記構築ステップが第ｎの構築ステップでない場合、Ｅ２が前記新たな状態セットＥ１になり、前記方法が次の構築ステップに進むステップと、
（ｃ．３）前記構築ステップが前記第ｎの構築ステップである場合、Ｅ２が単一の最終状態ｅＦ＝（ＵＦ，ＬＦ）を含み、ＬＦが前記収集リストを形成するステップ（５１６）と
を実施して、前記収集リストを構築するように構成されることを特徴とする、自動荷物配送システム。
【発明の詳細な説明】
【技術分野】
【０００１】
１．技術分野
本発明の分野は、物流の分野、特に自動荷物配送システムの分野である。
【０００２】
より詳細には、本発明は、そのような自動配送システムで荷物を順序付けするための方法に関する。
【背景技術】
【０００３】
自動配送システムの構成要素が、
・ｋ≧２として、ｋ個の供給元と、
・少なくとも１つの宛先と、
・ｋ個の供給元の１つから来る荷物をそれぞれ受け取るＦＩＦＯ（先入れ先出し）タイプのｋ個の供給元バッファデバイスと、
・ｋ個の供給元バッファデバイスから出る荷物を収集し、荷物を上記少なくとも１つの宛先に輸送するコレクタであって、ｋ個の供給元バッファデバイスの１つから出る荷物を収集するようにそれぞれ構成されたｋ個の連続するノードを含むコレクタと、
・顧客注文を処理するように構成された制御システムであって、各顧客注文が、供給元から抽出されて所与の宛先に提供されるべき荷物を、理想的には宛先の所与の昇順（これは、厳密な昇順の順番、例えば「１  ２  ３  ４  ５」でも、厳密でない昇順の順番、例えば「１  １  ２  ２  ２  ３  ４  ４  ５」でもよい）でリストする、制御システムと
を備えてなることが考えられる。各荷物は、宛先の順序番号に関連付けられる。
【０００４】
したがって、ｋ個の供給元バッファデバイスから出る荷物が、ｋ個の進入する荷物ストリームを形成し、コレクタで収集された後の荷物が、発出する荷物ストリームを形成することが考えられ、ここで、問題は、ｋ個の進入ストリームから発出ストリームを形成する（すなわち、ｋ個の進入ストリームを１つの発出ストリームにグループ化する）ことである。
【０００５】
制御システムは、顧客注文を処理し、自動配送システムの要素、特に供給元、ＦＩＦＯタイプの供給元バッファデバイス、コレクタ、および宛先を制御（指令）できるようにする命令を出力する。制御システムは、例えば、中央倉庫管理システムまたは倉庫制御システム（ＷＣＳ）である。
【０００６】
本発明は、それだけに限らないが特に、自動配送システムの各供給元が保管庫の一部であるとき（この部分は、本明細書では以下で「保管ユニット」とも呼ぶ）、および自動配送システムの各宛先が顧客注文準備ステーションまたはピッキングステーションであるときに適用することができる。
【０００７】
しかし、本発明の枠組みから逸脱することなく、多くの代替形態が想定可能であることは明らかである。例えば、各供給元は、保管庫、複数の保管庫を含むセット、または（保管庫ほど複雑ではない）保管デバイスとして定義することができる。
【０００８】
２．技術的背景
本明細書では以下、より具体的に、自動配送システムを使用して小包を準備する特定の場合に存在する課題および問題を述べる。本発明は、当然、この特定の用途に限定されない。
【０００９】
小包準備システムは、より具体的には、企業において、少量の商品の通信販売での発送や販売に使用される。これらの小包準備自動システムのユーザの主な例は、オフィス機器、衣類、化粧品、機械エンジニアリング産業での工具およびスペアパーツの供給業者である。これらのシステムにより、最小限の労力で、短期間に、正確な在庫追跡によって、正確な顧客注文に対応する小包の準備を可能にする。この顧客注文は、様々な量の様々な製品に関するものであり、各製品およびその対応する量が顧客注文ラインによって識別される（各顧客注文ラインは、所望の製品が置かれている保管コンテナを定義する）。
【００１０】
そのような自動小包準備システムの一例は、特に本出願人により出願されたフランス特許出願第２９１５９７９号に記載されている。そのシステムは、例えば、
・（上記の荷物に対応する）保管コンテナに製品を含む自動保管庫であって、各保管コンテナは、単一の製品参照に関連付けられている（これらは特定の顧客注文および／または製品の組合せを含むコンテナでもよい）、自動保管庫と、
・製品がオペレータによってピッキングされて、小包（発送コンテナ）に入れられる、顧客注文準備ステーションまたはピッキングステーションと、
・製品が置かれている保管コンテナを、保管庫から顧客注文準備または発送ステーションに、またはその逆に搬送する１組のコンベアと、
・倉庫制御システム（ＷＣＳ）と
を備えてなる。
【００１１】
自動保管庫は、例えば４つの保管ユニットを備え、各保管ユニットはレーンによって形成され、レーンは、各側で、重ね合わされる保管レベルのうちの複数のレベルで保管ラック（または棚ユニット）を提供し、各ラックは、その長さに沿って保管位置（セルとも呼ばれる）に細分化され、それぞれ、保管コンテナを収容するように意図されている。各保管レベルで、各レーンは、移送デバイス（収集および輸送用トロリまたはシャトルとも呼ばれる）の移動のためのトラックを受け取り、移送デバイスは、保管コンテナを保管位置内に位置決めし、これらの位置からピッキングすることができるように保管コンテナをシフトさせる。トラックは一般に２本の平行なレールによって形成され、トロリには、これらのレール上を移動するように車輪が装備されている。トロリは、所与の保管レベルで水平方向に移動することができるだけでなく、アレイの一端または両端（または中央）に配設されたエレベータ（アップ／ダウンエレベータまたはスパイラルコンベアまたはミニローダとも呼ぶ）を使用して、保管コンテナを搬送しているときまたは搬送していないときにレーンの１レベルから別のレベルに受け取られることもできる。さらに、これらのエレベータは、トロリに配置された保管コンテナをコンベアのセットに向けて移送することを可能にする。
【００１２】
制御システムは、各小包（発送コンテナ）に関連付けられた顧客注文を管理し、保管庫でのこれらの保管コンテナの位置、トロリおよび保管庫エレベータの利用可能性、ならびに、これらの保管コンテナが顧客注文準備またはピッキングステーションに向けて進む互いの順番に応じて保管コンテナ（荷物）をリストする。この目的は、すべての移動および小包準備時間を最適化し、準備ステーションでの、準備される小包の到着と、準備されるこの小包に関連する顧客注文にリストされた保管コンテナの到着との同期を保証することである。
【００１３】
ここで図１Ａ、図１Ｂ及び図１Ｃ（顧客注文の処理の３つの連続した状態に対応する）を参照して、自動パッケージ準備システムの特定の文脈（本明細書で上に提示した）での制御システムによって顧客注文を処理するため（および対応する荷物を順序付けするため）の第１の既知の解決策をより詳細に提示する。簡単にするために、これらの図には、自動配送システムのすべての構成要素が示されているわけではない。
【００１４】
図１Ａは、４つの保管ユニットＡ１〜Ａ４の末端のみを示し、これらは、自動保管庫の一部であり、４つの荷物保管供給元、すなわち、４つの保管ユニットＡ１〜Ａ４の１つのすぐ下流にそれぞれ配置された複数のＦＩＦＯ（先入れ先出し）タイプのバッファデバイス１１〜１４と、（例えば１つまたは複数のコンベアからなる）コレクタ１５とを構成し、コレクタ１５は、ノード２１〜２４を介して、供給元バッファデバイス１１〜１４から出る荷物を収集し、それらの荷物を顧客注文準備ステーション（宛先）１６まで搬送する。したがって、コレクタ１５は、自動保管庫に対して顧客注文準備ステーション１６を移動させる役割を果たす。実際、建物は、顧客注文準備ステーションを保管庫の横に配置することが常に可能であるとは限らない。
【００１５】
図１Ｃは、コレクタ１５と、顧客注文準備ステーション１６（例えば、１つまたは複数のコンベアを備え、荷物を受け取る宛先を構成する）と、ノード２５を介して荷物を受け取るために注文準備ステーション１６の上流に配置されたＦＩＦＯタイプの宛先バッファデバイス１７とのみを示す。
【００１６】
この例では、顧客注文は、図中で荷物に付されている昇順の番号１〜８に対応する宛先の所与の順番で、８つの荷物をリストするものと仮定される。言い換えると、顧客注文準備ステーション１６は、これら８つの荷物を１〜８の順番で受け取らなければならない。また、番号３および６を付された荷物は供給元Ａ１に保管され、番号１および２を付された荷物は供給元Ａ２に保存され、番号４および７を付された荷物は供給元Ａ３に保管され、番号５および８を付された荷物は供給元Ａ４に保管されることが仮定される。
【００１７】
上述した顧客注文を処理するために、制御システムは、保管されている顧客注文の荷物が宛先の所与の順番に従ってそこから出るように各供給元Ａ１〜Ａ４を制御する際に、第１の「供給元内」スケジューリング（供給元から出る前のスケジューリング）を実施する。したがって、図１Ａに示されるように、供給元バッファデバイス１１（供給元Ａ１に対して下流に配置される）は、番号３および６を付されている荷物を連続して受け取る。供給元バッファデバイス１２（供給元Ａ２に対して下流に配置される）は、番号１および２を付されている荷物を連続して受け取る。供給元バッファデバイス１３（供給元Ａ３に対して下流に配置される）は、番号４および７を付されている荷物を連続して受け取る。供給元バッファデバイス１４（保管ユニットＡ４に対して下流に配置される）は、番号５および８を付されている荷物を連続して受け取る。
【００１８】
次いで、制御システムは、供給元バッファデバイス１１〜１４およびノード２１〜２４を制御することによって、第２の「供給元間」スケジューリング（供給元から出た後のスケジューリング）を実施し、それにより、コレクタ１５で収集されるときに、顧客注文にリストされている荷物が、宛先の所望の順番で配置される。このために、決定規則（注入およびフォワードフィード規則）が、各ノード２１〜２４に適用される。
【００１９】
注入規則：供給元Ａ１〜Ａ４の１つから（供給元バッファデバイス１１〜１４の１つを介して）ノードに来る荷物に関して、このノードが宛先の最も上流にある場合には、このノードの下流でコレクタ１５に荷物が注入される。宛先の最も上流のノード以外のノードについては、宛先のより低い順序番号を有する他の荷物が、供給元バッファデバイスの１つまたはコレクタにおいてこのノードの上流に存在しない場合、および宛先のより低い順序番号を有する他の荷物が、他のノードに接続された供給元バッファデバイスの１つにおいてこのノードの下流に存在しない場合に、荷物が注入される（そうでない場合には注入されない）。例えば、供給元バッファデバイス１３からノード２３を介して出る準備ができていても、番号４を付された荷物は、供給元バッファデバイス２１および２２の１つまたはコレクタ１５において番号１、２、および３を付された荷物がノード２３の上流に位置している限り、コレクタ１５に注入されない。
【００２０】
フォワードフィード規則：コレクタ１５にすでに存在する荷物およびノードに来る（別の上流ノードから来る）荷物に関して、このノードに接続された供給元バッファデバイスに、宛先のより低い順序番号を有する他の荷物が存在しない場合には、上記荷物が前に移動する（そうでない場合には、前に移動しない）。例えば、番号３を付された荷物がコレクタ１５に配置（注入）されていないと仮定した場合、その荷物がノード２２に提示されるときに、番号１および２を付されたノードがこのノード２２に接続された供給元バッファデバイス１２に位置する限り、前に移動しない。
【００２１】
図１Ｂは、宛先の所望の順番（１〜８）で収集（配置）された後、メインコレクタ１５によって輸送される番号１〜８を付された荷物を示す。図１Ｃに示されるように、制御システムは、宛先バッファデバイス１７を制御して、荷物（参照符号２５を付されたノードを介してそこに入り、宛先の所望の順番ですでにソートされている）がそこから所望の割合で出て、顧客注文準備ステーション１６に提供されるようにする。
【００２２】
図１Ａ〜図１Ｃに示されるこの技法（およびその注入およびフォワードフィード規則）の１つの欠点は、コレクタの充填レート（したがって、このコレクタから出るときのフローレート）が最適ではないことである。
【００２３】
上記の欠点を克服するために、本出願人により出願されたフランス特許出願第３０５８７０８号に第２の既知の解決策が述べられている。この既知の解決策の一般的な原理は、供給元から来た荷物を、分析されるノードに注入することができるかどうかを決定するために、本明細書で上述した第１の従来技術の解決策よりも綿密な分析を行うことにある。したがって、特定の場合には、第１の既知の解決策は荷物を注入しないのに対し、第２の既知の解決策は、（閉塞のリスクがないことを保証しながら）荷物を注入する。したがって、第２の既知の解決策は、コレクタの充填レート（したがってコレクタからの発出フローレート）を増加させる。これはまた、ノードを介してコレクタに注入される前の荷物の待機時間を短縮する。
【００２４】
しかし、本明細書で上述した第１および第２の既知の解決策には、以下の２つの欠点がある。
・「供給元内」スケジューリング（すなわち供給元から出る前）は、各供給元で、所与の顧客注文について、供給元から出る荷物が、荷物の宛先の昇順の順序番号に従ってスケジュールされることを指示するので、供給元に強い制約を課す。そして、
・「供給元間」スケジューリング（すなわち、供給元から出た後）は、コレクタでの荷物の収集中に、荷物の宛先の昇順の順序番号との一致（言い換えると、コレクタでの収集の終了時に荷物に関する未整序が生じ得ない）を指示するので、供給元バッファデバイスおよびコレクタに強い制約を課す。
【００２５】
これらの欠点を克服するために、供給元、供給元バッファデバイス、およびコレクタに対する上記の重い制約をなくすことを狙いとする第３の既知の解決策がある。この制御は、供給元バッファデバイスから出る準備ができている荷物のための空きスペースがコレクタにある場合に、荷物がそのコレクタに収集されるというものである。この第３の既知の解決策を用いると、荷物は、供給元から未整序に出ることができ、コレクタに未整序で収集することができる。しかし、宛先での荷物の到着時に、荷物の宛先の昇順の順序番号が遵守されなければならない場合、コレクタで収集された後に、順序付け（スケジューリングとも呼ばれる）、すなわち荷物の宛先の所望の順番に従った並べ替えを実施する必要がある。このために、少なくとも１つの荷物順序付けおよびバッファ保管システム（またはデバイス）が、コレクタと宛先との間に配置される。そのような順序付けおよびバッファ保管システムの例は、（その内容を引用することにより本明細書の一部をなすものとする）本出願人により出願されたフランス特許出願第３０５１９４８号、フランス特許出願第３０４５５８３号、およびフランス特許出願第３０３１５１０号に記載されている。
【００２６】
しかし、第３の既知の解決策にも、以下のような欠点がある。
・コレクタでの空き場所を待つことにより、供給元バッファデバイスの１つまたは複数（特にコレクタの最も下流に位置するデバイス）において、荷物の望ましくない蓄積が生じる可能性がある。
・コレクタから出る荷物の流れが滑らかでなくなる可能性がある。これは、コレクタの機械的能力が完全には使用されないことを意味する（荷物が、コレクタにおいて互いに必要以上に間隔を空けて置かれ、スペースの損失をもたらし、ラインの最後での生産率を低下させる）。そして、
・コレクタでの荷物の収集の順番は、宛先の昇順の順序番号を考慮していない。荷物の並べ替え（必要な場合）は、コレクタと宛先の間に配置された荷物順序付けおよびバッファ保管システムに完全に依拠する。これは、荷物順序付けおよびバッファ保管システムの複雑さおよび性能をさらに高くする。
【先行技術文献】
【特許文献】
【００２７】
【特許文献１】フランス特許出願第２９１５９７９号
【特許文献２】フランス特許出願第３０５８７０８号
【特許文献３】フランス特許出願第３０５１９４８号
【特許文献４】フランス特許出願第３０４５５８３号
【特許文献５】フランス特許出願第３０３１５１０号
【発明の概要】
【００２８】
３．概要
本発明の特定の一実施形態では、
−ｋ≧２として、ｋ個の供給元と、
−少なくとも１つの宛先と、
−それぞれがｋ個の供給元の１つからの荷物を受け取る「先入れ先出し」タイプのｋ個の供給元バッファデバイスと、
−ｋ個の供給元バッファデバイスから出る荷物を収集し、荷物を上記少なくとも１つの宛先に輸送するコレクタであって、供給元バッファデバイスの１つから出る荷物を収集するようにそれぞれ構成されたｋ個の連続するノードを含むコレクタと、
−顧客注文を処理するように構成された上記制御システムであって、各顧客注文が、所与の宛先のための荷物をリストし、宛先の順序番号にそれぞれ関連付けられる、上記制御システムと
を備えてなる自動荷物配送システムにおける制御システムによって実施される、荷物を順序付けする方法であって、
制御システムが、
−収集すべきｎ個の荷物を含み、宛先の昇順の順序番号に対して上記ｎ個の荷物の未整序を低減する収集リストを構築するステップであって、上記ｎ個の荷物が、供給元バッファデバイスに含まれ、
【数１】
2020129378.tif 000003
であり、ここで、ｐ（ｉ）が、第ｉの供給元バッファデバイスで収集すべき荷物の数である、ステップと、
−収集リストに準拠したコレクタでの荷物の収集を実施するために、コレクタおよび供給元バッファデバイスを制御するステップと
を実施する方法が提案される。
【００２９】
したがって、提案される解決策は、制御システムが、コレクタおよび供給元バッファデバイスを制御して、宛先の昇順の順序番号の遵守の軽い制約の下で供給元バッファデバイスから出る荷物の収集を実施する、完全に新規性があり進歩性のある手法を提案する。この軽い制約を違反すると、コレクタでの荷物の収集中に未整序が発生し、提案された解決策がこの未整序を低減する。
【００３０】
したがって、提案される解決策は、第１と第２の既知の解決策の欠点と第３の既知の解決策の欠点との両方を軽減する。特に、提案される解決策は、供給元、供給元バッファデバイス、およびコレクタに対して上記の強い（重い）制約を課さず（定めず）、供給元バッファデバイスおよびコレクタに対する軽い制約のみを課す（すなわち、この場合、違反され得る制約は未整序を引き起こし、これは低減されることが求められる）。さらに、収集中の未整序の低減は、宛先の作業を容易にする（これらの宛先が、これらの宛先に到達する荷物の宛先の昇順の順序番号の遵守を課さない場合）、または荷物順序付けおよびバッファ保管システムの作業を軽減する（宛先に到着する荷物の宛先の昇順の順序番号の遵守を保証するために、コレクタと宛先との間に配置されたシステムがある場合）。
【００３１】
１つの特定の特性によれば、収集リストを構築するためのステップが、
（ａ）単一の状態ｅｉｎｉｔ＝（Ｕｉｎｉｔ，Ｌｉｎｉｔ）を有する第１の状態セットＥ１を初期化するステップであって、Ｕｉｎｉｔが、ｋ個のゼロを含むｋアプレットであり、Ｌｉｎｉｔが空のリストであるステップと、
（ｂ）第２の状態セットＥ２を空の値で初期化するステップと、
（ｃ）ｎ個の連続する構築ステップのうちの各構築ステップに関して、
（ｃ．１）ｅ＝（Ｕ，Ｌ）とし、ここでＵがｋ個の要素を含むｋアプレットであるとして、Ｅ１の各状態ｅについて、Ｕ＝（ｚ１，…，ｚｋ）であり、ここでｚｉが、第ｉの供給元バッファデバイスから取られる荷物の数であり、ｉ∈｛１，…，ｋ｝であり、Ｌが、Ｕに関連付けられた荷物のリストであり、
（ｃ．１．１）ｆ∈｛１，…，ｋ｝の各値に関して、
（ｃ．１．１．１）Ｕ（ｆ）が、Ｌに含まれる第ｆの供給元バッファデバイスの荷物の数であり、ｐ（ｆ）が、第ｆの供給元バッファデバイスに収集すべき荷物の数であるとして、Ｕ（ｆ）＜ｐ（ｆ）の場合、
−ｉ−  ｅ＝（Ｕ，Ｌ）から始めて、Ｕ（ｆ）に１を追加し、Ｌの最後に、第ｆの供給元バッファデバイスに含まれる荷物のシーケンス中で第（Ｕ（ｆ）＋１）の位置を占める荷物を追加して、新たな状態ｅＮ＝（ＵＮ，ＬＮ）を作成するステップと、
−ｉｉ−  宛先の昇順の順序番号に対する未整序計算関数を用いて、新たな状態ｅＮのリストＬＮの未整序の値ｄを計算するステップと、
−ｉｉｉ−  Ｕ’Ｎ＝ＵＮ、およびｄ’をリストＬ’Ｎの未整序の値として、Ｅ２が別の新たな状態ｅ’Ｎ＝（Ｕ’Ｎ，Ｌ’Ｎ）を含む場合、ｄ＜ｄ’のとき、ｅＮによってＥ２でのｅ’Ｎを置き換え、ｄ≧ｄ’のとき、ｅＮがＥ２に挿入されないステップと、
−ｉｖ−  Ｅ２が他の新しい状態ｅ’Ｎを含まない場合、ｅＮがＥ２に挿入されるステップと、
（ｃ．２）構築ステップが第ｎの構築ステップでない場合、Ｅ２が新たな状態セットＥ１になり、方法が次の構築ステップに進むステップと、
（ｃ．３）構築ステップが第ｎの構築ステップである場合、Ｅ２が単一の最終状態ｅＦ＝（ＵＦ，ＬＦ）を含み、ＬＦが上記収集リストを形成するステップと、
を含む。
【００３２】
したがって、制御システムは、（計算時間や複雑さなどの点で）高性能で簡単かつ自動的に収集リストを構築することができる。
【００３３】
１つの特定の特性によれば、ステップ（ｃ．１．１．１）において、制御システムが、Ｎ（ｆ）＜ｙｆであるかどうかも検証し、ここで、Ｎ（ｆ）が、ＬまたはＬ’に連続的に配置された第ｆの供給元バッファデバイスの荷物の最長シーケンスであり、ｙｆが所定の閾値である。さらに、ステップ（ｉ）〜（ｉｖ）は、Ｕ（ｆ）＜ｐ（ｆ）およびＮ（ｆ）＜ｙｆである場合にのみ実施される。
【００３４】
このようにして、同じ供給元バッファデバイスで連続して収集される荷物の数が制限される。これは、収集リスト内の荷物の（供給元および供給元バッファデバイスの観点での）出所のバランスを取る。
【００３５】
１つの特定の特性によれば、ステップ−ｉｉ−の後に、
−ｉｉａ−  ｄＨを所定値としてｄ＞ｄＨである場合、新たな状態ｅ１がＥ２’に挿入されず、ステップ（ｉｉｉ）および（ｉｖ）が実施されないステップ
が続く。
【００３６】
これは、制御システムによって成される計算を単純にする（管理すべき状態がより少なくなる）。
【００３７】
１つの特定の特性によれば、所定値ｄＨが、
−上記ｎ個の荷物を含み、
＊ｋ個の供給元バッファデバイスから出る準備が真にできている荷物のうち、ＬＨの第１の荷物が、宛先の最小の順序番号を有する荷物であり、
＊ＬＨの先行の荷物がｋ個の供給元バッファデバイスから出たと仮定して、ｋ個の供給元バッファデバイスから出る準備ができている荷物のうち、ＬＨの後続の各荷物が、宛先の最小の順序番号を有する荷物である
ように構築される参照リストＬＨを構築するステップと、
−上記未整序計算関数を用いて、リストＬＨの未整序の値としてｄＨを計算するステップと
によって計算される。
【００３８】
したがって、所定の未整序の値ｄＨまたはｄ’Ｈを計算するために、ヒューリスティック法（必ずしも最適解ではない解を迅速に与える計算法）を使用する。提案されるヒューリスティック法は実施が簡単である。
【００３９】
１つの特定の実施形態では、上記未整序計算関数が、ｑ個の荷物のリストＭに関して、
【数２】
2020129378.tif 000004
として書かれ、ここで、Ｋ（ｉ）が、リストＭの第ｉの荷物の前に配置されているリストＭの荷物の数であり、リストＭの第ｉの荷物の順序番号以下の宛先の順序番号を有する。
【００４０】
未整序計算関数Ｈ（Ｍ）は、宛先の厳密な昇順（例えば、「１  ２  ３  ４  ５」）または厳密でない昇順（例えば、「１  １  ２  ２  ２  ３  ４  ４  ５」）の順序番号と比較した未整序の計算のための高性能の解決策を提供する。
【００４１】
実施の変形形態では、未整序を計算するための他の関数を使用することもできる（以下を参照）。
【００４２】
１つの特定の特性によれば、所与の顧客注文の荷物が、宛先の所与の昇順の順番で所与の宛先に到達しなければならず、上記制御システムが、コレクタと上記少なくとも１つの宛先との間に配置された少なくとも１つの順序付けデバイスを制御するためのステップを実施して、ｎ個の荷物の未整序の訂正を行う。
【００４３】
したがって、この場合、提案される解決策は、宛先に到達する荷物の宛先の昇順の順序番号への準拠を保証する。さらに、上でさらに述べたように、この場合の提案される解決策は、（第３の従来技術の解決策と比較して）荷物順序付けおよびバッファ保管システムの作業を低減する。実際、スケジューリング作業は、一部は、コレクタによる供給元バッファデバイスからの荷物の収集の特定のメカニズムによって行われ、一部は、順序付けおよびバッファ保管システムによって行われる。
【００４４】
１つの特定の特性によれば、制御システムが、収集リストを構築するためのステップの前に、Ｒを２以上の整数として、供給元バッファデバイスの１つに含まれるＲ個の連続する荷物の少なくとも１つのグループに関して、Ｒ個の荷物の宛先の順序番号の関数として、宛先の代替順序番号を計算するステップを実施する。さらに、収集リストを構築するためのステップの実行に関して、制御システムが、Ｒ個の荷物のそれぞれについて、宛先の代替順序番号を使用する。
【００４５】
このようにして、Ｒ個の荷物の同一グループにある荷物が、収集リスト内で互いに続く。これは、例えば、高性能の機械的制約に準拠するために、それに対応して、関連の供給元バッファデバイスへのこれらＲ個の荷物の投入（およびまた、関連の供給元からのこれらＲ個の荷物の排出）に関してペースを設定することを可能にする。
【００４６】
１つの特定の特性によれば、Ｒ個の荷物の宛先の順序番号の関数としての、宛先の代替順序番号の計算が、
−  Ｒ個の荷物の宛先の順序番号の平均値を計算すること、
−  Ｒ個の荷物の宛先の順序番号の関数としてＲ個の荷物の未整序の値を計算すること、
−  Ｒ個の荷物の未整序の値が所定の閾値よりも大きい場合、宛先の代替順序番号が、最も近い整数に切り上げられた平均値であり、そうでない場合、宛先の代替順序番号が、最も近い整数に切り捨てられた平均値であること
を含む。
【００４７】
これは、制御システムによって行われる宛先の代替順序番号の計算を単純化する。
【００４８】
１つの特定の特性によれば、供給元バッファデバイスの１つへの少なくとも１つの新たな荷物の投入が、上記供給元バッファデバイスで収集すべき荷物、したがってｋ個の供給元バッファデバイスすべてで収集すべきｎ個の荷物の修正を促す場合、方法のステップの新たな実行が開始される。
【００４９】
このようにして、提案される解決策は、収集すべきｎ個の荷物の変更があるとすぐに、方法の新たな実行により動的に使用することができる。
【００５０】
本発明の別の実施形態は、上記プログラムがコンピュータ上で実行されるとき、上述した方法を実施するためのプログラムコード命令を含むコンピュータプログラム製品を提案する。
【００５１】
本発明の別の実施形態は、（その様々な実施形態の任意の１つにおいて）上述した方法を実施するためにコンピュータによって実行可能な１組の命令を備えるコンピュータプログラムを記憶するコンピュータ可読の非一時的記憶媒体の使用を提案する。
【００５２】
本発明の別の実施形態は、
−  ｋ≧２として、ｋ個の供給元と、
−  少なくとも１つの宛先と、
−  ｋ個の供給元の１つからの荷物をそれぞれ受け取る「先入れ先出し」タイプのｋ個の供給元バッファデバイスと、
−  ｋ個の供給元バッファデバイスから出る荷物を収集し、荷物を上記少なくとも１つの宛先に向けて輸送するコレクタであって、ｋ個の供給元バッファデバイスの１つから出る荷物を収集するようにそれぞれ構成されたｋ個の連続するノードを含むコレクタと、
−  顧客注文を処理するように構成された制御システムであって、各顧客注文が、所与の宛先のための荷物をリストし、宛先の順序番号にそれぞれ関連付けられる、制御システムと
を備える自動荷物配送システムであって、
上記制御システムが、
−  収集すべきｎ個の荷物を含み、宛先の昇順の順序番号に対して上記ｎ個の荷物の未整序を低減する収集リストを構築するステップであって、上記ｎ個の荷物が、ｋ個の供給元バッファデバイスに含まれ、
【数３】
2020129378.tif 000005
であり、ここで、ｐ（ｉ）が、第ｉの供給元バッファデバイスで収集すべき荷物の数である、ステップと、
−  収集リストに準拠したコレクタでの荷物の収集のために、コレクタおよび供給元バッファデバイスを制御するステップと、
を行うように構成された計算機を含む。
【００５３】
有利には、制御システムは、その様々な実施形態の任意の１つにおいて本明細書で上述したように荷物を順序付けするための方法において実施するステップの実施手段を備える。
【００５４】
４．図面のリスト
本発明の他の特徴および利点は、例示的かつ非網羅的な例として与えられる以下の説明および添付図面から明らかになろう。
【図面の簡単な説明】
【００５５】
【図１Ａ−１Ｃ】従来技術を参照してすでに述べた図であり、第１の既知の解決策による顧客注文の処理の３つの状態（コレクタでの収集前の荷物、コレクタでの収集後の荷物、コレクタから出た後のピッキングまたは準備ステーションに到達した荷物）を示す図である。
【図２】本発明による荷物順序付け方法を実施することが可能な自動配送システムの一例のブロック図である。
【図３】本発明の特定の一実施形態による荷物順序付け方法の流れ図である。
【図４】本発明の特定の一実施形態による制御システムの構造を表す図である。
【図５】図３のステップ３１（収集またはピッキングリストの構築）の特定の実施形態のアルゴリズムを示す図である。
【図６】図５のアルゴリズムによって見た状態ツリーの一例を示す図である。
【図７Ａ】単一の宛先を有する第１の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集前の荷物）を示す図である。
【図７Ｂ】単一の宛先を有する第１の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集後の荷物）を示す図である。
【図７Ｃ】単一の宛先を有する第１の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（最終スケジューリング後の荷物）を示す図である。
【図８Ａ】複数の宛先を有する第２の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集前の荷物）を示す図である。
【図８Ｂ】複数の宛先を有する第２の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集後の荷物）を示す図である。
【図８Ｃ】複数の宛先を有する第２の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（最終スケジューリング後の荷物）を示す図である。
【図９Ａ】宛先の代替順序番号を使用した第３の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集前の荷物）を示す図である。
【図９Ｂ】宛先の代替順序番号を使用した第３の実施形態における、本発明による荷物順序付け方法を用いた顧客注文の処理の１つの状態（コレクタでの収集後の荷物）を示す図である。
【発明を実施するための形態】
【００５６】
５．詳細な説明
本発明のすべての図において、同一の要素およびステップは同じ参照符号で表されている。
【００５７】
図２は、本発明による荷物順序付け方法を実施することが可能な自動配送システムの一例のブロック図を示す。この例では、システムは、５つの供給元Ｓ１〜Ｓ５（例えば保管庫の異なる部分（保管ユニット））と、５つの宛先Ｄ１〜Ｄ５（例えば顧客注文ピッキングまたは準備ステーション）と、コレクタ１（例えば１つまたは複数のコンベアからなる）と、順序付けおよび保管バッファデバイスまたはシステム９１と、制御システム９０（例えばＷＣＳタイプのもの）とを備える。この例では、供給元の数および宛先の数は、単に例示として与えられている。より一般的には、システムは、ｋ（ｋ≧２）個の供給元と、少なくとも１つの宛先とを備える。
【００５８】
すでに上でさらに説明したように、コレクタ１は、各宛先まで荷物を輸送するように構成され、複数の連続するノードを備える。参照符号Ｎ１〜Ｎ５を付されたノードはそれぞれ、供給元Ｓ１〜Ｓ５の１つから出る荷物を収集するように構成され、参照符号Ｎ１’〜Ｎ５’を付されたノードはそれぞれ、宛先Ｄ１〜Ｄ５の１つに向けて荷物を送るように構成される。これらのノードはそれぞれ、例えば９０度または４５度移送デバイスを備える。
【００５９】
各供給元Ｓ１〜Ｓ５は、例えば、ＦＩＦＯタイプの供給元バッファデバイスＦ１〜Ｆ５によってノードＮ１〜Ｎ５の１つに接続される。同様に、各宛先Ｄ１〜Ｄ５は、例えば、ＦＩＦＯタイプの宛先バッファデバイスＦ１’〜Ｆ５’によってノードＮ１’〜Ｎ５’の１つに接続される。
【００６０】
各宛先の上流で、順序付けおよびバッファ保管システム９１は、この宛先に関して、宛先の昇順の順番で荷物の最終スケジューリングを可能にする。以下でさらに詳細に述べるように、コレクタでの荷物の収集の終了時に、これらの荷物が（宛先の昇順の順番に対して）未整序であることが許容される。順序付けおよびバッファ保管システム９１は、この未整序をなくす。
【００６１】
一変形形態では、制約は、宛先に関してより融通性があり、宛先の昇順の順序番号が、この宛先に到着する荷物によって遵守されていないことが許容される。この変形形態では、各宛先の上流の順序付けおよびバッファ保管システム９１は、省略される（存在しない）か、または最終スケジューリングを実施するために使用されるが、その最終スケジューリングは部分的なものでよい（すなわち、時として上述した未整序をなくさずに減少させるだけである）。
【００６２】
別の変形形態では、複数の順序付けおよびバッファ保管システム９１（各宛先のすぐ上流かつコレクタ１の下流に１つ）は存在せず、（１組の宛先の上流に）ただ１つの順序付けおよびバッファ保管システム９１が存在する。
【００６３】
制御システム９０は、顧客注文を処理するように構成され、顧客注文はそれぞれ荷物をリストし、荷物は、供給元から抽出されて、理想的には（本明細書での上の論述を参照）、宛先の所与の昇順の順番で所与の宛先に提供されるべきである。
【００６４】
例えば、制御システム９０は、図５および図６を参照して本明細書で以下に述べる特定の実施形態に従って荷物順序付け方法を実施する。
【００６５】
次に図３を参照して、本発明の特定の一実施形態による荷物順序付け方法を提示する。この方法は、制御システム９０によって実施される。
【００６６】
ステップ３１で、制御システム９０は、収集されるべきｎ個の荷物を含み、宛先の昇順の順序番号に対するｎ個の荷物の未整序を低減する収集リストを準備する。ｎ個の荷物は、供給元バッファデバイスＦ１〜Ｆ５に含まれる。
【数４】
2020129378.tif 000006
が成り立ち、ここで、ｐ（ｉ）は、第ｉの供給元バッファデバイスで収集されるべき荷物の数である。収集リストを構築するためのこのステップ３１の特定の一実施形態を、図５を参照して本明細書で以下に述べる。
【００６７】
ステップ３２で、制御システム９０は、コレクタ１および供給元バッファデバイスＦ１〜Ｆ５を制御し、（コレクタでの）荷物の収集が収集リストに従って実施されるようにする。
【００６８】
所与の顧客注文の荷物が、宛先の所与の昇順の順番で所与の宛先に到着しなければならない場合、ステップ３３が実施され、ステップ３３で、制御システム９０は、ｎ個の荷物の未整序の訂正のために順序付けおよびバッファ保管システム９１を制御する。
【００６９】
テストステップ３４で、制御システム９０は、供給元バッファデバイスＦ１〜Ｆ５の１つへの少なくとも１つの新たな荷物の投入が、この供給元バッファデバイスに収集されるべき荷物の修正、したがってｋ個の供給元バッファデバイスの組に収集されるべきｎ個の荷物の修正を促すことを検証する。テストステップ３４で肯定応答があった場合（すなわち、収集されるべきｎ個の荷物の組の修正があった場合）、制御システム９０は、方法のステップの新たな実行を開始する。
【００７０】
一変形形態では、荷物順序付け方法は、図９Ａおよび図９Ｂを参照して以下でさらに述べる予備ステップ３０を含む。
【００７１】
図４は、本発明の特定の一実施形態による制御システム９０の構造を表す。この制御システムは、ランダムアクセスメモリ９２（例えばＲＡＭ）と、処理ユニット９１とを含み、処理ユニット９１は、例えばプロセッサを備え付けられ、読み取り専用メモリ９３（例えばＲＯＭまたはハードディスクドライブ）に記憶されたコンピュータプログラム９３０によって駆動される。
【００７２】
初期化時、コンピュータプログラムのコード命令は、例えば、ランダムアクセスメモリ９２にロードされ、次いで、処理ユニット９１のプロセッサによって実行されて、本発明の荷物順序付け方法を実施する（例えば、図３および図５の実施形態に従う）。処理ユニット９１は、（「命令」とも呼ばれる）コマンド９４を入力する。処理ユニット９１のプロセッサは、これらのコマンド９４を処理し、出力で（「命令」とも呼ばれる）他のコマンド９５を生成し、自動配送システムに含まれる様々な要素、特に供給元Ｓ１〜Ｓ５、ＦＩＦＯタイプの供給元バッファデバイスＦ１〜Ｆ５、コレクタ１、宛先Ｄ１〜Ｄ５、ＦＩＦＯタイプの宛先バッファデバイスＦ１’〜Ｆ５’、ならびに順序付けおよびバッファ保管システム９１の制御を可能にする（または指令する）。
【００７３】
この図４は、いくつかの取り得る方法のうち、その実施形態の任意の１つで本発明の技法を実施するただ１つの特定の手法を示す。実際、制御システムは、命令のシーケンスを含むプログラムを実行する再プログラム可能な計算機（例えばＰＣプロセッサ、ＤＳＰプロセッサ、マイクロコントローラなど）、または専用の計算機（例えば、ＦＰＧＡやＡＳＩＣなどの１組の論理ゲートまたは任意の他のハードウェアモジュール）で同様に良く実施することができる。
【００７４】
再プログラム可能な計算機を用いて制御システムを作製する場合、対応するプログラム（すなわち、命令のシーケンス）は、取外し可能な記憶媒体（例えばフロッピーディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなど）または取外し不可能な記憶媒体に記憶することができ、この記憶媒体は、コンピュータまたはプロセッサによって部分的または完全に読み出し可能である。
【００７５】
図５は、（収集リストＬＣを準備する）図３のステップ３１の特定の実施のアルゴリズムを示す。
【００７６】
ステップ５０１で、制御システムは、第１の状態セットＥ１を単一の状態ｅｉｎｉｔ＝（Ｕｉｎｉｔ，Ｌｉｎｉｔ）で初期化し、ここで、Ｕｉｎｉｔは、ｋ個のゼロを含むｋアプレットであり、Ｌｉｎｉｔは空リストである。
【００７７】
ステップ５０２で、制御システムは、第２の状態セットＥ２をゼロの値で初期化する。
【００７８】
テストステップ５０３で、制御システムは、ｎ個の連続する構築ステップ（すなわち、それらのすべて）が実施されたかどうかを検証する。
【００７９】
テストステップ５０３で肯定応答があった場合、制御システムはステップ５１６に進み、ステップ５１６で、Ｅ２に含まれる単一の最終状態ｅＦ＝（ＵＦ，ＬＦ）から収集リストＬＣを得る。実際、制御システムは、ＬＦを収集リストＬＣとして取る。
【００８０】
テストステップ５０３で否定応答があった場合、制御システムは、テストステップ５０４に進む際に次の構築ステップの処理を開始し、テストステップ５０４で、Ｅ１のすべての状態が処理されたかどうかを検証する。Ｅ１の各状態ｅは、ｅ＝（Ｕ，Ｌ）として書かれ、ここで、Ｕは、ｋ個の要素を含むｋアプレットであり、第ｉの供給元バッファデバイスで取られる荷物の数をｚｉとしてＵ＝（ｚ１，・・・，ｚｋ）であり、ｉ∈｛１，・・・，ｋ｝であり、Ｌは、Ｕに関連付けられた荷物のリストである。
【００８１】
テストステップ５０４で肯定応答があった場合、制御システムはステップ５１５に進み、ステップ５１５で、構築ステップが第ｎの構築ステップではない場合、Ｅ２が新たな状態セットＥ１になり、次いで制御システムが（次の構築ステップに進むために）ステップ５０３に戻る。
【００８２】
テストステップ５０４で否定応答があった場合、制御システムは、未処理状態Ｅ１を取り、テストステップ５０５に進み、テストステップ５０５で、ｆ∈｛１，・・・，ｋ｝としてｆのすべての値が処理されたかどうかを検証する。
【００８３】
ステップ５０５で肯定応答があった場合、制御システムは、ステップ５０４に戻る。テストステップ５０５に対して否定応答があった場合、制御システムは、ｆの未処理の値を取り、テストステップ５０６に進み、テストステップ５０６で、Ｕ（ｆ）＜ｐ（ｆ）であるかどうかを検証し、ここで、Ｕ（ｆ）は、Ｌに含まれる第ｆの供給元バッファデバイスの荷物の数であり、ｐ（ｆ）は、第ｆの供給元バッファデバイスで収集されるべき荷物の数である。
【００８４】
テストステップ５０６で否定応答があった場合、制御システムは、ステップ５０５に戻る。ステップ５０６で肯定応答があった場合、制御システムは、テストステップ５０６ａに進み、テストステップ５０６ａで、Ｎ（ｆ）＜ｙｆであるかどうかを検証し、ここで、Ｎ（ｆ）は、Ｌに連続的に配置された第ｆの供給元バッファデバイスの荷物の最大数であり、ｙｆは所定の値（例えば、ｙｆ＝６）である。
【００８５】
テストステップ５０６ａで否定応答があった場合、制御システムは、ステップ５０５に戻る。テストステップ５０６ａで肯定応答があった場合、制御システムはステップ５０７に進み、ステップ５０７で、Ｕ（ｆ）に１を加え、Ｌの最後に、第ｆの供給元バッファデバイスに含まれる荷物のシーケンスでの第（Ｕ（ｆ）＋１）の位置を占める荷物を加えて、ｅ＝（Ｕ，Ｌ）から始まる新たな状態ｅＮ＝（ＵＮ，ＬＮ）を作成する。
【００８６】
ステップ５０７の後にステップ５０８が行われ、ステップ５０８で、制御システムが、宛先の昇順の順序番号に対する未整序計算関数を用いて、新たな状態ｅＮのリストＬＮの未整序の値ｄを計算する。
【００８７】
ステップ５０８の１つの特定の実施形態では、制御システムは、未整序計算関数を使用し、未整序計算関数は、ｑ個の荷物のリストＭに関して、
【数５】
2020129378.tif 000007
と書かれ、ここで、Ｋ（ｉ）は、リストＭの第ｉの荷物の前に配置され、リストＭの第ｉの荷物の順序番号以下の宛先の順序番号を有するリストＭの荷物の数である。
【００８８】
それだけに限らないが特に、本発明の枠組みから逸脱することなく、以下の他の未整序計算関数を使用することができる。
［式２］
Ｂ（Ｍ）＝ＭＡＸ（Ｋ（ｉ）），  ｉ∈｛１，・・・，ｑ｝
ここで、Ｋ（ｉ）は、上でさらに定義したものである。
【数６】
2020129378.tif 000008
ここで、Ａ（ｉ）は、リストＭのｑ個の荷物が宛先の昇順の順序番号に従って並べ替えられた場合に、リストＭの第ｉの荷物が占める位置である。
［式４］
Ｇ（Ｍ）＝ＭＡＸ（｜（Ａ（ｉ）−ｉ｜），  ｉ∈｛１，・・・，ｑ｝
ここで、Ａ（ｉ）は、上でさらに定義したものである。
【００８９】
例えば、Ｍ＝（３，１，８，４，７，２，６，５）の場合、以下のようになる。
・Ｈ（Ｍ）＝（［（１−１）−０］＋［（２−１）−０］＋［（３−１）−２］＋［（４−１）−２］＋［（５−１）−３］＋［（６−１）−１］＋［（７−１）−４］＋［（８−１）−４］）＝１２
・Ｂ（Ｍ）＝４
・Ｆ（Ｍ）＝（｜３−１｜＋｜１−２｜＋｜８−３｜＋｜４−４｜＋｜７−５｜＋｜２−６｜＋｜６−７｜＋｜５−８｜）＝１８
・Ｇ（Ｍ）＝５
【００９０】
ステップ５０８の後にテストステップ５０９が続き、テストステップ５０９で、制御システムは、ｄ＞ｄＨであるかどうかを検証し、ここでｄＨは所定値である。
【００９１】
ステップ５０９の特定の一実施形態では、所定値ｄＨは以下のように計算される。
−ｎ個の荷物を含み、以下のように構築される参照リストＬＨを構築する。
・ｋ個の供給元バッファデバイスから実際に出る準備ができている荷物のうち、ＬＨの第１の荷物が、宛先の最小の順序番号を有する荷物である。
・ＬＨの先行の荷物がｋ個の供給元バッファデバイスから出たと仮定して、ｋ個の供給元バッファデバイスから出る準備ができている荷物のうち、ＬＨの後続の各荷物が、宛先の最小の順序番号を有する荷物である。
−未整序計算関数を用いて、リストＬＨの未整序の値としてｄＨを計算する。
【００９２】
テストステップ５０９で肯定応答があった場合、制御システムはステップ５０５に戻る。テストステップ５０９で否定応答があった場合、制御システムはテストステップ５１０に進み、ステップ５１０で、Ｅ２が別の新たな状態ｅ’Ｎ＝（Ｕ’Ｎ，Ｌ’Ｎ）を含むかどうかを検証する。ここで、Ｕ’Ｎ＝ＵＮであり、ｄ’は、リストＬ’Ｎの未整序の値である。
【００９３】
テストステップ５１０で肯定応答があった場合、制御システムはステップ５１２に進み、ステップ５１２で、ｄ＜ｄ’であるかどうかを検証する。テストステップ５１２で肯定応答があった場合、制御システムはステップ５１４に進み、ステップ５１４で、Ｅ２でのｅ’ＮをｅＮによって置き換える。テストステップ５１２で否定応答があった場合、制御システムはステップ５１３に進み、ステップ５１３で、ｅＮをＥ２に挿入しない。ステップ５１２またはステップ５１４の終了時に、制御システムはステップ５０５に戻る。
【００９４】
テストステップ５１０で否定応答があった場合、制御システムはステップ５１１に進み、ステップ５１１でｅＮをＥ２に挿入し、次いでステップ５０５に戻る。
【００９５】
ここで図６ならびに図７Ａ、図７Ｂ、および図７Ｃを参照して、１つの宛先のみを有する第１の実施における、本発明による荷物順序付け方法を用いた顧客注文の処理を提示する。図７Ａ、図７Ｂ、および図７Ｃは、この処理の以下の３つのステップである、コレクタでの収集前の荷物、コレクタでの収集後の荷物、および最終スケジューリング後の荷物をそれぞれ示す。
【００９６】
この例では、２つの供給元Ｓ１およびＳ２と、１つの宛先Ｄ１とがあると仮定される。処理すべき顧客注文は、番号１、２、３、４、５、６、７、８、９、および１０を付された荷物をリストする（図では、荷物は、それらの宛先の順序番号を付されている）。
【００９７】
図７Ａに示されるように、供給元バッファデバイスＦ１（供給元Ｓ１の下流にある）は、シーケンス７、６、１、９、および３に従って５つの荷物を含む。供給元バッファデバイスＦ２（供給元Ｓ２の下流にある）は、８、４、５、２、および１０のシーケンスに従って５つの荷物を含む。したがって、ｎ＝１０、ｐ（１）＝５、およびｐ（２）＝５である。
【００９８】
Ｅ１を初期化するためのステップと、図５を参照して上でさらに述べたｎ個の構築ステップとの結果は、以下のようである（未整序の値ｄの計算の関数としてＨ（Ｍ）を取る際）。
Ｅ１を初期化するためのステップ
状態ｅ００＝［Ｕ＝（０，０）；Ｌ＝（）］；ｄ＝０
構築ステップ１
状態ｅ１０＝［Ｕ＝（１，０）；Ｌ＝（８）］；ｄ＝０
状態ｅ０１＝［Ｕ＝（０，１）；Ｌ＝（７）］；ｄ＝０
構築ステップ２
状態ｅ２０＝［Ｕ＝（２，０）；Ｌ＝（８，４）］；ｄ＝１
状態ｅ１１＝［Ｕ＝（１，１）；Ｌ＝（７，８）］；ｄ＝０
状態ｅ’１１＝［Ｕ＝（１，１）；Ｌ＝（８，７）］；ｄ＝１（保持されない）
状態ｅ０２＝［Ｕ＝（０，２）；Ｌ＝（７，６）］；ｄ＝１
構築ステップ３
状態ｅ３０＝［Ｕ＝（３，０）；Ｌ＝（８，４，５）］；ｄ＝２
状態ｅ２１＝［Ｕ＝（２，１）；Ｌ＝（８，４，７）］；ｄ＝２
状態ｅ’２１＝［Ｕ＝（２，１）；Ｌ＝（７，８，４）］；ｄ＝２（保持されない）
状態ｅ１２＝［Ｕ＝（１，２）；Ｌ＝（７，８，６）］；ｄ＝２（保持されない）
状態ｅ’１２＝［Ｕ＝（１，２）；Ｌ＝（７，６，８）］；ｄ＝１
状態ｅ０３＝［Ｕ＝（０，３）；Ｌ＝（７，６，１）］；ｄ＝３
構築ステップ４
状態ｅ４０＝［Ｕ＝（４，０）；Ｌ＝（８，４，５，２）］；ｄ＝５
状態ｅ３１＝［Ｕ＝（３，１）；Ｌ＝（８，４，５，７）］；ｄ＝３
状態ｅ’３１＝［Ｕ＝（３，１）；Ｌ＝（８，４，７，５）］；ｄ＝４（保持されない）
状態ｅ２２＝［Ｕ＝（２，２）；Ｌ＝（８，４，７，６）］；ｄ＝４
状態ｅ’２２＝［Ｕ＝（２，２）；Ｌ＝（７，６，８，４）］；ｄ＝４（保持されない）
状態ｅ１３＝［Ｕ＝（１，３）；Ｌ＝（７，６，８，１）］；ｄ＝４（保持されない）
状態ｅ’１３＝［Ｕ＝（１，３）；Ｌ＝（７，６，１，８）］；ｄ＝３
状態ｅ０４＝［Ｕ＝（０，４）；Ｌ＝（７，６，１，９）］；ｄ＝３
構築ステップ５
状態ｅ５０＝［Ｕ＝（５，０）；Ｌ＝（８，４，５，２，１０）］；ｄ＝５
状態ｅ４１＝［Ｕ＝（４，１）；Ｌ＝（８，４，５，２，７）］；ｄ＝６
状態ｅ’４１＝［Ｕ＝（４，１）；Ｌ＝（８，４，５，７，２）］；ｄ＝７（保持されない）
状態ｅ３２＝［Ｕ＝（３，２）；Ｌ＝（８，４，５，７，６）］；ｄ＝５
状態ｅ’３２＝［Ｕ＝（３，２）；Ｌ＝（８，４，７，６，５）］；ｄ＝７（保持されない）
状態ｅ２３＝［Ｕ＝（２，３）；Ｌ＝（８，４，７，６，１）］；ｄ＝８（保持されない）
状態ｅ’２３＝［Ｕ＝（２，３）；Ｌ＝（７，６，１，８，４）］；ｄ＝６
状態ｅ１４＝［Ｕ＝（１，４）；Ｌ＝（７，６，１，８，９）］；ｄ＝３
状態ｅ’１４＝［Ｕ＝（１，４）；Ｌ＝（７，６，１，９，８）］；ｄ＝４（保持されない）
状態ｅ０５＝［Ｕ＝（０，５）；Ｌ＝（７，６，１，９，３）］；ｄ＝６
構築ステップ６
状態ｅ５１＝［Ｕ＝（５，１）；Ｌ＝（８，４，５，２，１０，７）］；ｄ＝７（保持されない）
状態ｅ’５１＝［Ｕ＝（５，１）；Ｌ＝（８，４，５，２，７，１０）］；ｄ＝６
状態ｅ４２＝［Ｕ＝（４，２）；Ｌ＝（８，４，５，２，７，６）］；ｄ＝８
状態ｅ’４２＝［Ｕ＝（４，２）；Ｌ＝（８，４，５，７，６，２）］；ｄ＝１０（保持されない）
状態ｅ３３＝［Ｕ＝（３，３）；Ｌ＝（８，４，５，７，６，１）］；ｄ＝１０（保持されない）
状態ｅ’３３＝［Ｕ＝（３，３）；Ｌ＝（７，６，１，８，４，５）］；ｄ＝９
状態ｅ２４＝［Ｕ＝（２，４）；Ｌ＝（７，６，１，８，４，９）］；ｄ＝６
状態ｅ’２４＝［Ｕ＝（２，４）；Ｌ＝（７，６，１，８，９，４）］；ｄ＝７（保持されない）
状態ｅ１５＝［Ｕ＝（１，５）；Ｌ＝（７，６，１，８，９，３）］；ｄ＝７
状態ｅ’１５＝［Ｕ＝（０，５）；Ｌ＝（７，６，１，９，３，８）］；ｄ＝７（保持されない）
構築ステップ７
状態ｅ５２＝［Ｕ＝（５，２）；Ｌ＝（８，４，５，２，７，１０，６）］；ｄ＝９（保持されない）
状態ｅ’５２＝［Ｕ＝（５，２）；Ｌ＝（８，４，５，２，７，６，１０）］；ｄ＝８
状態ｅ４３＝［Ｕ＝（４，３）；Ｌ＝（８，４，５，２，７，６，１）］；ｄ＝１４
状態ｅ’４３＝［Ｕ＝（４，３）；Ｌ＝（７，６，１，８，４，５，２）］；ｄ＝１４（保持されない）
状態ｅ３４＝［Ｕ＝（３，４）；Ｌ＝（７，６，１，８，４，５，９）］；ｄ＝９
状態ｅ’３４＝［Ｕ＝（３，４）；Ｌ＝（７，６，１，８，４，９，５）］；ｄ＝１０（保持されない）
状態ｅ２５＝［Ｕ＝（２，５）；Ｌ＝（７，６，１，８，４，９，３）］；ｄ＝１１
状態ｅ’２５＝［Ｕ＝（２，５）；Ｌ＝（７，６，１，８，９，３，４）］；ｄ＝１１（保持されない）
構築ステップ８
状態ｅ５３＝［Ｕ＝（５，３）；Ｌ＝（８，４，５，２，７，６，１０，１）］；ｄ＝１５（保持されない）
状態ｅ’５３＝［Ｕ＝（５，３）；Ｌ＝（８，４，５，２，７，６，１，１０）］；ｄ＝１４
状態ｅ４４＝［Ｕ＝（４，４）；Ｌ＝（８，４，５，２，７，６，１，９）］；ｄ＝１４
状態ｅ’４４＝［Ｕ＝（４，４）；Ｌ＝（７，６，１，８，４，５，９，２）］；ｄ＝１５（保持されない）
状態ｅ３５＝［Ｕ＝（３，５）；Ｌ＝（７，６，１，８，４，５，９，３）］；ｄ＝１５
状態ｅ’３５＝［Ｕ＝（３，５）；Ｌ＝（７，６，１，８，４，９，３，５）］；ｄ＝１５（保持されない）
構築ステップ９
状態ｅ５４＝［Ｕ＝（５，４）；Ｌ＝（８，４，５，２，７，６，１，１０，９）］；ｄ＝１５（保持されない）
状態ｅ’５４＝［Ｕ＝（５，４）；Ｌ＝（８，４，５，２，７，６，１，９，１０）］；ｄ＝１４
状態ｅ４５＝［Ｕ＝（４，５）；Ｌ＝（８，４，５，２，７，６，１，９，３）］；ｄ＝２０
状態ｅ’４５＝［Ｕ＝（４，５）；Ｌ＝（７，６，１，８，４，５，９，３，２）］；ｄ＝２２（保持されない）
構築ステップ１０
状態ｅ５５＝［Ｕ＝（５，５）；Ｌ＝（８，４，５，２，７，６，１，９，１０，３）］；ｄ＝２１（保持されない）
状態ｅ’５５＝［Ｕ＝（５，５）；Ｌ＝（８，４，５，２，７，６，１，９，３，１０）］；ｄ＝２０
【００９９】
したがって、状態ｅ’５５が最終状態であり、リストＬ＝（８，４，５，２，７，６，１，９，３，１０）が収集リストＬＣとして取られる。これは図７Ｂに示されている。順序付けおよびバッファ保管システム９１によってリストが並べ替えられた（最終スケジューリング）後、図７Ｃに示されるように、リスト（１，２，３，４，５，６，７，８，９，１０）が得られる。
【０１００】
図６は、図５のアルゴリズムによってこの例で見た状態のツリー（およびより正確にはこれらの状態のＵの値）を示す。
【０１０１】
ここで図８Ａ、図８Ｂ、および図８Ｃを参照して、いくつかの宛先を有する第２の実施における、本発明による荷物順序付け方法を用いた顧客注文の処理を提示する。図８Ａ、図８Ｂ、および図８Ｃは、この処理の以下の３つの状態である、コレクタでの収集前の荷物、コレクタでの収集後の荷物、および最終スケジューリング後の荷物をそれぞれ示す。
【０１０２】
この例では、３つの供給元Ｓ１、Ｓ２、およびＳ３と、４つの宛先Ｄ１、Ｄ２、Ｄ３、およびＤ４とがあると仮定される。宛先ごとに１つずつ、処理すべき２つの顧客注文がある。これらの顧客注文はそれぞれ、宛先の順序番号１、２、３、および４を有する４つの荷物をリストする。これらの図では、荷物は、それらの宛先の順序番号と、それらの宛先に対応する幾何符号（Ｄ１に関する楕円形、Ｄ２に関する三角形、Ｄ３に関する矩形、Ｄ４に関する円形）とによって参照される。
【０１０３】
図８Ａに示されるように、供給元バッファデバイスＦ１（供給元Ｓ１の下流にある）は、シーケンス３ｒ、１ｏ、２ｃ、４ｔ、および１ｒ（文字ｏ、ｔ、ｒ、およびｃはそれぞれ、「楕円形」、「三角形」、「矩形」、および「円形」に対応し、それらの宛先（それぞれＤ１、Ｄ２、Ｄ３、およびＤ４）を示す）に従って５つの荷物を含む。供給元バッファデバイスＦ２（供給元Ｓ２の下流にある）は、シーケンス２ｏ、１ｔ、４ｒ、３ｃ、３ｔ、および４ｃに従って６つの荷物を含む。供給元バッファデバイスＦ３（供給元Ｓ３の下流にある）は、シーケンス１ｃ、２ｒ、４ｏ、２ｔ、および３ｏで５つの荷物を含む。したがって、ｎ＝１６、ｐ（１）＝５、ｐ（２）＝６、およびｐ（３）＝５となる。
【０１０４】
図８Ｂは、図５のアルゴリズムを適用することによって得られる収集リストＬＣ＝（１ｃ，２ｏ，１ｔ，２ｒ，３ｒ，１ｏ，２ｃ，４ｔ，１ｒ，４ｏ，２ｔ，３ｏ，４ｒ，３ｃ，３ｔ，４ｃ）を示す。荷物１ｒおよび３ｏの位置決めにより、未整序が示される。
【０１０５】
図８Ｃは、順序付けおよびバッファ保管システム９１による並べ替え（最終スケジューリング）後の、異なる宛先バッファデバイスＦ１’〜Ｆ５’で正確に順序付けされた荷物を示す。
【０１０６】
ここで図９Ａおよび図９Ｂを参照して、宛先の代替順序番号を使用する第３の実施における、本発明による荷物順序付け方法を用いた顧客注文の処理を提示する。図９Ａおよび図９Ｂは、それぞれ、この処理の２つの状態、すなわち、コレクタでの収集前の荷物、およびコレクタでの収集後の荷物を示す。
【０１０７】
図３の荷物順序付け方法が（収集リストを構築するためのステップ３１の前に）予備ステップ３０を含む場合（上でさらに参照した変形形態）を考える。この予備ステップ３０では、制御システムは、供給元バッファデバイスＦ１〜Ｆ５に含まれる荷物の宛先の順序番号の関数として、宛先の代替順序番号を計算する。より具体的には、供給元バッファデバイスの１つに含まれるＲ個（Ｒは２以上の整数）の連続する荷物の少なくとも１つのグループ（または特定の一実施形態では各グループ）に関して、システムは、Ｒ個の荷物の宛先の順序番号の関数として宛先の代替順序番号を計算する。次いで、収集リストを構築するためのステップ３１の実行中に、制御システムは、Ｒ個の荷物のそれぞれについて、宛先の代替順序番号を使用する。
【０１０８】
特定の一実施形態では、ステップ３０で行われる計算は、Ｒ個の荷物の各グループについて以下のことを含む。
・Ｒ個の荷物の宛先の順序番号の平均値を計算する。
・Ｒ個の荷物の宛先の順序番号の関数としてＲ個の荷物の未整序の値を計算する（未整序計算関数の例はすでに上でさらに述べた）。
・Ｒ個の荷物の未整序の値が所定の閾値Ｓよりも大きい場合、宛先の代替順序番号は、最も近い整数に切り上げられた平均値である。そうでない場合、宛先の代替順序番号は、最も近い整数に切り捨てられた平均値である。
【０１０９】
所定の閾値は、例えば、Ｓ＝０である。この場合、Ｒ個の荷物に未整序がない場合にのみ、最も近い整数に切り捨てられた平均値を取る。一変形形態では、Ｓは、ゼロよりも大きい（例えば、Ｓ＝４）。この場合、Ｒ個の荷物の未整序がＳよりも小さい限り、より低い整数に切り捨てられた平均値を取る許容値が受け入れられる。
【０１１０】
図９Ａに示される例では、図８Ａの例において、３つの供給元Ｓ１、Ｓ２、およびＳ３（したがって３つの供給元バッファデバイスＦ１、Ｆ２、およびＦ３）、４つの宛先Ｄ１、Ｄ２、Ｄ３、およびＤ４、ならびに処理すべき４つの顧客注文（宛先ごとに１つ）があると仮定される。以下の制約が加えられる。供給元バッファデバイスの荷物が、コレクタ１でＲ個ずつ（すなわち一度にＲ個）収集されなければならない（この例ではＲ＝２）。
【０１１１】
図９Ａの例では、（破線で区切られている）以下のグループがある。すなわち、供給元バッファデバイスＦ１に関して、（３ｒ，１ｏ）および（２ｃ，４ｔ）（荷物１ｒは単独であるので考慮に入れない）と、供給元バッファデバイスＦ２に関して、（２ｏ，１ｔ）、（４ｒ，３ｃ）、および（３ｔ，４ｃ）と、供給元バッファデバイスＦ３に関して、（１ｃ，２ｒ）および（４ｏ，２ｔ）（荷物３ｏは単独であるので考慮に入れない）とのグループである。この例では、荷物１ｒおよび３ｏは、荷物のグループの一部ではない。したがって、荷物１ｒおよび３ｏに関して、宛先の代替順序番号の計算はない。荷物１ｒおよび３ｏは、収集リストを構築するためのステップ３１では考慮に入れられない（言い換えると、収集すべきｎ個の荷物の一部ではない）。収集すべきｎ個の荷物のセットが修正された場合（つまり、テストステップ３４で肯定応答があった場合）に、制御システム９０が方法のステップの新たな実行を開始するときに、荷物１ｒおよび３ｏが考慮に入れられる。一変形形態では、または収集すべきｎ個の荷物のセットの修正がない場合には、荷物１ｒおよび３ｏ（およびそれらの宛先の順序番号）は、収集リストを構築するためのステップ３１で即座に考慮に入れられる。
【０１１２】
これらのグループそれぞれについて、ステップ３０の計算（Ｓ＝０とする）の結果は、グループの各荷物の右側の括弧内に示されている。異なる丸めた値を有する以下の２つの例を考える。
・供給元バッファデバイスＦ２のグループ（２ｏ，１ｔ）について：宛先の代替順序番号は２である（２と１の平均＝１．５。２つの荷物に未整序があるので、値は最も近い整数に切り上げられる）。
・供給元バッファデバイスＦ３のグループ（１ｃ，２ｒ）について：宛先の代替順序番号は１である（１と２の平均＝１．５。２つの荷物に未整序がないので、値は最も近い整数に切り捨てられる）。
【０１１３】
図９Ｂは、図５のアルゴリズムに宛先の代替順序番号を適用する（荷物１ｒおよび３ｏは除く。それらは、それらの宛先の順序番号で考慮に入れられる）ことによって得られた収集リストＬＣ＝（１ｃ，２ｒ，２ｏ，１ｔ，３ｒ，１ｏ，２ｃ，４ｔ，１ｒ，４ｏ，２ｔ，３ｏ，４ｒ，３ｃ，３ｔ，４ｃ）を示す。
【符号の説明】
【０１１４】
１  コレクタ
１５  メインコレクタ
１６  顧客注文準備ステーション
１７  宛先バッファデバイス
９０  制御システム
９１  順序付けおよび保管バッファシステム
９２  ランダムアクセスメモリ
９３  読み取り専用メモリ
９４  コマンド
９５  コマンド
９３０  コンピュータプログラム
Ｄ１〜Ｄ５  宛先
Ｆ１〜Ｆ５  供給元バッファデバイス
Ｇ  セット
ＬＣ  収集リスト
Ｎ１〜Ｎ５  ノード
Ｓ１〜Ｓ５  供給元
【図１Ａ−１Ｃ】
2020129378.tif 000012
【図２】
2020129378.tif 000013
【図３】
2020129378.tif 000014
【図４】
2020129378.tif 000015
【図５】
2020129378.tif 000016
【図６】
2020129378.tif 000017
【図７Ａ】
2020129378.tif 000018
【図７Ｂ】
2020129378.tif 000019
【図７Ｃ】
2020129378.tif 000020
【図８Ａ】
2020129378.tif 000021
【図８Ｂ】
2020129378.tif 000022
【図８Ｃ】
2020129378.tif 000023
【図９Ａ】
2020129378.tif 000024
【図９Ｂ】
2020129378.tif 000025
【外国語明細書】
2020129378000001.pdf